Fast Approximate Search and Retrieval of High-Dimensional Data

University Of California-Santa Barbara, Santa Barbara CA

Investigators

Abstract

This research project is concerned with the problem of efficient, interactive and approximate similarity search in high-dimensional data sets. Large repositories of high dimensional data are central to a vast array of disciplines and applications, and the degree to which they can be exploited depends critically on the availability of efficient and smart tools for search and retrieval, analysis, and mining. The methodology involves approaches whose origins lie in several disciplines beside classical data management, including optimization, information theory, pattern recognition and signal compression. One line of attack hinges on the concept of approximate (rather than exact nearest neighbor) search which enables explicit search complexity-accuracy tradeoff analysis and includes: (a) the derivation of new accuracy criteria for effective tradeoff calculation; and (b) joint optimization techniques to design combined clustering and compression in the feature space as a framework for direct optimization of the search complexity-accuracy tradeoff. A second line of attack is concerned with interactive search involving relevance feedback from the users. It develops reduced complexity search techniques for relevance feedback mechanisms. The final phase of the project merges the two main thrusts to develop an efficient interactive approximate search system that optimizes the complexity-accuracy tradeoff. The project is inherently interdisciplinary and the advances made in it are expected to impact numerous disciplines where high-dimensional databases are of importance, as well as various areas of human endeavor -- scientific, medical, social, arts, entertainment, security, and more. The project Web site (http://www.scl.ece.ucsb.edu/html/prmdb_1.htm) is be used to provide access to the project's results.