A Two-Level Signature Scheme for Stable Set Similarity Joins

Daniel Ulrich Schmitt, Daniel Kocher, Nikolaus Augsten, Willi Mann, Alexander Miller

Research output: Contribution to conferencePaperpeer-review

Abstract

We study the set similarity join problem, which retrieves all pairs of similar sets from two collections of sets for a given distance function. Existing exact solutions employ a signature-based filter-verification framework: If two sets are similar, they must have at least one signature in common, otherwise they can be pruned safely. We observe that the choice of the signature scheme has a significant impact on the performance. Unfortunately, choosing a good signature scheme is hard because the performance heavily depends on the characteristics of the underlying dataset.

To address this problem, we propose a hybrid signature composition that leverages the most selective portion of each signature scheme. Sets with an unselective primary signature are detected, and the signatures are replaced with a more selective secondary signature. We propose a generic framework called TwoL and a cost model to balance the computational overhead and the selectivity of the signature schemes. We implement our framework with two complementary signature schemes for Jaccard similarity and Hamming distance, resulting in effective two-level hybrid indexes that join datasets with diverse characteristics efficiently. TwoL consistently outperforms state-of-the-art set similarity joins on a benchmark with 13 datasets that cover a wide range of data characteristics.
Original languageEnglish
Pages2686-2698
Number of pages13
DOIs
Publication statusPublished - Jul 2023
Event49th International Conference on Very Large Data Bases 2023 - Vancouver, Canada
Duration: 28 Aug 20231 Sept 2029
Conference number: 49
https://vldb.org/2023/

Conference

Conference49th International Conference on Very Large Data Bases 2023
Abbreviated titleVLDB 2023
Country/TerritoryCanada
CityVancouver
Period28/08/231/09/29
Internet address

Fields of Science and Technology Classification 2012

  • 102 Computer Sciences

Cite this