Fast Approximate Search and Retrieval of High-Dimensional Data

本研究课题主要研究高维数据集的高效、交互式近似相似性搜索问题。高维数据的大型存储库是众多学科和应用的核心，它们的利用程度严重依赖于用于搜索和检索、分析和挖掘的高效智能工具的可用性。该方法涉及的方法，其起源在于除了经典的数据管理，包括优化，信息论，模式识别和信号压缩的几个学科。一条攻击线取决于近似（而不是精确最近邻）搜索的概念，其使得能够进行显式搜索复杂性-准确性权衡分析，并且包括：（a）用于有效权衡计算的新准确性标准的推导;以及（B）联合优化技术，以设计特征空间中的组合聚类和压缩，作为用于搜索复杂性-准确性权衡的直接优化的框架。第二条攻击线是与涉及来自用户的相关性反馈的交互式搜索有关。它为相关反馈机制开发了降低复杂性的搜索技术。该项目的最后阶段合并了两个主要目标，以开发一个有效的交互式近似搜索系统，优化复杂性和准确性的权衡。该项目本质上是跨学科的，它所取得的进展预计将影响高维数据库非常重要的许多学科，以及人类奋进的各个领域-科学，医学，社会，艺术，娱乐，安全等。项目网址（http：//www.scl.ece.ucsb.edu/html/prmdb_1.htm）用于提供项目结果。

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.