Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

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

Posted on 2009-03-31
5
Medium Priority
?
1,294 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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 750 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

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

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

In this article we will get to know that how can we recover deleted data if it happens accidently. We really can recover deleted rows if we know the time when data is deleted by using the transaction log.
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
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…
In this video you will find out how to export Office 365 mailboxes using the built in eDiscovery tool. Bear in mind that although this method might be useful in some cases, using PST files as Office 365 backup is troublesome in a long run (more on t…

636 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