Tatham Oddie

http://www.smh.com.au/news/web/googles-photos-of-sydney-go-all-fuzzy/2007/08/13/1186857396182.html?page=fullpage

In the event that Asher Moses searched out the facts, he may have learnt a number of things.

The article justifies it’s technical position with a technical misconstrusion – “satellite views as close as 25m above the ground”. While aerial imagery resolution is generally expressed in terms of metres, this has no direct correlation to an elevation above the surface. Instead, the measurement represents the physical distance represented by each digital pixel on screen. While this isn’t a point that needs to be conveyed to the general public, it could have been represented with a statement along the lines of “but now maps of the CBD are blurry even when zoomed out to 1/12^th of their previous level”.

The author may also have noticed that the imagery is provided by DigitalGlobe, TerraMetrics and MapData Sciences (an Australian company). Perhaps the author could have contacted any of these companies prior to pestering security taskforces with superfluous conspiracy theories.

It is disappointing that in this day and age, journalism has dwindled to the extent of monitoring Google Maps for Orwell-inspired stories, backed up by references to Wikipedia and general technical inaccuracy.

Disclaimer: I don’t actually know anything about SQL performance. The techniques described below have been gleaned from other sources, seem to work for me, and it makes sense why they would. If you know more about SQL, please correct me.

—

Talking to Darren around Tech.Ed today, he expressed a need for a way to do proximity searches in SQL. These are queries along the lines of “give me all the records that talk about locations within 50km of X”. Now, in SQL 2008 this is baked into the product, but for SQL 2005 and below we need to do the maths ourselves.

The general query is relatively simple: calculate the distance-from-X for each row, then filter by the distance. Performing 6 trigonometric operations for every row, on every query is a pretty sure way to kill your average database though.

Instead, we add some persisted calculated columns to our table like so:

CREATE TABLE [dbo].[Locations]
(
    [LocationID] [uniqueidentifier] ROWGUIDCOL NOT NULL CONSTRAINT [DF_Locations_LocationID] DEFAULT (newid()),
    [Title] [varchar](100) NOT NULL,
    [Latitude] [decimal](9, 6) NOT NULL,
    [Longitude] [decimal](9, 6) NOT NULL,
    [ProximityX]  AS (cos(radians([Latitude]))*cos(radians([Longitude]))) PERSISTED,
    [ProximityY]  AS (cos(radians([Latitude]))*sin(radians([Longitude]))) PERSISTED,
    [ProximityZ]  AS (sin(radians([Latitude]))) PERSISTED,
    CONSTRAINT [PK_Locations] PRIMARY KEY CLUSTERED
    (
        [LocationID] ASC
    ) WITH (PAD_INDEX  = OFF, IGNORE_DUP_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY]
GO

Basically, we take the reusable parts of our calculation and store them between queries. Storing these precalculated components means that our comparisons can be done using relatively simple maths and only one trig function per row.

Because they are persisted calculated columns, they are only calculated when the row is created or updated. SQL manages this for us.

Finally, here’s a stored procedure to query that table:

CREATE PROCEDURE [dbo].[FindLocationsNearby]
   @CenterLat float,
   @CenterLon float,
   @SearchRadius float
AS
BEGIN
    –Store the radius of the earth (in km so that we can search by km)
    declare @EarthRadius float
    set @EarthRadius = 6378.14

    –Calculate the X, Y and Z axis values for the center point
    declare @CenterX float
    declare @CenterY float
    declare @CenterZ float
    set @CenterX = cos(radians(@CenterLat)) * cos(radians(@CenterLon))
    set @CenterY = cos(radians(@CenterLat)) * sin(radians(@CenterLon))
    set @CenterZ = sin(radians(@CenterLat))

    –Perform the database search
    SELECT    Title,
            Distance = @EarthRadius * acos(ProximityX * @CenterX + ProximityY * @CenterY + ProximityZ * @CenterZ)
    FROM    Locations
    WHERE    @EarthRadius * acos(ProximityX * @CenterX + ProximityY * @CenterY + ProximityZ * @CenterZ) <= @SearchRadius
    ORDER BY Distance ASC
END
GO

This technique was extracted from an Access/SQL 2000 article I found on MSDN.