Differences

This shows you the differences between two versions of the page.

--- admin:optimization:geo:math [2010/07/28 05:05]
els
+++ — (current)
@@ Line 1: / Line 1: @@
-{{page>:top_add&nofooter&noeditbtn}}
-====== Geographic Searches  - Radius Distance Searches ======
-[[admin:optimization:geo:radius|Back to Geographic Searches]]
-===== The Math Behind Radius Distance Searches =====
-The math behind radius searches is somewhat complex, and there are several possible approaches.
-==== Why not use ranges of latitude and longitude? ====
-One might think that the easiest approach would be to simply search for a latitude between //a// and //b//, and a longitude between //c// and //d//.  While this is very simple, it leads to a lot of inaccuracy.  Such a range renders something close to a square rather than a circle.  (In fact, because of the nature of longitudinal lines, it usually produces a near-trapezoid shape.)  The area of a circle is about 78% of the area of a square, so this would lead to a lot of additional rows that are not intended.  Moreover, the corner of the square is about 141% of the radius of the circle, and that would be generally unacceptable.
-==== Remember the Pythagorean algorithm?  ====
-Remember (a<sup>2</sup> + b<sup>2</sup> = c<sup>2</sup>)?  This Pythagorean algorithm calculates the third side of a right triangle, called a hypotenuse.  If the Earth was completely flat, and map coordinates were accurate squares, this would be an easy way to calculate distances.  But alas, the Earth is a sphere, or an egg-shaped, slightly wobbly approximation of a sphere, so Euclidean geometry will not give us the desired result.
-==== Law of Cosines ====
-The Law of Cosines produces a pretty accurate distance, but it is expensive to compute.  Using trigonometric functions, it takes into consideration that the Earth is not flat, but instead is a sphere.
-  acos ((sin(lat1) * sin(lat2)) + (cos(lat1) * cos(lat2) * cos(long1-long2))
-While the Law of Cosines is quite accurate, it cannot be used for all calculations without degrading performance.  Omnidex uses the Law of Cosines when needed, but not all time.
-==== Law of Haversines ====
-The Law of Haversines is more accurate than the Law of Cosines when calculating very small distances.  One must ask, though, what is the purpose of a database-oriented distance search.  Typically, we are looking for all business within a mile of us, or all people within a mile of our business.  The latitude and longitude coordinates can be accurate to within a few feet, but a business address is less precise.  Accuracy within 100 feet satisfies nearly all of these kinds of databases searches.  Therefore, the additional costs of the more-accurate Law of Haversinces are simply not worth the computational overhead.
-==== Omnidex's Approach to Distance Searches =====
-Omnidex takes two distinct approaches to calculating distances.  When calculating pure distances, Omnidex uses the Law of Cosines to insure sufficient accuracy.  However, when performance indexed searches for all rows within a given radius, it takes a more sophisticated approach that combines performance and accuracy.
-Omnidex recognizes that most searches are for medium range distances, such as a radius of 1 to 100 miles.  Database applications don't typically ask for businesses within 10,000 miles, nor businesses within 100 feet.  Omnidex tunes its algorithms for these medium range distances to achieve a combination of performance and accuracy.
-Within these medium range distances, the varying accuracy of the algorithms only affects those rows that are near the perimeter of the circle.  In a search for rows within five miles, those rows that are one mile away will qualify with all of the approaches; however the more accurate algorithms are needed for those rows that are just over or just under the five mile perimeter.  Omnidex starts with the more efficient algorithms to isolate the bulk of the rows and then refines them with more costly algorithms to insure accurate around the perimeter.
-Omnidex begins by searching the index for those rows within the outer ranges of latitude and longitude.  While this qualifies about 22% too many rows, it is very fast and narrows down the search.  Omnidex then shifts to the Pythagorean formula, adjusting as necessary to still insure enough accuracy.  Usually, this reduces the overage to just a few percentage points.  Finally, it uses the Law of Cosines to insure accuracy around the perimeter of the circle.   Using these approaches, the Omnidex algorithms are tuned to within 100 ft of accuracy in the most populated areas of the Earth.
-{{page>:bottom_add&nofooter&noeditbtn}}

Back to top

admin/optimization/geo/math.1280293507.txt.gz · Last modified: 2012/10/26 14:52 (external edit)

Sitemap Recent Changes