Pith. sign in

REVIEW 4 major objections 5 minor 51 references

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

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read SSCard proposes a substring cardinality estimator built from a pruned suffix tree and a learned FM-index, claiming bounded worst-case error of $2\epsilon|P|$ and better q-error, construction time, and space than existing methods on five…

desk verdict Clever multi-string FM-index with pruned suffix tree and spline compression, but the error bound counts occurrences, not distinct strings, so the central guarantee overreaches. read the letter →

arxiv 2505.24312 v1 pith:NBZ57DM3 submitted 2025-05-30 cs.DB

Yirui Zhan , Wen Nie , Jun Gao This is my paper
classification cs.DB
keywords substringcardinalityestimationFM-indexBurrows-WheelertransformprunedsuffixtreelearnedindexsplineinterpolationLIKEpredicateq-error
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes SSCard, a way to estimate how many rows of a text column contain a given substring, which is the quantity behind SQL LIKE predicates. The method extends the FM-index to a collection of strings, organizes the index with a pruned suffix tree of limited height, and replaces the FM-index's rank tables with spline functions trained to a maximum error. Short patterns are answered exactly from counts stored on tree nodes, while longer patterns are searched backward through the learned FM-index. The paper reports that on five real datasets SSCard lowers average q-error by about 20%, maximum q-error by 80%, and construction time by 50% relative to the second-best methods, with a worst-case absolute error of $2\epsilon|P|$. The contribution matters because substring predicates are common and existing estimators either assume independence for long patterns or provide no error bound.

What carries the argument

The central object is a pruned suffix tree-guided learned FM-index: a Burrows-Wheeler-transform index whose rank computations are carried by error-bounded spline functions, organized by a height-limited suffix tree whose nodes carry exact prefix cardinalities. The load-bearing identity is the BWT property that the $i$-th occurrence of a character in the $L$-array lines up with the $i$-th occurrence in the $F$-array; the paper's enhanced comparator restores this property for variable-length strings. The pushup operation consolidates rare characters' $L$-triples at higher tree nodes, and each learned function $\mathit{rank}_f(c,i)$ approximates the cumulative occurrence count. Greedy spline interpolation keeps each approximation within $\epsilon$, so a backward search of length $|P|$ has worst-case absolute error $2\epsilon|P|$.

What would settle it

Build a dataset of $N$ rows, each equal to some fixed pattern $P$ repeated $M$ times, and query $P$ where $|P|$ exceeds the suffix tree height. SSCard's backward search counts occurrences, so its estimate will be close to $N\cdot M$ instead of the true cardinality $N$, producing q-error near $M$ and breaking the claimed error regime.

Watch

Extended reading notes

Core claim

The central claim is that a learned FM-index, reorganized around a pruned suffix tree, can be a compact and error-bounded estimator of substring cardinality. To make the FM-index work on multiple strings, the paper defines an enhanced comparator using a first rotation-based lexicographic order for prefix cases, which restores the BWT ordering property that the standard FM-index counting argument relies on. A suffix tree of height $h$ annotates each node with the exact number of data strings that contain the path label, so patterns up to length $h$ are estimated exactly. The paper uses a pushup operation to move rare $L$-triples to higher-level nodes and fits each bucket of $L$-triples with greedy spline interpolation under error bound $\epsilon$; estimation then starts from the longest suffix that is present in the tree and finishes the pattern by backward search. Experiments on five datasets are reported as showing better q-error, smaller index size, and shorter construction time than traditional and learned baselines.

Load-bearing premise

The method counts every occurrence of a pattern inside a row, but the cardinality it promises is the number of distinct rows containing the pattern, so for patterns longer than the tree height it must assume repeated occurrences within a single row are rare enough to ignore, and no bound is proved for that case.

Editorial extensions

