The math behind radius searches is somewhat complex but interesting, and there are several possible approaches.
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 (a2 + b2 = c2)? 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.
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.
The Law of Haversines is more accurate than the Law of Cosines when calculating very small distances. One must ask, though, what is the typical distance used in radius searches. Usually 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 takes two distinct approaches to calculating distances. When calculating pure distances, Omnidex uses the Law of Cosines to insure sufficient accuracy. However, when performing searches within the Omnidex indexes 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 only 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. Recognizing this, Omnidex begins with the efficient algorithms to isolate the bulk of the rows and then refines those that are close to the perimeter 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 sufficient accuracy. This reduces the overage to a very small percentage. To finalize the result and insure the accuracy, Omnidex uses the Law of Cosines for those rows 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 while insuring the performance needed in today's online applications.