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.0156513e-05
Overall Rank: 10,355 | 30.59%
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,764	Practical Parameterized Query Optimization via Efficient Plan Reuse and List-wise Ranking	2026	SIGMOD	4.9605343e-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.00061463175
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046249672
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036394222
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035920657
320	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021128745
355	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00020146245
372	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019768921
461	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017835351
774	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014063511
1,061	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012207625
1,164	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.0001170903
1,466	Substring Selectivity Estimation	1999	PODS	0.00010546176
2,228	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	8.7912743e-05
2,981	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.7739779e-05
3,371	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	7.3493132e-05
3,481	LOGER: A Learned Optimizer towards Generating Efficient and Robust Query Execution Plans	2023	VLDB	7.2463722e-05
3,555	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.1877332e-05
3,740	FACE: A Normalizing Flow based Cardinality Estimator	2022	VLDB	7.0398782e-05
5,153	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	6.2375324e-05
6,906	LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries	2024	SIGMOD	5.634971e-05
7,440	Cardinality Estimation of Approximate Substring Queries using Deep Learning	2022	VLDB	5.5118924e-05
10,088	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB	5.0695702e-05

Semantically Similar Papers

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