Optimal Preprocessing for Answering On-Line Product Queries
Optimal Preprocessing for Answering On-Line Product Queries
复制标题
回答在线产品查询的最佳预处理
DOI：
--
复制
发表时间：
2024
期刊：
影响因子：
--
通讯作者：
B. Schieber
中科院分区：
文献类型：
--
作者：
Noga Alon;B. Schieber
我们研究为尽可能快地回答某些在线查询所需的预处理量。我们从以下基本问题开始。假设给定一个半群$(S,\circ)$。设$s_1,\ldots,s_n$是$S$的元素。我们想要回答形如“$s_i\circ s_{i + 1}\circ\cdots\circ s_{j - 1}\circ s_j$的乘积是什么？”的在线查询，其中对于任意给定的$1\leq i\leq j\leq n$。我们表明，对于任何固定的$k$，$\Theta(n\lambda(k,n))$的时间和空间预处理对于在至多$k$步内回答每个这样的查询既是必要的也是充分的。函数$\lambda(k,\cdot)$是原始递归层次结构的$\lfloor{k/2}
floor$层上某个函数的逆函数。在需要线性预处理的情况下，我们表明可以在$O(lpha(n))$步内回答每个这样的查询，并且这是最优的。函数$lpha(n)$是逆阿克曼函数。
我们还考虑以下扩展问题。设$T$是一棵树，其每个顶点都关联一个$S$中的元素。我们想要回答形如“从$u$到$v$的路径上顶点所关联元素的乘积是什么？”的在线查询，其中$u$和$v$是$T$中的任意一对顶点。对于回答此类查询所需的预处理，我们推导出与上述类似的结果。
我们所有的顺序预处理算法都可以有效地并行化，以给出在CREW PRAM上运行时间为$O(\log n)$的最优并行算法。这些并行算法在运行时间和操作总数方面都是最优的。我们的算法，特别是对于具有最小或最大运算的实数半群的算法，在某些图算法、通信网络的利用以及数据库检索中具有各种应用。
We examine the amount of preprocessing needed for answering certain on-line queries as fast as possible. We start with the following basic problem. Suppose we are given a semigroup $(S,circ )$. Let $s_1 ,ldots, s_n$ be elements of $S$. We want to answer on-line queries of the form, ``What is the product $s_i circ s_{i+1} circ cdots circ s_{j-1} circ s_j$?' for any given $1le ile jle n$. We show that a preprocessing of $Theta(n lambda (k,n))$ time and space is both necessary and sufficient to answer each such query in at most $k$ steps, for any fixed $k$. The function $lambda (k,cdot)$ is the inverse of a certain function at the $lfloor {k/2}
floor$-th level of the primitive recursive hierarchy. In case linear preprocessing is desired, we show that one can answer each such query in $O( alpha (n))$ steps and that this is best possible. The function $alpha (n)$ is the inverse Ackermann function. We also consider the following extended problem. Let $T$ be a tree with an element of $S$ associated with each of its vertices. We want to answer on-line queries of the form, ``What is the product of the elements associated with the vertices along the path from $u$ to $v$?' for any pair of vertices $u$ and $v$ in $T$. We derive results that are similar to the above, for the preprocessing needed for answering such queries. All our sequential preprocessing algorithms can be parallelized efficiently to give optimal parallel algorithms which run in $O(log n)$ time on a CREW PRAM. These parallel algorithms are optimal in both running time and total number of operations. Our algorithms, especially for the semigroup of the real numbers with the minimum or maximum operations, have various applications in certain graph algorithms, in the utilization of communication networks and in Database retrieval.