Cardinality Estimation of Approximate Substring Queries using Deep Learning

Summary: DL-based cardinality estimation for approximate substring queries, outperforming traditional summaries. Introduces efficient train-data generation with shared computations and a novel learning method for fast, accurate training; experiments show clear gains over baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12984
Venue: VLDB
Year: 2022
Pagerank: 5.6597123e-05
Overall Rank: 7,268 | 50.14%
DOI: 10.14778/3551793.3551859

Incoming Non-self Citations Over Time

Authors

1. Suyong Kwon (Seoul National University)
2. Woohwan Jung (Hanyang University)
3. Kyuseok Shim (Seoul National University)

BibTeX Citation

@article{kwon_vldb22,
        title = {{Cardinality Estimation of Approximate Substring Queries using Deep Learning}},
        author = {Kwon, Suyong and Jung, Woohwan and Shim, Kyuseok},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {11},
        pages = {3145--3157},
        doi = {10.14778/3551793.3551859},
        url = {https://doi.org/10.14778/3551793.3551859},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,760	LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries	2024	SIGMOD	5.7826781e-05
9,520	Experimental Analysis of Large-scale Learnable Vector Storage Compression	2024	VLDB	5.2561283e-05
9,556	CAFE: Towards Compact, Adaptive, and Fast Embedding for Large-scale Recommendation Models	2024	SIGMOD	5.2528121e-05
9,844	Cardinality Estimation of LIKE Predicate Queries using Deep Learning	2025	SIGMOD	5.2094602e-05
10,097	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.1502319e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035838391
323	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021264788
401	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019092557
1,140	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.0001200574
1,427	Substring Selectivity Estimation	1999	PODS	0.00010812749
2,061	Selectivity Estimation For Boolean Queries	2000	PODS	9.2445049e-05
2,899	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.97814e-05
3,446	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	7.4087786e-05
3,545	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.3249967e-05
3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.1663952e-05
5,011	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	6.4020848e-05
5,412	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.2272563e-05
7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	5.5664611e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR
2	5,712	Sample-Efficient Cardinality Estimation Using Geometric Deep Learning	2024	VLDB
3	5,011	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD
4	5,792	Pre-training Summarization Models of Structured Datasets for Cardinality Estimation	2022	VLDB
5	2,543	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD
6	1,573	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD
7	2,723	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB
8	10,097	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD
9	4,617	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD
10	9,844	Cardinality Estimation of LIKE Predicate Queries using Deep Learning	2025	SIGMOD