Pail: Efficient kNN Search on Set-Valued Attributes

Summary: Pail targets kNN search over set-valued attributes, where range-search and top-k join methods suffer from low-selectivity filtering and costly index traversal. It embeds positional filtering in a similarity-bound-ordered index, enabling aggressive pruning and early termination; up to 3 orders of magnitude faster. (summarized by gpt-5.6-luna on Aug 28 2026)

Paper ID: h22a83a2f2d6a85a6
Venue: VLDB
Year: 2026
Pagerank: 4.9605343e-05
Overall Rank: 10,929 | 26.75%
DOI: 10.14778/3836663.3836686
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Daniel Schmitt (University of Salzburg)
2. Thomas Hütter (Software Competence Center Hagenberg)
3. Nikolaus Augsten (University of Salzburg)

BibTeX Citation

@article{schmitt_vldb26,
        title = {{Pail: Efficient kNN Search on Set-Valued Attributes}},
        author = {Schmitt, Daniel and Hütter, Thomas and Augsten, Nikolaus},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {11},
        pages = {3245--3258},
        doi = {10.14778/3836663.3836686},
        url = {https://doi.org/10.14778/3836663.3836686},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051134355
75	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037163157
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00032945275
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027077763
202	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025244506
966	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012777679
2,514	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB	8.3446573e-05
2,933	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.827041e-05
2,957	Spatio-Textual Similarity Joins	2013	VLDB	7.799694e-05
3,359	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	7.3640394e-05
3,604	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1548073e-05
5,467	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1037173e-05
5,923	Dima: A Distributed In-Memory Similarity-Based Query Processing System	2017	VLDB	5.9283659e-05
9,158	Balance-Aware Distributed String Similarity-Based Query Processing System	2019	VLDB	5.2041319e-05
9,778	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.115551e-05
11,400	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.9605343e-05
11,809	A Two-Level Signature Scheme for Stable Set Similarity Joins	2023	VLDB	4.9605343e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,623	Similarity Search: A Matching Based Approach	2006	VLDB
2	7,035	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD
3	6,475	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
4	901	PASE: PostgreSQL Ultra-High-Dimensional Approximate Nearest Neighbor Search Extension	2020	SIGMOD
5	8,135	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD
6	3,784	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
7	828	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD
8	3,330	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
9	10,332	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
10	12,803	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB