Approximating query completeness by predicting the number of answers in DHT-based web applications

ABSTRACT

Due to the rapid development of theWeb, applications based on the P2P paradigm gain more and more interest. Recently, such systems start to evolve to adopt standard database functionalities in terms of complex query processing support. This goes far beyond simple key lookups, as provided by standard DHT systems, which makes estimating the completeness of query answers a crucial challenge. In this paper, we discuss the semantics of completeness for complex queries in P2P database systems and propose methods based on the notion of routing graphs for estimating the number of expected query answers. Further, we discuss probabilistic guarantees for the estimated values and evaluate the proposed methods through an implemented system.

REFERENCES

• 1: Karl Aberer , Magdalena Punceva , Manfred Hauswirth , Roman Schmidt, Improving Data Access in P2P Systems, IEEE Internet Computing, v.6 n.1, p.58-67, January 2002 [doi>10.1109/4236.978370]
• 2: R. Bhagwan, D. Moore, S. Savage, and G. M. Voelker. Replication Strategies for Highly Available Peer-to-Peer Storage. In Future directions in Distributed Computing, pages 153--158, 2002.
• 3: Min Cai , Martin Frank, RDFPeers: a scalable distributed RDF repository based on a structured peer-to-peer network, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988760]
• 4: Brent Chun , David Culler , Timothy Roscoe , Andy Bavier , Larry Peterson , Mike Wawrzoniak , Mic Bowman, PlanetLab: an overlay testbed for broad-coverage services, ACM SIGCOMM Computer Communication Review, v.33 n.3, July 2003 [doi>10.1145/956993.956995]
• 5: S. D. Gribble, A. Y. Halevy, Z. G. Ives, M. Rodrig, and D. Suciu. What Can Database Do for Peer-to-Peer? In WebDB 2001, pages 31--36, 2001.
• 6: 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
• 7: Marcel Karnstedt , Kai-Uwe Sattler , Michael Haß , Manfred Hauswirth , Brahmananda Sapkota , Roman Schmidt, Estimating the number of answers with guarantees for structured queries in p2p databases, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458304]
• 8: M. Karnstedt, K. Sattler, M. Richtarsky, J. Müller, M. Hauswirth, R. Schmidt, and R. John. UniStore: Querying a DHT-based Universal Storage. In ICDE'07, Demonstr. Program, pages 1503--1504, 2007.
• 9: Marcel Karnstedt , Kai-Uwe Sattler , Roman Schmidt, Completeness Estimation of Range Queries in Structured Overlays, Proceedings of the Seventh IEEE International Conference on Peer-to-Peer Computing, p.71-78, September 02-05, 2007
• 10: Amihai Motro, Completeness Information and Its Application to Query Processing, Proceedings of the 12th International Conference on Very Large Data Bases, p.170-178, August 25-28, 1986
• 11: Dushyanth Narayanan , Austin Donnelly , Richard Mortier , Antony Rowstron, Delay aware querying with seaweed, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 12: Felix Naumann , Johann-Christoph Freytag , Ulf Leser, Completeness of integrated information sources, Information Systems, v.29 n.7, p.583-615, October 2004 [doi>10.1016/j.is.2003.12.005]
• 13: Martin Theobald , Gerhard Weikum , Ralf Schenkel, Top-k query evaluation with probabilistic guarantees, Proceedings of the Thirtieth international conference on Very large data bases, p.648-659, August 31-September 03, 2004, Toronto, Canada

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Management, Performance

Keywords:
dht, probabilistic guarantees, query completeness, query processing