Informační systém Masarykovy univerzity 

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

česky | in English

AMATO, Giuseppe, Fausto RABITTI, Pasquale SAVINO a Pavel ZEZULA. Region proximity in metric spaces and its use for approximate similarity search. ACM Transactions on Information Systems, New York: ACM Press, 2003, roč. 21, č. 2, s. 192 - 227. ISSN 1046-8188.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Region proximity in metric spaces and its use for approximate similarity search
Autoři AMATO, Giuseppe (380 Itálie), Fausto RABITTI (380 Itálie), Pasquale SAVINO (380 Itálie) a Pavel ZEZULA (203 Česká republika, garant).
Vydání ACM Transactions on Information Systems, New York, ACM Press, 2003, 1046-8188.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor Počítačový hardware a software
Stát vydavatele Spojené státy americké
Utajení není předmětem státního či obchodního tajemství
WWW URL
Impakt faktor Impact factor: 3.533
Kód RIV RIV/00216224:14330/03:00008675
Organizační jednotka Fakulta informatiky
UT WoS 000182275900003
Klíčová slova anglicky Approximation algorithms; approximate similarity search; metric data; metric trees; performance evaluation
Štítky approximate similarity search, Approximation algorithms, metric data, metric trees, performance evaluation
Změnil Změnil: prof. Ing. Pavel Zezula, CSc., učo 47485. Změněno: 14. 5. 2003 10:06.
Anotace
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.
Návaznosti
MSM 143300004, záměrNázev: Digitální knihovny
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
VytisknoutZobrazeno: 23. 10. 2017 06:10

Relevantní odkazy 


Nahoru | Aktuální datum a čas: 23. 10. 2017 06:10, 43. (lichý) týden

Kontakty: istech(zavináč/atsign)fi(tečka/dot)muni(tečka/dot)cz, studijní odd., správci práv, is-technici, e-technici, IT podpora | Použití cookies | Více o Informačním systému