Как я могу расширить этот SQL-запрос, чтобы найти k ближайших соседей?

Question

У меня есть база данных, полная двумерных данных - точек на карте. Каждая запись имеет поле типа геометрии. То, что мне нужно, это передать точку в хранимую процедуру, которая возвращает k ближайших точек (k также будет передан в sproc, но это легко). Я нашел запрос на http://blogs.msdn.com/isaac/archive/2008/10/23/nearest-neighbors.aspx, который получает единственного ближайшего соседа, но я не могу понять, как его расширить, чтобы найти ближайших соседей k.

Это текущий запрос - T это таблица, g это поле геометрия, @x является точкой искать вокруг, Numbers представляет собой таблицу с целыми числами от 1 до п:

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 

Внутренний запрос выбирает ближайшую непустую область, а внешний запрос выбирает верхний результат из этой области; внешний запрос может быть легко изменен на (например) SELECT TOP(20), но если ближайший регион содержит только один результат, вы застряли в этом.

Я полагаю, что я, вероятно, нужно рекурсивно искать в первой области, содержащей к записи, но без использования переменной таблицы (которая будет вызывать проблемы с обслуживанием, как вы должны создать структуру таблицы, и это может изменяться - там» много полей), я не вижу, как это сделать.

Answer 1

Что произойдет, если вы удалите TOP (1) WITH TIES из внутреннего запроса и установите внешний запрос для возврата верхнего k строк?

Мне также было бы интересно узнать, помогает ли эта поправка вообще. Это должно быть более эффективным, чем при использовании 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 - непроверенной - У меня нет доступа к SQL 2008 здесь.

Answer 2

Проголосовано Inside Microsoft® SQL Server® 2008: T-SQL Programming. Раздел 14.8.4.

Следующий запрос будет возвращать 10 достопримечательности Ближайшие к @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; 

Примечание: только часть пункта WHERE Этот запрос получает поддержку от пространственного индекса , Однако оптимизатор запросов правильно оценивает поддерживаемую часть (сравнение «<») с использованием индекса. Это ограничивает количество строк для , которые должны быть проверены частью «> =», и запрос выполняется хорошо. Изменение Значение @start может иногда ускорить запрос, если он медленнее , чем хотелось бы.

Листинг 2-1. Создание и заполнение вспомогательной таблицы чисел

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;