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