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.