REWA: A General Theory Of Witness-based Similarity

Abstract

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\}\{\Delta^\{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 compo

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyphadke2025rewa

Related papers

• Supermodular Locality Sensitive Hashes (2018)0.00
• Axiomatic Explanations For Visual Search, Retrieval, And Similarity Learning (2021)0.00
• Representation Learning For Efficient And Effective Similarity Search And Recommendation (2021)0.00
• Similarity Learning Via Kernel Preserving Embedding (2019)10.35
• Massively-parallel Similarity Join, Edge-isoperimetry, And Distance Correlations On The Hypercube (2016)2.26
• Fast Similarity Sketching (2017)9.41
• AMES: Asymmetric And Memory-efficient Similarity Estimation For Instance-level Retrieval (2024)9.70
• Learning Similarity Preserving Binary Codes For Recommender Systems (2022)0.00