PAIL: Efficient kNN Search on Set-Valued Attributes
Abstract
We study the 𝑘-nearest neighbors (𝑘NN) search problem on the domain of sets. Given a query set, the goal is to retrieve the 𝑘 most similar sets from a collection according to a specified similarity function. Most existing solutions for set similarity queries focus on range search or top-𝑘 joins, which typically assume and exploit high similarity thresholds. We observe that existing approaches for 𝑘NN search -as well as adaptations of range search and top-𝑘 algorithms -exhibit poor performance due to low selectivity of their filtering techniques and high index traversal costs.
To address these limitations, we propose Pail, a 𝑘NN search algorithm for sets that supports a wide range of similarity functions. Pail implements the positional filter -a filter that was previously used for post-filtering of candidates returned by an index -directly into a novel index structure to effectively prune candidates. To efficiently traverse only the necessary parts of the index, Pail leverages the monotonicity of the similarity functions with respect to positional information. This traversal enables early termination by ensuring that the index is accessed in descending order of similarity upper bounds. To reduce index access overhead, we propose size grouping and eager reading of index entries that relax filter tightness for improved overall performance. Extensive experiments across diverse datasets demonstrate that Pail consistently outperforms competing algorithms by up to three orders of magnitude.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on6
- Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and LimitationsPiotr Indyk, Haike XuNeurIPS 2023 · 55 citations
- Adaptive Top-k Overlap Set Similarity JoinsZhong Yang, Bolong Zheng, GuoHui Li, Xi Zhao et al.ICDE 2020 · 20 citations
- LES3: Learning-based exact set similarity searchYifan Li, Xiaohui Yu, Nick KoudasVLDB 2021 · 8 citations
- MetricJoin: Leveraging Metric Properties for Robust Exact Set Similarity JoinsManuel Widmoser, Daniel Kocher, Nikolaus Augsten, Willi MannICDE 2023 · 4 citations
- A Two-Level Signature Scheme for Stable Set Similarity JoinsDaniel Ulrich Schmitt, Daniel Kocher, Nikolaus Augsten, Willi Mann et al.VLDB 2023 · 3 citations
Related papers
- minIL: A Simple and Small Index for String Similarity Search with Edit DistanceZhong Yang, Bolong Zheng, Xianzhi Wang, Guohui Li et al.ICDE 2022 · 2 citations
- Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor SearchFangyuan Zhang, Mengxu Jiang, Guanhao Hou, Jieming Shi et al.SIGMOD 2025 · 8 citations
- Koios: Top-k Semantic Overlap Set SearchPranay Mundra, Jianhao Zhang, Fatemeh Nargesian, Nikolaus AugstenICDE 2023 · 7 citations
- Graph-Based Algorithms for Diverse Similarity SearchPiyush Anand, Piotr Indyk, Ravishankar Krishnaswamy, Sepideh Mahabadi et al.ICML 2025
- PICK: An SRAM-based Processing-in-Memory Accelerator for K-Nearest-Neighbor Search in Point CloudsChen Nie, Chao Jiang, Liming Xiao, Weifeng Zhang et al.DAC 2025
