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.