Approximating query completeness by predicting the number of answers in DHT-based web applications
Marcel Karnstedt, Kai-Uwe Sattler, Michael Haß, Manfred Hauswirth, Brahmananda Sapkota, Roman Léandre Schmidt · 2008
Due to the rapid development of the Web, 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.