D 2000

Approximate Similarity Search in Metric Data by Using Region Proximity

AMATO, Giuseppe, Pasquale SAVINO, Rabitti FAUSTO and Pavel ZEZULA

Basic information

Original name

Approximate Similarity Search in Metric Data by Using Region Proximity

Authors

AMATO, Giuseppe, Pasquale SAVINO, Rabitti FAUSTO and Pavel ZEZULA

Edition

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

Publisher

ERCIM

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10000 1. Natural Sciences

Country of publisher

Switzerland

Confidentiality degree

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

RIV identification code

RIV/00216224:14330/00:00002860

Organization unit

Faculty of Informatics

ISBN

ERCIM-01-W01
Změněno: 19/2/2001 17:19, prof. Ing. Pavel Zezula, CSc.

Abstract

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.

Links

MSM 143300004, plan (intention)
Name: Digitální knihovny
Investor: Ministry of Education, Youth and Sports of the CR, Digital libraries