Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations
share
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 PSE_X(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 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 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 ∈ℝ^d depending on the output from previous queries q_1, q_2, …, q_j-1.
READ FULL TEXT