Fast Approximate Search and Retrieval of High-Dimensional Data

高维数据的快速近似搜索和检索

• 批准号: 0329267
• 负责人: Kenneth Rose
• 金额: $ 39万
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0329267&HistoricalAwards=false
• 关键词: Fast; Approximate; Search; Retrieval; Dimensional

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.

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