Adaptive And Dynamic Multi-resolution Hashing For Pairwise Summations

Qin Lianke, Reddy Aravind, Song Zhao, Xu Zhaozhuo, Zhuo Danyang. Arxiv 2022

[Paper]    
ARXIV Independent

In this paper, we propose Adam-Hash: an adaptive and dynamic multi-resolution hashing data-structure for fast pairwise summation estimation. Given a data-set $X\subset {\mathbb{R}}^d$, a binary function $f:{\mathbb{R}}^d\times {\mathbb{R}}^d\to \mathbb{R}$, and a point $y\in {\mathbb{R}}^d$, the Pairwise Summation Estimate \(\mathrm{PSE}X(y) := \frac{1}{|X|} \sum{x \in X} f(x,y)\). For any given data-set $X$, we need to design a data-structure such that given any query point $y\in {\mathbb{R}}^d$, the data-structure approximately estimates \(\mathrm{PSE}X(y)\) in time that is sub-linear in $|X|$. Prior works on this problem have focused exclusively on the case where the data-set is static, and the queries are independent. In this paper, we design a hashing-based PSE data-structure which works for the more practical \textit{dynamic} setting in which insertions, deletions, and replacements of points are allowed. Moreover, our proposed Adam-Hash is also robust to adaptive PSE queries, where an adversary can choose query $q_j\in {\mathbb{R}}^d$ depending on the output from previous queries \(q_1, q_2, \dots, q{j-1}\).

Similar Work

• Multi-resolution Hashing For Fast Pairwise Summations
• The Power Of Asymmetry In Binary Hashing
• Dartminhash Fast Sketching For Weighted Sets
• Set Similarity Search Beyond Minhash