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.