ITR: Efficient Algorithms with Implicit Input Data

本研究的主要目的是建立方法fortheoretical算法的研究，其中输入数据的访问是以隐式的方式提供。这样的计算模型在处理大数据集的算法中自然出现。隐式输入可以对应于无法直接访问整个数据的情况下的部分数据（例如，因为它过于昂贵），或者它可以对应于压缩或编码的数据。当只有这样的数据存储在系统中，而没有提供或提供对真实的数据的直接访问时，就会发生这种情况。传统上，复杂性理论处理显式给定输入数据的经典定义：输入是显式给定的，普遍接受的标准是搜索具有线性复杂性的算法，或者至少是输入大小的多项式。这种算法通常被认为是最有效的。然而，如果我们处理大量数据，这一点就会发生重大变化。有时需要找到好的算法来处理隐式给定的数据，并且只访问数据的一小部分（例如，随机样本），或数据的小压缩或编码表示。我们所拥有的关于数据的信息现在的大小比整个原始输入的大小要小得多。在极端情况下，它甚至可以是常数（小样本足够好地近似，具有很高的概率，确切的输出）。本研究的主题是了解经典模型（其中访问数据是明确的）和模型中的问题，其中访问输入是隐式的复杂性之间的关系。主要研究一维和二维压缩文本的算法、属性测试算法和基于采样的近似算法。在文本的情况下，隐式输入是输入的压缩版本，而在属性测试的情况下，缩减输入通常是输入的小样本。在后一种情况下，我们还处理预处理输入的问题：预言机为输入数据的一些基本结构提供快速答案，例如，(in几何设置）正交范围查询。在这种情况下，对输入的隐式访问受到允许查询范围和输入数据表示的约束。本研究的目标是推进算法的最新技术，限制对输入数据的访问，特别是压缩文本的算法和基于采样的属性测试和近似算法。本提案的智力价值是广泛的，它涉及新类别问题的计算复杂性的进步：压缩或完全压缩的一维和二维文本中的模式匹配，仅访问一小部分输入数据的属性测试，以及处理隐式输入数据的抽象组合算法。研究人员相信，在这项研究中探索的算法效率的新方面可能会开创计算机科学的一个重要而新颖的领域。这在大规模数据的时空有效处理方面非常重要，在纯理论方面也非常重要。这项研究工作的最终结果是理解对输入数据的特殊访问对相关算法效率的影响。

The main objective of this research is to establish methods fortheoretical study of algorithms for which the access to the input data isprovided in an implicit way. Such models of computations arise naturallyin the context of algorithms working with large data sets. The implicitinput may correspond either to a partial data in situations when theentire data cannot be directly accessed (for example, because it isprohibitively expensive), or it may correspond to compressed or codeddata. It happens when only such data is stored in the system and no directaccess to the real data is provided or is available.Traditionally, complexity theory deals with the classical definition ofthe explicitly given input data: the input is given explicitly and thegenerally accepted standard is to search for algorithms having thecomplexity linear, or at least polynomial in terms of the input size. Suchalgorithms are viewed usually as the most efficient. However, thissignificantly changes if we deal with massive data. It is sometimesnecessary to find good algorithms which deal with implicitly given dataand access only small part of the data (e.g., a random sample), or smallcompressed or encoded representation of the data. The information which wehave about the data is now of size which would be substantially muchsmaller than the size of the whole original input. In the extremesituations it can be even constant (small sample sufficiently wellapproximating, with high probability, the exact output).The main theme of this research is to understand the relation between thecomplexity of the problems in the classical model (where the access todata is given explicitly) and the problems in the model in which theaccess to the input is implicit. The main focus is on study algorithms forone- and two-dimensional compressed texts, algorithms for propertytesting, and sampling-based approximation algorithms. In case of texts theimplicit input is the compressed version of the input and in the case ofproperty testing the reduced input is usually a small sample of the input.In the latter case, the we also deal with the problems on preprocessedinput: an oracle provides fast answers to some basic structures underlyingthe input data, e.g., (in geometric setting) orthogonal range queries. Inthis case the implicit access to the input is constrained by range ofallowable queries and by the input data representation. The goals for thisresearch are to advance the state-of-the art in algorithms with restrictedaccess to the input data in general, in particular algorithms forcompressed texts and sampling-based property testing and approximationalgorithms.The intellectual merit of this proposal is wide and it involves advancesin computational complexity of new classes of problems: pattern-matchingin compressed or fully compressed one and two-dimensional texts, propertytesting with access only to a small portion of the input data and abstractcombinatorial algorithms dealing with implicit input data. It is a beliefof the investigators that new aspects of the algorithmic efficiencyexplored in this research may initiate an important and novel area ofcomputer science. This would be of great importance in time and spaceeffective processing of massive data, as well as of great importance inpure theory. The end-result of this research effort are an understandingof the effects of special access to the input data on the efficiency ofrelated algorithms.