Abstract
In this paper, we present Pampoo, a novel distributed framework for efficient query processing in P2P systems. We propose a new locality preserving data structure Skip-trie as its substrate. Skip-trie incorporates the advantages of skip graph with features of traditional trie. Thus, Pampoo can efficiently support various types of queries such as range queries and k nearest neighbor queries. We study the time cost of search and update operations on Skip-trie structure under our Pampoo framework. We further briefly present a repairing strategy to boost the robustness of Pampoo system. Extensive experiments are conducted to verify the effectiveness and efficiency of our approach.
Supported by the National Natural Science Foundation of China (60673139, 60473073, 60573090).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: A scalable peer-to-peer lookup service for internet applications. In: SIGCOMM 2001 (2001)
Druschel, P., Rowstron, A.: Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In: Middleware (2001)
Aberer, K., Punceva, M., Hauswirth, M., Schmidt, R.: Improving data access in P2P systems. IEEE Internet Computing 6(1), 58–67 (2002)
Aberer, K., Cudré-Mauroux, P., Datta, A., Despotovic, Z., Hauswirth, M., Punceva, M., Schmidt, R.: P-Grid: A Self organizing Structured P2P System. In: ACM SIGMOD Record (2003)
Rowstron, A., Druschel, P.: Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In: Middleware (2001)
Cuenca-Acuna, F.M., et al.: PlanetP: Using Gossiping to Build Content Addressable Peer-to-Peer Information Sharing Communities. Technical Report DCS-TR-487, Rutgers University (September 2002)
Ratnasamy, S., et al.: A scalable content-addressable network. In: SIGCOMM 2001 (2001)
Ramabhadran, S., Ratnasamy, S., Hellerstein, J., Shenker, S.: Brief Announcement: Prefix Hash Tree. In: Proc. of PODC 2004 (2004)
Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content-addressable network. In: Proc. ACM SIGCOMM 2001, ACM Press, New York (2001)
Aspnes, J., Kirsch, J., Krishnamurthy, A.: Load balancing and locality in range-queriable data structures. In: ACM PODC 2004, ACM Press, New York (2004)
Aspnes, J., Shah, G.: Skip graphs. In: ACM-SIAM Symposium on Discrete Algorithms(January 2003)
Harvey, N., et al.: SkipNet: A scalable overlay network with practical locality preserving properties. In: Proc.of 4th USENIX Symp. on Internet Technologies and Systems (2003)
Mei Li.DP-tree: A Balanced Tree-based Indexing Framework for Peer-to-Peer Systems. In Proc. Of icnp 2006 (2006)
Datta, A., et,: al. Range queries in trie-structured overlays. In: Proc. of P2P 2005 (2005)
Zatloukal, K.C., Harvey, N.J.A.: Family Trees:An ordered dictionary with optimal congestion, locality, degree, and search time. In: 15th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 301–310. ACM Press, New York (2004)
Naor, M., Wieder, U.: Know thy neighbor’s neighbor: Better routing in skip-graphs and small worlds. In: 3rd Int. Workshop on Peer-to-Peer Systems (2004)
Abraham, I., Aspnes, J., Yuan, J.: Skip B-Trees. In: Proc. of Opodis 2005 (2005)
Gupta, A., Agrawal, D., Abbadi, A.E.: Approximate Range Selection Queries in Peer-to-Peer Systems. In: CIDR 2003. 1st Biennial Conference on Innovative Data Systems Research (2003)
Sahin, O.D., Gupta, A., Agrawal, D., Abbadi., A.E., Peer-to-peer, A.: Framework for Caching Range Queries. In: 20th ICDE 2004 (2004)
Ganesan, P., Bawa, M., Garcia-Molina, H.: Online balancing of range-partitioned data with applications to peer-to-peer systems. In: Proc. of VLDB 2004 (2004)
Pugh, W.: Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM 33(6) (1990)
Risson, J., Moors, T.: Survey of Research towards Robust Peer-to-Peer Networks: Search Methods. Technical Report UNSW-EE-P2P-1-1, University of New South Wales, Sydney, Australia (September 2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meifang, L., Hongkai, Z., Derong, S., Tiezheng, N., Yue, K., Ge, Y. (2007). Pampoo: An Efficient Skip-Trie Based Query Processing Framework for P2P Systems. In: Xu, M., Zhan, Y., Cao, J., Liu, Y. (eds) Advanced Parallel Processing Technologies. APPT 2007. Lecture Notes in Computer Science, vol 4847. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76837-1_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-76837-1_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-76836-4
Online ISBN: 978-3-540-76837-1
eBook Packages: Computer ScienceComputer Science (R0)