On Locality-sensitive Indexing in Generic Metric Spaces

NOVÁK, David, Martin KYSELÁK a Pavel ZEZULA. On Locality-sensitive Indexing in Generic Metric Spaces. In 3rd International Conference on Similarity Search and Applications. New York: ACM Press, 2010, s. 59-66. ISBN 978-1-4503-0420-7.

Základní údaje

Originální název

On Locality-sensitive Indexing in Generic Metric Spaces

Název česky

O indexovaní respektujícím vzdálenosti objektů v obecných metrických prostorech.

Autoři

NOVÁK, David (203 Česká republika, garant, domácí), Martin KYSELÁK (203 Česká republika) a Pavel ZEZULA (203 Česká republika, domácí)

Vydání

New York, 3rd International Conference on Similarity Search and Applications, od s. 59-66, 8 s. 2010

Nakladatel

ACM Press

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Turecko

Utajení

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

Forma vydání

tištěná verze "print"

Kód RIV

RIV/00216224:14330/10:00044857

Organizační jednotka

Fakulta informatiky

ISBN

978-1-4503-0420-7

Klíčová slova anglicky

locality-sensitive hashing; metric space; similarity search; approximation; scalability

Štítky

DISA

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

The concept of Locality-sensitive Hashing (LSH) has been successfully used for searching in high-dimensional data and a number of locality-preserving hash functions have been introduced. In order to extend the applicability of the LSH approach to a general metric space, we focus on a recently presented Metric Index (M-Index), we redefine its hashing and searching process in the terms of LSH, and perform extensive measurements on two datasets to verify that the M-Index fulfills the conditions of the LSH concept. We widely discuss "optimal" properties of LSH functions and the efficiency of a given LSH function with respect to kNN queries. The results also indicate that the M-Index hashing and searching is more efficient than the tested standard LSH approach for Euclidean distance.

---

Návaznosti

GAP103/10/0886, projekt VaV	Název: Vizuální vyhledávání obrázků na Webu (Akronym: VisualWeb) Investor: Grantová agentura ČR, Vizuální vyhledávání obrázků na Webu
GA201/09/0683, projekt VaV	Název: Vyhledávání v rozsáhlých multimediálních databázích Investor: Grantová agentura ČR, Vyhledávání v rozsáhlých multimediálních databázích
GPP202/10/P220, projekt VaV	Název: Podobnostní vyhledávání s konstantní škálovatelností (Akronym: SIM-SCALE) Investor: Grantová agentura ČR, Podobnostní vyhledávání s konstantní škálovatelností
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky