Solved

Search Canadian Postal Codes within given Radius (using Longitude & Latitude)

Posted on 2009-03-31
5
1,201 Views
Last Modified: 2012-05-06
Hello, I want to be able to implement a search, where it returns all Canadian Postal Codes, that is within a given Radius of another Canadian Postal Code.
Before I do so, I'd like to hear some opinions from experienced professionals, about the correct design.
I find that my way is a little overkill or very brute, (or maybe I'm actually right, i need confirmation)..

------------------------------------------------------------------------
----- Given:
- Using Asp.net 2.0, C#

- Sql Server 2005

- An import file with all postal code with longitude and latitude in the following format:
Code /  Longitude /  Latitude  
(ie, L3M 2Z9 / 2001245 / -45754)

- Formula to calculate 2 points on Earth:
6371 km * cos-1(cos(Long1-Long2)cos(Lat1)cos(Lat2)+sin(Lat1)sin(Lat2))
               6371km is the Radius if Eath.

- There is almost 1 000 000 postal codes in Canada.
------------------------------------------------------------------------
----- Specs & Requirements
- User enters a Canadian Postal Code and a Radius range (km), all Postal Code within that range shall be displayed.

- The search query must perform better than 1 second, the lower the better


-----------------------------------------------------------------------------------------------
---- My initial Approach:

So I hope it's clear up to here.
Now how do I do this?
Let me tell you what I was originally thinking of doing. It's the most straightforward concept you can think of. Import all, and compute all at each search:

- Import the whole import file to Sql Server Database, where the table has 3 fields:
PostalCode, Longitude, Latitude

- When user press Search (with Postal Code and Radium (km) given)
The query would look something like this: (Parameters: ~PostalCode~, ~Radius~)

Select t1.* from tblPostalCode t1, tblPostalCode t2
where (6371 km * cos - 1( cos( t1.Longitude  - t2.Longitude) cos( t1.Latitude) cos( t2..Latitude) + sin(t1.Latitude) sin(t2..Latitude))) <= ~Radius~
and t2.PostalCode =  ~PostalCode~

-----------------------------------------------------------------------
----- My Concerns
I haven't dont this yet. But I estimate that this query would take forever
There is almost a million postal codes in Canada. Not to mention it might extend to Us Zip code in the future, but let's put that aside for now.
In my query.. it would have to compute that formula a million time. I think it's a bit dumb.              

What do you think? Is there an official way to do this? Maybe another DB design, with some pre-calculation/work at Import instead? I can't have user wait for more than a second per search.

Thank you very much! :)
0
Comment
Question by:chshwong
  • 2
  • 2
5 Comments
 
LVL 2

Expert Comment

by:FJS159
ID: 24032468
You could limit the data it has to search through by matching on the first letter of the postal code since each province would be different.  That would cut you down to only having to do the calculations on a few hundred thousand.  You may want to include bordering provinces, but no need to do calculations on BC if you are looking in Ontario.
0
 

Author Comment

by:chshwong
ID: 24035648
Thanks FJS159

I'm sure filtering province through first letter would already be a great start.
Already around 10 times less comparison.

Anything else?

Thanks! :)
0
 
LVL 2

Accepted Solution

by:
FJS159 earned 250 total points
ID: 24040200
Here are some links for people who have done something similar.
http://blogs.lessthandot.com/index.php/DataMgmt/DataDesign/sql-server-zipcode-latitude-longitude-pr
http://www.petefreitag.com/item/622.cfm
http://www.zipcodeworld.com/samples/distance.mssql.html
http://www.easypeasy.com/guides/article.php?article=64

for speed of the query are you indexing the long, lat and postal code fields?
If you are using SQL 2005 you may find it faster using CLR.
http://linktosql.wordpress.com/2008/10/08/sqlclr-exercise/
0
 
LVL 16

Expert Comment

by:t0t0
ID: 24073608
I'm not an expert in cartography however, looking at it logiacally, imagine all your postcodes laid out on a grid. Write the XY grid references next to the postcode such as: postcode1, x, y. postcode2, x, y. etc.

Then, you could pick any 2 postcodes say, pc45, 23.45, 98.06 and pc4023, 601.34, 994.03 and calculate their distance using pythagoras' thereom where the right-angled triagle ABC = A:(23.45, 98.06), B:(601.34, 994.03) and C:(577.98, 895.97) where C is x2-x1, y2-y1. The distance is AB (the hypotenuse).

To find the relative distances of other postcodes, you simply read down the list fetching a postcode's XY coordinates, calculate C and find AB. If it falls in range then add the postcode and distance to your target list. By noting the gradient of AB you could also pinpoint it's relative position.

Finally, you could limit your search to fall within a limited range. The limited range is (x1 + or - range) for x2 and (y1 + or - range) for y2.

0
 
LVL 16

Expert Comment

by:t0t0
ID: 24136069
Hiya chshwong

Please confirm whether you need further assistance with this question
0

Featured Post

Efficient way to get backups off site to Azure

This user guide provides instructions on how to deploy and configure both a StoneFly Scale Out NAS Enterprise Cloud Drive virtual machine and Veeam Cloud Connect in the Microsoft Azure Cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

by Mark Wills Attending one of Rob Farley's seminars the other day, I heard the phrase "The Accidental DBA" and fell in love with it. It got me thinking about the plight of the newcomer to SQL Server...  So if you are the accidental DBA, or, simp…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
Two types of users will appreciate AOMEI Backupper Pro: 1 - Those with PCIe drives (and haven't found cloning software that works on them). 2 - Those who want a fast clone of their boot drive (no re-boots needed) and it can clone your drive wh…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

856 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question