CODEWITHSUNDEEP
algorithmmapsgraph-algorithm
twlkyao
twlkyao

Reputation: 14628

How to find specific dots in lots of dots quickly(Location Based Service)?

I have a map of about tens of millions of dots stand for people's location, now given a dot, how to find the dots(stand for people's location) at a distance in 1 kilo meters from the given dot quickly? What is the best algorithm?

Upvotes: 0

Views: 94

Answers (3)

AbcAeffchen
AbcAeffchen

Reputation: 15017

I think the fastest a fast way is to use a grid to filter all dots that are definitly too far away. to the other dots you can compute the distance exact.

Im not sure how your dots look like. But let a dot be a pair of coordinates (x,y). You can save them sorted (in a database), so it is easy to find all dots (a,b) with x - max_dist < a < x + max_dist and y - max_dist < b < y + max_dist. so you get a little square with only some dots. Now you can compute the exact distance between (x,y) and the dots (a,b) in the square.

This should also work with gps-coordinats. sure, coordinates on a sphere do not form a square, but if the sphere is much larger than the maximum distance it do not matter.

Upvotes: 1

Vikram Bhat
Vikram Bhat

Reputation: 6246

You can use kd tree to get all dots within a particular distance from given point. In dense graph such as yours the problem can be solved in O(logn + k) where k are total points that can be found in the region and n is total points .

Upvotes: 2

mcdowella
mcdowella

Reputation: 19621

Grids sound like a very practical solution, but there are a number of tree-based data structures for this problem as well. The basic idea is that you arrange your data in a tree and add annotations to the tree such as a bounding box at each node which holds all the points held below that node. Then when you search the tree you can work out that you don't need to look in the descendants of most nodes.

http://en.wikipedia.org/wiki/K-d_tree http://en.wikipedia.org/wiki/Cover_tree

Upvotes: 1

Related Questions