{"id":"108b1b37-41e1-4033-919b-0197283146f7","arxiv_id":"2505.24312","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"SSCard estimates substring cardinality using a pruned suffix tree over an FM-index, with learned spline rank functions and an error bound, achieving lower q-error and smaller space than prior methods on five datasets.","lead":"SSCard is a new estimator for the number of database rows that match a SQL substring (LIKE) query. It combines a compressed FM-index with a pruned suffix tree and error-bounded spline functions to give fast, space-efficient estimates that beat existing learned and rule-based methods on five real datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"FM-index path counts total occurrences, not distinct strings; the 2ε|P| error bound ignores this, so the central accuracy guarantee is unsupported for patterns longer than h=3.","rationale":"The reader's weakest assumption and my concern coincide. I considered whether the unproven enhanced comparator (Section 3.1) is the more fundamental issue, but even if the comparator is correct, the FM-index path still returns an occurrence count, not a distinct-string count. The paper itself acknowledges the missing deduplication in Section 5.3 and in the future-work sentence that L-triples would need string IDs. Since most queries in Table 2 have length 6-8 and h=3, the exact cnt values on suffix-tree nodes cover only a minority of the workload; the backward-search path is the main estimation route for the rest. Thus the claimed worst-case error bound and the q-error bound derived from it do not apply to the quantity the paper sets out to estimate. The concrete synthetic test would settle whether this is merely a theoretical caveat or a measurable failure. I keep the reader's CONDITIONAL verdict: the issue is identifiable and potentially addressable (e.g., add a per-string multiplicity bound, store string IDs, or restrict error-bound claims to occurrence counts), but it must be resolved before the accuracy guarantees are accepted.","tokens_in":23979,"tokens_out":9944,"duration_ms":129926,"concrete_test":"Use the released code to build SSCard with h=3, ε=32 on a synthetic set of 1,000 identical strings, each equal to 'abc' repeated 10 times (length 30). Query P='abcabc' (length 6>h). The true distinct cardinality is 1, while total occurrences of P across the set is 9,000. If SSCard returns roughly 9,000, the resulting q-error (≈9,000) far exceeds the claimed bound 1+2ε|P|=385, confirming that the FM-index path counts occurrences. If it returns roughly 1, then an undocumented deduplication mechanism exists and should be specified in the paper.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5.3 splits the estimation error into two sources and only bounds the second (spline rank error), explicitly stating that the multiple-occurrence issue is 'serious when the length of a pattern is limited but can be significantly alleviated with cnt annotated to the suffix tree nodes.' That alleviation covers only patterns of length at most h=3. For longer patterns, Algorithm 4 returns end-start+1 from an FM-index backward search over cyclic shifts of all data strings, so every occurrence of P inside a string contributes a separate row. The L-triples store (L[i], i, r) with no string ID (the Conclusion lists extending L-triples with string IDs as future work), so the search cannot deduplicate multiple occurrences within one string. Consequently SSCard estimates total occurrences, not the distinct-string cardinality defined in Section 2.2. The claimed worst-case absolute error 2ε|P| is a bound on the spline approximation of an occurrence count, not on the error relative to the defined cardinality; the unmodeled multiplicity can inflate the estimate by a factor equal to the number of occurrences per string, which the paper does not bound. This directly affects the abstract's error-bound contribution and the q-error bound 1+2ε|P| used in Section 6.2.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24281,"tokens_out":21341,"duration_ms":246775,"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":[{"comment":"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.","section":"§5.3, §2.2, Algorithm 4, §8"},{"comment":"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.","section":"Algorithm 4, §5.1"},{"comment":"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.","section":"§3.1"},{"comment":"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.","section":"Abstract, §6.2, Table 3"}],"minor_comments":[{"comment":"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.","section":"§6.2"},{"comment":"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.","section":"Table 6"},{"comment":"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.","section":"§6.1"},{"comment":"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.","section":"§5.2"},{"comment":"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.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the empirical core is solid and the code release is a plus, but the central error-bound claim needs to be reconciled with the fact that the estimator counts occurrences while the evaluation measures distinct-string cardinality. I would ask the authors to state explicitly which quantity SSCard targets, to fix Algorithm 4 so that the cnt field is actually used for short patterns (or to remove that claim), and to correct the abstract's numerical claims against Tables 3-4. The multi-string BWT comparator also deserves a real proof. These are fixable within the scope of a revision, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is a genuine engineering contribution: it extends the FM-index to multiple strings with a rotation-based comparator, wraps it in a pruned suffix tree, and uses spline fits with an explicit epsilon to compress rank lookups. The pushup idea is neat, and the experiments are more thorough than most in this area, with code released. If the central guarantee held, the max q-error improvements would be worth chasing.\n\nThe soft spot is exactly where the stress-test note lands. Cardinality is defined as distinct strings containing the pattern, but the FM-index path counts occurrences. L-triples carry no string ID, so Algorithm 4 returns row counts, not distinct-string counts, for any pattern longer than h=3. Section 5.3 admits the multiple-occurrence issue and says cnt on suffix tree nodes alleviates it, but that only covers short patterns. For longer patterns the 2ε|P| bound bounds approximation error on an occurrence count, not error relative to the defined query. The paper never bounds the multiplicities, and the q-error formula 1+2ε|P| is vacuous once 2ε|P| exceeds the true count. This is a load-bearing gap: the abstract's error-bound contribution is unsupported as written.\n\nLesser issues: the enhanced comparator is asserted, not proved; the abstract's headline reductions do not line up precisely with Table 3 and Table 4; and the experiments pick one hyperparameter set without a stated tuning protocol, though Figure 9 at least shows sensitivity to h. Related work is cited fairly, and the write-up is clear about what is new.\n\nNone of this kills the work. The design is clever, the space results are real, and the multiple-occurrence gap is probably fixable by adding string IDs or annotating suffix tree nodes differently and stating a bound on duplicate occurrences per string. As it stands, the paper overclaims a formal guarantee it does not deliver.\n\nFor a SIGMOD-class venue, send it to reviewers. They should ask for a proof or a convincing empirical study of the multiplicity issue before acceptance.","headline":"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.","tokens_in":24761,"tokens_out":3769,"would_cite":false,"duration_ms":49698,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["substring cardinality estimation","FM-index","Burrows-Wheeler transform","pruned suffix tree","learned index","spline interpolation","LIKE predicate","q-error"],"falsifier":"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.","tokens_in":23764,"feed_emoji":"🔍","tokens_out":7352,"duration_ms":78217,"temperature":0.7,"pith_summary":"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.","feed_headline":"SSCard cuts worst-case q-error 80% on five datasets","feed_subtitle":"A suffix tree plus error-bounded splines gives DB optimizers exact short patterns and controllable long-pattern error.","key_machinery":"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|$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the FM-index and its backward-search counting procedure, the base structure SSCard extends to multiple strings.","marker":"[11]"},{"why":"Defines the BWT and the F/L ordering property that the paper's enhanced comparator must preserve.","marker":"[6]"},{"why":"The MO pruned suffix-tree estimator, the main traditional baseline and source of the independence assumption for long patterns.","marker":"[21]"},{"why":"The LBS k-gram estimator, a competing traditional method for approximate substring selectivity.","marker":"[33]"},{"why":"PGM-index, one of the error-bounded learned index models that motivates replacing rank tables with learned functions.","marker":"[13]"},{"why":"RadixSpline, source of the greedy spline interpolation method used for error-bounded rank approximation.","marker":"[26]"},{"why":"DREAM, a deep-learning substring cardinality estimator used as a baseline.","marker":"[31]"},{"why":"LPLM, the most recent learned LIKE-predicate estimator used as a baseline.","marker":"[3]"},{"why":"Astrid, the deep-learning substring selectivity estimator whose data setup and ground-truth generation are reused.","marker":"[43]"}],"fun_headline_variants":["SSCard: 80% max q-error cut, 50% faster build","SSCard: exact short substrings, bounded long ones","Suffix tree + FM-Index: substring cardinality with error bounds","SSCard slashes max q-error 80% on 5 real datasets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["SSCard: 80% max q-error cut, 50% faster build","SSCard: exact short substrings, bounded long ones","Suffix tree + FM-Index: substring cardinality with error bounds","SSCard slashes max q-error 80% on 5 real datasets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001038,"raw_usage":{"total_tokens":4384,"prompt_tokens":979,"completion_tokens":3405,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":595,"completion_tokens_details":{"reasoning_tokens":3323}},"tokens_in":595,"tokens_out":3405,"duration_ms":26658,"temperature":1.0,"reasoning_tokens":3323,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:26:43.415380+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the FM-index and its backward-search counting procedure, the base structure SSCard extends to multiple strings."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the BWT and the F/L ordering property that the paper's enhanced comparator must preserve."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The MO pruned suffix-tree estimator, the main traditional baseline and source of the independence assumption for long patterns."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The LBS k-gram estimator, a competing traditional method for approximate substring selectivity."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"DREAM, a deep-learning substring cardinality estimator used as a baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"LPLM, the most recent learned LIKE-predicate estimator used as a baseline."}],"review_version":1}