I am currently involved in a project where the program I am writing is supposed to return a list of the 10 doctors nearest to a visitor's zip code. Note that this is not the same as doctors in a given radius (say 10 miles), but it does use the same basic formula. This article will be the first of a two part series and lays the groundwork for calculating what is nearest to a zip code. In the second part I intend to show how I integrate this logic with a list of doctors with addresses.
Below you will find the results of my experimental queries that compare the classic radius methodology with my own "10 nearest" methodology. My production program uses a UDB (DB2) database, and I thought of the performance contrasts between UDB and MySQL was interesting, so I am going to show all the comparisons below. Finally, I wanted to show what differences there were between the more accurate "Haversine Formula" as compared to the less intensive "Spherical Law of Cosines" when calculating the distance between two points on a sphere. These examples should give you plenty of real life code you can use in your own programs.
The company I work for subscribes to the zip code database (referred to here as ZipUSA) from http://www.zipdatafiles.com/data/ The data comes from the United States Postal Service and other sources, but I have occasionally found strange geocoding results. I will probably write a different article about that using a different application that I have written.Within 10 miles
Haversine Formula
The following finds the zip codes within 10 miles of 27712 using the haversine (great circle) equation. The field names are based on the ZipUSA tables.
SELECT DISTINCT
destination.zip_code,
3956 * 2 * ASIN(SQRT(
POWER(SIN((origin.lat - destination.lat) * 0.0174532925 / 2), 2) +
COS(origin.lat * 0.0174532925) *
COS(destination.lat * 0.0174532925) *
POWER(SIN((origin.lng - destination.lng) * 0.0174532925 / 2), 2)
)) distance
FROM
tblZipUSA origin,
tblZipUSA destination
WHERE
origin.zip_code = '27712'
AND
3956 * 2 * ASIN(SQRT(
POWER(SIN((origin.lat - destination.lat) * 0.0174532925 / 2), 2) +
COS(origin.lat * 0.0174532925) *
COS(destination.lat * 0.0174532925) *
POWER(SIN((origin.lng - destination.lng) * 0.0174532925 / 2), 2)
)) < 10
ORDER BY
distance, zip_code
The ZipUSA database was set up with the same indexes in MySQL and UDB (DB2). Queries in MySQL were run in the phpAdmin tool. The UDB/DB2 queries were run in Quest.
MySQL
| zip_code | distance |
|---|---|
| 27712 | 0 |
| 27704 | 4.75326962990057 |
| 27705 | 5.34287681627437 |
| 27708 | 5.57383981806715 |
| 27503 | 5.58564401941337 |
| 27701 | 6.41245709075393 |
| 27706 | 6.58029004252293 |
| 27709 | 6.59449266010451 |
| 27702 | 6.61586916445661 |
| 27710 | 6.61586916445661 |
| 27711 | 6.61586916445661 |
| 27715 | 6.61586916445661 |
| 27717 | 6.61586916445661 |
| 27722 | 6.61586916445661 |
| 27707 | 8.57121741472298 |
| 27703 | 9.5828790270889 |
| 27278 | 9.58552637370736 |
| 27564 | 9.72570727493623 |
| 27509 | 9.80777888765073 |
Showing rows 0 - 18 (19 total, Query took 2.1139 sec)
DB2/UDB
| zip_code | distance |
|---|---|
| 27712 | 0 |
| 27704 | 4.75326962990023 |
| 27705 | 5.34287681627435 |
| 27708 | 5.57383981806714 |
| 27503 | 5.58564401941335 |
| 27701 | 6.41245709075397 |
| 27706 | 6.58029004252301 |
| 27709 | 6.5944926601046 |
| 27702 | 6.61586916445641 |
| 27710 | 6.61586916445641 |
| 27711 | 6.61586916445641 |
| 27715 | 6.61586916445641 |
| 27717 | 6.61586916445641 |
| 27722 | 6.61586916445641 |
| 27707 | 8.571217414723011 |
| 27703 | 9.582879027088699 |
| 27278 | 9.58552637370768 |
| 27564 | 9.725707274936291 |
| 27509 | 9.80777888765007 |
19 rows selected in 35.77 secs.
I was very shocked to have such a slow run time in UDB! I was expecting better performance from a corporate-level product. I also went back and checked all the indexes to verify they were on the same fields as were in my MySQL database. I do not have enough knowledge about UDB to explain why this disparity exists or how one might optimize the query to run better on this platform. I would not think one should have to do that.
Spherical Law of Cosines
SELECT DISTINCT
destination.zip_code,
3956 * ACOS(
SIN(origin.lat * 0.0174532925) * SIN(destination.lat * 0.0174532925) +
COS(origin.lat * 0.0174532925) * COS(destination.lat * 0.0174532925) *
COS((destination.lng - origin.lng) * 0.0174532925)
) AS distance
FROM
tblZipUSA origin,
tblZipUSA destination
WHERE
origin.zip_code = '27712'
AND
3956 * ACOS(
SIN(origin.lat * 0.0174532925) * SIN(destination.lat * 0.0174532925) +
COS(origin.lat * 0.0174532925) * COS(destination.lat * 0.0174532925) *
COS((destination.lng - origin.lng) * 0.0174532925)
) < 10
ORDER BY
distance, zip_code
MySQL
| zip_code | distance |
|---|---|
| 27712 | 0 |
| 27704 | 4.75326963012033 |
| 27705 | 5.34287681651191 |
| 27708 | 5.57383981817397 |
| 27503 | 5.58564401945863 |
| 27701 | 6.41245709087189 |
| 27706 | 6.58029004273494 |
| 27709 | 6.59449266019943 |
| 27702 | 6.61586916464669 |
| 27710 | 6.61586916464669 |
| 27711 | 6.61586916464669 |
| 27715 | 6.61586916464669 |
| 27717 | 6.61586916464669 |
| 27722 | 6.61586916464669 |
| 27707 | 8.57121741478871 |
| 27703 | 9.58287902708428 |
| 27278 | 9.58552637385399 |
| 27564 | 9.72570727482013 |
| 27509 | 9.80777888768795 |
Showing rows 0 - 18 (19 total, Query took 1.9229 sec)
DB2/UDB
| zip_code | distance |
|---|---|
| 27712 | 0 |
| 27704 | 4.75326963012037 |
| 27705 | 5.3428768165119 |
| 27708 | 5.57383981817396 |
| 27503 | 5.58564401945862 |
| 27701 | 6.41245709087191 |
| 27706 | 6.58029004247087 |
| 27709 | 6.59449266019946 |
| 27702 | 6.61586916438409 |
| 27710 | 6.61586916438409 |
| 27711 | 6.61586916438409 |
| 27715 | 6.61586916438409 |
| 27717 | 6.61586916438409 |
| 27722 | 6.61586916438409 |
| 27707 | 8.571217414991439 |
| 27703 | 9.58287902726561 |
| 27278 | 9.58552637385398 |
| 27564 | 9.72570727482014 |
| 27509 | 9.807778887510789 |
19 rows selected in 11.05 secs.
It is obvious that using the Spherical Law of Cosines equation is much faster than the Haversine Formula. MySQL shows a 5% improvement in speed and UDB shows a 53% performance improvement. It is also obvious that the distances calculated are very close. For these mile calculations, the first seven decimal places are the same. In most applications I have seen, the miles are rounded off to two decimal places, meaning that there is no reason to use the Haversine formula for distances as far apart as most "centers of zip codes" are. Haversine calculations are more suited to much closer calculations. Also, since zip code to zip code distances are only used for approximate distances, it would not make sense to nit-pick over the only-so-slightly more accurate results the Haversine formula gives. And even beyond that, accuracy depends a lot on the latitude and longitude data supplied. I have found that different sources have different geocoding information concerning the geographic center of zip codes.
10th closest
The next part of this experiment was to find the 10 nearest zip codes to the one given. The first step is finding out which zip ranks number 10. In this case it is simply a matter of choosing the 10th zip code from the list.
Haversine Formula
SELECT DISTINCT
destination.zip_code,
3956 * 2 * ASIN(SQRT(
POWER(SIN((origin.lat - destination.lat) * 0.0174532925 / 2), 2) +
COS(origin.lat * 0.0174532925) *
COS(destination.lat * 0.0174532925) *
POWER(SIN((origin.lng - destination.lng) * 0.0174532925 / 2), 2)
)) distance
FROM
tblZipUSA origin,
tblZipUSA destination
WHERE
origin.zip_code = '27712'
ORDER BY
distance, zip_code
LIMIT 10, 1
| Zip Code | Distance |
|---|---|
| 27711 | 6.61586916445661 |
Showing rows 0 - 0 (1 total, Query took 3.4441 sec)
Spherical Law of Cosines
SELECT DISTINCT
destination.zip_code,
3956 * ACOS(
SIN(origin.lat * 0.0174532925) * SIN(destination.lat * 0.0174532925) +
COS(origin.lat * 0.0174532925) * COS(destination.lat * 0.0174532925) *
COS((destination.lng - origin.lng) * 0.0174532925)
) AS distance
FROM
tblZipUSA origin,
tblZipUSA destination
WHERE
origin.zip_code = '27712'
ORDER BY
distance, zip_code
LIMIT 10, 1
| zip_code | distance |
|---|---|
| 27711 | 6.61586916464669 |
Showing rows 0 - 0 (1 total, Query took 3.1833 sec)
10th Closest Without PO Box Zip Codes
If you have a stiuation where you will be working only with street addresses and can eliminate the zip codes, there is some performance improvement. In the ZipUSA tables, this is accomplished by placing fac_cd and zip_class in the WHERE clause. However, I soon found that 1) some of our doctors are using P.O. Boxes, and 2) some small towns only have post offices with PO Boxes. I ended up not using that further past this experiment.
SELECT DISTINCT
destination.zip_code,
(3956 * (2 * ASIN(SQRT(
POWER(SIN(((origin.lat-destination.lat)*0.017453293)/2),2) +
COS(origin.lat*0.017453293) *
COS(destination.lat*0.017453293) *
POWER(SIN(((origin.lng-destination.lng)*0.017453293)/2),2)
)))) distance
FROM
tblZipUSA origin,
tblZipUSA destination
WHERE
origin.zip_code='27712'
AND destination.fac_cd = 'P'
AND destination.zip_class != 'P'
ORDER BY distance
LIMIT 10,1
| Zip Code | Distance |
|---|---|
| 27703 | 9.58287927196898 |
Showing rows 0 - 0 (1 total, Query took 2.4226 sec)
Nearest 10
Now that we can find the 10th closest zip code, we can join the two types of queries together to find all the zip codes up to the closest 10th. As a pleasant side effect, if there is a tie for 10th place, all of those zip codes are included as well. This becomes particularly obvious in the case where several P.O. Box zip codes are served from the same post office, and thus have the same geocoding. Of course, it is possible that there will be two or more physically distinct zip codes that will be equidistant from a given reference zip code, but I can only imagine that would be a very rare case.
Haversine Formula
SELECT DISTINCT
destination.zip_code,
3956 * 2 * ASIN(SQRT(
POWER(SIN((origin.lat - destination.lat) * 0.0174532925 / 2), 2) +
COS(origin.lat * 0.0174532925) *
COS(destination.lat * 0.0174532925) *
POWER(SIN((origin.lng - destination.lng) * 0.0174532925 / 2), 2)
)) distance
FROM
tblZipUSA origin,
tblZipUSA destination,
(
SELECT DISTINCT
destination1.zip_code,
3956 * 2 * ASIN(SQRT(
POWER(SIN((origin1.lat - destination1.lat) * 0.0174532925 / 2), 2) +
COS(origin1.lat * 0.0174532925) *
COS(destination1.lat * 0.0174532925) *
POWER(SIN((origin1.lng - destination1.lng) * 0.0174532925 / 2), 2)
)) distance
FROM
tblZipUSA origin1,
tblZipUSA destination1
WHERE
origin1.zip_code = '27712'
ORDER BY
distance, zip_code
LIMIT 10, 1
) zipDistance
WHERE
origin.zip_code = '27712'
AND
3956 * 2 * ASIN(SQRT(
POWER(SIN((origin.lat - destination.lat) * 0.0174532925 / 2), 2) +
COS(origin.lat * 0.0174532925) *
COS(destination.lat * 0.0174532925) *
POWER(SIN((origin.lng - destination.lng) * 0.0174532925 / 2), 2)
)) <= zipDistance.distance
ORDER BY
distance, zip_code
| zip_code | distance |
|---|---|
| 27712 | 0 |
| 27704 | 4.75326962990057 |
| 27705 | 5.34287681627437 |
| 27708 | 5.57383981806715 |
| 27503 | 5.58564401941337 |
| 27701 | 6.41245709075393 |
| 27706 | 6.58029004252293 |
| 27709 | 6.59449266010451 |
| 27702 | 6.61586916445661 |
| 27710 | 6.61586916445661 |
| 27711 | 6.61586916445661 |
| 27715 | 6.61586916445661 |
| 27717 | 6.61586916445661 |
| 27722 | 6.61586916445661 |
Showing rows 0 - 13 (14 total, Query took 5.6745 sec)
Spherical Law of Cosines
SELECT DISTINCT
destination.zip_code,
3956 * ACOS(
SIN(origin.lat * 0.0174532925) * SIN(destination.lat * 0.0174532925) +
COS(origin.lat * 0.0174532925) * COS(destination.lat * 0.0174532925) *
COS((destination.lng - origin.lng) * 0.0174532925)
) AS distance
FROM
tblZipUSA origin,
tblZipUSA destination,
(
SELECT DISTINCT
destination1.zip_code,
3956 * ACOS(
SIN(origin1.lat * 0.0174532925) * SIN(destination1.lat * 0.0174532925) +
COS(origin1.lat * 0.0174532925) * COS(destination1.lat * 0.0174532925) *
COS((destination1.lng - origin1.lng) * 0.0174532925)
) AS distance
FROM
tblZipUSA origin1,
tblZipUSA destination1
WHERE
origin1.zip_code = '27712'
ORDER BY
distance, zip_code
LIMIT 10, 1
) zipDistance
WHERE
origin.zip_code = '27712'
AND
3956 * ACOS(
SIN(origin.lat * 0.0174532925) * SIN(destination.lat * 0.0174532925) +
COS(origin.lat * 0.0174532925) * COS(destination.lat * 0.0174532925) *
COS((destination.lng - origin.lng) * 0.0174532925)
) <= zipDistance.distance
ORDER BY
distance, zip_code
| zip_code | distance |
|---|---|
| 27712 | 0 |
| 27704 | 4.75326963012033 |
| 27705 | 5.34287681651191 |
| 27708 | 5.57383981817397 |
| 27503 | 5.58564401945863 |
| 27701 | 6.41245709087189 |
| 27706 | 6.58029004273494 |
| 27709 | 6.59449266019943 |
| 27702 | 6.61586916464669 |
| 27710 | 6.61586916464669 |
| 27711 | 6.61586916464669 |
| 27715 | 6.61586916464669 |
| 27717 | 6.61586916464669 |
| 27722 | 6.61586916464669 |
Showing rows 0 - 13 (14 total, Query took 5.1353 sec)
So there you have it. In the second part of this series I will show how I use this same kind of logic to find the 10 closest locations from a database of addresses. Until then, enjoy!
