Spatial Indexing

Question

I want to create a large database of GPS coordinates that can be queried by saying "Return all coordinates that are within 'n' metres of [this coordinate]".

I would like to know how to implement Quadtree Indexing in Sqlserver2008?

I want to write a .net module that calls the query which uses quad tree so that i can retrieve the objects so quickly.

How can i implement the above functionality?

Thanks in advance

Complexity

Answer 1

CREATE TABLE mytable (id INT NOT NULL, mypoint GEOGRAPHY NOT NULL, ...)

CREATE SPATIAL INDEX SX_mytable_mypoint ON mytable (mypoint)

SELECT  *
FROM    mytable
WHERE   mypoint.STDistance(geography::STGeomFromText(N'POINT (latitude longitude)', 4326) <= @N

Stakeout

Thanks for that.But my Sqlserver2008 datatype is geometry not geography.Actually,i want to know what the quad tree implementations is in sqlserver2008?If i create index spatial index on my table ,that means it is quad tree implementatiion? – Complexity

No, it's a B-Tree that indexes cells on a tesselated surface. SQL Server doesn't support R-Tree or Q-Tree natively. However, it still has decent performance. For GPS data it's better to keep places as GEOGRAPHY, since GEOMETRY assumes plain coordinates (as opposed to spherical). – Stakeout

Means q-tree implementation is not possible in sqlserver2008? – Complexity

This article: research.microsoft.com/pubs/64532/tr-2005-122.pdf shows some hints, though I should admit I've never tried it. As for 2008, all indexes implemented natively by SQL Server are B-Tree. – Stakeout

Thanks alot.I have one more doubt on exporting data from Navteq map to Sqlserver2008.If i put datatype as geography or geometry the values in map or not exporting.but if i use varchar they are exporting.Do you have any idea about this? – Complexity

Answer 2

I know that your article specifically references implementing the QuadTree in SqlServer2008, but as an option you could use one implemented in managed code.

Seem my article: http://www.codeproject.com/KB/recipes/QuadTree.aspx

Cali