Difference between revisions of "Range Search"
(Range search description. Please, somebody - fix my typo and grammar errors) |
m (some cleanup; let me know if you don't like it.) |
||
| Line 1: | Line 1: | ||
| − | + | '''Range search''' is a data analysis algorithm, which is very similar to [[Dynamic Clustering|k-NN]]. The main difference is that k-NN increases area (sphere or hypercube) until it contains required amount of data points, but range search do not do it. | |
| − | Range search | ||
| − | |||
| − | |||
| − | == | + | == 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 | |
| − | === Illustrations | + | == Advantages == |
| + | The main advantage against knn algorithm is getting only corresponding data. k-NN 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 | ||
| + | |||
| + | == Illustrations == | ||
Legend: | Legend: | ||
* little black dots - data points | * little black dots - data points | ||
* big red dots - current situation | * big red dots - current situation | ||
| − | * red areas - area of data points which used for data | + | * red areas - area of data points which used for data analysis |
| − | [[File:Knn.gif|K nearest neighbours algorithm]] | + | {| border="1" cellspacing="0" cellpadding="5" |
| − | + | | [[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 ||align="center"| '''Range search''' algorithm ||align="center"| [[Visit Count Stats]] algorithm | |
| − | + | |} | |
| − | [[File:Rs.gif|Range search algorithm]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | [[File:Vcs.gif|Visit count stats algorithm]] | ||
| − | Visit | ||
| − | == See | + | == See also == |
| − | * [[Dynamic Clustering]] | + | * [[Dynamic Clustering]] (k-nearest neighbors) |
* [[Visit Count Stats]] | * [[Visit Count Stats]] | ||
[[Category:Log-Based Algorithms]] | [[Category:Log-Based Algorithms]] | ||
Revision as of 15:13, 8 August 2011
Range search is a data analysis algorithm, which is very similar to k-NN. The main difference is that k-NN 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
The main advantage against knn algorithm is getting only corresponding data. k-NN 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
Illustrations
Legend:
- little black dots - data points
- big red dots - current situation
- red areas - area of data points which used for data analysis
 |
 |
|
| k-nearest neighbours algorithm | Range search algorithm | Visit Count Stats algorithm |
See also
- Dynamic Clustering (k-nearest neighbors)
- Visit Count Stats
