부산대학교 도서관

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 $PS{E_X}(y): = \frac{1}{{\left| X \right|}}\sum\nolimits_{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 ∈ ℝ 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 .