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

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

(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.