AF: Small: New Challenges in Geometric Search and Retrieval

几何检索是对多维几何数据进行预处理以实现快速存取的问题。高效的几何搜索和检索在工程和科学中具有根本的重要性，并且在知识发现和数据挖掘、模式识别和分类、机器学习、数据压缩、多媒体数据库、文档检索和统计学等不同领域中有许多应用。由于这些问题精确解的高度复杂性，研究者们开始在近似的范围内考虑这些问题，在近似的范围内，距离上的小误差是可以容忍的。近年来，我们对近似搜索算法的计算复杂性的理解有了很大的进步。这已经从理论的最佳时空权衡实现这些问题的实际softwaresystems的发展。尽管如此，仍然存在许多重要的、具有挑战性的问题。该奖项下的研究将加深和拓宽我们对近似邻近搜索计算复杂性的理解。特别是，PI将研究用于多面体成员查询的新数据结构，基于多面体的近似最近邻搜索方法，邻近数据结构的简化和统一，用于邻近搜索的动态数据结构，以及这些算法和数据结构的软件实现。除了新算法和数据结构的贡献之外，软件系统和库将作为本研究的一部分开发，这将在网上免费提供，以帮助其他学科的科学家和工程师解决他们自己的应用问题，包括最近邻和范围搜索。几何检索算法，作为这项研究的一部分，将被纳入计算几何的研究生课程。课程材料将通过网络提供，作为有兴趣了解这一领域的研究人员的资源。

Geometric retrieval is the problem of preprocessing multi-dimensionalgeometric data for rapid access. Efficient geometric search andretrieval are of fundamental importance in engineering and science, andhave numerous applications in areas as diverse as knowledge discoveryand data mining, pattern recognition and classification, machinelearning, data compression, multimedia databases, document retrieval,and statistics. Given the high complexity of exact solutions to theseproblems, researchers have been led to consider these problems in the contextof approximation, where small errors in distance are tolerated.Over recent years, there have been many advances in our understanding ofthe computational complexity of approximation algorithms for proximitysearching. This has ranged from the development of a theory of the bestspace-time tradeoffs achievable for these problems to practical softwaresystems. Nonetheless, there are still many important, challengingproblems that remain. Research under this award will both deepen and broadenour understanding of the computational complexity of approximateproximity searching. In particular, PI will study new datastructures for polytope membership queries, polytope-based approaches toapproximate nearest neighbor searching, simplification and unificationof proximity data structures, dynamic data structures for proximitysearching, and software implementations of these algorithms and datastructures.In addition to the contributions of new algorithms and data structures,software systems and libraries will be developed as part of thisresearch, which will be made freely available over the Web to helpscientists and engineers in other disciplines solve their ownapplication problems that involve nearest neighbor and range searching.The geometric retrieval algorithms, developed as a part of thisresearch, will be incorporated into a graduate-level course incomputational geometry. Course materials will be made available over theWeb as a resource for researchers interested in learning about thisarea.