CIF:Small:Collaborative Research: Compressed databases for similarity queries: fundamental limits and algorithms

CIF:Small:协作研究：用于相似性查询的压缩数据库：基本限制和算法

• 批准号: 1321174
• 负责人: Tsachy Weissman
• 金额: $ 25万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-07-01 至 2016-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1321174&HistoricalAwards=false
• 关键词: CIF; Small; Collaborative; Research; Compressed

Information theory has had a profound impact on the fields of data transmission and compression. In contrast, it has yielded comparably few insights into problems such as knowledge extraction from and efficient search of massive datasets. While current information-theoretic tools and techniques can be applied to these problems to some extent, the paradigms for which these tools were developed will be being carefully reexamined in this project. Models that accurately capture the fundamental challenges faced by efficient search in modern massive database systems will be developed and analyzed. The asymptotic fundamental limits, which characterize the tradeoffs between accuracy, compression rate and search efficiency, will be investigated, along with development of practical algorithms that approach the ultimate benchmarks. One concrete problem being pursued is that of compression for efficient query and search. In this setting, the goal is, given a compressed representation, to answer search queries about the data that was compressed. This is in stark contrast to traditional compression, where the data need be merely reconstructible from the compressed form. The approach taken is tailored to distributed database design, but is also relevant to compression schemes that allow search within the compressed domain. The fundamental quantities studied play a similar role to that of the channel capacity and entropy/rate-distortion in channel and source coding, respectively. On one hand, they yield an understanding of the fundamental limits on the performance that any system for similarity queries based on compressed representations can hope to attain. On the other, the insights obtained from the theory are guiding the construction of schemes that approach these limits in practice. We will investigate how existing practical approaches (such as various hashing and clustering techniques) perform with respect to the information theoretic limits, and the extent to which approaches that have proved to be practical in source and channel coding can be used as building blocks to develop new efficient search algorithms that significantly improve on the current state of the art.

信息理论对数据传输和压缩领域产生了深远的影响。相比之下，它对诸如从知识提取和对大规模数据集的有效搜索等问题等问题产生了相当多的见解。尽管当前的信息理论工具和技术可以在某种程度上应用于这些问题，但在该项目中将仔细地重新检查这些工具的范例。将开发和分析在现代大规模数据库系统中有效搜索所面临的基本挑战的模型。将研究渐近基本限制，这些限制将研究精度，压缩率和搜索效率之间的权衡，以及开发实现最终基准的实用算法的开发。要解决的一个具体问题是用于有效查询和搜索的压缩问题。在这种情况下，目标是给定压缩表示形式，以回答有关被压缩数据的搜索查询。这与传统的压缩形成鲜明对比，在这种压缩中，数据仅需从压缩形式重新结构。采用的方法是针对分布式数据库设计量身定制的，但也与允许在压缩域内进行搜索的压缩方案有关。研究的基本数量分别与通道和源源编码中的通道容量和熵/速率延伸的作用相似。一方面，他们对基于压缩表示的任何相似性查询系统的性能的基本限制产生了理解。另一方面，从理论中获得的见解指导了在实践中达到这些限制的方案的构建。我们将研究现有的实用方法（例如各种哈希和聚类技术）如何在信息理论限制方面执行如何执行，以及在源和渠道编码中被证明是实用的方法的程度，可以用作开发新的有效搜索算法的构建障碍，从而在现有艺术的现状中显着改善。