Given a similarity function and two sets of object, a similarity join returns all pairs of objects (from each set respectively) such that their similarity value satisifies a given criterion. A typical example is to find pairs of documents such that their cosine similarity is above a constant (say, 0.95), as they are likely to be near duplicate documents.
In this project, we focus on efficient algorithms to perform the similarity join exactly on (multi-) sets or strings. Commonly used similarity functions for (multi-) sets or strings are more complex than Euclidean distance functions. As a result, many previous approaches have to compute the approximate results instead.
We have developed several fast algorithms that address the above performance issue. They work for Jaccard, Dice, Cosine similarities and Edit distance constraints. We have also devised algorithms to compute top-k similar pairs progressively so that a user does not need to specify a similarity threshold for some unknown dataset.
This project is partly funded by ARC Discovery Project DP0987273.
Academic Staff:
PhD Student:
Wei Wang. Efficient Exact Similarity Join Algorithms. Seminar at University of Technology, Sydney, Oct 2009.
Chuan Xiao, Wei Wang, Xuemin Lin, Haichuan Shang. Top-k Set Similarity Joins. ICDE 2009.
Slides
Summary: Not sure about which similarity threshold to use when performing similarity join? Then this top-k similarity join algorithm is for you; it computes the k pairs of records that have the highest similarity value in a progressive manner.
Wei Wang. Similarity Join Algorithms: An Introduction. Tutorial at SEBD 2008.
Slides (ppt slides available upon request).
Chuan Xiao, Wei Wang, Xuemin Lin. Ed-Join: An Efficient Algorithm for Similarity Joins with Edit Distance Constraints. VLDB 2008.
Chuan Xiao, Wei Wang, Xuemin Lin, Jeffrey Xu Yu. Efficient Similarity Joins for Near Duplicate Detection. WWW 2008.