If this is right

  • Patterns no longer than the tree height are answered exactly from node annotations, removing the largest source of error for short strings.
  • Setting $\epsilon$ gives a tunable worst-case error of $2\epsilon|P|$, letting a deployment trade space for accuracy predictably.
  • Construction needs only one pass over the suffix tree to fit splines, so SSCard reports preprocessing in minutes rather than hours on the smaller datasets, without GPU training.
  • The pushup operation cuts space sharply on large-alphabet, skewed data, with the WIKI index reported at about 23 MB versus 89–365 MB for baselines.
  • The multiple-SSCard update strategy, borrowed from LSM-tree design, makes insertion time stay nearly constant as data grows, at a small cost in q-error and query time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extension: the $2\epsilon|P|$ bound applies to the FM-index occurrence count, not to the distinct-string cardinality; on workloads where the same long pattern recurs many times inside individual rows, reported q-error improvements could degrade until a deduplication mechanism is added.
  • Extension: fixing the tree height at 3 leaves a gap that adaptive height selection could close; choosing $h$ from pattern-length and repeat-frequency statistics would trade a little space to shrink the region where duplicates are assumed rare.
  • Extension: the enhanced multi-string BWT comparator is a transferable primitive that could support row-level compressed indexing for other database operations, such as wildcard predicates or string join selectivity.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper presents SSCard, an index-based estimator for the cardinality of SQL LIKE (substring) predicates, defined as the number of distinct strings containing the pattern. SSCard merges the cyclic shifts of all data strings into an extended BWT using a proposed enhanced comparator, organizes the resulting rows into a pruned suffix tree of height h, groups L-triples into segments, applies a pushup operation that moves rare characters toward the root, and represents each segment's rank function with error-bounded spline interpolation. Estimation is bidirectional: a suffix of the query already present in the pruned suffix tree provides a starting interval, and backward search over the FM-index extends it to the full pattern. The paper claims a worst-case absolute error of at most 2ε|P|, controls the q-error similarly, and reports O(nm/c_m) space and O(h·|P|) query time, with experiments on five real datasets showing state-of-the-art q-error, construction time, and size, plus incremental updates and a Postgres end-to-end study.

Significance. If the claims hold, SSCard addresses a real gap: substring cardinality estimation for database optimizers, where prior learned methods offer no error guarantees. The error-bounded spline representation for BWT rank, the pruned-suffix-tree organization with pushup, and the multi-string BWT extension are transferable ideas, and the space results (e.g., the 91% reduction from pushup on WIKI in Table 8 and the roughly 3-5x size advantage over the sdsl FM-index in Table 6) are concrete evidence of practical value. The paper ships source code, evaluates on five datasets plus the JOB end-to-end workload, and includes ablations over ε, h, pushup, and update strategies, which make the empirical core reproducible and credible. However, the headline formal claim, a worst-case error bound against the defined distinct-string cardinality, is not supported by the algorithm as described; the theoretical contribution therefore requires re-scoping or additional machinery before the paper's claims can be accepted as stated.

major comments (4)
  1. [§5.3, §2.2, Algorithm 4, §8] The paper defines cardinality as the number of distinct strings containing the pattern (§2.2), but Algorithm 4 returns end-start+1 after a backward search over the merged cyclic shifts, which counts the total occurrences of P across all rows. Each occurrence of P inside a string yields a separate row, and the L-triples carry no string ID (§8 explicitly defers adding string IDs to future work), so the estimator cannot deduplicate within a string. Section 5.3's error analysis therefore bounds only the spline error of an occurrence count: the claimed worst-case absolute error 2ε|P| and the q-error bound 1+2ε|P| used in §6.2 are not bounds relative to the defined cardinality. The unmodeled multiplicity can inflate the estimate by the number of occurrences per string; the paper acknowledges this issue but gives no bound for patterns longer than h=3. Since the experimental query workloads contain only patterns of length at most 8, the good q-error results are consistent with small empirical multiplicity but do not validate the stated worst-case claim.
  2. [Algorithm 4, §5.1] Even for patterns shorter than the tree height h, the pseudocode returns the interval size end-start+1 rather than the annotated distinct count cnt: for |P| ≤ h the loop condition k-1 ≥ 2 is false, and the returned value equals the number of rows with the pattern as a prefix (e.g., node 7 in Figure 3 has interval size 5 but cnt=3). The prose in §5.1 promises that the suffix tree records the cardinalities of strings with lengths smaller than h and that cnt alleviates the multiple-occurrence problem, but Algorithm 4 never reads cnt. Either the algorithm is missing a branch that returns cnt when the whole pattern is matched in the tree, or the short-pattern exactness claim is not implemented; the manuscript as written is internally inconsistent on this point.
  3. [§3.1] The extension of the BWT to multiple strings rests on the claim that the enhanced comparator, standard lexicographic order plus first rotation-based lexicographic order for prefix cases, preserves Property 2. The support is a case analysis with a few examples rather than a proof: the text does not establish that the comparator is transitive (required for the radix sort in Algorithm 1 to produce a well-defined order), that the recursive tie-breaking in case (2) is well-founded, or that the pairwise order is consistent globally across all rows and characters. Because the entire SSCard structure and its backward search depend on Property 2, this needs a rigorous proof or a citation to an existing one.
  4. [Abstract, §6.2, Table 3] The abstract's headline claim of an average reduction of 20% in the average q-error is not supported by Table 3: computing (second-best avg minus SSCard avg) per dataset gives approximately 9% on DBLP-AN, 7% on IMDB-AN, 6% on IMDB-MT, 2% on TPCH-PN, and 19% on WIKI, a mean of roughly 8.5%. Similarly, the 50% lower construction time claim varies by dataset in Table 4 (about 15% lower than MO on DBLP-AN but 73% lower on IMDB-MT), and the phrase 'compared with second-best approaches' is ambiguous about whether the comparison is per dataset or pooled. Please reconcile the abstract with the reported numbers.
