4

I want to memorize geographical points for fast retrieval:

  1. I store a few {latitude, longitude, Java object}
  2. I query for all objects contained within n kilometers of a particular latitude, longitude

Requirements:

  • Free, open source
  • Pure Java
  • Query within a "rectangle" (defined by lat1,long1-lat2,long2) is also OK but circle preferred
  • Approximations OK, in particular, the app will not be used near the poles
  • Persistence not needed
  • Lightweight. The JAR should not be more than a megabyte, hopefully much less than that.

Non-solutions:

  • GeoRedis is not embedded and not in Java
  • Geo-tree is not in Java
  • GeoTools is too big
  • JTS does not allow to query for all points, judging from its documentation.
Improve this question
0

2 Answers 2

Reset to default
3

It's been several months since you posted your request, but if you still have the need, please consider FeSimpleGeoProx

I think it meets all of your stated requirements: FeSimpleGeoProx is a lightweight collection of user-supplied geographical points which supports fast proximity search by search within a radius or by rectangle.

  • Free, open source (Apache version 2.0 license)
  • Pure Java
  • Supports query within a circle (start point and radius)
  • Supports query within a "rectangle" (defined by lat1,long1-lat2,long2)
  • Multiple objects can be stored at the same latitude/longitude without a workaround.
  • Lightweight. The jars (both FeProxiMap and LatLng on which it depends) are together less than 100K.

In the performance/weight spectrum, it falls between linear search (lightweight but slow: for a reasonable search, this is between 100 and 1000 times faster) and GeoRedis (which is blazingly fast but heavier weight). Also, the documentation on GeoRedis says that its answers are approximate, while these are precisely as exact as LatLng will give.

Disclaimers: I am the author of FeSimpleGeoProx. Also, it relies on the excellent (and also FOSS) SimpleLatLng, which must be downloaded separately.

Improve this answer
7
  • Looks great! Does it behave correctly near the poles, by any chance?
    – Nicolas Raoul ♦
    Commented Jun 20, 2016 at 2:33
  • Thanks, and I think the answer is "yes". I'm relying on SimpleLatLng, which I believe handles points near the poles well - my search thingy is pretty much exactly as correct as SimpleLatLng. My unit tests (which include a data set near the poles), show identical results to brute-force checking of every point in the data set, just much faster for "reasonable" searches.
    – CPerkins
    Commented Jun 20, 2016 at 12:31
  • Cool! Have you tried checking from about how many points FeSimpleGeoProx gets more performant than brute-force?
    – Nicolas Raoul ♦
    Commented Jun 20, 2016 at 13:53
  • Indeed I have. If you run the included performance benchmarks, you'll see that it's much faster (100 to 1000 x) faster on a non-trivial set of points if your search is relatively small: that is, if the returned set of points is a small portion of the total points in the full data set. As the returned dataset size grows, performance degrades, and ultimately, if the search returns all or nearly all (~ 80%) of the points in the world, performance is actually worse than linear search.
    – CPerkins
    Commented Jun 20, 2016 at 15:41
  • @NicolasRaoul If you end up using it, please let me know your experiences. I built it to be useful.
    – CPerkins
    Commented Jun 22, 2016 at 19:51
4

Quadtree is usable:

... but it has some drawbacks:

  • Search is not by radius, it is rectangle.
  • Flat map, won't work near the poles.
  • Two different objects can't be stored at the same latitude/longitude. This can be worked around by making each object a List of objects.
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.