Range Search Task

A range search task is a similarity search task that requires the finding of points within some specified distance [math]\displaystyle{ r }[/math] from a query point [math]\displaystyle{ q }[/math].

• AKA: Distance Range Search.
• 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 [math]\displaystyle{ q \in P }[/math]
    • a Distance Value [math]\displaystyle{ r }[/math] (Radius)
  • output:
    • a Point Set drawn from [math]\displaystyle{ P }[/math].
  • It can be expressed as: [math]\displaystyle{ R(q,r) = \{p \in P \vert d(p,x) \le r \} }[/math]
  • It can be an Approximate Similarity Search Task.
  • It can be solved by a Range Search Algorithm.
• Example(s):
  • "Find all restaurants within a 5 minute walk from here."
  • a Range-based String Matching Task, such as: "Find all strings within 5 string edit operations of citation string [math]\displaystyle{ c }[/math].”
• Counter-Example(s):
  • a Nearest Neighbor Search Task.
  • a Similarity Join Search Task.
• See: Approximate 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.

---