Dynamic Enumeration of Similarity Joins

Abstract

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 $\varphi (\cdot )$, and a distance threshold $r>0$, report all pairs of points $(a,b)\in A\times B$ with $\varphi (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).