Towards a unified framework for string similarity joins

Pengfei Xu, Jiaheng Lu

Research output: Contribution to journalArticleScientificpeer-review

Abstract

A similarity join aims to find all similar pairs between two collections of records. Established algorithms utilise different similarity measures, either syntactic or semantic, to quantify the similarity between two records. However, when records are similar in forms of a mixture of syntactic and semantic relations, utilising a single measure becomes inadequate to disclose the real similarity between records, and hence unable to obtain high-quality join results.

In this paper, we study a unified framework to find similar records by combining multiple similarity measures. To achieve this goal, we first develop a new similarity framework that unifies the existing three kinds of similarity measures simultaneously, including syntactic (typographic) similarity, synonym-based similarity, and taxonomy-based similarity. We then theoretically prove that finding the maximum unified similarity between two strings is generally NP-hard, and furthermore develop an approximate algorithm which runs in polynomial time with a non-trivial approximation guarantee. To support efficient string joins based on our unified similarity measure, we adopt the filter-and-verification framework and propose a new signature structure, called pebble, which can be simultaneously adapted to handle multiple similarity measures. The salient feature of our approach is that, it can judiciously select the best pebble signatures and the overlap thresholds to maximise the filtering power. Extensive experiments show that our methods are capable of finding similar records having mixed types of similarity relations, while exhibiting high efficiency and scalability for similarity joins. The implementation can be downloaded at https://github.com/HY-UDBMS/AU-Join.
Original languageEnglish
JournalProceedings of the VLDB Endowment
Volume12
Issue number11
Pages (from-to)1289-1302
Number of pages14
ISSN2150-8097
DOIs
Publication statusPublished - 1 Jul 2019
MoE publication typeA1 Journal article-refereed
EventInternational Conference on Very Large Data Bases - 404 S Figueroa St., Los Angeles, United States
Duration: 26 Aug 201930 Aug 2019
Conference number: 2019
https://vldb.org/2019/

Fields of Science

  • 113 Computer and information sciences
  • database
  • string processing

Cite this