minor comments (5)
  1. [§6.2] The displayed derivation '1 + 2ε|P|/(y-2ε|P|) ≤ 1 + 2ε|P|' requires y ≥ 2ε|P|+1; the paper does not justify the inequality for smaller y, where a separate argument using the clamping of estimates to at least 1 would be needed.
  2. [Table 6] The WIKI row reports no FM-index query time, and the description 'encode the WIKI dataset as single-bit characters' is too vague to judge whether the comparison uses the same data; please specify the encoding and clarify why the sdsl FM-index could not be run on the original WIKI strings.
  3. [§6.1] Ground-truth cardinalities are generated from the summary structure of [43]; for TPCH-PN, which has only 92 unique words and 1,128 patterns, exact cardinalities are trivially computable and should be used, and the paper should state whether reported q-errors are measured against exact or approximate cardinalities.
  4. [§5.2] The incremental deletion path is described as symmetric to insertion ('building a new pruned suffix tree T_d'), but the interaction between T_i and T_d for patterns present in both inserted and deleted strings is not specified, and Figure 10 evaluates only insertions, so the deletion strategy is unvalidated.
  5. [General] The running head 'SIGMOD, Trovato et al.' and the contribution list ordering (i, iii, ii) should be fixed, and there are several typos ('for a a pattern', 'WlKl', 'competitior', 'budeget'); additionally, the pushup arrows and gray triples in Figure 4 are hard to read in print.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the worst-case error bound follows from the spline construction, and the occurrence-vs-cardinality gap is an acknowledged correctness issue rather than a circular derivation.

full rationale

SSCard's central derivation chain is not circular. The main analytic result (Section 5.3) is that each backward step using a spline rank function with per-fit error bound epsilon contributes at most 2*epsilon to the interval endpoints, so the cumulative absolute error is at most 2*epsilon*|P|; this is a direct consequence of the stated spline construction and the triangle inequality, not a fitted parameter being reused as a prediction. The q-error bound discussed in Section 6.2 is a routine translation of that per-step error bound, with its magnitude dominated by the user-supplied epsilon and pattern length. The suffix-tree node cnt values provide exact cardinalities for patterns of length at most h, and the bidirectional algorithm combines those with FM-index backward search; neither component is defined in terms of the other's output. There are no load-bearing self-citations: the only references with overlapping authors ([7] and [49]) concern a learned optimizer and query scheduling in related-work context, not the estimation claim. The paper's own Section 5.3 explicitly identifies the multiple-occurrence issue, noting that FM-index backward search returns occurrences rather than distinct-string counts and that it is 'serious when the length of a pattern is limited but can be significantly alleviated with cnt annotated to the suffix tree nodes'; Section 8 then lists extending L-triples with string IDs as future work. This is an acknowledged correctness and scope gap in the error-bound theorem, not a circular step. Hyperparameters (h=3, c_m=10, l=5000, epsilon=32) are tuned in experiments and could raise external-validity concerns, but estimating q-error on the test set after tuning is not a derivation in which the output is equivalent to the input. The empirical comparison is comparative and self-contained against external baselines, so no circularity score above 0 is warranted.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central claim rests on hand-chosen hyperparameters (h, l, c_m, epsilon), an unproven multi-string BWT comparator property, and the unquantified assumption that occurrence counts approximate distinct-string cardinality for long patterns. No new physical or conceptual entities beyond data structures are introduced.

