SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index

Summary: SSCard: suffix-tree-guided FM-index for cardinality estimation in LIKE predicates. Extends FM-index to multiple strings using a pruned suffix tree with pushup compression for tight short bounds; spline interpolation with error guarantees, plus bidirectional and incremental updates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h0377a45bed7de40a
Venue: SIGMOD
Year: 2026
Pagerank: 5.0322912e-05
Overall Rank: 10,329 | 30.58%
DOI: 10.1145/3749183

Incoming Non-self Citations Over Time

Authors

1. Yirui Zhan (Peking University)
2. Wen Nie (Huawei Technologies Co. Ltd.)
3. Jun Gao (Peking University)

BibTeX Citation

@inproceedings{zhan_sigmod26,
        title = {{SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index}},
        author = {Zhan, Yirui and Nie, Wen and Gao, Jun},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3749183},
        url = {https://dl.acm.org/doi/10.1145/3749183},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,703	Practical Parameterized Query Optimization via Efficient Plan Reuse and List-wise Ranking	2026	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061067652
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046363107
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036476265
85	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035876108
318	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021166957
361	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00020000855
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019822444
458	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017880664
768	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014107655
1,058	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012224038
1,163	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.0001174542
1,462	Substring Selectivity Estimation	1999	PODS	0.00010578962
2,217	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	8.8151982e-05
2,969	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.7993378e-05
3,361	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	7.3726415e-05
3,479	LOGER: A Learned Optimizer towards Generating Efficient and Robust Query Execution Plans	2023	VLDB	7.2665349e-05
3,563	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.2023194e-05
3,742	FACE: A Normalizing Flow based Cardinality Estimator	2022	VLDB	7.0564546e-05
5,129	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	6.2582129e-05
6,889	LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries	2024	SIGMOD	5.6536655e-05
7,420	Cardinality Estimation of Approximate Substring Queries using Deep Learning	2022	VLDB	5.5301786e-05
10,057	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB	5.0863889e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,518	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB
2	1,065	Are We Ready For Learned Cardinality Estimation?	2021	VLDB
3	1,462	Substring Selectivity Estimation	1999	PODS
4	1,163	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD
5	9,381	Efficient and Effective Cardinality Estimation for Skyline Family	2023	SIGMOD
6	9,154	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD
7	462	An End-to-End Learning-based Cost Estimator	2020	VLDB
8	10,032	Cardinality Estimation of LIKE Predicate Queries using Deep Learning	2025	SIGMOD
9	6,955	Space-efficient Substring Occurrence Estimation	2011	PODS
10	7,420	Cardinality Estimation of Approximate Substring Queries using Deep Learning	2022	VLDB