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