[OSM-dev] Best and FASTEST Spatial DB for only calculating points near to X?

Christian Vetter veaac.fdirct at gmail.com
Fri Dec 14 20:05:02 GMT 2012


Hi,

If the only thing you are interested in is asking for the amount of points
within a given radius, I would strongly advise not to use a database, but
quickly implement a dedicated data structure for that. That can usually be
an order of magnitude faster than a general purpose database.

E.g. consider a simple KD-Tree [1]:

When doing you query you can simply stop recursion if the current block is
completely within the given circle.
You can implement a KD-Tree in a really lightweight manner, completely
implicitly. Just storing the coordinates, the KD-Tree structure is encoded
in the ordering of them. You can have a look at an example [2]: Have a look
at the function NearNeighbors, it could easily be modified to count the
amount of points instead of returning them.

The only reason I could think of for using a database is, that you have to
handle much more data than fits into memory. However, even in that case a
specialized data structure should perform better - it's only more effort to
implement :-)

Best regards,

Christian Vetter

[1]: http://en.wikipedia.org/wiki/K-d_tree
[2]:
http://code.google.com/p/monav/source/browse/plugins/osmimporter/statickdtree.h

On Fri, Dec 14, 2012 at 7:39 PM, Ander Pijoan <ander.pijoan at deusto.es>wrote:

> Hi all,
>
> I am starting to develope an application that needs of a spatial database.
>
> I'm almost sure that I will use PostGIS because it works great but taking
> into account that I will ONLY make querys to get a number of points near to
> another point and that what I most need is the answer to be fast, could
> there be another database system that might be more suitable for it?
>
> I've seen that MongoDB has a spatial 2D index and I don't know if for the
> operations I'm going to do it could be faster than PostGIS.
>
> I know that being a Friday afternoon it's a difficult question but can
> someone give me some advice about this?
>
> Thank you very much.
>
> --
> Ander Pijoan Lamas
> Research Assistant, Deustotech
> Computer Science Engineer
> University of Deusto
>
> E-mail: ander.pijoan at deusto.es
> Phone: +34 664471228
> in: http://www.linkedin.com/profile/view?id=162888312
>
>
> _______________________________________________
> dev mailing list
> dev at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20121214/1f08fc9f/attachment.html>


More information about the dev mailing list