Supporting complex multi-dimensional queries in P2P systems

More and more applications require peer-to-peer (P2P) systems to support complex queries over multi-dimensional data. For example, a P2P auction network for real estate frequently needs to answer queries such as "select five available buildings closest to the airport". Such queries are not efficiently supported in current P2P systems. Towards an efficient and scalable P2P system capable of processing complex multi-dimensional queries, we first propose a comprehensive framework for sharing, indexing, and querying multi-dimensional data, where (i) peers with more computational power coordinate indexing and query processing, and (ii) other peers participate in part of the computation in order to achieve scalability and load-balance. Based on this framework, we propose Network-R-tree (NR-tree), a P2P adaptation of the dominant spatial index - R*-tree. NR-tree, indexing spatial data at clustered peers, is capable of processing complex queries such as range queries and k-nearest neighbor queries. We propose query processing algorithms for range and k-nearest neighbor queries and experimentally prove the effectiveness of proposed techniques with real data.