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

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

Project abstract 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