Lune

ICDE2023顶会

MetricJoin: Leveraging Metric Properties for Robust Exact Set Similarity Joins

Manuel Widmoser, Daniel Kocher, Nikolaus Augsten, Willi Mann

摘要

Given two collections of sets, the set similarity join reports all pairs of sets that are within a given distance threshold. State-of-the-art solutions employ an inverted list index and several heuristics to compute the join result efficiently. Prefix-based solutions benefit from infrequent set elements, known as tokens, and spend considerable time scanning long lists if the token frequency is not sufficiently skewed. Partition-based methods are less sensitive to the token distribution but suffer from a significantly larger memory footprint, limiting their applicability as the threshold or the set sizes grow. Solutions from the domain of metric-based similarity search are designed to reduce the overall number of distance computations. Generic metric techniques cannot compete with state-of-the-art similarity joins tailored to sets, which in turn do not exploit metric filter opportunities.We propose MetricJoin, the first exact set similarity join technique that leverages the metric properties of set distance functions. In contrast to its competitors, MetricJoin is robust, i.e., datasets with different characteristics can be joined efficiently in terms of runtime and memory. Our algorithm embeds sets in vector space, organizes long inverted lists in spatial indexes, and employs an effective metric filter to prune unqualified sets. MetricJoin requires only linear space in the collection size and substantially reduces the number of sets that must be considered. In our performance studies, MetricJoin outperforms state-of-the-art solutions by up to an order of magnitude in runtime and generates up to five orders of magnitude fewer candidates.

问 Lune

几分钟看清这篇 Paper 的位置,不用再花一下午。

Lune 能读引用它和与它最相关的顶会 Paper,讲清它说了什么、后来怎样、哪里站不住,每一点都注明出自哪篇 Paper。不用硬啃,也不靠猜。

已有 3 篇顶会 Paper 引用了它。别等审稿人问起,先弄清它们发现了什么。

可以从这些问题问起

Lune 可以查阅

摘要 · 引用它的顶会 Paper · 相关的 Paper

获取答案

免费开始,无需绑卡

脉络

  • PAIL: Efficient kNN Search on Set-Valued Attributes 引用了 Extensible and Robust Evaluation of Similarity Queries
它引用的引用它的从左到右按年份排列,引用越多,位置越高。

引用它的顶会 Paper3

  1. SeDA: Bridging the Gap between Efficient Syntactic and Precise Semantic Search of Similar Passages in Large Text CorporaPranay Mundra, Daniel Kocher, Martin Schaeler, Nikolaus AugstenVLDB 2026
  2. PAIL: Efficient kNN Search on Set-Valued AttributesDaniel Ulrich Schmitt, Thomas Hütter, Nikolaus AugstenVLDB 2026
  3. Extensible and Robust Evaluation of Similarity QueriesDaniel Ulrich Schmitt, Thomas Hütter, Nikolaus AugstenVLDB 2025

相关 Paper

  1. TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite MatchingAlexandros Zeakis, Dimitrios Skoutas, Dimitris Sacharidis, Odysseas Papapetrou 等VLDB 2023 · 7 次引用
  2. DiskJoin: Large-scale Vector Similarity Join with SSDYanqi Chen, Xiao Yan, Alexandra Meliou, Eric LoSIGMOD 2026 · 2 次引用
  3. Adaptive Top-k Overlap Set Similarity JoinsZhong Yang, Bolong Zheng, GuoHui Li, Xi Zhao 等ICDE 2020 · 20 次引用
  4. SSC-Join: An Efficient Syntactic-Semantic Collaboration Based Set Semantic Similarity Join AlgorithmLianyin Jia, Chengchen Zeng, Mengjuan Li, Suprio Ray 等ICDE 2026
  5. Fast Approximate Similarity Join in Vector DatabasesJiadong Xie, Jeffrey Xu Yu, Yingfan LiuSIGMOD 2025 · 6 次引用
黄昏的海面,两侧是细线勾勒的悬崖