Pith. sign in

REVIEW 3 major objections 4 minor 62 references

Resilient Pattern Mining

T0 review · 3 major / 4 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 Exact near-linear-time algorithm mines substrings that survive any k letter substitutions.

desk verdict New problem and clever algorithm, but the main theorem is unproven: Section 5's #-to-alphabet reduction has a real gap. read the letter →

arxiv 2506.04935 v1 pith:R4TDYIHP submitted 2025-06-05 cs.DS

Pengxin Bian , Panagiotis Charalampopoulos , Lorraine A. K. Ayad , Manal Mohamed , Solon P. Pissis , Grigorios Loukides This is my paper
classification cs.DS MSC 68W3268R15
keywords resilientpatternminingfrequentsubstringstringalgorithmssuffixtreelettersubstitutionsrunsperiodicsubstringsversioneddata
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 proves that robustness of frequent substrings can be checked without trying any substitution: given a string S of length n and integers tau and k, it finds every substring that still occurs at least tau times after any k positions of S are replaced by other letters. The claimed complexity is O(n log n) time and O(n) space, with no dependence on tau or k, which would make resilience checks essentially as cheap as indexing the string once. The motivation is that real-world strings—genomes, text versions, code repositories—change in a bounded number of positions, and patterns that survive such changes remain usable longer. The algorithm returns, for every starting position, the length of the longest resilient prefix, from which the full set of resilient substrings can be listed in linear time.

What carries the argument

The load-bearing mechanism is the suffix tree of S—the compact trie of all suffixes of S—combined with three auxiliary structures: constant-time periodic extension queries to decide periodicity of any fragment; mergeable AVL trees that maintain, during a tree traversal, the sorted list of occurrence positions of the string at each node; and a run-index built in linear time, with runs grouped by Lyndon root (the lexicographically smallest rotation of the period block), from which the containing runs of a periodic substring are retrieved in O(log n + tau + k) time. Two combinatorial facts carry the counting: Lemma 1, that any three occurrences of an aperiodic substring cannot all overlap, and Lemma 2, that any position of S is contained in at most two runs sharing the same period. These facts bound how much damage a single letter substitution can do and justify the greedy destruction-counting algorithms AperiodicResilient and PeriodicResilient.

What would settle it

For a small string over a two-letter alphabet, compare the algorithm's output against a brute-force enumeration of all substitution sets: if any substring reported as (tau,k)-resilient ceases to be tau-frequent after some substitution using real letters, the Section 5 equivalence fails. For alphabets of size at least 4, instead take a periodic substring P and a set of '#' substitutions that destroy y occurrences of P, apply the constructs of Lemma 9 and Lemma 10, and check each resulting literal substitution for a newly created occurrence of P; one such occurrence refutes Lemma 11.

Watch

Extended reading notes

Core claim

The central discovery is that resilience to k substitutions is a counting property of occurrence sets, not a search over substitution scenarios. The paper proves (Theorem 3) that for |Sigma| >= 4 the (tau,k)-Resilient Pattern Mining problem is solvable in O(n log n) time and O(n) space. The argument splits every candidate substring into aperiodic or periodic: an aperiodic substring's occurrences overlap at most in pairs, so one substitution can destroy at most two of them and a greedy scan of the sorted occurrence list settles the question; a periodic substring's occurrences cluster inside runs, and because any position lies in at most two runs with the same period, the same greedy idea applies after clusters are retrieved. The full set of substrings is covered by a bottom-up suffix-tree traversal that checks only O(n log n/(tau+k)) candidates, one per suffix-tree edge near the cut. Finally, the paper claims that using a special letter outside the alphabet in the counting argument is equivalent to using true alphabet letters whenever the alphabet has at least four letters.

Load-bearing premise

The central assumption is that destroying occurrences of a substring with a special character outside the alphabet is always equivalent to doing so with real alphabet letters, a claim the paper proves only for alphabets of size at least four.

Editorial extensions

If this is right

  • If Theorem 3 holds, then resilience to k substitutions is computable in the same asymptotic time as building a suffix tree, independent of the robustness budget k.
  • For versioned datasets such as software libraries and Wikipedia pages, the (tau,k)-resilient substrings found in one version remain tau-frequent for thousands of later versions, while plain frequent substrings stop being frequent almost immediately.
  • Clustering viral genomes by their resilient substrings reproduces the ground-truth taxonomy with NMI up to 1 and Rand Index up to 0.96, outperforming clustering by plain frequent substrings and by an established alignment-free method.
  • On real strings of length about 2*10^8, the enhanced-suffix-array implementation runs in hundreds of seconds and linear memory, scales near-linearly with n, and does not slow down as tau or k grow.

