Istituto di Scienza e Tecnologie dell'Informazione     
Amato G., Rabitti F., Savino P., Zezula P. Region Proximity in Metric Spaces and its use for Approximate Similarity Search. In: Acm Transactions on Information Systems, vol. 21 (2) pp. 192 - 227. ACM, 2003.
Similarity search structures for metric data typically bound object partitions by ball regions. Since regions can overlap, a relevant issue is to estimate the proximity of regions in order to predict the number of objects in the regions' intersection. The paper analyzes the problem by using a probabilistic approach and provides a solution that effectively computes the proximity through realistic heuristics that only require small amounts of auxiliary data. An extensive simulation to validate the technique is provided. An application is then developed to demonstrate how the proximity measure can be successfully applied to the approximate similarity search. Search speedup is achieved by ignoring data regions whose proximity with the query region is smaller than a user defined threshold. This idea is implemented in a metric tree environment for the similarity range and nearest neighbors queries. Several measures of efficiency and effectiveness are applied to evaluate proposed approximate search algorithms on real-life data sets. Improvements of two orders of magnitude are achieved for moderately approximated search results. We demonstrate that the precision of proximity measures can significantly influence the quality of approximated algorithms.
Subject Approximation algorithms
Performance evaluation
Metric trees
Approximate similarity search
Metric data
E.1 Data Structures. Trees
E.5 Files. Sorting/Searching
H.2.2 Physical Design. Access Methods
H.3.3 Information Search and Retrieval. Search process

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional