Just-in-time query retrieval over partially indexed data on structured P2P overlays

ABSTRACT

Structured peer-to-peer (P2P) overlays have been successfully employed in many applications to locate content. However, they have been less effective in handling massive amounts of data because of the high overhead of maintaining indexes. In this paper, we propose PISCES, a Peer-based system that Indexes Selected Content for Efficient Search. Unlike traditional approaches that index all data, PISCES identifies a subset of tuples to index based on some criteria (such as query frequency, update frequency, index cost, etc.). In addition, a coarse-grained range index is built to facilitate the processing of queries that cannot be fully answered by the tuple-level index. More importantly, PISCES can adaptively self-tune to optimize the subset of tuples to be indexed. That is, the (partial) index in PISCES is built in a Just-In-Time (JIT) manner. Beneficial tuples for current users are pulled for indexing while indexed tuples with infrequent access and high maintenance cost are discarded. We also introduce a light-weight monitoring scheme for structured networks to collect the necessary statistics. We have conducted an extensive experimental study on PlanetLab to illustrate the feasibility, practicality and efficiency of PISCES. The results show that PISCES incurs lower maintenance cost and offers better search and query efficiency compared to existing methods.

REFERENCES

• 1: http://data.aolsearchlogs.com.
• 2: http://www.planet-lab.org.
• 3: http://www.sigmod.org/codearchive/sigmod2008/.
• 4: http://www.tpc.org/tpch.
• 5: S3:scalable,shareable and secure p2p based data management system. In http://www.comp.nus.edu.sg/ s3p2p/.
• 6: Karl Aberer , Philippe Cudré-Mauroux , Anwitaman Datta , Zoran Despotovic , Manfred Hauswirth , Magdalena Punceva , Roman Schmidt, P-Grid: a self-organizing structured P2P system, ACM SIGMOD Record, v.32 n.3, September 2003 [doi>10.1145/945721.945729]
• 7: James Aspnes , Gauri Shah, Skip graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 8: Asad Awan , Ronaldo A. Ferreira , Suresh Jagannathan , Ananth Grama, Distributed Uniform Sampling in Unstructured Peer-to-Peer Networks, Proceedings of the 39th Annual Hawaii International Conference on System Sciences, p.223.3, January 04-07, 2006 [doi>10.1109/HICSS.2006.126]
• 9: Owe Axelsson, Iterative solution methods, Cambridge University Press, New York, NY, 1995
• 10: Ashwin R. Bharambe , Mukesh Agrawal , Srinivasan Seshan, Mercury: supporting scalable multi-attribute range queries, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 11: S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. In ICDE, 2001.
• 12: S. Boyson , T. Corsi, Managing the Real-Time Supply Chain, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 3, p.70, January 07-10, 2002
• 13: A. Broder and M. Mitzenmacher. Network application of bloom filters: A survey. In Internet Mathematics, 2004.
• 14: Adina Crainiceanu , Prakash Linga , Ashwin Machanavajjhala , Johannes Gehrke , Jayavel Shanmugasundaram, P-ring: an efficient and robust P2P range index structure, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247507]
• 15: Anwitaman Datta , Manfred Hauswirth , Renault John , Roman Schmidt , Karl Aberer, Range Queries in Trie-Structured Overlays, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing, p.57-66, August 31-September 02, 2005 [doi>10.1109/P2P.2005.31]
• 16: Robin Dhamankar , Yoonkyong Lee , AnHai Doan , Alon Halevy , Pedro Domingos, iMAP: discovering complex semantic matches between database schemas, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007612]
• 17: AnHai Doan , Pedro Domingos , Alon Y. Halevy, Reconciling schemas of disparate data sources: a machine-learning approach, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.509-520, May 21-24, 2001, Santa Barbara, California, United States
• 18: Prasanna Ganesan , Beverly Yang , Hector Garcia-Molina, One torus to rule them all: multi-dimensional queries in P2P systems, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017081]
• 19: Ryan Huebsch , Joseph M. Hellerstein , Nick Lanham , Boon Thau Loo , Scott Shenker , Ion Stoica, Querying the internet with PIER, Proceedings of the 29th international conference on Very large data bases, p.321-332, September 09-12, 2003, Berlin, Germany
• 20: M. Hugos. Essentials of Supply Chain Management. John Wiley & Sons, Inc., 2006.
• 21: M. Hugos. Essentials of Supply Chain Management. John Wiley & Sons, Inc., 2006.
• 22: Eiichiro Kazumori, Selling online versus offline: theory and evidences from Sotheby's, Proceedings of the 4th ACM conference on Electronic commerce, p.125-134, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779944]
• 23: Eiichiro Kazumori, Selling online versus offline: theory and evidences from Sotheby's, Proceedings of the 4th ACM conference on Electronic commerce, p.125-134, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779944]
• 24: Boon Thau Loo , Joseph M. Hellerstein , Ryan Huebsch , Scott Shenker , Ion Stoica, Enhancing P2P file-sharing with an internet-scale query processor, Proceedings of the Thirtieth international conference on Very large data bases, p.432-443, August 31-September 03, 2004, Toronto, Canada
• 25: M. Lupu, J. Li, B. C. Ooi, and S. Shi. Clustering wavelets to speed-up data dissemination in structured manets. In ICDE, 2007.
• 26: Gurmeet Singh Manku, Balanced binary trees for ID management and load balance in distributed hash tables, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011797]
• 27: Gurmeet Singh Manku , Moni Naor , Udi Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007368]
• 28: W. S. Ng, B. C. Ooi, and K.-L. Tan. Bestpeer: A self-configurable peer-to-peer system. In ICDE, 2002.
• 29: T. Pitoura, N. Ntarmos, and P. Triantafillou. Replication, load balancing and efficient range query processing in dhts. In EDBT, 2006.
• 30: Stefan Podlipnig , Laszlo Böszörmenyi, A survey of Web cache replacement strategies, ACM Computing Surveys (CSUR), v.35 n.4, p.374-398, December 2003 [doi>10.1145/954339.954341]
• 31: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 32: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 33: O. D. Sahin , A. Gupta , D. Agrawal , A. El Abbadi, A Peer-to-peer Framework for Caching Range Queries, Proceedings of the 20th International Conference on Data Engineering, p.165, March 30-April 02, 2004
• 34: Praveen Seshadri , Arun N. Swami, Generalized Partial Indexes, Proceedings of the Eleventh International Conference on Data Engineering, p.420-427, March 06-10, 1995
• 35: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 36: M. Stonebraker, The case for partial indexes, ACM SIGMOD Record, v.18 n.4, p.4-11, Dec. 1989 [doi>10.1145/74120.74121]
• 37: Daniel Stutzbach , Reza Rejaie , Nick Duffield , Subhabrata Sen , Walter Willinger, On unbiased sampling for unstructured peer-to-peer networks, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177084]
• 38: Igor Tatarinov , Zachary Ives , Jayant Madhavan , Alon Halevy , Dan Suciu , Nilesh Dalvi , Xin (Luna) Dong , Yana Kadiyska , Gerome Miklau , Peter Mork, The Piazza peer data management project, ACM SIGMOD Record, v.32 n.3, September 2003 [doi>10.1145/945721.945732]
• 39: R. Zhang and Y. C. Hu. Assisted peer-to-peer search with partial indexing. In INFOCOM, Miami, USA, March 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance

Keywords:
baton, can, just-in-time, partial indexing, peer-to-peer, sampling, self-tuning