free parameters (4)
  • epsilon (spline error bound) = 32
    Set to 32 for all datasets in Section 6.1; the ablation in Figure 8 studies values 4-64, so the final value is chosen on the same datasets used for evaluation.
  • h (pruned suffix tree height) = 3
    Height of the pruned suffix tree; Section 6.3 Figure 9 shows it is selected as a trade-off point using the evaluation datasets.
  • l (segment size) = 5000
    Minimum segment size constraint in suffix tree construction (Section 4.1, Section 6.1), chosen by hand.
  • c_m (minimum same-character L-triples per segment) = 10
    Threshold for the pushup operation (Section 4.2, Section 6.1), chosen by hand.
assumptions (4)
  • ad hoc to paper The enhanced comparator preserves BWT Property 2 for the merged cyclic shifts of multiple variable-length strings.
    Stated in Section 3.1 with a three-case argument; no formal proof is provided, and the correctness of all FM-index operations depends on it.
  • domain assumption Spline interpolation with maximum error epsilon can represent each bucket's rank function.
    Adopted from learned-index literature (RadixSpline, PGM); the paper does not prove that rank data from text is always spline-approximable within epsilon, but treats it as the method's design contract.
  • ad hoc to paper For patterns longer than the tree height h, the number of rows containing a pattern is well approximated by the number of suffix occurrences of the pattern in the extended BWT.
    The target cardinality counts distinct strings but the FM-index counts occurrences; Section 5.3 acknowledges the issue and hand-waves it as alleviated, but gives no bound. This is load-bearing for the error-bound claim.
  • domain assumption Ground-truth cardinalities generated by the summary data structure of Astrid [43] are correct for the target metric.
    Section 6.1 says actual cardinalities are generated using the same summary data structure as [43], which is assumed to match the distinct-string semantics the paper defines.

how reviews work

0 comments
Cite this review

Pith. "Pith review of SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index." pith.science (2026). https://pith.science/paper/NBZ57DM3

@misc{pith2026250524312,
  author       = {Pith},
  title        = {Pith review of: SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NBZ57DM3}},
  note         = {Machine review of arXiv:2505.24312}
}
read the original abstract

Accurate cardinality estimation of substring queries, which are commonly expressed using the SQL LIKE predicate, is crucial for query optimization in database systems. While both rule-based methods and machine learning-based methods have been developed to optimize various aspects of cardinality estimation, their absence of error bounds may result in substantial estimation errors, leading to suboptimal execution plans. In this paper, we propose SSCard, a novel SubString Cardinality estimator that leverages a space-efficient FM-Index into flexible database applications. SSCard first extends the FM-Index to support multiple strings naturally, and then organizes the FM-index using a pruned suffix tree. The suffix tree structure enables precise cardinality estimation for short patterns and achieves high compression via a pushup operation, especially on a large alphabet with skewed character distributions. Furthermore, SSCard incorporates a spline interpolation method with an error bound to balance space usage and estimation accuracy. Additional innovations include a bidirectional estimation algorithm and incremental update strategies. Extensive experimental results in five real-life datasets show that SSCard outperforms both traditional methods and recent learning-based methods, which achieves an average reduction of 20% in the average q-error, 80% in the maximum q-error, and 50% in the construction time, compared with second-best approaches.

Figures

Figures reproduced from arXiv: 2505.24312 by the authors.

