PAIL: Efficient kNN Search on Set-Valued Attributes

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.