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.115551e-05
Overall Rank: 9,778 | 34.46%
DOI: 10.14778/3476249.3476263
PDF: Download (CC BY-NC-ND 4.0)

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,929	Pail: Efficient kNN Search on Set-Valued Attributes	2026	VLDB	4.9605343e-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.0019892478
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046249672
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027077763
427	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018429918
774	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014063511
870	Learning Multi-dimensional Indexes	2020	SIGMOD	0.0001332034
966	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012777679
987	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012643645
1,424	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010694144
1,445	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010607118
2,362	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.5601252e-05
2,514	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB	8.3446573e-05
2,581	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB	8.2491224e-05
2,741	Speculative Distributed CSV Data Parsing for Big Data Analytics	2019	SIGMOD	8.0574455e-05
2,752	Uni-Detect: A Unified Approach to Automated Error Detection in Tables	2019	SIGMOD	8.0387193e-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
3,715	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0549546e-05
4,186	Data Integration and Machine Learning: A Natural Synergy	2018	SIGMOD	6.7408641e-05
5,632	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.0402517e-05
6,888	Analysis of Indexing Structures for Immutable Data	2020	SIGMOD	5.6394555e-05
8,516	Tree-Encoded Bitmaps	2020	SIGMOD	5.3110731e-05
12,199	Top-k Queries over Digital Traces	2019	SIGMOD	4.9605343e-05

Semantically Similar Papers

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