Approximation Algorithms for Geometric Retrieval

几何检索和范围搜索是基本的计算问题。在多维空间中给定了大量的点，问题是对这些点进行预处理，以便可以计数或报告位于给定查询范围内的点的数量。这个问题在科学领域有广泛的应用，如知识发现、模式识别和数据压缩。虽然这是很好的研究，它的计算复杂度是相当高的。研究者和他的合作者的初步工作表明，近似可以导致相当快的运行时间，但仍有许多问题有待了解。本研究的目的是系统地研究近似距离搜索的计算复杂度。本研究将研究范围搜索的计算复杂度如何取决于问题公式的各种元素，包括范围空间的几何特征（如光滑性和锐性）和半群的性质（如完整性和幂等性）。研究人员将通过开发有效的算法和数据结构、推导下界和探索时空权衡来研究范围搜索。这项研究的智力价值源于对精确和近似范围搜索的计算复杂性的深入理解，以及对新的、更有效的计算解决方案的发现。更广泛的影响包括生产用于近似范围搜索的新的有效软件系统，这将有助于提高应用领域的技术水平，以及生产关于范围搜索的指导材料，这些材料将在网络上提供。

Geometric retrieval and range searching are fundamental computational problems. A large set of points is given in multi-dimensional space, and the problem is to preprocess these points so that it is possible to count or report the number of points lying inside a given query range. This problem has wide ranging applications in science in areas such as knowledge discovery, pattern recognition, and data compression. Although this is well studied, its computational complexity is quite high. Preliminary work by the investigator and his collaborators has shown that approximation can result in considerably faster running times, but there are still many issues that remain to be understood. The goal of this research is to systematically study the computational complexity of approximate range searching.This research will study how the computational complexity of range searching depends on various elements of the problem's formulation, including geometric characteristics of the range space (such as smoothness and sharpness) and properties of the semigroup (such as integrality and idempotence). The investigators will study range searching through the development of efficient algorithms and data structures, derivation of lower bounds, and exploration of space-time trade-offs. The intellectual merit of this research his research stems from a deepening understanding of the computational complexity of exact and approximate range searching and the discovery of new, more efficient computational solutions. The broader impacts include the production of new efficient software systems for approximate range searching, which will serve to advance the state of the art in applications areas, and the production of instructional materials on range searching, which will be made available over the web.