4

Let's say I have a geographical map, where points are represented by latitude\longitude. I have a number of points on this map, and points could be added\deleted\moved at any time.

What I need is, to get the "hottest spots" - the areas that include the highest numbers of points divided by area - or in other words, the areas with the highest density of points.

I need an efficient data structure and also an algorithm that re-calculates the hottest spots on any change. The computational complexity and memory complexity must be minimal, because the number of points could get very high.

I wish to know and maintain a list of the hottest spots in descending order - the most crowdest area first, then the less crowded areas. It's OK to have a list of limited size - for example, the 100 hottest spots.

Of course, to prevent 100% density on one isolated point, there is a minimal area (defined as a constant).

The definition of "area" here is any perceivable area on the map that contains points. It could be the whole map, but the algorithm shouldn't see that as a hot spot of course =)

Thanks ahead! If it needs any clarification please say so...

SirKnigget
  • 3,614
  • 2
  • 28
  • 61
  • I'm mainly investigating, because I don't even know what is the knowledge area in algorithms that could help me answer this question... There is a "raw force" solution that isn't very efficient as you could imagine. – SirKnigget Mar 09 '11 at 13:20
  • How do you define a area? What is the maximum distance between two points for them to be considered in the same area? or have you already have the areas somehow defined already? – Mario Duarte Mar 09 '11 at 13:29
  • Because I need a result in descending order, it doesn't matter as long as the first result will have higher density than the second, and so on... There must be a minimum of course for an "area" to prevent 100% density for one isolated point (will add that to main question of course). – SirKnigget Mar 09 '11 at 13:37
  • Maybe clustering algorithms may help. Searching for "k-means" or perhaps even "SVM" can be a good start. The problem is as difficult to be stated precisely as to be solved. – Alexandre C. Mar 09 '11 at 15:13

3 Answers3

5

What you are doing is statistically known as '2-dimensional density estimation' (so you know where to look).

One common method is 'kernel smoothing'. Imagine a disc sitting on each of your data points. The kernel smoothing over the area is the number of discs overlapping at each point. That's a kernel smoothing using a uniform kernel of fixed radius.

You don't have to use uniform kernels, nor do they have to be the same size at all points - this is now "adaptive bandwidth kernel smoothing".

That gives you a grid which you can update pretty easily, especially if you have a finite kernel (you can use a Gaussian (aka Normal) kernel which is infinite, but would be clipped to your study area). Every time you add or take away a point, you add or take away its kernel's contribution to the density.

So that's half the problem - you now have a grid of densities. Then you can use clustering algorithms to partition it and find separate peaks according to whatever criteria a) defines a 'peak' and b) defines it as separate from an adjacent peak. Someone else has already suggested clustering algorithms. I have done this (ten years ago) using clustering functions in "R", the statistical package. Speed isn't its strong point though...

You might want to take this over to http://stats.stackexchange.com

Spacedman
  • 92,590
  • 12
  • 140
  • 224
  • Good idea. The OP now may want to find contour lines of a smooth function, which can be done locally. The problem is that points move. – Alexandre C. Mar 09 '11 at 16:16
  • An improvement may be to store the points into a quadtree and use a compactly supported radial kernel in order to be able to compute the estimated density quickly at any point of the map. Then, compute contour level at a fixed height (say 10, assuming unit-peaked kernel) -- I can expand on this if you want. Each time a point moves, gets deleted, or added, the parts of the contour level curves which need to be recomputed are located thanks to the quadtree and bounded support of the kernel function. The hotspots are given by the connected components of the interior of the contour level lines. – Alexandre C. Mar 09 '11 at 16:32
  • I understood the disc analogy - beyond that seems like a field of knowledge that I'll either have to get into, or find someone else that will. What would be a good reference for that? How would you approach the problem of partitioning? Just for getting this clear - let's say I have a lot of point in the city of New York - One concentration is in Central Park and another concentration is at the Statue of Liberty. I want to discern between those two separate hot spots, but also have the whole city as the third densest hot spot (according to the area / # of points definition). – SirKnigget Mar 10 '11 at 00:03
2

This is too long for a comment but here's just an idea as to how I'd "play" with this and see if I can come up with something interesting. But one thing is sure: the following can be made to be very fast.

Can this be easily translated to some discrete problem? You'd first "align" all your coordinates to a big map (you define how much each square is big and you make every entry map to one such point). You'd then end up with something like this:

0000000000000000000000000000
00XX000000000000000000X00000
00X00000000000000X0000000000
0000000000000000000000000000
0000000000000000000000000000
000000X00000000X000000000000
0000000000000000000000000000
000000000000X000000000X00000
00000000000000000000000X0000
0000000000000000000000000000

Then you'd compute each entry and it's number of adjacent neighbours:

0000000000000000000000000000
0033000000000000000001000000
0030000000000000010000000000
0000000000000000000000000000
0000000000000000000000000000
0000001000001001000000000000
0000000000000000000000000000
0000000000001010000000200000
0000000000000000000000020000
0000000000000100000000000000

Then you can augment the size of your square, say by two, and hence divide your map:

(the map ain't correct, it's jut to give an idea of what I'm thinking about)

09001001000000
00000000000000
00100001100000
00000110002000
00000002000000
00000100000000

Then you re-count the adjacent neighbours, etc.

To me this would allow to find hotspot depending on your "resolution": you'd simply look for the biggest numbers and that would be your "hotspots".

Because in this case:

0000X00000
0000XX0000
0000000000
0000000000
0Y0Y000000
0000000000
0Y0Y000000

Either 'X' can be the hottest spot (three interesting point close to each other) or 'Y' (four points close to each other, but they're not as close than for the 'X').

Because you said you needed speed, I'd just turn this into a discrete problem and represent my graphs as arrays. I'd then allow for a variable "area" size.

Looks like a fun problem to work on :)

SyntaxT3rr0r
  • 27,745
  • 21
  • 87
  • 120
  • Nice idea for starting, one addition to this - a "point" in your representation could include multiple entries, so it needs to consider this. Replace the 'X's with the number of entries in that coordinate, then refine the calculation. – SirKnigget Mar 09 '11 at 23:54
1

The type of algorithm used will depend on the distribution of points. You could very well run into a much harder problem of group partitioning into "areas." Since you seem to need something to get you started, I recommend you read up on Convex Hulls and calculating the area of an abritray 2D polygon and how to determine if a point is in a polygon.

Community
  • 1
  • 1
Andrew White
  • 52,720
  • 19
  • 113
  • 137