Orthogonal Vectors Indexing

Orthogonal Vectors Indexing
复制标题

正交向量索引

DOI：
10.4230/lipics.isaac.2017.40
复制
发表时间：
2017
期刊：
ArXiv
影响因子：
--
通讯作者：
E. Porat
E. Porat
中科院分区：
--
文献类型：
--
作者：
Isaac Goldstein;Moshe Lewenstein;E. Porat

文献摘要

被引文献

相似文献

近年来，人们对条件下界的证明进行了大量的研究，以揭示类P的内部结构。这些条件下界是基于许多流行的关于研究问题的理论。最常用的假设之一是著名的强指数时间假设（SETH）。事实证明，在许多情况下，基于SETH证明的条件硬度通过一个中间问题-正交向量（OV）问题。 几乎所有关于条件下界的研究工作都集中在时间复杂度上。很少有人关注空间复杂性。在最近的一项工作中，Goldstein et al. [WADS[2017]为证明空间及其与时间的相互作用的条件下界奠定了基础。在这种精神下，研究OV的数据结构变体的空间复杂性是很有吸引力的，这种变体称为\n {OV索引}。在这个问题中，$n$个大小为$c\log{n}$的布尔向量用于预处理。作为一个查询，给出了一个向量v，我们需要验证是否有一个输入向量与它正交。 这个OV索引问题本身就很有趣，但它也可能对已知有条件困难的问题有很强的影响，就时间复杂度而言，基于OV。基于此，本文从多个方面对OV标引进行了研究。我们给出了一些空间有效的算法的问题，显示空间和查询时间之间的权衡，描述如何解决其报告的变体，揭示了这个问题和研究良好的SetDisjointness问题之间的一个有趣的连接，并演示了如何可以更有效地解决随机输入。
In the recent years, intensive research work has been dedicated to prove conditional lower bounds in order to reveal the inner structure of the class P. These conditional lower bounds are based on many popular conjectures on well-studied problems. One of the most heavily used conjectures is the celebrated Strong Exponential Time Hypothesis (SETH). It turns out that conditional hardness proved based on SETH goes, in many cases, through an intermediate problem - the Orthogonal Vectors (OV) problem. Almost all research work regarding conditional lower bound was concentrated on time complexity. Very little attention was directed toward space complexity. In a recent work, Goldstein et al.[WADS 2017] set the stage for proving conditional lower bounds regarding space and its interplay with time. In this spirit, it is tempting to investigate the space complexity of a data structure variant of OV which is called \emph{OV indexing}. In this problem $n$ boolean vectors of size $c\log{n}$ are given for preprocessing. As a query, a vector $v$ is given and we are required to verify if there is an input vector that is orthogonal to it or not. This OV indexing problem is interesting in its own, but it also likely to have strong implications on problems known to be conditionally hard, in terms of time complexity, based on OV. Having this in mind, we study OV indexing in this paper from many aspects. We give some space-efficient algorithms for the problem, show a tradeoff between space and query time, describe how to solve its reporting variant, shed light on an interesting connection between this problem and the well-studied SetDisjointness problem and demonstrate how it can be solved more efficiently on random input.