Dynamic Enumeration of Similarity Joins Article Swipe

MAKE IMPACT

Pankaj K. Agarwal , Xiao Hu , Stavros Sintos , Jun Yang · YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2105.01818

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

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2105.01818

PDF

https://arxiv.org/pdf/2105.01818

OA Status

green

Cited By

2

References

43

Related Works

10

OpenAlex ID

https://openalex.org/W3157068322

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W3157068322

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2105.01818

Digital Object Identifier

Title

Dynamic Enumeration of Similarity Joins

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2021

Year of publication

Publication date

2021-05-05

Full publication date if available

Authors

Pankaj K. Agarwal, Xiao Hu, Stavros Sintos, Jun Yang

List of authors in order

Landing page

https://arxiv.org/abs/2105.01818

Publisher landing page

PDF URL

https://arxiv.org/pdf/2105.01818

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2105.01818

Direct OA link when available

Concepts

Enumeration, Join (topology), Similarity (geometry), Joins, Metric space, Combinatorics, Dimension (graph theory), Bounded function, Mathematics, Metric (unit), Cardinality (data modeling), Discrete mathematics, Nearest neighbor search, Hash function, Data structure, Algorithm, Computer science, Data mining, Image (mathematics), Programming language, Operations management, Economics, Artificial intelligence, Mathematical analysis, Computer security

Top concepts (fields/topics) attached by OpenAlex

Cited by

2

Total citation count in OpenAlex

Citations by year (recent)

2021: 2

Per-year citation counts (last 5 years)

References (count)

43

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload