Projects per year
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.
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 language | English |
---|---|
Pages | 2686-2698 |
Number of pages | 13 |
DOIs | |
Publication status | Published - Jul 2023 |
Event | 49th International Conference on Very Large Data Bases 2023 - Vancouver, Canada Duration: 28 Aug 2023 → 1 Sept 2029 Conference number: 49 https://vldb.org/2023/ |
Conference
Conference | 49th International Conference on Very Large Data Bases 2023 |
---|---|
Abbreviated title | VLDB 2023 |
Country/Territory | Canada |
City | Vancouver |
Period | 28/08/23 → 1/09/29 |
Internet address |
Fields of Science and Technology Classification 2012
- 102 Computer Sciences
Projects
- 1 Active
-
DESQ: DESQ - Declarative and Efficient Similarity Queries
Augsten, N. (Principal Investigator)
1/12/21 → 30/11/25
Project: Research
Research output
- 2 Patent
-
Method for Stable Set Similarity Join
Schmitt, D. U. (Inventor), Augsten, N. (Inventor), Kocher, D. (Inventor) & Mann, W. (Inventor), 2 Nov 2023, IPC No. G06F 16/22 2019.1, Patent No. WO2023208903A1Research output: Patent
-
Method for Stable Set Similarity Joins
Schmitt, D. U. (Inventor), Augsten, N. (Inventor), Kocher, D. (Inventor), Mann, W. (Inventor) & Miller, A. (Inventor), 1 Nov 2023, IPC No. G06F16/22, Patent No. EP4270210A1Research output: Patent
-
A Two-Level Signature Scheme for Stable Set Similarity Joins
Schmitt, D. U. (Speaker)
10 Feb 2024Activity: Talk or presentation › Oral presentation › science to science / art to art
-
A Two-Level Signature Scheme for Stable Set Similarity Joins
Schmitt, D. U. (Speaker)
30 Aug 2023Activity: Talk or presentation › Poster presentation › science to science / art to art
-
A Two-Level Signature Scheme for Stable Set Similarity Joins
Schmitt, D. U. (Speaker)
30 Aug 2023Activity: Talk or presentation › Oral presentation › science to science / art to art