2003
Similarity Join in Metric Spaces Using eD-Index
DOHNAL, Vlastislav, Claudio GENNARO a Pavel ZEZULAZákladní údaje
Originální název
Similarity Join in Metric Spaces Using eD-Index
Název česky
Podobnostní spojení pro metrické prostory použitím eD-Indexu
Autoři
DOHNAL, Vlastislav (203 Česká republika), Claudio GENNARO (380 Itálie) a Pavel ZEZULA (203 Česká republika, garant)
Vydání
LNCS 2736. Berlin, Database and Expert Systems Applications, DEXA 2003, od s. 484-493, 10 s. 2003
Nakladatel
Springer
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Česká republika
Utajení
není předmětem státního či obchodního tajemství
Impakt faktor
Impact factor: 0.515 v roce 2002
Kód RIV
RIV/00216224:14330/03:00008910
Organizační jednotka
Fakulta informatiky
ISSN
UT WoS
000185936400048
Klíčová slova anglicky
similarity join; index structures; performance; metric data
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 22. 10. 2010 16:12, doc. RNDr. Vlastislav Dohnal, Ph.D.
V originále
Similarity join in distance spaces constrained by the metric postulates is the necessary complement of more famous similarity range and the nearest neighbor search primitives. However, the quadratic computational complexity of similarity joins prevents from applications on large data collections. We present the eD-Index, an extension of D-index, and we study an application of the eD-Index to implement two algorithms for similarity self joins, i.e. the range query join and the overloading join. Though also these approaches are not able to eliminate the intrinsic quadratic complexity of similarity joins, significant performance improvements are confirmed by experiments.
Česky
Operace podobnostního spojení v metrických prostorech tvoří důležitý doplněk k známějším rozsahovým dotazům a dotazům na nejbližší sousedy, avšak kvadratická výpočetní složitost podobnostního spojení zabraňuje jej aplikovat na velké kolekce dat. Představujeme index zvaný eD-Index, který je rozšířením původní struktury D-Index, a analyzujeme implementace dvou rozdílných algoritmů -- rozsahové podobnostní spojení a spojení pomocí přetěžování. Ačkoli tyto přístupy jsou schopny odstranit kvadratickou složitost, poskytují významné urychlení, což je experimentálně potvrzeno.
Návaznosti
| MSM 143300004, záměr |
|