2

I need a way to get the zipcode of a lat/long pair fast (<10 ms), and at a high rate (thousands of qps)

I've loaded a shapefile from the US Census Bureau into a mysql database with spatial indexing and I've been using the following code to query it:

select
    zipcode
from
    geo.part
where
    ST_Contains(boundary,
            POINT(?, ?))
    LIMIT 1;

It works great, only I'm seeing response times between 20 and 100ms.

Do you have any suggestions to have it run faster?

A different stack? (postgres with postgis maybe?)

The shapefile had quite a lot of points per zipcode, I don't really need that much resolution. Would pruning those files make much of a difference (remove half of the points for each zipcode)?

Something else?

Improve this question
6
  • 2
    mysql is still limited with spatial functions and would recommend a postgres/POSTGIS solution then spatial indexes can be fully utilized for fast geocoding/reverse geocoding.
    – Mapperz ♦
    Commented Oct 7, 2013 at 13:37
  • 1
    The absolute fastest solution will be raster-based, because raster lookup is a O(1) operation (with small implicit constants) whereas shapefile point-in-poly tests are O(log(n)) (n = number of vertices) and have a much larger implicit constant. (Think nanoseconds, not milliseconds.) As with all such optimization situations, there are trade-offs: you need sufficient RAM (or high-speed direct access storage somewhere) to hold the grid, which would require around 6 GB at 100 m resolution, 24 GB at 50 m resolution, and so on. You would need to deal with possible errors near the boundaries, too.
    – whuber
    Commented Oct 7, 2013 at 15:08
  • @ mapperz In some cases mysql can perform better than PostGIS, due to the fact that large geometries are compressed my PostGIS, which makes them disk-bound. See openlife.cc/blogs/2013/april/… and the relevant comments from Leo and other PostGIS committers. Its a very interesting discussion on spatial DB performance.
    – DPierce
    Commented Oct 7, 2013 at 17:16
  • @whuber rasterization sounds interesting, but I can't get the same numbers. Only taking the surface area of the US (which is probably impossible), and 100m2 per pixel, with one byte for each pixel (which isn't enough for a zipcode), I'm getting almost 100GB. wolframalpha.com/input/?i=%28surface+of+the+us+%2F+100+m2%29+*+1+byte
    – Adrian Mester
    Commented Oct 8, 2013 at 13:39
  • @Adrian Let's use common sense. We could cover the US with a rectangle measuring 3000 by 5000 km. That's 15 million cells of 1 km^2 each. The Pizza Principle tells us that filling the same area with squares 0.1 km = 100m on a side will require 1/(0.1)^2 = 100 times as much, which is 15*100 million = 1.5 billion cells. (A more accurate value is 0.98 billion: we're close enough). Wolfram Alpha states, somewhat cryptically, that it is interpreting your input in units of 100 m^2, not (100 m)^2: that's why your answer is 100 times too large.
    – whuber
    Commented Oct 8, 2013 at 14:36

1 Answer 1

Reset to default
2

Polygons with a large number of vertices query more slowly than those with fewer vertices. I've found that unioning 1:100k country boundaries with a 5x5 degree regular grid (resulting in multiple polygons per country, increasing the polygon count by an order of magnitude) permitted Oracle queries under 10ms (an order of magnitude improvement), and when I used an Esri memory-based shape library, I could process millions of identity operations with a mean measured in microseconds.

I'd recommend you evaluate the mean extent of your current polygons and process them with a regular polygon overlay so that the mean extent is cut in half. There is a law of diminishing returns (as the total number of polygons increases, response rate eventually slows), so sometimes you need to try several different sized grids to find the optimal response rate with any given dataset framework.

Improve this answer
1
  • 1
    Good advice in general. Also, ensure you have a spatial index built :) Depending on your accuracy requirement you could also simplify your polygons, removing redundant vertices.
    – Paul Ramsey
    Commented Oct 7, 2013 at 16:32

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.