Dynamic enumeration of similarity joins

Journal Article

This paper considers enumerating answers to similarity-join queries under dynamic updates: Given two sets of n points A,B in ℝd, a metric φ(·), and a distance threshold r > 0, report all pairs of points (a, b) ∈ A × B with φ(a, b) ≤ 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 ℓ1, ℓ∞ metrics with logO(1) n update time and delay. We show that such a data structure is not feasible for the ℓ2 metric for d ≥ 4. For approximate enumeration of similarity join, where the distance threshold is a soft constraint, we obtain a unified linear-size data structure for ℓp metric, with logO(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).

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Hu, X; Sintos, S; Yang, J

Published Date

  • July 1, 2021

Published In

Volume / Issue

  • 198 /

International Standard Serial Number (ISSN)

  • 1868-8969

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.ICALP.2021.11

Citation Source

  • Scopus