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: 7530
Venue: SIGMOD
Year: 2026
Pagerank: 5.1502319e-05
Overall Rank: 10,097 | 30.73%
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,508	Practical Parameterized Query Optimization via Efficient Plan Reuse and List-wise Ranking	2026	SIGMOD	5.093636e-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
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
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
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
378	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00019638121
477	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017851226
790	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.0001401445
1,071	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012322342
1,140	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.0001200574
1,427	Substring Selectivity Estimation	1999	PODS	0.00010812749
2,203	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	8.9610447e-05
2,899	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.97814e-05
3,309	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	7.5368417e-05
3,516	LOGER: A Learned Optimizer towards Generating Efficient and Robust Query Execution Plans	2023	VLDB	7.3524442e-05
3,545	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.3249967e-05
3,688	FACE: A Normalizing Flow based Cardinality Estimator	2022	VLDB	7.201795e-05
5,011	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	6.4020848e-05
6,760	LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries	2024	SIGMOD	5.7826781e-05
7,268	Cardinality Estimation of Approximate Substring Queries using Deep Learning	2022	VLDB	5.6597123e-05
9,861	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB	5.2055975e-05

Semantically Similar Papers

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