The complexity of the co-occurrence problem

DOI10.1007/978-3-031-20643-6_4MaRDI QIDQ6166971zbMATH OpenOpenAlexFDO

Authors Philip Bille, Inge Li Gørtz, Tord Stordalen

Publication date 4 August 2023

Published in String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.10383

zbMATH Keywords

data structureslower boundsstrings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Let $S$ be a string of length $n$ over an alphabet $Sigma$ and let $Q$ be a subset of $Sigma$ of size $qgeq2$. The 'co-occurrence problem' is to construct a compact data structure that supports the following query: given an integer $w$ return the number of length-$w$ substrings of $S$ that contain each character of $Q$ at least once. This is a natural string problem with applications to, e.g., data mining, natural language processing, and DNA analysis. The state of the art is an $O(sqrtnq)$ space data structure that -- with some minor additions -- supports queries in $O(loglogn)$ time [CPM 2021]. Our contributions are as follows. Firstly, we analyze the problem in terms of a new, natural parameter $d$, giving a simple data structure that uses $O(d)$ space and supports queries in $O(loglogn)$ time. The preprocessing algorithm does a single pass over $S$, runs in expected $O(n)$ time, and uses $O(d)$ space in addition to the input. Furthermore, we show that $O(d)$ space is optimal and that $O(loglogn)$-time queries are optimal given optimal space. Secondly, we bound $d=O(sqrtnq)$, giving clean bounds in terms of $n$ and $q$ that match the state of the art. Furthermore, we prove that $Omega(sqrtnq)$ bits of space is necessary in the worst case, meaning that the $O(sqrtnq)$ upper bound is tight to within polylogarithmic factors. All of our results are based on simple and intuitive combinatorial ideas that simplify the state of the art.

Recommendations

• Implicit complexity for coinductive data: a characterization of corecurrence
• The Complexity of Problems in P Given Correlated Instances
• Kolmogorov complexity cores
• A combinatorial approach to complexity
• scientific article; zbMATH DE number 62483
• On the complexity of the cogrowth sequence
• The complexity of counting problems
• The complexity of some complementation problems
• scientific article; zbMATH DE number 403953

Cites work

• scientific article; zbMATH DE number 6381684 (Why is no real title available?)
• scientific article; zbMATH DE number 1947405 (Why is no real title available?)
• AWLCO: All-Window Length Co-Occurrence
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Universal classes of hash functions

Cited in

(3)

• Frequency-constrained substring complexity
• The Complexity of Problems in P Given Correlated Instances
• AWLCO: All-Window Length Co-Occurrence

This page was built for publication: The complexity of the co-occurrence problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166971)