Region proximity in metric spaces and its use for approximate similarity search

Varování

Publikace nespadá pod Fakultu sportovních studií, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

AMATO Giuseppe RABITTI Fausto SAVINO Pasquale ZEZULA Pavel

Rok publikování 2003
Druh Článek v odborném periodiku
Časopis / Zdroj ACM Transactions on Information Systems
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://doi.acm.org/10.1145/763693.763696
Obor Počítačový hardware a software
Klíčová slova Approximation algorithms; approximate similarity search; metric data; metric trees; performance evaluation
Popis 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. This paper analyzes the problem 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 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 to 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. An analytical model is developed to relate proximity parameters and the quality of search. 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info