Scalable Similarity Search in Metric Spaces

BATKO, Michal, Claudio GENNARO, Savino PASQUALE and Pavel ZEZULA. Scalable Similarity Search in Metric Spaces. In Pre-proceedings of the Sixth Thematic Workshop of the EU Network of Excellence DELOS. Cagliari: Edizioni Progetto Padova, 2004, p. 213-224.

Basic information

Original name

Scalable Similarity Search in Metric Spaces

Name in Czech

Škálovatelné podobnostní hledání v metrických prostorech

Authors

BATKO, Michal (203 Czech Republic), Claudio GENNARO (380 Italy), Savino PASQUALE (380 Italy) and Pavel ZEZULA (203 Czech Republic, guarantor)

Edition

Cagliari, Pre-proceedings of the Sixth Thematic Workshop of the EU Network of Excellence DELOS, p. 213-224, 12 pp. 2004

Publisher

Edizioni Progetto Padova

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

20206 Computer hardware and architecture

Country of publisher

Italy

Confidentiality degree

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

RIV identification code

RIV/00216224:14610/04:00010210

Organization unit

Institute of Computer Science

Keywords in English

distributed data; scalable structures; similarity search; metric space

Tags

DISA, distributed data, Metric Space, scalable structures, similarity search

Tags

International impact, Reviewed

---

Abstract

V originále

Similarity search in metric spaces represents an important paradigm for content-based retrieval of many applications. Existing centralized search structures can speed-up retrieval, but they do not scale up to large volume of data because the response time is linearly increasing with the size of the searched file. The proposed GHT* index is a scalable and distributed structure. By exploiting parallelism in a dynamic network of computers, the GHT* achieves practically constant search time for similarity range queries in data-sets of arbitrary size. The amount of replicated routing information on each server increases logarithmically. At the same time, the potential for interquery parallelism is increasing with the growing data-sets because the relative number of servers utilized by individual queries is decreasing. All these properties are verified by experiments on a prototype system using real-life data-sets.

In Czech

Tento článek popisuje strukturu pro distribuované podobnostní hledaní v metrických prostorech.

---

Links

MSM 143300004, plan (intention)

Name: Digitální knihovny Investor: Ministry of Education, Youth and Sports of the CR, Digital libraries