NDLI: Efficient range query processing in metric spaces over highly distributed data

Content Provider	Springer Nature Link
Author	Doulkeridis, Christos Vlachou, Akrivi Kotidis, Yannis Vazirgiannis, Michalis
Copyright Year	2009
Abstract	Similarity search in P2P systems has attracted a lot of attention recently and several important applications, like distributed image search, can profit from the proposed distributed algorithms. In this paper, we address the challenging problem of efficient processing of range queries in metric spaces, where data is horizontally distributed across a super-peer network. Our approach relies on SIMPEER (Doulkeridis et al. in Proceedings of VLDB, pp. 986–997, 2007), a framework that dynamically clusters peer data, in order to build distributed routing information at super-peer level. SIMPEER allows the evaluation of exact range and nearest neighbor queries in a distributed manner that reduces communication cost, network latency, bandwidth consumption and computational overhead at each individual peer. In this paper, we extend SIMPEER by focusing on efficient range query processing and providing recall-based guarantees for the quality of the result retrieved so far. This is especially useful for range queries that lead to result sets of high cardinality and incur high processing costs, while the complete result set becomes overwhelming for the user. Our framework employs statistics for estimating an upper limit of the number of possible results for a range query and each super-peer may decide not to propagate further the query and reduce the scope of the search. We provide an experimental evaluation of our framework and show that our approach performs efficiently, even in the case of high degree of distribution.
Starting Page	155
Ending Page	180
Page Count	26
File Format	PDF
ISSN	09268782
Journal	Distributed and Parallel Databases
Volume Number	26
Issue Number	2-3
e-ISSN	15737578
Language	English
Publisher	Springer US
Publisher Date	2009-07-09
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Similarity search Peer-to-peer Range queries Memory Structures Operating Systems Database Management Information Systems Applications (incl.Internet) Data Structures
Content Type	Text
Resource Type	Article
Subject	Information Systems and Management Information Systems Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Adaptive processing of historical spatial range queries in peer-to-peer sensor networks

Distributed top-k aggregation queries at large

Distributed stream join query processing with semijoins

Efficient processing of aggregation queries in sensor networks

Indexing views to route queries in a PDMS

Linking identical neighborly partitions for efficient high-dimensional similarity search in unstructured peer-to-peer systems

Fault-tolerant query processing in structured P2P-systems

Parallel processing of continuous queries over data streams

Reducing network traffic in unstructured P2P systems using Top-k queries

Efficient range query processing in metric spaces over highly distributed data

Similar Documents

Adaptive processing of historical spatial range queries in peer-to-peer sensor networks

Distributed top-k aggregation queries at large

Distributed stream join query processing with semijoins

Efficient processing of aggregation queries in sensor networks

Indexing views to route queries in a PDMS

Linking identical neighborly partitions for efficient high-dimensional similarity search in unstructured peer-to-peer systems

Fault-tolerant query processing in structured P2P-systems

Parallel processing of continuous queries over data streams

Reducing network traffic in unstructured P2P systems using Top-k queries

Efficient range query processing in metric spaces over highly distributed data