Approximate Similarity Search in Metric Data by Using Region Proximity

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

AMATO Giuseppe SAVINO Pasquale FAUSTO Rabitti ZEZULA Pavel

Year of publication 2000
Type Article in Proceedings
Conference Proceedings of the First DELOS Network of Excellence Workshop on "Information Seeking, Searching and Querying in Digital Libraries"
MU Faculty or unit

Faculty of Informatics

Citation
Field Information theory
Description The problem of approximated similarity search for the range and nearest neighbor queries is investigated for generic metric spaces. The search speedup is achieved by ignoring data regions with a small, user defined, proximity with respect to the query. For zero proximity, exact similarity search is performed. The problem of proximity of metric regions is explained and a probabilistic approach is applied. Approximated algorithms use a small amount of auxiliary data that can easily be maintained in main memory. The idea is implemented in a metric tree environment and experimentally evaluated on real-life files using specific performance measures. Improvements of two orders of magnitude can be achieved for moderately approximated search results. It is also demonstrated that the precision of proximity measures can significantly influence the quality of approximated algorithms.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info