Similarity Join Search Task

A Similarity Join Search Task is a Similarity Search Task that requires finding all of the points within some specified distance from each other.

• Context:
  • Input:
    • a Metric Space [math]\displaystyle{ M }[/math] (with Point Set [math]\displaystyle{ P }[/math] and Distance Function [math]\displaystyle{ d }[/math]).
    • a Query Point q ∈ P
    • a Distance Value r
  • output:
    • a Point Set Relation of points in [math]\displaystyle{ P }[/math] with distance [math]\displaystyle{ r }[/math] from each other.
  • It can be an Approximate Similarity Search Task.
  • It can be solved by a Similarity Join Search Algorithm.
• Example(s):
  • What are all pairs of cities and gravel deposits that are apart by less than 12 hours shipping. (can assist with detecting which cities are overserved and which are underserved).
• See: Range Search Task.

---

---

References

2007

• (Zezula et al., 2007) ⇒ Pavel Zezula, Giuseppe Amato, and Vlastislav Dohnal. (2007). “Similarity Search - The Metric Space Approach." Tutorial at ACM SAC 2007.

2006

• (Zezula et al., 2006) ⇒ Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, and Michal Batko. (2006). “Similarity Search: The Metric Space Approach." Springer, Advances in Database Systems.

---