论文标题
对成对求和的自适应和动态多分辨率哈希
Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations
论文作者
论文摘要
在本文中，我们提出了Adam-Hash：一种自适应和动态的多分辨率哈希数据结构，用于快速成对求和估计。给定一个数据集$ x \ subset \ mathbb {r}^d $，二进制函数$ f：\ mathbb {r}^d \ times \ times \ mathbb {r}^d \ to \ mathbb {r {r {r} $，以及一个点$ y \ in \ mathbb {r} $ \ mathrm {pse} _x（y）：= \ frac {1} {| x |} \ sum_ {x \ in x} f（x，y）$。对于任何给定的数据集$ x $，我们需要设计一个数据结构，以便给定任何查询点$ y \ in \ mathbb {r}^d $，数据结构大约估计$ \ mathrm {pse} _x _x（y）$，均在$ | x | $ | x | $中均为sub-linear。关于此问题的先前工作仅集中在数据集静态并且查询是独立的情况下。在本文中，我们设计了一个基于哈希的PSE数据结构，该结构适用于更实用的\ textit {dynamic}设置，其中允许插入，删除和替换点。此外，我们提出的Adam-Hash也可以适应自适应PSE查询，在\ Mathbb {r}^d $中，对手可以选择查询$ q_j \ in \ Mathbb {r}^d $，具体取决于先前查询$ q_1，q_1，q_2，q_2，\ dots，q_ dots，q_ {j-1} $。
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}$.
