Range Search

Introduction

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

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

Illustrations

Legend:

• little black dots - data points
• big red dots - current situation
• red areas - area of data points which used for data analisys

K nearest neighbours algorithm

---

Range search algorithm

---

Visit count stats algorithm

See Also

• Dynamic Clustering
• Visit Count Stats