Reading between the lines

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

  • If the Section 5 equivalence could be extended to alphabets of size 2 and 3, the same algorithm would apply to binary strings and to the raw DNA alphabet without the |Sigma| >= 4 restriction; the paper leaves this as an open direction.
  • The same run-based counting template may transfer to other local edit operations (insertions, deletions, or bounded-length block edits): what is needed is an analogue of Lemma 1/Lemma 2 bounding how many occurrences one edit can cover.
  • A direct empirical falsifier is available for small n: enumerate all k-subsets of positions and all replacement letters, compute the true (tau,k)-resilient set by brute force, and compare it with the algorithm's output on random strings over alphabets of size 2, 3, and 4; any mismatch would isolate the failing lemma exactly.
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

3 major / 4 minor

Summary. The paper defines the (τ,k)-Resilient Pattern Mining (RPM) problem: given a string S of length n and integers τ,k, return for each starting position the length of the longest prefix of the suffix that remains τ-frequent under any k letter substitutions. The authors give a DP-based baseline with O(n^3 k log n) time and O(n^2) space, and a claimed O(n log n)-time, O(n)-space algorithm based on suffix trees, runs, periodic extension queries, and counting arguments for aperiodic and periodic substrings. A central part is Section 5, which aims to show that destroying occurrences with a special symbol # outside the alphabet can be simulated by substitutions with alphabet letters whenever |Σ|≥4. The paper also reports experiments on large genomic, text, source-code, XML, and versioned datasets, plus a clustering case study.

Significance. If correct, the main theorem is significant: it shows that an exact resilience check over all k-letter substitutions can be performed in time independent of τ and k, which is a striking and practically useful result. The problem is natural, the compact representation via an OUTPUT array is sensible, and the experiments suggest that resilient substrings behave differently from frequent substrings and are useful in versioned-data and clustering applications. The strength of the paper, however, is conditional on the proof of the #-to-Σ reduction and on the correctness of the Phase 2 binary search; both currently have load-bearing gaps. The paper also deserves credit for including detailed proofs of the main combinatorial lemmas and for testing on real large-scale datasets.

major comments (3)
  1. [Section 5, Lemma 9 (Fact 2)] The proof of Fact 2 is incomplete. After deriving that a new occurrence at position y forces the substituted letter at x to equal T[x+(i-y)], the set of forbidden letters over all y∈[|U|,i) has size up to |X|-|P|, which can exceed σ-2. Thus the assertion that |Σ|≥4 guarantees two safe letters does not follow from the stated argument. Since Fact 2 supports Fact 3 and hence Lemma 9, and Lemma 9 is one of the four cases used in Lemma 11, the reduction from #-substitutions to alphabet substitutions is not established. This directly affects the exactness of Theorem 3 with respect to Definition 6.
  2. [Section 5, Lemma 8] The pigeonhole step in the proof of Lemma 8 is not justified. The text claims that because |V|<m we have 2|V|>m, but this implication is false (and the alternative reading 2^{|V|}>m also fails for small |V|). Without a valid counting argument, the existence of the string V′ that destroys the single overlapping occurrence is unproven, and this case is needed in Lemma 11.
  3. [Section 4.2 and proof of Theorem 3 (Lemma 15)] Lemma 15 asserts that occ_S(P)=occ_S(str(v)) for a prefix P of str(v), which is false in general. For example, in S=abababxabab, taking str(v)=ababab and P=abab gives occurrences of P at positions 0,2,7, while str(v) occurs only at position 0. Since AperiodicResilient and PeriodicResilient require the sorted occurrence list and run set of the queried substring P, Phase 2's binary search cannot simply reuse the occurrence data of str(v). As written, the algorithm may misclassify prefixes along cut edges, so both the correctness of the OUTPUT array and the claimed O(n log n) bound are not proven. The manuscript should specify how the SA intervals and occurrence lists of implicit loci are obtained and used during the binary search.
minor comments (4)
  1. [Section 5, Lemma 11 (final paragraph)] The final paragraph is incorrect as stated: replacing a letter at a position with a letter other than P[0] prevents occurrences starting at that exact position, not occurrences starting earlier. The proof can be repaired by deleting this paragraph, since the unused budget can be left unspent under d_H(S,S′)≤k, but the current wording is misleading.
  2. [General numbering] Lemma 7 appears twice (Section 4.3 and Section 5), and Lemma 15 is introduced only inside the proof of Theorem 3 without being listed in the paper's lemma sequence. The duplicate and out-of-order numbering should be fixed.
  3. [Section 7, Figure 12 captions] The text states that the comparison with RPM-DP uses a prefix of DNA with n=10,000, while the caption of Figure 12 says n=1000. This inconsistency should be corrected.
  4. [Section 4.2] There is a typo in 'preprosessing' in the preprocessing paragraph; please correct it.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the RPM derivation is self-contained and reduces to external combinatorial and data-structure results.

full rationale

