Detailed Information on Publication Record
2003
Similarity Join in Metric Spaces Using eD-Index
DOHNAL, Vlastislav, Claudio GENNARO and Pavel ZEZULABasic information
Original name
Similarity Join in Metric Spaces Using eD-Index
Name in Czech
Podobnostní spojení pro metrické prostory použitím eD-Indexu
Authors
DOHNAL, Vlastislav (203 Czech Republic), Claudio GENNARO (380 Italy) and Pavel ZEZULA (203 Czech Republic, guarantor)
Edition
LNCS 2736. Berlin, Database and Expert Systems Applications, DEXA 2003, p. 484-493, 10 pp. 2003
Publisher
Springer
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Czech Republic
Confidentiality degree
není předmětem státního či obchodního tajemství
Impact factor
Impact factor: 0.515 in 2002
RIV identification code
RIV/00216224:14330/03:00008910
Organization unit
Faculty of Informatics
ISSN
UT WoS
000185936400048
Keywords in English
similarity join; index structures; performance; metric data
Tags
International impact, Reviewed
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.
In Czech
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.
Links
| MSM 143300004, plan (intention) |
|