Solved

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

Posted on 2009-03-31
5
1,180 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

Complete Microsoft Windows PC® & Mac Backup

Backup and recovery solutions to protect all your PCs & Mac– on-premises or in remote locations. Acronis backs up entire PC or Mac with patented reliable disk imaging technology and you will be able to restore workstations to a new, dissimilar hardware in minutes.

Join & Write a Comment

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…
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
This video explains how to create simple products associated to Magento configurable product and offers fast way of their generation with Store Manager for Magento tool.
You have products, that come in variants and want to set different prices for them? Watch this micro tutorial that describes how to configure prices for Magento super attributes. Assigning simple products to configurable: We assigned simple products…

759 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

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now