AF: Small: New Challenges in Geometric Search and Retrieval

点击翻译按钮获取中文摘要

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.