Gapped String Indexing in Subquadratic Space and Sublinear Query Time
Gapped String Indexing in Subquadratic Space and Sublinear Query Time
复制标题
次二次空间中的间隙字符串索引和次线性查询时间
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Teresa Anna Steiner
中科院分区：
文献类型：
--
作者：
Philip Bille;Inge Li Gørtz;Moshe Lewenstein;S. Pissis;E. Rotenberg;Teresa Anna Steiner
在间隙字符串索引中，目标是紧凑地表示长度为$n$的字符串$S$，这样对于任何由两个字符串$P_1$和$P_2$组成的查询，称为模式，以及一个整数间隔$[alpha， eta]$，称为间隙范围，我们可以快速找到$P_1$和$P_2$在$S$中出现的距离为$[alpha， eta]$。空白字符串索引是计算生物学和文本挖掘中的一个核心问题，因此得到了重要的研究兴趣，包括参数化和启发式方法。尽管有这种兴趣，最著名的间隔字符串索引的时间-空间权衡是直接的$O(n)$ space和$O(n+occ)$查询时间，或者$Omega(n^2)$ space和$ ilde{O}(|P_1| + |P_2| +occ)$查询时间。我们突破了这个障碍，获得了多项式次二次空间和多项式次线性查询时间的第一个有趣的权衡。特别地，我们证明了，对于每一个$0leq delta leq 1$，存在一个用于缺口字符串索引的数据结构，该数据结构具有$ ilde{O}(n^{2-delta/3})$或$ ilde{O}(n^{3-2delta})$空间和$ ilde{O}(|P_1| + |P_2| + n^{delta}cdot (occ+1))$查询时间，其中$occ$是报告出现的次数。作为获得主要结果的新工具，我们引入了移位集相交问题。我们证明了这个问题等价于3SUM的索引变体（3SUM indexing）。通过一系列的约简，我们得到了间隙字符串索引问题的一个解决方案。此外，我们改进了决定移位集交集的数据结构，使我们能够支持问题的报告变体。通过获得3SUM索引的等价性，我们因此为3SUM索引的报告变体提供了新的改进的数据结构，并且我们展示了如何在最先进的解决方案上改进对于任意恒定大小的字母的Jumbled索引。
In Gapped String Indexing, the goal is to compactly represent a string $S$ of length $n$ such that for any query consisting of two strings $P_1$ and $P_2$, called patterns, and an integer interval $[alpha, eta]$, called gap range, we can quickly find occurrences of $P_1$ and $P_2$ in $S$ with distance in $[alpha, eta]$. Gapped String Indexing is a central problem in computational biology and text mining and has thus received significant research interest, including parameterized and heuristic approaches. Despite this interest, the best-known time-space trade-offs for Gapped String Indexing are the straightforward $O(n)$ space and $O(n+occ)$ query time or $Omega(n^2)$ space and $ ilde{O}(|P_1| + |P_2| + occ)$ query time. We break through this barrier obtaining the first interesting trade-offs with polynomially subquadratic space and polynomially sublinear query time. In particular, we show that, for every $0leq delta leq 1$, there is a data structure for Gapped String Indexing with either $ ilde{O}(n^{2-delta/3})$ or $ ilde{O}(n^{3-2delta})$ space and $ ilde{O}(|P_1| + |P_2| + n^{delta}cdot (occ+1))$ query time, where $occ$ is the number of reported occurrences. As a new tool towards obtaining our main result, we introduce the Shifted Set Intersection problem. We show that this problem is equivalent to the indexing variant of 3SUM (3SUM Indexing). Via a series of reductions, we obtain a solution to the Gapped String Indexing problem. Furthermore, we enhance our data structure for deciding Shifted Set Intersection, so that we can support the reporting variant of the problem. Via the obtained equivalence to 3SUM Indexing, we thus give new improved data structures for the reporting variant of 3SUM Indexing, and we show how this improves upon the state-of-the-art solution for Jumbled Indexing for any alphabet of constant size $sigma>5$.
DOI：
--
发表时间：
2024
期刊：
SIAM
影响因子：
--
作者：
Aronov, Boris;Cardinal, Jean;Dallant, Justin;Iacono, John
通讯作者：
Iacono, John
数据结构与密码学的结合：带预处理的 3SUM
DOI：
10.1145/3357713.3384342
发表时间：
2020
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Golovnev, Alexander;Guo, Siyao;Horel, Thibaut;Park, Sunoo;Vaikunathan, Vinod.
通讯作者：
Vaikunathan, Vinod.