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

J 2003

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

AMATO, Giuseppe, Fausto RABITTI, Pasquale SAVINO a Pavel ZEZULA

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

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

20206 Computer hardware and architecture

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

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

Změněno: 14. 5. 2003 10:06, prof. Ing. Pavel Zezula, CSc.

Anotace

V originále

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ěr

Název: Digitální knihovny

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Digitální knihovny

Citovat

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.

@article{486237,
   author = {Amato, Giuseppe and Rabitti, Fausto and Savino, Pasquale and Zezula, Pavel},
   article_location = {New York},
   article_number = {2},
   keywords = {Approximation algorithms; approximate similarity search; metric data; metric trees; performance evaluation},
   language = {eng},
   issn = {1046-8188},
   journal = {ACM Transactions on Information Systems},
   title = {Region proximity in metric spaces and its use for approximate similarity search},
   url = {http://doi.acm.org/10.1145/763693.763696},
   volume = {21},
   year = {2003}
}

TY  - JOUR
ID  - 486237
AU  - Amato, Giuseppe - Rabitti, Fausto - Savino, Pasquale - Zezula, Pavel
PY  - 2003
TI  - Region proximity in metric spaces and its use for approximate similarity search
JF  - ACM Transactions on Information Systems
VL  - 21
IS  - 2
SP  - 192 - 227
EP  - 192 - 227
PB  - ACM Press
SN  - 10468188
KW  - Approximation algorithms
KW  - approximate similarity search
KW  - metric data
KW  - metric trees
KW  - performance evaluation
UR  - http://doi.acm.org/10.1145/763693.763696
N2  - 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.
ER  -

AMATO, Giuseppe, Fausto RABITTI, Pasquale SAVINO a Pavel ZEZULA. Region proximity in metric spaces and its use for approximate similarity search. \textit{ACM Transactions on Information Systems}. New York: ACM Press, 2003, roč.~21, č.~2, s.~192 - 227. ISSN~1046-8188.

Podrobný výpis o publikaci