Many data sets can profitably be viewed as points in a high-dimensional space: think of employee salary and seniority, weather stations' hourly reports of temperature, humidity, wind speed, and direction, or even the images from your cellphone camera as color values per pixel. Geometric retrieval problems seek to preprocess multi-dimensional geometric data for rapid access; for two examples, "nearest neighbor queries" could find images similar to a query image, and "range queries" could find all times with temperature and humidity above given thresholds. These queries are of fundamental importance throughout engineering and science, and have applications in knowledge discovery and data mining, pattern recognition and classification, machine learning, data compression, multimedia databases, document retrieval, and statistics.
The high computational complexity of nearest neighbor and range queries in high dimensions has inspired research into approximate solutions. The work of this project deepens and broadens our understanding of the computational complexity of these two problems. It studies new, more efficient solutions to key special cases, including low-complexity approximations to convex bodies, faster algorithms for polytope membership queries, applications to approximate nearest neighbor searching, efficient approximation algorithms for Euclidean minimum spanning trees, and range searching with structural queries. These improved algorithms will lead to more efficient solutions in the applications described above.
Software systems and libraries developed as part of this project will be made freely available over the Web to help scientists and engineers in other disciplines. The algorithms developed as a part of this project will be incorporated into graduate and undergraduate courses at the University of Maryland. Course materials will be made available over the Web as a resource for researchers interested in learning more about this area.
