An efficient similarity join algorithm with cosine similarity predicate

Dongjoo Lee, Jaehui Park, Junho Shim, Sang Goo Lee

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

27 Scopus citations


Given a large collection of objects, finding all pairs of similar objects, namely similarity join, is widely used to solve various problems in many application domains.Computation time of similarity join is critical issue, since similarity join requires computing similarity values for all possible pairs of objects. Several existing algorithms adopt prefix filtering to avoid unnecessary similarity computation; however, existing algorithms implementing the prefix filtering have inefficiency in filtering out object pairs, in particular, when aggregate weighted similarity function, such as cosine similarity, is used to quantify similarity values between objects. This is mostly caused by large prefixes the algorithms select. In this paper, we propose an alternative method to select small prefixes by exploiting the relationship between arithmetic mean and geometric mean of elements' weights. A new algorithm, MMJoin, implementing the proposed methods dramatically reduces the average size of prefixes without much overhead. Finally, it saves much computation time. We demonstrate that our algorithm outperforms a state-of-the-art one with empirical evaluation on large-scale real world datasets.

Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications - 21st International Conference, DEXA 2010, Proceedings
Number of pages15
EditionPART 2
StatePublished - 2010
Event21st International Conference on Database and Expert Systems Applications, DEXA 2010 - Bilbao, Spain
Duration: 30 Aug 20103 Sep 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume6262 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st International Conference on Database and Expert Systems Applications, DEXA 2010


Dive into the research topics of 'An efficient similarity join algorithm with cosine similarity predicate'. Together they form a unique fingerprint.

Cite this