Creator of Knowledge
Information Resources Management Association
Advancing the Concepts & Practices of Information Resources Management in Modern Organizations

Estimating the Completeness of Range Queries over Structured P2P Databases: Fundamentals, Theory, and Effective Applications to Distributed Information Systems

Estimating the Completeness of Range Queries over Structured P2P Databases: Fundamentals, Theory, and Effective Applications to Distributed Information Systems
View Sample PDF
Author(s): Alfredo Cuzzocrea (ICAR-CNR, Italy & University of Calabria, Italy), Marcel Karnstedt (DERI, NUI Galway, Ireland), Manfred Hauswirth (DERI, NUI Galway, Ireland), Kai-Uwe Sattler (Ilmenau University of Technology, Germany) and Roman Schmidt (Ecole Polytechnique Federale de Lausanne, Switzerland)
Copyright: 2012
Pages: 31
Source title: Next Generation Content Delivery Infrastructures: Emerging Paradigms and Technologies
Source Author(s)/Editor(s): Giancarlo Fortino (Università della Calabria, Italy) and Carlos E. Palau (Universidad Politécnica de Valencia, Spain)
DOI: 10.4018/978-1-4666-1794-0.ch011



Range queries are a very powerful tool in a wide range of data management systems and are vital to a multitude of applications. The hierarchy of structured overlay systems can be utilized in order to provide efficient techniques for processing them, resulting in the support of applications and techniques based on range queries in large-scale distributed information systems. On the other hand, due to the rapid development of the Web, applications based on the P2P paradigm gain more and more interest, having such systems started to evolve towards adopting standard database functionalities in terms of complex query processing support. This goes far beyond simple key lookups, as provided by standard distributed hashtables (DHTs) systems, which makes estimating the completeness of query answers a crucial challenge. Unfortunately, due to the limited knowledge and the usually best-effort characteristics, deciding about the completeness of query results, e.g., getting an idea when a query is finished or what amount of results is still missing, is very challenging. There is not only an urgent need to provide this information to the user issuing queries, but also for implementing sophisticated and efficient processing techniques based on them. In this chapter, the authors propose a method for solving this task. They discuss the applicability and quality of the estimations, present an implementation and evaluation for the P-Grid system, and show how to adapt the technique to other overlays. The authors also 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. Finally, they discuss probabilistic guarantees for the estimated values and evaluate the proposed methods through an implemented system.

Related Content

Mahesh Kumar Jha, Monika Singh, Anindita Sahoo. © 2021. 25 pages.
Reinaldo Padilha França, Ana Carolina Borges Monteiro, Rangel Arthur, Yuzo Iano. © 2021. 20 pages.
Eisha Akanksha. © 2021. 40 pages.
Sasmita Mohanty. © 2021. 19 pages.
Anjali Anjali. © 2021. 22 pages.
Richa Rajesh Tengshe, Anindita Sahoo. © 2021. 26 pages.
Subrata Kumar Routray. © 2021. 22 pages.
Body Bottom