brainiac

NodeJS library for geographic localization using k-gon clouds in fixed distance.

Many applications answer questions like:

• How many ATMs are within a 5 mile radius from where I am?
• How many banks can I walk to within a mile?
• How many Chipotle restaurants are near my hotel?

These questions are structured as how many Xs are near Y.

Or, given a fixed distance from some query coordinate, give me all locations.

The brainiac structure solves this problem with an augmented BST based on k, referring to the k-Gon clouds placed "about" every location coordinate, and d, the fixed distance.

The brainiac structure uses the haversine formula to compute distance between coordinates.

Read more about the project here.

##usage

var b = require('brainiac');
var brain = b.brainiac(k,d);

// Add coordinates
brain.add(40.7974,-74.481536);
brain.add(34.020029,-118.286931);
brain.add(29.426468,-98.491233);
brain.add(37.62261,-122.37804);
brain.add(61.59938,-149.126804);
brain.add( 39.653671,-104.959502);
brain.add(47.850015,-122.279457);
brain.add(52.114942,-106.632519);
brain.add(47.622767,-122.33668);
brain.add(41.643112,-88.001369);

// Query against the structure
var query = brain.query(41.643155,-88.001322)

// Return queries are of the following format
query === [
	{
		latitude: 41.643112, 
		longitude: -88.001369,
		borders: [...]
	},
	...
]

##efficiency

Compare the brainiac structure to some simple method of iterating through all location coordinates and computing distance to some query coordinate.

The brainiac structure can be written as:

Search an augmented binary search tree for a longitude interval.
Search some augmented binary search tree for a latitude interval over some longitude interval.
For all members of a node's data set within that tree:
	Compare haversine distance to some query coordinate.
	If less than d, add to return list.
Return return list.

Or, in a time complexity analysis as follows:

O(logn) + O(logn) + O(m)

Where m is the average density of these created "interval squares".

Read more about the efficiency here.