The paper's central claim (Theorem 3) is derived from Definition 6 through a chain of new and external lemmas. No parameter is fitted to data and later reported as a prediction; the algorithm computes OUTPUT by counting destroyed occurrences, and the correctness argument ties those counts back to the definition via an interval-hitting theorem from Chrobak et al./Damaschke, runs, periodic-extension queries, priority search trees, and AVL merges. The paper explicitly flags the '#'-substitution convention as an assumption to be discharged and devotes Section 5 to showing that alphabet letters can replace '#', rather than silently equating the two. Even if Lemma 11's proof contains gaps, those are correctness risks for a particular bridge lemma, not a reduction of the theorem to its own input. The only self-citations appearing in the paper, e.g., [BCG+23] and [LZL+24], are used for motivation or experimental methodology and are not load-bearing for the main algorithm or its complexity bound. All load-bearing tools are external and independent of the target result. Therefore no specific circular step can be exhibited.

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

No fitted constants: tau and k are problem inputs, and the experiments sweep over them. All algorithmic building blocks are cited prior results with proofs elsewhere, and none of them assumes the RPM result. The only invented content is the problem definition and the combinatorial arguments, not entities. The |Sigma| >= 4 condition is an explicit domain assumption.

assumptions (9)
  • standard math Suffix tree construction in O(n) time over integer alphabets (Farach 1997).
    Used in Section 4.2 to build the index for the main algorithm.
  • standard math Number of runs in a string is O(n) and all runs can be computed in O(n) time (Bannai et al. 2017; Ellert-Fischer 2021).
    Used by IsPeriodic and Lemma 6 to group periodic substrings.
  • standard math O(1)-time periodic-extension queries after O(n) preprocessing (Kociumaka et al. 2024, Theorem 2).
    Provides the theoretical O(1) IsPeriodic check; authors note no implementation exists.
  • standard math O(1)-time minimal rotation of a substring (Kociumaka 2016).
    Used in Lemma 6 query to find the Lyndon root of a periodic substring.
  • standard math Priority search trees support 3-sided range reporting in O(log n + output) time (McCreight 1985).
    Used in Lemma 6 to retrieve runs with a given Lyndon root.
  • standard math AVL trees can be merged in O(log((n1+n2)/n1)) time (Brown-Tarjan 1979).
    Used in Section C.2 to maintain sorted occurrence lists in the DFS.
  • standard math Interval scheduling DP computes the maximum number of intervals hit by k points in O(k f^2) time (Chrobak et al. 2021; Damaschke 2017).
    Black-box used in RPM-DP.
  • domain assumption Alphabet size satisfies |Sigma| >= 4.
    Required by Theorem 3 for the Section 5 reduction of '#' substitutions to alphabet letters.
  • domain assumption Alphabet size sigma = n^{O(1)}.
    Stated in Section 2 so integer-alphabet suffix tree construction applies.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Resilient Pattern Mining." pith.science (2026). https://pith.science/paper/R4TDYIHP

@misc{pith2026250604935,
  author       = {Pith},
  title        = {Pith review of: Resilient Pattern Mining},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R4TDYIHP}},
  note         = {Machine review of arXiv:2506.04935}
}
abstract

Frequent pattern mining is a flagship problem in data mining. In its most basic form, it asks for the set of substrings of a given string $S$ of length $n$ that occur at least $\tau$ times in $S$, for some integer $\tau\in[1,n]$. We introduce a resilient version of this classic problem, which we term the $(\tau, k)$-Resilient Pattern Mining (RPM) problem. Given a string $S$ of length $n$ and two integers $\tau, k\in[1,n]$, RPM asks for the set of substrings of $S$ that occur at least $\tau$ times in $S$, even when the letters at any $k$ positions of $S$ are substituted by other letters. Unlike frequent substrings, resilient ones account for the fact that changes to string $S$ are often expensive to handle or are unknown. We propose an exact $\mathcal{O}(n\log n)$-time and $\mathcal{O}(n)$-space algorithm for RPM, which employs advanced data structures and combinatorial insights. We then present experiments on real large-scale datasets from different domains demonstrating that: (I) The notion of resilient substrings is useful in analyzing genomic data and is more powerful than that of frequent substrings, in scenarios where resilience is required, such as in the case of versioned datasets; (II) Our algorithm is several orders of magnitude faster and more space-efficient than a baseline algorithm that is based on dynamic programming; and (III) Clustering based on resilient substrings is effective.

Figures

Figures reproduced from arXiv: 2506.04935 by the authors.

