DOHNAL, Vlastislav, Claudio GENNARO and Pavel ZEZULA. Similarity Join in Metric Spaces Using eD-Index. In Database and Expert Systems Applications, DEXA 2003. LNCS 2736. Berlin: Springer, 2003. p. 484-493. ISSN 0302-9743.
Other formats:   BibTeX LaTeX RIS
Basic 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
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Czech Republic
Confidentiality degree is not subject to a state or trade secret
Impact factor Impact factor: 0.515 in 2002
RIV identification code RIV/00216224:14330/03:00008910
Organization unit Faculty of Informatics
ISSN 0302-9743
UT WoS 000185936400048
Keywords in English similarity join; index structures; performance; metric data
Tags DISA, index structures, metric data, performance, similarity join
Tags International impact, Reviewed
Changed by Changed by: doc. RNDr. Vlastislav Dohnal, Ph.D., učo 2952. Changed: 22/10/2010 16:12.
Abstract
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.
Abstract (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)Name: Digitální knihovny
Investor: Ministry of Education, Youth and Sports of the CR, Digital libraries
PrintDisplayed: 19/3/2024 05:53