CODEWITHSUNDEEP
google-mapshierarchical-clustering
julienp
julienp

Reputation: 51

Map with more than 1 million markers, issue at high zoom level

Context:

Google Map with 1 million markers (object with a lat/long) to display. We use Fluster 2 for clustering.

For zoom level 11 to 21 (assuming there are 21 zoom levels and 21 is the closest to the ground) the computation time for clustering markers (create cluster markers) is fine.

Issue I encounter:

Agglomeration clustering is being slow down after zoom 11 (when the user zooms out from the ground). Given the number of markers, around 1,000,000, I need either a fast computation method or a turnaround.

Btw, I am not interested in commercial solutions.

Upvotes: 2

Views: 2054

Answers (2)

Cybercartel
Cybercartel

Reputation: 12592

You can use a spatial index and reduce the dimension. Then you can pull markers separately on each zoom levels. I wrote a PHP script with many space filling curve and a quadkey for academic purpose. I've also some commercial solution.

To start you can read:

When you need a more accurate search you can still use it to eliminate nearest-neighbor computation with all locations.

Upvotes: 0

Kunukn
Kunukn

Reputation: 2236

Fluster 2 is a javascript which is client side clustering right?

With millions of points you should consider definitely use server side clustering or even pre-cluster points in advance if possible.

This topic is related to this https://stackoverflow.com/questions/986852/clustering-coordinates-on-server-side

With that many points you could make a simple grid-clustering. This is fast technique as mentioned by google http://code.google.com/intl/da-K/apis/maps/articles/toomanymarkers.html#gridbasedclustering

I have made a blog about grid-clustering with example code in C# http://kunuk.wordpress.com/2011/09/15/clustering-grid-cluster.

Interesting question :) In an algorithm design book by jon kleinberg there is mention of calculation of 1.000.000 items gives about 1 sec for O(n) and 20 sec for O(nlogn).

Some tricks should be considered to only use partial of the data in the calculation if you can't keep it O(n).

Upvotes: 1

Related Questions