Forum OpenACS Q&A: gps to zipcode query: postgres or postgresql + postgis or how?

(Yes, I am excluding perhaps Hawaii and Alaska for now, and I am also assuming that a simple 2D geometry, assuming the GPS coordinates are Euclidean and not spherically based will be good enough to find the closest zip code.)

So assuming something simple like

create table zipcode (
  zcode  integer primary key,
  loc    point
);

I have the zipcode data from the postoffice and it contains lat, lon.  (As I'm sure you guys know....)

I notice that Postgresql already supports the point type.  And I figured how to enter points into the db.

What I haven't figured out how is to make a query that selects other rows that are closed to my target.

select zcode, loc from zipcode where loc ## 'userx, usery';

That seems to fail.

Can someone tell me:

A)  Can I do this in postgresql without using postgis, and if so, how? (and what indices should I create?)
B)  Where a good reference to making queries with the postgres native geometric types can be found?

I'm happy to use postgis, I just don't want to toss an a-bomb after a fly.  If I implement postgis and do this in postgis, would it be faster than the "native" postgres query, and if so, why?

And how would I do this postgis and what sort of index would I need to create?

And hell, all I need is a mapping the fastest way possible.  Given that I have the zipcode => (lat, lon) data, anyone know of any C code to do a spatial search?

Thanks,

select code, point_distance(loc, :X, :Y) as dist
  from zip
 where @ (:X - loc[0]) < x_delta_max
   and @ (:Y - loc[1]) < y_delta_max
 order by dist
 limit 1

to avoid doing an exact distance calculation unless the zipcode you're checking is relatively close to the point you're testing. [xy]_delta_max should be tuned depending on the maximum distance between centers of adjacent zipcode areas in the US.

This may of course have no noticable effect on performance, but it's an obvious first optimisation.

Roberto, I took a look at earthdistance and did some experimenting....  Thanks for pointing this out.  It actually helped me catch an error in my tables where I swapped lat and long.

The USPS gives little information about how much area zipcodes can represent.  The question here is if I need to use earthdistance (which uses a lot of float multiplication and division as well as 5 sin and cos and one acos operation for each measurement) or whether some bad assumptions about our flat planet would suffice and let me use point_distance which should require no trig and probably takes two mults and one square root per measurement.

Googling for a table of State sizes in square miles, and dividing that by the count(*) of zips in that state revealed that except for Alaska, the average size of a zip code is 100 sq. miles with a max of 492 sq miles and a std. deviation of 113 sq miles.

Alaska has an avg zip code size of 2120 sq. miles.

Also, if you examine the max and min latitudes of the zipcodes and you haphazardly guess that Washington or Maine have the highest in the continental US, then it turns out that the US is bounded by about 24 degrees in Florida and about 50 degrees somewhere in Washington.

In Washington, geodistance shows that one degree of latitude is about 44 miles.  In Florida, it's 60 miles, and at the top of Alaska, it's only 26 miles.

So in the lower 48, the average zip code area is 10 miles on a side and one degree of latitude covers 44 miles at the smallest.  Zip codes within the first std. deviation (is it right that that would be 68% of all zip codes?) are root(100 + 113) on a side (assuming square zip code shapes) and zip codes in the first three std. deviations (99%?) are root (100 + 113 + 113 + 113) = 21 miles.

The world IS flat!  As far as this application is concerned, it's safe to ignore geo_distance and just use point_distance, and, in the optimization above, a number like .5 is probably conservative.

And Alaska (a state I really love and I encourage you to visit)  Well as far as this app goes, if you're not within 22 miles of the center of a zip code, well you probably still are interested in the services in that zip code.

So I'll have to be concerned about that, uh, someday.  First thought at that solution, is that if the first query returns no rows, then check to see if you're in the Alaskan zone and rerun it without the the delta_x optimization.

I've come across Egnor's work before.  In fact I am almost positive I found a link to it here, but I cannot find it now (I'm also getting some sort of error when I search for zip (but not when I search for zipcode)).

But uh, I wasn't sure how to make use of Egnor's work.  My take was that it was more a work for Google to implement than one of us.  It involves, if I understood it correctly, crawling the page for patterns that make up addresses, and then associating the 3D location of that address to that page.

So if your query is "show me the stores within 20 miles of here", there is no way that you or I can implement that, that has to be done at google.  I believe.

As a smaller matter, he also acknowledged there was some work to be done on his address patterns, noting IIRC, that while Google lists three addresses on their contact form, his address parser only picked up one of them.