统一了各类相似性计算方法，揭示其背后的共同数学机制。
REWA: A General Theory of Witness-Based Similarity
- 用代数结构中的见证投影统一建模相似性计算
- 证明所有主流方法编码复杂度均为 O(log N)
- 适用于从布隆过滤器到Transformer注意力的多种场景
我们提出一个普适的相似性保持编码框架，将离散、连续、代数和学习型相似性方法统一于单一理论体系。通过在幺半群上定义相似性为函数见证投影，证明在任意代数结构下，编码复杂度为 \\[ O\left(\frac{1}{Δ^{2}}\log N\right) \\[ 且保持排序特性。该统一揭示了布隆过滤器、局部敏感哈希（LSH）、Count-Min sketch、随机傅里叶特征与Transformer注意力核均为同一机制的实例。在四次独立哈希下提供完整证明并给出显式常数，通过归一化与截断处理重尾见证，证明1970-2024年间主要相似性方法均满足 \\[ O(\log N) \\[ 复杂度。给出了布尔、自然数、实数、热带及乘积幺半群的显式构造，证明紧致浓度界，并展示组合性质以支持多原语相似性系统。
原文摘要 · Abstract (English)
We present a universal framework for similarity-preserving encodings that subsumes all discrete, continuous, algebraic, and learned similarity methods under a single theoretical umbrella. By formulating similarity as functional witness projection over monoids, we prove that \[ O\!\left(\frac{1}{Δ^{2}}\log N\right) \] encoding complexity with ranking preservation holds for arbitrary algebraic structures. This unification reveals that Bloom filters, Locality Sensitive Hashing (LSH), Count-Min sketches, Random Fourier Features, and Transformer attention kernels are instances of the same underlying mechanism. We provide complete proofs with explicit constants under 4-wise independent hashing, handle heavy-tailed witnesses via normalization and clipping, and prove \[ O(\log N) \] complexity for all major similarity methods from 1970-2024. We give explicit constructions for Boolean, Natural, Real, Tropical, and Product monoids, prove tight concentration bounds, and demonstrate compositional properties enabling multi-primitive similarity systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。