4

I have about a million points like this:

  • Latitude
  • Longitude
  • Text (short text of less than 128 characters)

I am writing an app that must quickly show what points are around the user.

User: I am at lat0,long0. What points are around me?
Server: Nearest to you is lat1,long1 then lat2,long2 then [...] then lat100,long100.
[User scrolls through the points]
User: I have checked this first hundred points. Give me more.
Server: Next nearest to you is lat101,long101 then lat102,long102 then [...] then lat200,long200.

Once per day, new points data arrive, replacing all existing points. This reload should not interrupt the requests for more than a minute. Serving old data while loading the new data would be great in order to have zero interruption.

Requirements:

  • Open source
  • Gratis
  • I can load new data into it via an API, or via command line on the same server
  • Efficient paging (when user scrolls wildly and generates many requests, the response time to these requests do not get slower and slower)
  • Requires as little maintenance as possible
  • Lightweight. In particular, I would prefer to avoid a full-text search server that happens to also have spatial features.
  • Runs on a VM with 1GB of RAM and a modest processor

Bonus if it also handles "categories": Each point has a category, and the user can ask for only points of a certain category, there are mo more than 20 categories. No need for text search, the text associated with each point is not something anybody will ever search for. All data is public, so no need for authentication. Can use any coordinate system, I will adapt.

Improve this question
6
  • @Thomas: I added all details you asked for, is it OK? :-) Full text search will not work here, you can not get the point nearest to 21.837642,76.234823 by searching the database for "21.837642" and "76.234823", because these strings do not exist in database. You can not use < and > operators either, because resulting points would be inside a rectangle instead of inside a circle.
    – Nicolas Raoul ♦
    Aug 30 '16 at 9:55
  • Thanks for the update. Full text search on the text, of course, not on the points. (The rectangle may still be useful, because it narrows the points in question: you only need to check the points in the rectangle to make it a circle. But these are implementation details. Let's see what answers you get.)
    – Thomas Weller
    Aug 30 '16 at 11:04
  • How would you like the paging done? With radially increasing distance?
    – CPerkins
    Aug 30 '16 at 13:44
  • @Thomas: As stated in the last paragraph, I don't want to perform any text search. Only spatial search is involved here, not text search. The text is irrelevant, often it is only a random number.
    – Nicolas Raoul ♦
    Aug 30 '16 at 15:12
  • @CPerkins: Yes, exactly. The first query would return points contained within a disc, then the subsequent queries would returned points contained in further and further concentric annuluses ("rings"). FeSimpleGeoProx and Georedis have most of the math needed, but they lack a server interface... if possible I would prefer to avoid developing my own server.
    – Nicolas Raoul ♦
    Aug 30 '16 at 15:20
1

Would Postgres (with PostGIS) be too heavy duty? It would handle searching a million points and live on-the-fly updates with ease.

Postgres is a full RDBMS - PostGIS is the name of the geospatial extensions. (Oracle and SQL Server also have good geospatial extensions, they're not open source though; MySQL's are poor). The geospatial extensions allow you to perform SQL queries using the geometry of the shapes. You're only working with simple points but this can include complex polygons. A query for all locations within radius miles of a lon,lat coord would be something like:

SELECT * FROM your_table
WHERE ST_Distance(the_geom, ST_MakePoint(lon,lat)) <= radius * 1609.34

(the_geom would be the geometry column on your data table)

A roll-you-own approach would use a KD tree. With only 1GB RAM, you'd probably have to keep the index on disk - so an SSD for speed. The data loading would have to create a new index file, and then swap it in.

(Not gratis, but I could be hired to code up the index itself if you were interested)

Improve this answer
1
  • PostGIS sounds good! Feel free to add more details about that solution :-)
    – Nicolas Raoul ♦
    Jul 17 '19 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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