Similarity Grid for Searching in Metric Spaces

D 2005

Similarity Grid for Searching in Metric Spaces

BATKO, Michal; Claudio GENNARO a Pavel ZEZULA

Základní údaje

Originální název

Similarity Grid for Searching in Metric Spaces

Název česky

Podobnostní GRID pro hledání v metrických prostrorech

Autoři

BATKO, Michal; Claudio GENNARO a Pavel ZEZULA

Vydání

Berlin, Peer-to-Peer, Grid, and Service-Orientation in Digital Library Architectures: 6th Thematic Workshop of the EU Network of Excellence DELOS. Revised Selected Papers. LNCS 3664, od s. 25-44, 20 s. 2005

Nakladatel

Springer-Verlag Heidelberg

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

20206 Computer hardware and architecture

Stát vydavatele

Německo

Utajení

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

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14610/05:00013400

Organizační jednotka

Ústav výpočetní techniky

ISBN

3-540-28711-6

UT WoS

000232268700003

Klíčová slova anglicky

distributed data; scalable structures; similarity search; metric space

Štítky

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

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 29. 6. 2009 14:42, RNDr. Michal Batko, Ph.D.

Anotace

ORIG CZ

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 structure also scales well with respect to the growing volume of retrieved data. Moreover, a small 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.

Česky

Podobnostní hledání v centralizovaném prostředí se ukazuje nedostatečným z hlediska škálovatelnosti. GHT* je distribuovaná struktura pro podobnostní hledání, založeném na metrických prostorech, která dosahuje prakticky konstantní odezvy pro libovolně rozsáhlá data.

Návaznosti

1ET100300419, projekt VaV

Název: Inteligentní modely, algoritmy, metody a nástroje pro vytváření sémantického webu

Investor: Akademie věd ČR, Inteligentní modely, algoritmy, metody a nástroje pro vytváření sémantického webu

Citovat

BATKO, Michal; Claudio GENNARO a Pavel ZEZULA. Similarity Grid for Searching in Metric Spaces. In Peer-to-Peer, Grid, and Service-Orientation in Digital Library Architectures: 6th Thematic Workshop of the EU Network of Excellence DELOS. Revised Selected Papers. LNCS 3664. Berlin: Springer-Verlag Heidelberg, 2005, s. 25-44. ISBN 3-540-28711-6.

@inproceedings{580521,
   author = {Batko, Michal and Gennaro, Claudio and Zezula, Pavel},
   address = {Berlin},
   booktitle = {Peer-to-Peer, Grid, and Service-Orientation in Digital Library Architectures: 6th Thematic Workshop of the EU Network of Excellence DELOS. Revised Selected Papers. LNCS 3664},
   keywords = {distributed data; scalable structures; similarity search; metric space},
   language = {eng},
   location = {Berlin},
   isbn = {3-540-28711-6},
   pages = {25-44},
   publisher = {Springer-Verlag Heidelberg},
   title = {Similarity Grid for Searching in Metric Spaces},
   year = {2005}
}

TY  - CONF
ID  - 580521
AU  - Batko, Michal - Gennaro, Claudio - Zezula, Pavel
PY  - 2005
TI  - Similarity Grid for Searching in Metric Spaces
PB  - Springer-Verlag Heidelberg
CY  - Berlin
SN  - 3540287116
KW  - distributed data
KW  - scalable structures
KW  - similarity search
KW  - metric space
N2  - 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 structure also scales well with respect to the growing volume of retrieved data. Moreover, a small 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.
ER  -

BATKO, Michal; Claudio GENNARO a Pavel ZEZULA. Similarity Grid for Searching in Metric Spaces. In \textit{Peer-to-Peer, Grid, and Service-Orientation in Digital Library Architectures: 6th Thematic Workshop of the EU Network of Excellence DELOS. Revised Selected Papers. LNCS 3664}. Berlin: Springer-Verlag Heidelberg, 2005, s.~25-44. ISBN~3-540-28711-6.

Přehled o publikaci