Approximation Algorithms for Geometric Retrieval

几何检索的近似算法

• 批准号: 0635099
• 负责人: David Mount
• 金额: $ 30.74万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-10-01 至 2010-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0635099&HistoricalAwards=false
• 关键词: Approximation; Algorithms; 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.

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