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

信息论对数据传输和压缩领域产生了深远的影响。相比之下，它在海量数据集的知识提取和高效搜索等问题上的见解相对较少。虽然目前的信息论工具和技术可以在某种程度上应用于这些问题，但开发这些工具的范例将在本项目中仔细重新审查。将开发和分析准确捕捉现代海量数据库系统中有效搜索所面临的基本挑战的模型。随着接近最终基准的实用算法的开发，将研究表征准确率、压缩比和搜索效率之间权衡的渐近基本极限。正在研究的一个具体问题是为有效查询和搜索而进行的压缩。在此设置中，目标是在给定压缩表示形式的情况下，回答有关压缩数据的搜索查询。这与传统的压缩形成了鲜明的对比，在传统的压缩中，数据只需要从压缩的形式中重建。所采用的方法是为分布式数据库设计量身定做的，但也与允许在压缩域中进行搜索的压缩方案相关。所研究的基本量分别在信道和信源编码中起着类似于信道容量和熵/率失真的作用。一方面，它们理解了任何基于压缩表示的相似性查询系统所希望达到的性能的基本限制。另一方面，从理论中获得的见解正在指导实践中接近这些限制的方案的构建。我们将调查现有的实用方法(如各种散列和群集技术)如何相对于信息论限制执行，以及已被证明在信源和信道编码中实用的方法可以在多大程度上被用作构建块，以开发显著改进当前技术状态的新的高效搜索算法。

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.