揭示相似性搜索与信息论的数学等价关系，为检索系统提供理论基石。
The Information Theory of Similarity
- 用信息论重新诠释基于见证的相似性系统，证明其与互信息等价
- 证明REWA编码复杂度下界为O(Δ⁻² log N)，不可再压缩
- 适用于理解检索系统本质的学者及算法设计者
我们建立了基于见证的相似性系统（REWA）与香农信息论之间的精确数学等价关系。证明了见证重叠即互信息，REWA的比特复杂度上限源于信道容量限制，且保持排序的编码需满足率失真约束。这一统一揭示，过去五十年的相似性搜索研究——从布隆过滤器到局部敏感哈希再到神经检索——实际上隐式构建了关系数据的信息论。我们推导出根本性下界，表明REWA的 $O(Δ^{-2} "log N)$ 复杂度是最优的：任何编码方案都无法在更少比特下保持相似性排序。该框架确立了语义相似性具有物理单位（互信息比特），搜索即通信（查询通过噪声信道传输），而检索系统面临类似于香农信道编码定理的基本容量限制。
原文摘要 · Abstract (English)
We establish a precise mathematical equivalence between witness-based similarity systems (REWA) and Shannon's information theory. We prove that witness overlap is mutual information, that REWA bit complexity bounds arise from channel capacity limitations, and that ranking-preserving encodings obey rate-distortion constraints. This unification reveals that fifty years of similarity search research -- from Bloom filters to locality-sensitive hashing to neural retrieval -- implicitly developed information theory for relational data. We derive fundamental lower bounds showing that REWA's $O(Δ^{-2} \log N)$ complexity is optimal: no encoding scheme can preserve similarity rankings with fewer bits. The framework establishes that semantic similarity has physical units (bits of mutual information), search is communication (query transmission over a noisy channel), and retrieval systems face fundamental capacity limits analogous to Shannon's channel coding theorem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。