SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index
Yirui Zhan, Wen Nie, Jun Gao · 2025
Read SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index by Yirui Zhan, Wen Nie, Jun Gao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-24312.txt.
Description
Databases answer questions like 'names containing park' millions of times, and guessing how many rows match steers the whole query plan. Bad guesses mean slow plans, and most estimators give no error bound. Yirui Zhan, Wen Nie, and Jun Gao present SSCard in 2025, an estimator built on a compressed text index. A pruned suffix tree organizes the index, giving exact counts for short patterns and squeezing large alphabets hard. A spline fit with a stated error bound covers the rest.
The estimator also works from both ends of a pattern and updates as data changes. On five real datasets it cuts average error by a fifth and worst-case error by four fifths against the runner-up. Build time halves as well.
Catalog record
| CREATOR | Yirui Zhan, Wen Nie, Jun Gao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-24312