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.9793485e-05
Overall Rank: 10,859 | 27.00%
DOI: 10.14778/3836663.3836686

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.00051312804
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037091678
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.0003305531
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027163517
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025331535
963	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012816649
2,513	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB	8.3679178e-05
2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.8519256e-05
2,944	Spatio-Textual Similarity Joins	2013	VLDB	7.828107e-05
3,350	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	7.3910669e-05
3,596	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1790375e-05
5,444	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1268526e-05
5,912	Dima: A Distributed In-Memory Similarity-Based Query Processing System	2017	VLDB	5.9501002e-05
9,126	Balance-Aware Distributed String Similarity-Based Query Processing System	2019	VLDB	5.22387e-05
9,741	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.1349531e-05
11,339	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.9793485e-05
11,759	A Two-Level Signature Scheme for Stable Set Similarity Joins	2023	VLDB	4.9793485e-05

Semantically Similar Papers

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