LES3: Learning-based Exact Set Similarity Search

Summary: LES3 introduces a learning-based exact set similarity search that partitions sets and uses a TGM bitmap index to prune candidates. Analytical partitioning under distributional assumptions informs L2P and PTR, enabling pruning and faster exact search than baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h2978f38bf36d168d
Venue: VLDB
Year: 2021
Pagerank: 5.1349531e-05
Overall Rank: 9,741 | 34.51%
DOI: 10.14778/3476249.3476263

Incoming Non-self Citations Over Time

Authors

1. Yifan Li (York University)
2. Xiaohui Yu (York University)
3. Nick Koudas (University of Toronto)

BibTeX Citation

@article{li_vldb21,
        title = {{LES3: Learning-based Exact Set Similarity Search}},
        author = {Li, Yifan and Yu, Xiaohui and Koudas, Nick},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {11},
        pages = {2073--2086},
        doi = {10.14778/3476249.3476263},
        url = {https://doi.org/10.14778/3476249.3476263},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,859	Pail: Efficient kNN Search on Set-Valued Attributes	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 25 of 25 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.001992968
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046284649
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027163517
430	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018409112
779	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014030069
868	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013354403
963	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012816649
992	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012646771
1,421	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010726757
1,446	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010629222
2,354	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.5896515e-05
2,513	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB	8.3679178e-05
2,577	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB	8.2738285e-05
2,735	Speculative Distributed CSV Data Parsing for Big Data Analytics	2019	SIGMOD	8.0761736e-05
2,748	Uni-Detect: A Unified Approach to Automated Error Detection in Tables	2019	SIGMOD	8.0610697e-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
3,714	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0769061e-05
4,171	Data Integration and Machine Learning: A Natural Synergy	2018	SIGMOD	6.7608137e-05
5,618	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.0630987e-05
6,861	Analysis of Indexing Structures for Immutable Data	2020	SIGMOD	5.6608447e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3296886e-05
12,150	Top-k Queries over Digital Traces	2019	SIGMOD	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,546	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD
2	1,318	LSH Ensemble: Internet-Scale Domain Search	2016	VLDB
3	2,060	Similarity search in the blink of an eye with compressed indices	2023	VLDB
4	2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
5	168	Efficient Exact Set-Similarity Joins	2006	VLDB
6	4,147	Local Similarity Search for Unstructured Text	2016	SIGMOD
7	10,656	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD
8	3,350	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB
9	8,110	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD
10	3,569	A Partition-Based Approach to Structure Similarity Search	2014	VLDB