Figure 1
Figure 1. (a) Running time and (b) Jaccard similarity. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. S = banana$: (a) ST(S); each branching non-root node is labeled by its frequency (circle) and each terminal node li by its associated starting position i (square). Node v is the locus of str(v) = ana and sd(v) = |str(v)| = 3. (b) SA(S). (c) The lexicographically sorted suffixes of S. (d) LCP(S). Parameter k can be set based on domain knowledge (e.g., in bioinformatics, we can use the substitution rate [PHD00]). The … view at source ↗
Figure 3
Figure 3. The periodic structure of R in the case when it has two occurrences in S that start at most |R|/2 positions apart. Proof. Let the common period of the considered runs be p. First, note that j ′ ≥ j + 2p − 1 since, for any run R, we have |R| ≥ 2per(R). Now, two runs with the same period p cannot overlap by x ≥ p positions; if this were the case, the portion of S spanned by these runs would have period p and this woul… view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: The setting in Fact 2, where fragments equal to Z (with period i − y) are shaded. In this setting, P can only occur at position y of T ′ if letter a at position x is substituted with letter δ = T[x + (i − y)]. In each of the constructed strings T ′ , each new occurrenc…
Figure 5
Figure 5. Figure 5: RFR for varying τ . The RFR values are on the top of the bars. Resilience in Versioned Datasets. Fig. 7a (and Fig. 7b) shows that the set of τ -frequent substrings in version 1 of the BOOST (and WIKI dataset), denoted by FREQ, changes in the next version of the dataset…
Figure 6
Figure 6. Figure 6: RFR for varying k. The RFR values are on the top of the bars. 2000 6000 10000 FREQ RESI 4 6 8 10 50 = k 0 Version 2 (a) BOOST 800 2400 4000 FREQ RESI 20 30 40 50 60 70 = k 0 10 20 Version (b) WIKI 10 20 30 FREQ RESI 1000 2000 3000 4000 5000 6000 V 0.0 0.2 0.4 LR (%) (c…
Figure 7
Figure 7. Figure 7: The earliest version in which at least one of the [PITH_FULL_IMAGE:figures/full_fig_p023_7.png]
Figure 8
Figure 8. Figure 8: Running time for varying τ . analogous and omitted). RPM-ESA occupies much less space than RPM-ST (e.g., 3.2 times less on average in the experiments of Fig. 11a and Fig. 11b), due to the use of the enhanced suffix array, which occupies less space than the suffix tree …
Figure 9
Figure 9. Figure 9: Running time for varying k. 25 50 75 100 125 150 175 200 n (MB) 0 300 600 900 1200 Runtime (s) RPM-ST RPM-ESA (a) Prefixes of DNA 25 50 75 100 125 150 175 200 n (MB) 0 20 40 60 80 Memory (GB) RPM-ST RPM-ESA (b) Prefixes of DNA [PITH_FULL_IMAGE:figures/full_fig_p025_9.png]
Figure 10
Figure 10. Figure 10: (a) Running time and (b) space for varying [PITH_FULL_IMAGE:figures/full_fig_p025_10.png]
Figure 11
Figure 11. Figure 11: Space for varying (a) τ and (b) k. string is the feature value, and the k-means clustering algorithm is used to cluster the feature matrix. We set k = 5 in k-means, as the ground truth clustering has 5 clusters. 24 [PITH_FULL_IMAGE:figures/full_fig_p025_11.png]
Figure 12
Figure 12. Figure 12: Running time of RPM-DP, RPM-ST and RPM-ESA for (a) varying τ and (b) varying k. 5000 10000 20000 50000 100000 n 10 2 10 0 10 2 10 4 10 6 Runtime (s) RPM-DP RPM-ST RPM-ESA (a) Prefixes of DNA 5000 10000 20000 50000 100000 n 10 0 10 2 10 4 10 6 Memory (MB) RPM-DP RPM-ST…
Figure 13
Figure 13. Figure 13: (a) Running time and (b) space of RPM-DP, RPM-ST and RPM-ESA for varying n. We evaluated how similar is the clustering obtained from the clustering algorithm based on (τ, k)-resilient substrings to the ground truth; see Table 2a. We used two well-known measures: Norma…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

