Approximate Similarity Search in Metric Data by Using Region
Proximity

D 2000

Approximate Similarity Search in Metric Data by Using Region Proximity

AMATO, Giuseppe; Pasquale SAVINO; Rabitti FAUSTO a Pavel ZEZULA

Základní údaje

Originální název

Approximate Similarity Search in Metric Data by Using Region Proximity

Autoři

AMATO, Giuseppe; Pasquale SAVINO; Rabitti FAUSTO a Pavel ZEZULA

Vydání

Zurich, Proceedings of the First DELOS Network of Excellence Workshop on "Information Seeking, Searching and Querying in Digital Libraries" s. 101-106, Workshop series, 2000

Nakladatel

ERCIM

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10000 1. Natural Sciences

Stát vydavatele

Švýcarsko

Utajení

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

Kód RIV

RIV/00216224:14330/00:00002860

Organizační jednotka

Fakulta informatiky

ISBN

ERCIM-01-W01

Změněno: 19. 2. 2001 17:19, prof. Ing. Pavel Zezula, CSc.

Anotace

V originále

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.

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; Pasquale SAVINO; Rabitti FAUSTO a Pavel ZEZULA. Approximate Similarity Search in Metric Data by Using Region Proximity. In Proceedings of the First DELOS Network of Excellence Workshop on "Information Seeking, Searching and Querying in Digital Libraries". Zurich: ERCIM, 2000, s. 101-106. Workshop series. ISBN ERCIM-01-W01.

@inproceedings{348853,
   author = {Amato, Giuseppe and Savino, Pasquale and Fausto, Rabitti and Zezula, Pavel},
   address = {Zurich},
   booktitle = {Proceedings of the First DELOS Network of Excellence Workshop on "Information Seeking, Searching and Querying in Digital Libraries"},
   language = {eng},
   location = {Zurich},
   isbn = {ERCIM-01-W01},
   pages = {101-106},
   publisher = {ERCIM},
   title = {Approximate Similarity Search in Metric Data by Using Region Proximity},
   year = {2000}
}

TY  - CONF
ID  - 348853
AU  - Amato, Giuseppe - Savino, Pasquale - Fausto, Rabitti - Zezula, Pavel
PY  - 2000
TI  - Approximate Similarity Search in Metric Data by Using Region Proximity
VL  - Workshop series
PB  - ERCIM
CY  - Zurich
SN  - ERCIM01W01
N2  - 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.
ER  -

AMATO, Giuseppe; Pasquale SAVINO; Rabitti FAUSTO a Pavel ZEZULA. Approximate Similarity Search in Metric Data by Using Region Proximity. In \textit{Proceedings of the First DELOS Network of Excellence Workshop on ''Information Seeking, Searching and Querying in Digital Libraries''}. Zurich: ERCIM, 2000, s.~101-106. Workshop series. ISBN~ERCIM-01-W01.

Přehled o publikaci