Noname manuscript No. (will be inserted by the editor) Efficient Range Query Processing in Metric Spaces over Highly Distributed Data

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 ap-proach relies on SIMPEER [13], 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 pro-cessing and providing recall-based guarantees for the quality of the result re-trieved so far. This is especially useful for range queries that lead to result sets of high cardinality and incur a high processing cost, while the complete result set becomes overwhelming for the user. Our framework employs statis