2026-08-10T23:54:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14080 2024-03-06T10:53:25Z ddc:004 open_access

Dynamic Enumeration of Similarity Joins Agarwal, Pankaj K. Hu, Xiao Sintos, Stavros Yang, Jun dynamic enumeration similarity joins worst-case delay guarantee 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 𝓁₁, 𝓁_∞ metrics with log^{O(1)} n update time and delay. We show that such a data structure is not feasible for the 𝓁₂ 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 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Xiao Hu and Stavros Sintos and Jun Yang 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.11 urn:nbn:de:0030-drops-140803 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.11 eng https://creativecommons.org/licenses/by/4.0/legalcode