62 extracted references · 29 canonical work pages

  1. [1]

    Resilient k-clustering

    Sara Ahmadian, MohammadHossein Bateni, Hossein Esfandiari, Silvio Lattanzi, Morteza Monemizadeh, and Ashkan Norouzi - Fard. Resilient k-clustering. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2024 , pages 29--38. ACM , 2024. http://dx.doi.org/10.1145/3637528.3671888 doi:10.1145/3637528.3671888

    arXiv 2024

  2. [2]

    Center-based clustering under perturbation stability

    Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. Inf. Process. Lett. , 112(1-2):49--54, 2012. http://dx.doi.org/10.1016/J.IPL.2011.10.006 doi:10.1016/J.IPL.2011.10.006

    doi:10.1016/j.ipl.2011.10.006 2012

  3. [3]

    Replacing suffix trees with enhanced suffix arrays

    Mohamed Ibrahim Abouelhoda, Stefan Kurtz, and Enno Ohlebusch. Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms , 2(1):53--86, 2004. URL: https://doi.org/10.1016/S1570-8667(03)00065-0, http://dx.doi.org/10.1016/S1570-8667(03)00065-0 doi:10.1016/S1570-8667(03)00065-0

    work page doi:10.1016/s1570-8667(03)00065-0 2004

  4. [4]

    Pissis, Giovanna Rosone, and Michelle Sweering

    Giulia Bernardini, Huiping Chen, Alessio Conte, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone, and Michelle Sweering. Combinatorial algorithms for string sanitization. ACM Trans. Knowl. Discov. Data , 15(1):8:1--8:34, 2021. URL: https://doi.org/10.1145/3418683, http://dx.doi.org/10.1145/3418683 doi:10.1145/3418683

    work page doi:10.1145/3418683 2021

  5. [5]

    Big data: principles and paradigms

    Rajkumar Buyya, Rodrigo N Calheiros, and Amir Vahid Dastjerdi. Big data: principles and paradigms . Morgan Kaufmann, 2016. URL: https://doi.org/10.1016/C2015-0-04136-3, http://dx.doi.org/10.1016/C2015-0-04136-3 doi:10.1016/C2015-0-04136-3

    work page doi:10.1016/c2015-0-04136-3 2016

  6. [6]

    Pissis, Giulia Punzi, Leen Stougie, and Michelle Sweering

    Giulia Bernardini, Alessio Conte, Garance Gourdel, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Giulia Punzi, Leen Stougie, and Michelle Sweering. Hide and mine in strings: Hardness, algorithms, and experiments. IEEE Trans. Knowl. Data Eng. , 35(6):5948--5963, 2023. URL: https://doi.org/10.1109/TKDE.2022.3158063, http://dx.doi.org/1...

    arXiv 2023

  7. [7]

    Phoni: Streamed matching statistics with multi-genome references

    Christina Boucher, Travis Gagie, I Tomohiro, Dominik K \"o ppl, Ben Langmead, Giovanni Manzini, Gonzalo Navarro, Alejandro Pacheco, and Massimiliano Rossi. Phoni: Streamed matching statistics with multi-genome references. In 2021 Data Compression Conference (DCC) , pages 193--202. IEEE, 2021. URL: https://doi.org/10.1109/DCC50243.2021.00027, http://dx.doi...

    arXiv 2021

  8. [8]

    The "runs" theorem

    Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The "runs" theorem. SIAM J. Comput. , 46(5):1501--1514, 2017. URL: https://doi.org/10.1137/15M1011032, http://dx.doi.org/10.1137/15M1011032 doi:10.1137/15M1011032

    doi:10.1137/15m1011032 2017

