Difference between revisions of "Range Search"

From Robowiki
Jump to navigation Jump to search
(Range search description. Please, somebody - fix my typo and grammar errors)
m (link to R-Tree implementation added)
 
(7 intermediate revisions by 4 users not shown)
Line 1: Line 1:
−
=== Introduction ===
+
'''Range search''' is a data analysis algorithm, which is very similar to [[Dynamic Clustering|k-NN]] algorithm. The main difference is that k-NN gets a fixed number of data points while range search does not.
−
Range search - it's data analysis algorithm, which is very similar to knn. The main difference is, that knn increases area (sphere or hypercube) until it contains required amount of data points, but range search do not do it.
 
−
=== How it works ===
 
−
Record state (aka situation, turn snapshot etc.) with some set of attributes (velocity, acceleration, x, y, etc.). When you need in data, calculate some hypercube with center in current situation. For example current situation is {velocity = 8, acceleration = 0, x = 200, y = 200}, then hypercube can be described as set if intervals {[6;8], [0;0], [180; 220], [180, 220]}. Then iterate through all data and select these points, which are contained by this hypercube. Then use this data points for targeting, movement or elsewhere
 
  
−
=== Advantages ===
+
== How it works ==
−
The main advantage against knn algorithm is getting only corresponding data. knn algorithm can get too many not corresponding data, until gets k data points or get too little corresponding data, if k is much lesser, then data points around current situation
+
Record state (aka situation, turn snapshot, etc.) with some set of attributes (velocity, acceleration, x, y, etc.). When you need data, calculate some hypercube centered at the current situation. For example, if the current situation is {velocity = 8, acceleration = 0, x = 200, y = 200}, then hypercube can be described as the set of intervals {[6,8], [0,0], [180, 220], [180, 220]}. Then iterate through all data and select the points that are contained by this hypercube. Then use these data points for targeting, movement, etc.
  
−
=== Illustrations ===
+
== Advantages & Disadvantages ==
−
Legend:
+
The main advantage of range searching over the k-NN algorithm is that range searching gets only corresponding data. The k-NN algorithm can get data points that do not correspond to the current situation if ''k'' is too high for the current data, or it may ignore relevant data, if ''k'' is much less than the number of data points 'around' the current situation.
−
* little black dots - data points
 
−
* big red dots - current situation
 
−
* red areas - area of data points which used for data analisys
 
−
[[File:Knn.gif|K nearest neighbours algorithm]]
 
−
K nearest neighbours algorithm
 
  
−
----
+
But at the same time, with lesser data (i.e. at the beginning of the match), k-NN algorithm can utilize all data available automatically, while range searching, like visit count stats, may get limited or no data at all. This does not apply in multiple buffers system.
  
−
[[File:Rs.gif|Range search algorithm]]
+
== Illustrations ==
−
Range search algorithm
+
Legend:
−
 
+
* little black dots ({{dot}}) - data points
−
----
+
* big red dots (<span style="color:red;font-size:200%;line-height:50%">{{dot}}</span>) - current situation
−
 
+
* red areas - area of data points used for data analysis
−
[[File:Vcs.gif|Visit count stats algorithm]]
+
{| border="1" cellspacing="0" cellpadding="5"
−
Visit count stats algorithm
+
| [[File:Knn.gif|K nearest neighbours algorithm]] || [[File:Rs.gif|Range search algorithm]] || [[File:Vcs.gif|Visit count stats algorithm]]
 +
|-
 +
|align="center"| [[Dynamic Clustering|k-nearest neighbours]] algorithm<br/>with Euclidian distance formula ||align="center"| '''Range search''' algorithm ||align="center"| [[Visit Count Stats]] algorithm
 +
|}
  
−
== See Also ==
+
== See also ==
−
* [[Dynamic Clustering]]
+
* [[Dynamic Clustering]] (k-nearest neighbors)
 
* [[Visit Count Stats]]
 
* [[Visit Count Stats]]
 +
* [[User:Jdev/Code/R_Tree|R-Tree implementation]]
  
 
[[Category:Log-Based Algorithms]]
 
[[Category:Log-Based Algorithms]]

Latest revision as of 12:57, 20 December 2011

Range search is a data analysis algorithm, which is very similar to k-NN algorithm. The main difference is that k-NN gets a fixed number of data points while range search does not.

How it works

Record state (aka situation, turn snapshot, etc.) with some set of attributes (velocity, acceleration, x, y, etc.). When you need data, calculate some hypercube centered at the current situation. For example, if the current situation is {velocity = 8, acceleration = 0, x = 200, y = 200}, then hypercube can be described as the set of intervals {[6,8], [0,0], [180, 220], [180, 220]}. Then iterate through all data and select the points that are contained by this hypercube. Then use these data points for targeting, movement, etc.

Advantages & Disadvantages

The main advantage of range searching over the k-NN algorithm is that range searching gets only corresponding data. The k-NN algorithm can get data points that do not correspond to the current situation if k is too high for the current data, or it may ignore relevant data, if k is much less than the number of data points 'around' the current situation.

But at the same time, with lesser data (i.e. at the beginning of the match), k-NN algorithm can utilize all data available automatically, while range searching, like visit count stats, may get limited or no data at all. This does not apply in multiple buffers system.

Illustrations

Legend:

  • little black dots ( · ) - data points
  • big red dots ( · ) - current situation
  • red areas - area of data points used for data analysis
K nearest neighbours algorithm Range search algorithm Visit count stats algorithm
k-nearest neighbours algorithm
with Euclidian distance formula		 Range search algorithm Visit Count Stats algorithm

See also

Retrieved from "http://robowiki.net/w/index.php?title=Range_Search&oldid=23171"