Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations
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 ⊂ ℝd, a binary function f : ℝd × ℝd → ℝ, and a point y ∈ ℝd, the Pairwise Summation Estimate PSEX(y): = 1/|X|ΣxϵX f(x,y). For any given data-set X, we need to design a data-structure such that given any query point y ∈ ℝd, the data-structure approximately estimates PSEX(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 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 qj ∈ ℝd depending on the output from previous queries q1, q2,..., qj-1.
