String indexing for top-k close consecutive occurrences

Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen, Eva Rotenberg, Teresa Anna Steiner*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

64 Downloads (Pure)

Abstract

The classic string indexing problem is to preprocess a string S into a compact data structure that supports efficient subsequent pattern matching queries, that is, given a pattern string P, report all occurrences of P within S. In this paper, we study a basic and natural extension of string indexing called the string indexing for top-k close consecutive occurrences problem (SITCCO). Here, a consecutive occurrence is a pair (i,j), i<j, such that P occurs at positions i and j in S and there is no occurrence of P between i and j, and their distance is defined as j−i. Given a pattern P and a parameter k, the goal is to report the top-k consecutive occurrences of P in S of minimal distance. The challenge is to compactly represent S while supporting queries in time close to the length of P and k. We give three time-space trade-offs for the problem. Let n be the length of S, m the length of P, and ϵ∈(0,1]. Our first result achieves O(nlog⁡n) space and optimal query time of O(m+k). Our second and third results achieve linear space and query times either O(m+k1+ϵ) or O(m+klog1+ϵ⁡n). Along the way, we develop several techniques of independent interest, including a new translation of the problem into a line segment intersection problem and a new recursive clustering technique for trees.

Original languageEnglish
JournalTheoretical Computer Science
Volume927
Pages (from-to)133-147
ISSN0304-3975
DOIs
Publication statusPublished - 2022

Bibliographical note

Funding Information:
We thank anonymous reviewers of an earlier draft of this paper for their insightful comments and suggestions for improvement. Philip Bille, Inge Li Gørtz, Max Pedersen and Eva Rotenberg were partially supported by the Danish Research Council grant Adaptive Compressed Computation (DFF-8021-002498).

Keywords

  • Consecutive occurrences
  • Pattern matching
  • String indexing

Fingerprint

Dive into the research topics of 'String indexing for top-k close consecutive occurrences'. Together they form a unique fingerprint.

Cite this