¿Cómo puedo extender esta consulta SQL para encontrar los k vecinos más cercanos?

Question

Tengo una base de datos llena de datos bidimensionales: puntos en un mapa. Cada registro tiene un campo del tipo de geometría. Lo que usted debe ser capaz de hacer es pasar un punto a un procedimiento almacenado que devuelve los k puntos más cercanos (k también se pasa al procedimiento almacenado, pero eso es fácil). He encontrado una consulta en la que recibe el http://blogs.msdn.com/isaac/archive/2008/10/23/nearest-neighbors.aspx solo vecino más cercano, pero no puedo imaginar cómo extender para encontrar los k vecinos más cercanos.

Ésta es la consulta actual - T es la tabla, g es el campo de la geometría, @x es el punto que buscar alrededor, Numbers es una tabla con los enteros del 1 al n:

DECLARE @start FLOAT = 1000; 
WITH NearestPoints AS 
(
    SELECT TOP(1) WITH TIES *, T.g.STDistance(@x) AS dist 
    FROM Numbers JOIN T WITH(INDEX(spatial_index)) 
    ON T.g.STDistance(@x) < @start*POWER(2,Numbers.n) 
    ORDER BY n 
) 
SELECT TOP(1) * FROM NearestPoints 
ORDER BY n, dist 

El interior consulta selecciona la región no vacía más cercana y la consulta externa luego selecciona el resultado superior de esa región; la consulta externa se puede cambiar fácilmente a (por ejemplo) SELECT TOP(20), pero si la región más cercana solo contiene un resultado, usted está atrapado con eso.

Calculo que probablemente tendrá que buscar de forma recursiva para la primera región que contiene k registros, pero sin necesidad de utilizar una variable de tabla (lo que causaría problemas de mantenimiento ya que hay que crear la estructura de la tabla y es susceptible de cambiar - no' re lotes de campos), no puedo ver cómo.

Answer 1

¿Qué ocurre si elimina TOP (1) WITH TIES de la consulta interna y configura la consulta externa para que devuelva las filas k superiores?

yo también interesaría saber si esta modificación ayuda en absoluto. Debería ser más eficaz que utilizar TOP:

DECLARE @start FLOAT = 1000 
     ,@k INT = 20 
     ,@p FLOAT = 2; 

WITH NearestPoints AS 
(
    SELECT * 
      ,T.g.STDistance(@x) AS dist 
      ,ROW_NUMBER() OVER (ORDER BY T.g.STDistance(@x)) AS rn 
    FROM Numbers 
    JOIN T WITH(INDEX(spatial_index)) 
    ON T.g.STDistance(@x) < @start*POWER(@p,Numbers.n) 
    AND (Numbers.n - 1 = 0 
      OR T.g.STDistance(@x) >= @start*POWER(@p,Numbers.n - 1) 
     ) 
) 
SELECT * 
FROM NearestPoints 
WHERE rn <= @k; 

NB - no probado - no tengo acceso a SQL 2008 aquí.

Answer 2

citado de Inside Microsoft® SQL Server® 2008: T-SQL Programming. Sección 14.8.4.

la siguiente consulta devolverá los 10 puntos de interés cercana a @input:

DECLARE @input GEOGRAPHY = 'POINT (-147 61)'; 
DECLARE @start FLOAT = 1000; 
WITH NearestNeighbor AS(
    SELECT TOP 10 WITH TIES 
    *, b.GEOG.STDistance(@input) AS dist 
    FROM Nums n JOIN GeoNames b WITH(INDEX(geog_hhhh_16_sidx)) -- index hint 
    ON b.GEOG.STDistance(@input) < @start*POWER(CAST(2 AS FLOAT),n.n) 
    AND b.GEOG.STDistance(@input) >= 
    CASE WHEN n = 1 THEN 0 ELSE @start*POWER(CAST(2 AS FLOAT),n.n-1) END 
    WHERE n <= 20 
    ORDER BY n 
) 
    SELECT TOP 10 geonameid, name, feature_code, admin1_code, dist 
    FROM NearestNeighbor 
    ORDER BY n, dist; 

Nota: Sólo una parte de la cláusula WHERE de esta consulta es apoyada por el índice espacial . Sin embargo, el optimizador de consultas evalúa correctamente la parte apoyada (el "<" comparación) usando el índice. Esto restringe el número de filas para que la parte "> =" debe ser probada, y la consulta funciona bien. Cambiando el valor de @start a veces puede acelerar la consulta si es más lento de lo deseado.

Listado 2-1. Crear y llenar la tabla auxiliar de Números

SET NOCOUNT ON; 
USE InsideTSQL2008; 

IF OBJECT_ID('dbo.Nums', 'U') IS NOT NULL DROP TABLE dbo.Nums; 

CREATE TABLE dbo.Nums(n INT NOT NULL PRIMARY KEY); 
DECLARE @max AS INT, @rc AS INT; 
SET @max = 1000000; 
SET @rc = 1; 

INSERT INTO Nums VALUES(1); 
WHILE @rc * 2 <= @max 
BEGIN 
    INSERT INTO dbo.Nums SELECT n + @rc FROM dbo.Nums; 
    SET @rc = @rc * 2; 
END 

INSERT INTO dbo.Nums 
    SELECT n + @rc FROM dbo.Nums WHERE n + @rc <= @max;