Dynamic Enumeration of Similarity Joins
Dynamic Enumeration of Similarity Joins
复制标题
DOI：
10.4230/lipics.icalp.2021.11
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
P. Agarwal;Xiao Hu;Stavros Sintos;Jun Yang
中科院分区：
文献类型：
--
作者：
P. Agarwal;Xiao Hu;Stavros Sintos;Jun Yang
本文考虑动态更新下相似连接查询的枚举答案：给定$\mathbb{R}^d$中的两组$n$点$A,B$，一个度量值$\phi(\cdot)$和一个距离阈值$r>0$，报告所有与$\phi(a,b) \le r$的点$(a, b) \in A \times B$对。我们的目标是将$A,B$存储到一个动态数据结构中，无论何时要求，都可以枚举具有最坏情况延迟保证的所有结果对，即枚举两个连续对之间的时间是有界的。此外，当在$A$或$B$中插入或删除一个点时，可以有效地更新数据结构。我们提出了几种有效的数据结构来回答低维的相似连接查询。为了精确地枚举相似连接，我们提出了具有$\log^{O(1)} n$更新时间和延迟的$\ell_1, \ell_\infty$指标的近线性大小的数据结构。我们证明这种数据结构对于$d \ge 4$的$\ell_2$度量是不可行的。对于相似连接的近似枚举，其中距离阈值为软约束，我们获得了$\ell_p$度量的统一线性大小数据结构，具有$\log^{O(1)} n$延迟和更新时间。在高维情况下，我们利用局部敏感哈希（LSH）提出了一种具有最坏情况延迟保证的高效数据结构。
This paper considers enumerating answers to similarity-join queries under dynamic updates: Given two sets of $n$ points $A,B$ in $\mathbb{R}^d$, a metric $\phi(\cdot)$, and a distance threshold $r>0$, report all pairs of points $(a, b) \in A \times B$ with $\phi(a,b) \le r$. Our goal is to store $A,B$ into a dynamic data structure that, whenever asked, can enumerate all result pairs with worst-case delay guarantee, i.e., the time between enumerating two consecutive pairs is bounded. Furthermore, the data structure can be efficiently updated when a point is inserted into or deleted from $A$ or $B$. We propose several efficient data structures for answering similarity-join queries in low dimension. For exact enumeration of similarity join, we present near-linear-size data structures for $\ell_1, \ell_\infty$ metrics with $\log^{O(1)} n$ update time and delay. We show that such a data structure is not feasible for the $\ell_2$ metric for $d \ge 4$. For approximate enumeration of similarity join, where the distance threshold is a soft constraint, we obtain a unified linear-size data structure for $\ell_p$ metric, with $\log^{O(1)} n$ delay and update time. In high dimensions, we present an efficient data structure with worst-case delay-guarantee using locality sensitive hashing (LSH).