Christos Doulkeridis
Kjetil Nørvåg
ABSTRACT
Traditional routing indices in peer-to-peer (P2P) networks are mainly designed for document retrieval applications and maintain aggregated one-dimensional values representing the number of documents that can be obtained in a certain direction in the network. In this paper, we introduce the concept of multidimensional routing indices (MRIs), which are suitable for handling multidimensional data represented by minimum bounding regions (MBRs). Depending on data distribution on peers, the aggregation of the MBRs may lead to MRIs that exhibit extremely poor performance, which renders them ineffective. Thus, focusing on a hybrid unstructured P2P network, we analyze the parameters for building MRIs of high selectivity. We present techniques that boost the query routing performance by detecting similar peers and grouping and reassigning these peers to other parts of the hybrid network in a distributed and scalable way. We demonstrate the advantages of our approach using large-scale simulations.
- A. Crespo and H. Garcia-Molina. Routing indices for peer-to-peer systems. In Proc. of ICDCS, page 23, 2002. Google Scholar
Digital Library
- C. Doulkeridis, K. Nørvåg, and M. Vazirgiannis. DESENT: Decentralized and distributed semantic overlay generation in P2P networks. IEEE Journal on Selected Areas in Communications (J-SAC), 25(1):25--34, 2007. Google ScholarDigital Library
- C. Doulkeridis, A. Vlachou, Y. Kotidis, and M. Vazirgiannis. Peer-to-peer similarity search in metric spaces. In Proc. of VLDB, pages 986--997, 2007. Google ScholarDigital Library
- C. du Mouza, W. Litwin, and P. Rigaux. SD-Rtree: A scalable distributed R-tree. In Proc. of ICDE, pages 296--305, 2007.Google Scholar
- V. Gaede and O. Günther. Multidimensional access methods. ACM Comput. Surv., 30(2):170--231, 1998. Google ScholarDigital Library
- P. Ganesan, B. Yang, and H. Garcia-Molina. One torus to rule them all: Multidimensional queries in P2P systems. In Proc. of WebDB, pages 19--24, 2004. Google ScholarDigital Library
- R. Hayek, G. Raschia, P. Valduriez, and N. Mouaddib. Summary management in P2P systems. In Proc. of EDBT, pages 16--25, 2008. Google ScholarDigital Library
- K. Hose, C. Lemke, and K.-U. Sattler. Processing relaxed skylines in PDMS using distributed data summaries. In Proc. of CIKM, pages 425--434, 2006. Google ScholarDigital Library
- H. V. Jagadish, B. C. Ooi, Q. H. Vu, R. Zhang, and A. Zhou. VBI-tree: A peer-to-peer framework for supporting multi-dimensional indexing schemes. In Proc. of ICDE, page 34, 2006. Google ScholarDigital Library
- S. Ratnasamy, P. Francis, M. Handley, R. M. Karp, and S. Shenker. A scalable content-addressable network. In Proc. of SIGCOMM, pages 161--172, 2001. Google ScholarDigital Library
- S. Umeyama. An eigendecomposition approach to weighted graph matching problems. IEEE Trans.Pattern Anal. Mach. Intell., 10(5):695--703, 1988. Google ScholarDigital Library
- A. Vlachou, C. Doulkeridis, K. Nørvåg, and M. Vazirgiannis. On efficient top-k query processing in highly distributed environments. In Proc. of SIGMOD, pages 753--764, 2008. Google ScholarDigital Library
- B. Yang and H. Garcia-Molina. Designing a super-peer network. In Proc. of ICDE, page 49, 2003.Google Scholar
Index Terms
- Multidimensional routing indices for efficient distributed query processing
Recommendations
On the selectivity of multidimensional routing indices
CIKM '10: Proceedings of the 19th ACM international conference on Information and knowledge managementRecently, the problem of efficiently supporting advanced query operators, such as nearest neighbor or range queries, over multidimensional data in widely distributed environments has attracted much attention. In unstructured peer-to-peer (P2P) networks, ...
Index-based query processing on distributed multidimensional data
This work introduces decentralized query processing techniques based on MIDAS, a novel distributed multidimensional index. In particular, MIDAS implements a distributed k-d tree, where leaves correspond to peers, and internal nodes dictate message ...
Efficient Range Query Processing in Peer-to-Peer Systems
With the increasing popularity of the peer-to-peer (P2P) computing paradigm, many general range query schemes for distributed hash table (DHT)-based P2P systems have been proposed in recent years. Although those schemes can provide range query ...
Comments