Show all 62 references
  1. [9]

    Are stable instances easy? Comb

    Yonatan Bilu and Nathan Linial. Are stable instances easy? Comb. Probab. Comput. , 21(5):643--660, 2012. URL: https://doi.org/10.1017/S0963548312000193, http://dx.doi.org/10.1017/S0963548312000193 doi:10.1017/S0963548312000193

    2012 doi

  2. [10]

    Brown and Robert E

    Mark R. Brown and Robert E. Tarjan. A fast merging algorithm. Journal of the ACM (JACM) , 26(2):211--226, April 1979. http://dx.doi.org/10.1145/322123.322127 doi:10.1145/322123.322127

    1979

  3. [11]

    Perturbation resilient clustering for k-center and related problems via LP relaxations

    Chandra Chekuri and Shalmoli Gupta. Perturbation resilient clustering for k-center and related problems via LP relaxations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018 , pages 9:1--9:16, 2018. http://dx.doi.org...

    2018 doi

  4. [12]

    Golin, Tak Wah Lam, and Dorian Nogneng

    Marek Chrobak, Mordecai J. Golin, Tak Wah Lam, and Dorian Nogneng. Scheduling with gaps: new models and algorithms. J. Sched. , 24(4):381--403, 2021. http://dx.doi.org/10.1007/S10951-021-00691-W doi:10.1007/S10951-021-00691-W

    2021 doi

  5. [13]

    Algorithms on strings

    Maxime Crochemore, Christophe Hancart, and Thierry Lecroq. Algorithms on strings . Cambridge University Press, 2007. http://dx.doi.org/10.1017/CBO9780511546853 doi:10.1017/CBO9780511546853

    2007 doi

  6. [14]

    Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen

    Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Extracting powers and periods in a word from its runs structure. Theor. Comput. Sci. , 521:29--41, 2014. http://dx.doi.org/10.1016/J.TCS.2013.11.018 doi:10.1016/J.TCS....

    2014 doi

  7. [15]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition . MIT Press, 2009

    2009

  8. [16]

    Computational pan-genomics: status, promises and challenges

    The Computational Pan - Genomics Consortium. Computational pan-genomics: status, promises and challenges. Briefings Bioinform. , 19(1):118--135, 2018. http://dx.doi.org/10.1093/BIB/BBW089 doi:10.1093/BIB/BBW089

    2018 doi

  9. [17]

    Hiding messages in DNA microdots

    Catherine Taylor Clelland, Viviana Risca, and Carter Bancroft. Hiding messages in DNA microdots. Nature , 399(6736):533--534, 1999. URL: https://doi.org/10.1038/21092, http://dx.doi.org/10.1038/21092 doi:10.1038/21092

    1999 doi

  10. [18]

    Refined algorithms for hitting many intervals

    Peter Damaschke. Refined algorithms for hitting many intervals. Inf. Process. Lett. , 118:117--122, 2017. http://dx.doi.org/10.1016/J.IPL.2016.11.001 doi:10.1016/J.IPL.2016.11.001

    2017 doi

  11. [19]

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006 , volume 3876 of Lecture Notes in Computer Science , pages 265--284. Springer...

    2006 doi

  12. [20]

    Puglisi, and Andrew Turpin

    Jasbir Dhaliwal, Simon J. Puglisi, and Andrew Turpin. Practical efficient string mining. IEEE Trans. Knowl. Data Eng. , 24(4):735--744, 2012. http://dx.doi.org/10.1109/TKDE.2010.242 doi:10.1109/TKDE.2010.242

    2012 doi

  13. [21]

    Linear time runs over general ordered alphabets

    Jonas Ellert and Johannes Fischer. Linear time runs over general ordered alphabets. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 , pages 63:1--63:16, 2021. http://dx.doi.org/10.4230/LIPICS.ICALP.2021.63 doi:10.4230/LIPICS.ICALP.2021.63

    2021 doi

  14. [22]

    Evans, Andrew D

    Patricia A. Evans, Andrew D. Smith, and Harold T. Wareham. On the complexity of finding common approximate substrings. Theor. Comput. Sci. , 306(1-3):407--430, 2003. URL: https://doi.org/10.1016/S0304-3975(03)00320-7, http://dx.doi.org/10.1016/S0304-3975(03)00320-7 doi:10.1016...

    2003 doi

  15. [23]

    Optimal suffix tree construction with large alphabets

    Martin Farach. Optimal suffix tree construction with large alphabets. In 38th Annual Symposium on Foundations of Computer Science, FOCS 1997 , pages 137--143, 1997. http://dx.doi.org/10.1109/SFCS.1997.646102 doi:10.1109/SFCS.1997.646102

    1997

  16. [24]

    NCBI genome datasets, 2024

    National Center for Biotechnology Information. NCBI genome datasets, 2024. URL: https://www.ncbi.nlm.nih.gov/datasets/genome/

    2024

  17. [25]

    Fast frequent string mining using suffix arrays

    Johannes Fischer, Volker Heun, and Stefan Kramer. Fast frequent string mining using suffix arrays. In Proceedings of the 5th IEEE International Conference on Data Mining ( ICDM 2005) , pages 609--612. IEEE Computer Society, 2005. http://dx.doi.org/10.1109/ICDM.2005.62 doi:10.1...

    2005 doi

  18. [26]

    Optimal string mining under frequency constraints

    Johannes Fischer, Volker Heun, and Stefan Kramer. Optimal string mining under frequency constraints. In Knowledge Discovery in Databases: PKDD 2006, 10th European Conference on Principles and Practice of Knowledge Discovery in Databases , pages 139--150. Springer, 2006. http:/...

    2006 doi

  19. [27]

    Optimal dynamic strings

    Pawe Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub a cki, and Piotr Sankowski. Optimal dynamic strings. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '18, page 1509–1528. Society for Industrial and Applied Mathematics, 2018....

    2018 doi

  20. [28]

    Fully functional suffix trees and optimal text searching in bwt-runs bounded space

    Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Fully functional suffix trees and optimal text searching in bwt-runs bounded space. J. ACM , 67(1):2:1--2:54, 2020. http://dx.doi.org/10.1145/3375890 doi:10.1145/3375890

    2020 doi

  21. [29]

    Finding near-duplicate web pages: a large-scale evaluation of algorithms

    Monika Henzinger. Finding near-duplicate web pages: a large-scale evaluation of algorithms. In SIGIR 2006: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval , pages 284--291. ACM , 2006. http://dx.doi.org/10....

    2006

  22. [30]

    Data Mining: Concepts and Techniques, 3rd edition

    Jiawei Han, Micheline Kamber, and Jian Pei. Data Mining: Concepts and Techniques, 3rd edition . Morgan Kaufmann, 2011. http://dx.doi.org/10.1016/C2009-0-61819-5 doi:10.1016/C2009-0-61819-5

    2011 doi

  23. [31]

    Average sensitivity of decision tree learning

    Satoshi Hara and Yuichi Yoshida. Average sensitivity of decision tree learning. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023 . OpenReview.net, 2023. URL: https://openreview.net/forum?id=boik01yhssB

    2023

  24. [32]

    Choudhuri, Enno Ohlebusch, Chris Schleiermacher, Jens Stoye, and Robert Giegerich

    Stefan Kurtz, Jomuna V. Choudhuri, Enno Ohlebusch, Chris Schleiermacher, Jens Stoye, and Robert Giegerich. Reputer: the manifold applications of repeat analysis on a genomic scale. Nucleic Acids Research , 29(22):4633--4642, 11 2001. URL: https://doi.org/10.1093/nar/29.22.4633...

    2001 doi

  25. [33]

    Cory Kapser and Michael W. Godfrey. Improved tool support for the investigation of duplication in software. In 21st IEEE International Conference on Software Maintenance (ICSM 2005) , pages 305--314. IEEE Computer Society, 2005. http://dx.doi.org/10.1109/ICSM.2005.52 doi:10.11...

    2005 doi

  26. [34]

    Knuth, James H

    Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput. , 6(2):323--350, 1977. http://dx.doi.org/10.1137/0206024 doi:10.1137/0206024

    1977 doi

  27. [35]

    Linear-time longest-common-prefix computation in suffix arrays and its applications

    Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park. Linear-time longest-common-prefix computation in suffix arrays and its applications. In Combinatorial Pattern Matching, 12th Annual Symposium, CPM 2001 , pages 181--192, 2001. http://dx.doi.org/10.1007/3-5...

    2001 doi

  28. [36]

    Minimal suffix and rotation of a substring in optimal time

    Tomasz Kociumaka. Minimal suffix and rotation of a substring in optimal time. In 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016 , pages 28:1--28:12, 2016. http://dx.doi.org/10.4230/LIPICS.CPM.2016.28 doi:10.4230/LIPICS.CPM.2016.28

    2016 doi

  29. [37]

    Internal pattern matching queries in a text and applications

    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Internal pattern matching queries in a text and applications. SIAM J. Comput. , 53(5):1524--1577, 2024. http://dx.doi.org/10.1137/23M1567618 doi:10.1137/23M1567618

    2024 doi

  30. [38]

    Small fitness effect of mutations in highly conserved non-coding regions

    Gregory V Kryukov, Steffen Schmidt, and Shamil Sunyaev. Small fitness effect of mutations in highly conserved non-coding regions. Human molecular genetics , 14(15):2221--2229, 2005. http://dx.doi.org/10.1093/hmg/ddi226 doi:10.1093/hmg/ddi226

    2005 doi

  31. [39]

    Yongkun Li, Lily He, Rong Lucy He, and Stephen S.-T. Yau. A novel fast vector method for genetic sequence comparison. S ci R ep. , 22, 2017. http://dx.doi.org/10.1038/s41598-017-12493-2 doi:10.1038/s41598-017-12493-2

    2017 doi

  32. [40]

    Efficient secure similarity computation on encrypted trajectory data

    An Liu, Kai Zheng, Lu Li, Guanfeng Liu, Lei Zhao, and Xiaofang Zhou. Efficient secure similarity computation on encrypted trajectory data. In 31st IEEE International Conference on Data Engineering, ICDE 2015 , pages 66--77. IEEE Computer Society, 2015. http://dx.doi.org/10.110...

    2015

  33. [41]

    Pissis, and Maria Matsangidou

    Ling Li, Wiktor Zuba, Grigorios Loukides, Solon P. Pissis, and Maria Matsangidou. Scalable order-preserving pattern mining. In Elena Baralis, Kun Zhang, Ernesto Damiani, M \' e rouane Debbah, Panos Kalnis, and Xindong Wu, editors, IEEE International Conference on Data Mining, ...

    2024

  34. [42]

    McCreight

    Edward M. McCreight. Priority search trees. SIAM J. Comput. , 14(2):257--276, 1985. http://dx.doi.org/10.1137/0214021 doi:10.1137/0214021

    1985 doi

  35. [43]

    Udi Manber and Eugene W. Myers. Suffix arrays: A new method for on-line string searches. SIAM J. Comput. , 22(5):935--948, 1993. http://dx.doi.org/10.1137/0222058 doi:10.1137/0222058

    1993 doi

  36. [44]

    Indexing highly repetitive string collections, part i: Repetitiveness measures

    Gonzalo Navarro. Indexing highly repetitive string collections, part i: Repetitiveness measures. ACM Comput. Surv. , 54(2), March 2021. URL: https://doi.org/10.1145/3434399, http://dx.doi.org/10.1145/3434399 doi:10.1145/3434399

    2021 doi

  37. [45]

    Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance

    Xuan Vinh Nguyen, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. J. Mach. Learn. Res. , 11:2837--2854, 2010. http://dx.doi.org/10.5555/1756006.1953024 doi:10.5555/1756006.1953024

    2010

  38. [46]

    The pizza and chili corpus - texts

    Pizza and Chili Corpus. The pizza and chili corpus - texts. https://pizzachili.dcc.uchile.cl/texts.html, 2024

    2024

  39. [47]

    Carvalho, Laurent Marsan, and Marie - France Sagot

    Nadia Pisanti, Alexandra M. Carvalho, Laurent Marsan, and Marie - France Sagot. RISOTTO: fast extraction of motifs with mismatches. In LATIN 2006: Theoretical Informatics, 7th Latin American Symposium , pages 757--768, 2006. http://dx.doi.org/10.1007/11682462\_69 doi:10.1007/1...

    2006 doi

  40. [48]

    Towards efficient mining of proportional fault-tolerant frequent itemsets

    Ardian Kristanto Poernomo and Vivekanand Gopalkrishnan. Towards efficient mining of proportional fault-tolerant frequent itemsets. In John F. Elder IV, Fran c oise Fogelman - Souli \' e , Peter A. Flach, and Mohammed Javeed Zaki, editors, Proceedings of the 15th ACM SIGKDD Int...

    2009

  41. [49]

    Hudson, and Anna Di Rienzo

    Molly Przeworski, Richard R. Hudson, and Anna Di Rienzo . Adjusting the focus on human variation. Trends in Genetics , 16(7):296--302, 2000. http://dx.doi.org/https://doi.org/10.1016/S0168-9525(00)02030-8 doi:https://doi.org/10.1016/S0168-9525(00)02030-8

    doi

  42. [50]

    Objective criteria for the evaluation of clustering methods

    William M Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association , 66(336):846--850, 1971. http://dx.doi.org/10.1080/01621459.1971.10482356 doi:10.1080/01621459.1971.10482356

    1971

  43. [51]

    Comparison of five methods for finding conserved sequences in multiple alignments of gene regulatory regions

    Nikola Stojanovic, Liliana Florea, Cathy Riemer, Deborah Gumucio, Jerry Slightom, Morris Goodman, Webb Miller, and Ross Hardison. Comparison of five methods for finding conserved sequences in multiple alignments of gene regulatory regions. Nucleic Acids Research , 27(19):3899-...

    1999 doi

  44. [52]

    MACFP: maximal approximate consecutive frequent pattern mining under edit distance

    Jingbo Shang, Jian Peng, and Jiawei Han. MACFP: maximal approximate consecutive frequent pattern mining under edit distance. In Proceedings of the 2016 SIAM International Conference on Data Mining , pages 558--566. SIAM , 2016. http://dx.doi.org/10.1137/1.9781611974348.63 doi:...

    2016 doi

  45. [53]

    Groundhog day: near-duplicate detection on twitter

    Ke Tao, Fabian Abel, Claudia Hauff, Geert - Jan Houben, and Ujwal Gadiraju. Groundhog day: near-duplicate detection on twitter. In 22nd International World Wide Web Conference, WWW '13 , pages 1273--1284. International World Wide Web Conferences Steering Committee / ACM , 2013...

    2013

  46. [54]

    Repcorpus, 2024

    RepCorpus Team. Repcorpus, 2024. URL: https://pizzachili.dcc.uchile.cl/repcorpus/real/

    2024

  47. [55]

    Towards more robust and accurate sequential recommendation with cascade-guided adversarial training

    Juntao Tan, Shelby Heinecke, Zhiwei Liu, Yongjun Chen, Yongfeng Zhang, and Huan Wang. Towards more robust and accurate sequential recommendation with cascade-guided adversarial training. In Proceedings of the 2024 SIAM International Conference on Data Mining, SDM 2024 , pages ...

    2024 doi

  48. [56]

    The 100 000 genomes project: bringing whole genome sequencing to the nhs

    Clare Turnbull, Richard H Scott, Ellen Thomas, Louise Jones, Nirupa Murugaesu, Freya Boardman Pretty, Dina Halai, Emma Baple, Clare Craig, Angela Hamblin, et al. The 100 000 genomes project: bringing whole genome sequencing to the nhs. Bmj , 361, 2018. http://dx.doi.org/10.113...

    2018 doi

  49. [57]

    Susana Vinga and Jonas S. Almeida. Alignment-free sequence comparison-a review. Bioinform. , 19(4):513--523, 2003. http://dx.doi.org/10.1093/BIOINFORMATICS/BTG005 doi:10.1093/BIOINFORMATICS/BTG005

    2003 doi

  50. [58]

    Average sensitivity of graph algorithms

    Nithin Varma and Yuichi Yoshida. Average sensitivity of graph algorithms. SIAM J. Comput. , 52(4):1039--1081, 2023. http://dx.doi.org/10.1137/21M1399592 doi:10.1137/21M1399592

    2023 doi

  51. [59]

    Opr-miner: Order-preserving rule mining for time series

    Youxi Wu, Xiaoqian Zhao, Yan Li, Lei Guo, Xingquan Zhu, Philippe Fournier - Viger, and Xindong Wu. Opr-miner: Order-preserving rule mining for time series. IEEE Trans. Knowl. Data Eng. , 35(11):11722--11735, 2023. http://dx.doi.org/10.1109/TKDE.2022.3224963 doi:10.1109/TKDE.20...

    2023

  52. [60]

    Average sensitivity of E uclidean k-clustering

    Yuichi Yoshida and Shinji Ito. Average sensitivity of E uclidean k-clustering. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022 , 2022. URL: http://papers.nips.cc/paper\_files/paper/2022/hash...

    2022

  53. [61]

    Sensitivity analysis of the maximum matching problem

    Yuichi Yoshida and Samson Zhou. Sensitivity analysis of the maximum matching problem. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021 , pages 58:1--58:20, 2021. http://dx.doi.org/10.4230/LIPICS.ITCS.2021.58 doi:10.4230/LIPICS.ITCS.2021.58

    2021 doi

  54. [62]

    Feida Zhu, Xifeng Yan, Jiawei Han, and Philip S. Yu. Efficient discovery of frequent approximate sequential patterns. In Proceedings of the 7th IEEE International Conference on Data Mining (ICDM 2007) , pages 751--756. IEEE Computer Society, 2007. http://dx.doi.org/10.1109/ICD...

    2007 doi

Pith tools

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