Figure 1
Figure 1. Burrows-Wheeler Transform. The output of BWT are the 𝐹 and 𝐿-array, which are extracted from the first and last columns of M. Operations on the BWT do not rely on the middle parts (gray area in [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Extension of the BWT to multiple strings. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. An illustration of SSCard with ℎ=2 and 𝑐𝑚 = 2 (The meanings of the symbols are in [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: An illustration of pushup with ℎ = 2,𝑙 = 5 and 𝑐𝑚 = 2. The 𝐿-triples in node 6 are pushed up to node 4 as their occurrences are smaller than 𝑐𝑚. Similar cases apply to the other 𝐿-triples shown in gray. and the length to implicitly represent the cyclic shifts in the sp…
Figure 5
Figure 5. Figure 5: Cardinaltity estimation using SSCard Before giving the full method in the cardinality deestimation, we first detail the 𝑅𝑎𝑛𝑘 (𝑐,𝑖) used in SSCard in Algorithm 3. Given the 𝑖-th index and a character 𝑐, the major step is to locate the seg￾ment that stores its learned fu…
Figure 6
Figure 6. Figure 6: Q-error of estimators varying pattern lengths [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Q-error of estimators varying actual result cardinality [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]
Figure 8
Figure 8. Figure 8: Improvement of spline interpolation [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: Study of the effect of the Suffix tree height [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]
Figure 10
Figure 10. Figure 10: Incremental update (DBLP-AN) of nodes in the pruned suffix tree 𝑇𝑖 exceeds 2.5 × 105 , we either rebuild the existing SSCard or create a new one, depending on the update strategy. As shown in [PITH_FULL_IMAGE:figures/full_fig_p012_10.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

51 extracted references · 44 canonical work pages

  1. [1]

    Mehmet Aytimur and Ali Cakmak. 2018. Estimating the selectivity of LIKE queries using pattern-based histograms.Turkish Journal of Electrical Engineering and Computer Sciences26, 6 (2018), 3319–3334

    work page 2018

  2. [2]

    Mehmet Aytimur and Ali Cakmak. 2021. Using positional sequence patterns to estimate the selectivity of SQL LIKE queries.Expert Systems with Applications 165 (2021), 113762

    work page 2021

  3. [3]

    Mehmet Aytimur, Silvan Reiner, Leonard Wörteler, Theodoros Chondrogiannis, and Michael Grossniklaus. 2024. LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries.Proceedings of the ACM on Management of Data2, 1 (2024), 1–25

    work page 2024

  4. [4]

    Nicolas Bruno and Surajit Chaudhuri. 2004. Conditional selectivity for statistics on query expressions. InProceedings of the 2004 ACM SIGMOD international conference on Management of data. 311–322

    work page 2004

  5. [5]

    Nicolas Bruno, Surajit Chaudhuri, and Luis Gravano. 2001. STHoles: A multidi- mensional workload-aware histogram. InProceedings of the 2001 ACM SIGMOD international conference on Management of data. 211–222

    work page 2001

  6. [6]

    Michael Burrows. 1994. A block-sorting lossless data compression algorithm. SRS Research Report124 (1994)

    work page 1994

  7. [7]

    Tianyi Chen, Jun Gao, Hedui Chen, and Yaofeng Tu. 2023. Loger: A learned opti- mizer towards generating efficient and robust query execution plans.Proceedings of the VLDB Endowment16, 7 (2023), 1777–1789

    work page 2023

  8. [8]

    Arghya Kusum Das, M Oguzhan Kulekci, and Sharma V Thankachan. 2022. Memory–Efficient FM-Index Construction for Reference Genomes. In2022 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). IEEE, 736– 739

    work page 2022

Show all 51 references
  1. [9]

    Arthur L Delcher, Simon Kasif, Robert D Fleischmann, Jeremy Peterson, Owen White, and Steven L Salzberg. 1999. Alignment of whole genomes.Nucleic acids research27, 11 (1999), 2369–2376

    1999

  2. [10]

    Arthur L Delcher, Adam Phillippy, Jane Carlton, and Steven L Salzberg. 2002. Fast algorithms for large-scale genome alignment and comparison.Nucleic acids research30, 11 (2002), 2478–2483

    2002

  3. [11]

    Paolo Ferragina and Giovanni Manzini. 2000. Opportunistic data structures with applications. InProceedings 41st annual symposium on foundations of computer science. IEEE, 390–398

    2000

  4. [12]

    Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, and Gonzalo Navarro. 2004. An alphabet-friendly FM-index. InInternational Symposium on String Processing and Information Retrieval. Springer, 150–160

    2004

  5. [13]

    Paolo Ferragina and Giorgio Vinciguerra. 2020. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds.Proceedings of the VLDB Endowment13, 8 (2020), 1162–1175

    2020

  6. [14]

    Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. 2019. Fiting-tree: A data-aware index structure. InProceedings of the 2019 International Conference on Management of Data. 1189–1206

    2019

  7. [15]

    Simon Gog, Alistair Moffat, and Matthias Petri. 2017. CSA++: fast pattern search for large alphabets. In2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 73–82

    2017

  8. [16]

    Surajit Chaudhuri Venkatesh Ganti Luis Gravano. [n. d.]. Selectivity Estimation for String Predicates: Overcoming the Underestimation Problem. ([n. d.])

  9. [17]

    Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. 2003. High-order entropy- compressed text indexes. (2003)

    2003

  10. [18]

    D Gusfield. 1997. Algorithms on strings, trees, and sequences Cambridge Univer- sity Press.Cambridge, England(1997)

    1997

  11. [19]

    Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, and Carsten Binnig. 2019. Deepdb: Learn from data, not from queries! arXiv preprint arXiv:1909.00607(2019)

    2019 arXiv

  12. [20]

    Darryl Ho, Jialin Ding, Sanchit Misra, Nesime Tatbul, Vikram Nathan, Vasimuddin Md, and Tim Kraska. 2019. LISA: towards learned DNA sequence search.arXiv preprint arXiv:1910.04728(2019)

    2019 arXiv

  13. [21]

    HV Jagadish, Raymond T Ng, and Divesh Srivastava. 1999. Substring selectiv- ity estimation. InProceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 249–260

    1999

  14. [22]

    Juha Kärkkäinen and Esko Ukkonen. 1996. Lempel-Ziv parsing and sublinear-size index structures for string matching. InProc. 3rd South American Workshop on String Processing (WSP). 141–155

    1996

  15. [23]

    Martin Kiefer, Max Heimel, Sebastian Breß, and Volker Markl. 2017. Estimating join selectivities using bandwidth-optimized kernel density models.Proceedings of the VLDB Endowment10, 13 (2017), 2085–2096

    2017

  16. [24]

    Andreas Kipf, Michael Freitag, Dimitri Vorona, Peter Boncz, Thomas Neumann, and Alfons Kemper. 2019. Estimating filtered group-by queries is hard: Deep learning to the rescue. In1st International Workshop on Applied AI for Database Systems and Applications

    2019

  17. [25]

    Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2018. Learned cardinalities: Estimating correlated joins with deep learning.arXiv preprint arXiv:1809.00677(2018)

    2018 arXiv

  18. [26]

    Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2020. RadixSpline: a single-pass learned index. InProceedings of the third international workshop on exploiting artificial intelligence techniques for data management. 1–5

    2020

  19. [27]

    Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2020. RadixSpline: a single-pass learned index. InProceedings of aiDM@SIGMOD 2020. 5:1–5:5

    2020

  20. [28]

    Chi, Jeffrey Dean, and Neoklis Polyzotis

    Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The Case for Learned Index Structures. InProceedings of the 2018 SIGMOD. 489–504

    2018

  21. [29]

    Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The case for learned index structures. InProceedings of the 2018 international conference on management of data. 489–504

    2018

  22. [30]

    P Krishnan, Jeffrey Scott Vitter, and Bala Iyer. 1996. Estimating alphanumeric selectivity in the presence of wildcards. InProceedings of the 1996 ACM SIGMOD international conference on Management of data. 282–293

    1996

  23. [31]

    Suyong Kwon, Woohwan Jung, and Kyuseok Shim. 2022. Cardinality estimation of approximate substring queries using deep learning.Proceedings of the VLDB Endowment15, 11 (2022), 3145–3157

    2022

  24. [32]

    Hongrae Lee, Raymond T Ng, and Kyuseok Shim. 2007. Extending q-grams to estimate selectivity of string matching with low edit distance. InProceedings of the 33rd international conference on Very large data bases. Citeseer, 195–206

    2007

  25. [33]

    Hongrae Lee, Raymond T Ng, and Kyuseok Shim. 2009. Approximate substring selectivity estimation. InProceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. 827–838

    2009

  26. [34]

    Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How good are query optimizers, really? (11 2015), 204–215

    2015

  27. [35]

    Heng Li. 2014. Fast construction of FM-index for long sequence reads.Bioinfor- matics30, 22 (2014), 3274–3275

    2014

  28. [36]

    Richard J Lipton, Jeffrey F Naughton, and Donovan A Schneider. 1990. Practical selectivity estimation through adaptive sampling. InProceedings of the 1990 ACM SIGMOD international conference on Management of data. 1–11

    1990

  29. [37]

    Grigorios Loukides and Solon P. Pissis. 2021. Bidirectional String Anchors: A New String Sampling Mechanism(LIPIcs, Vol. 204). 64:1–64:21

    2021

  30. [38]

    Grigorios Loukides, Solon P Pissis, et al. 2023. Text indexing for long patterns: Anchors are all you need. InVLDB 2023-49th International Conference on Very Large Data Bases, Vol. 16. 2117–2131

    2023

  31. [39]

    Chen Luo and Michael J Carey. 2020. LSM-based storage techniques: a survey. The VLDB Journal29, 1 (2020), 393–418

    2020

  32. [40]

    Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Al- izadeh, and Tim Kraska. 2021. Bao: Making learned query optimization practical. InProceedings of the 2021 International Conference on Management of Data. 1275– 1288

    2021

  33. [41]

    Thomas Neumann and Sebastian Michel. 2008. Smooth interpolating histograms with error guarantees. InBritish National Conference on Databases. Springer, 126–138

    2008

  34. [42]

    Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. 1996. The log-structured merge-tree (LSM-tree).Acta Informatica33 (1996), 351–385

    1996

  35. [43]

    Suraj Shetiya, Saravanan Thirumuruganathan, Nick Koudas, and Gautam Das

  36. [44]

    Jared T Simpson and Richard Durbin. 2010. Efficient construction of an assembly string graph using the FM-index.Bioinformatics26, 12 (2010), i367–i373

    2010

  37. [45]

    Kostas Tzoumas, Amol Deshpande, and Christian S Jensen. 2011. Lightweight graphical models for selectivity estimation without independence assumptions. Proceedings of the VLDB Endowment4, 11 (2011), 852–863

    2011

  38. [46]

    Esko Ukkonen. 1995. On-line construction of suffix trees.Algorithmica14, 3 (1995), 249–260

    1995

  39. [47]

    Jiayi Wang, Chengliang Chai, Jiabin Liu, and Guoliang Li. 2021. FACE: A normal- izing flow based cardinality estimator.Proceedings of the VLDB Endowment15, 1 (2021), 72–84

    2021

  40. [48]

    Yaoshu Wang, Chuan Xiao, Jianbin Qin, Xin Cao, Yifang Sun, Wei Wang, and Makoto Onizuka. 2020. Monotonic cardinality estimation of similarity selection: A deep learning approach. InProceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 1197–1212. SS...

    2020

  41. [49]

    Chenhao Xu, Chunyu Chen, Jinglin Peng, Jiannan Wang, and Jun Gao. 2025. BQSched: A Non-intrusive Scheduler for Batch Concurrent Queries via Rein- forcement Learning. arXiv:2504.19142 [cs.DB] https://arxiv.org/abs/2504.19142

    2025 arXiv

  42. [50]

    Yuan Yao, Deming Ye, Peng Li, Xu Han, Yankai Lin, Zhenghao Liu, Zhiyuan Liu, Lixin Huang, Jie Zhou, and Maosong Sun. 2019. DocRED: A large-scale document- level relation extraction dataset.arXiv preprint arXiv:1906.06127(2019). Received 20 February 2007; revised 12 March 2009;...

    2019 arXiv

  43. [2020]

    Astrid: accurate selectivity estimation for string predicates using deep learning.Proceedings of the VLDB Endowment14, 4 (2020)

    2020

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.