Geometric retrieval is the problem of preprocessing multi-dimensional geometric data for rapid access. Efficient geometric search and retrieval are of fundamental importance in engineering and science, and have numerous applications in areas as diverse as knowledge discovery and data mining, pattern recognition and classification, machine learning, data compression, multimedia databases, document retrieval, and statistics. Given the high complexity of exact solutions to these problems, researchers have been led to consider these problems in the context of approximation, where small errors in distance are tolerated.
Over recent years, there have been many advances in our understanding of the computational complexity of approximation algorithms for proximity searching. This has ranged from the development of a theory of the best space-time tradeoffs achievable for these problems to practical software systems. Nonetheless, there are still many important, challenging problems that remain. Research under this award will both deepen and broaden our understanding of the computational complexity of approximate proximity searching. In particular, PI will study new data structures for polytope membership queries, polytope-based approaches to approximate nearest neighbor searching, simplification and unification of proximity data structures, dynamic data structures for proximity searching, and software implementations of these algorithms and data structures.
In addition to the contributions of new algorithms and data structures, software systems and libraries will be developed as part of this research, which will be made freely available over the Web to help scientists and engineers in other disciplines solve their own application problems that involve nearest neighbor and range searching. The geometric retrieval algorithms, developed as a part of this research, will be incorporated into a graduate-level course in computational geometry. Course materials will be made available over the Web as a resource for researchers interested in learning about this area.
