String indexing for top-k close consecutive occurrences

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

1 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 two 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(n log n) space and optimal query time of O(m + k), and our second result achieves linear space and query time O(m + k1+ε). 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
Title of host publicationProceedings of 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
EditorsNitin Saxena, Sunil Simon
Number of pages17
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication dateDec 2020
Article number14
ISBN (Electronic)9783959771740
DOIs
Publication statusPublished - Dec 2020
Event40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - Virtual, Goa, India
Duration: 14 Dec 202018 Dec 2020
Conference number: 40

Conference

Conference40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Number40
Country/TerritoryIndia
CityVirtual, Goa
Period14/12/202018/12/2020
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume182
ISSN1868-8969

Bibliographical note

Funding Information:
Funding Philip Bille: Supported by the Danish Research Council grant DFF-8021-002498. Inge Li Gørtz: Supported by the Danish Research Council grant DFF-8021-002498. Max Rishøj Pedersen: Supported by the Danish Research Council grant DFF-8021-002498. Eva Rotenberg: Supported by the Danish Research Council grant DFF-8021-002498.

Publisher Copyright:
© Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen, Eva Rotenberg, and Teresa Anna Steiner.

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