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

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

9 голосов
/ 26 марта 2010

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

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

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), но если ближайший регион содержит только один результат, вы застряли с этим.

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

Ответы [ 2 ]

2 голосов
/ 25 августа 2010

Цитируется из Внутри Microsoft® SQL Server® 2008: программирование на T-SQL . Раздел 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;

Примечание: только часть этого запроса ГДЕ предложение поддерживается пространственным индекс. Тем не менее, оптимизатор запросов правильно оценивает поддерживаемую часть (сравнение «<») с использованием индекса. Это ограничивает количество строк для какая часть "> =" должна быть проверена, и запрос работает хорошо. изменения значение @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;
2 голосов
/ 26 марта 2010

Что произойдет, если вы удалите 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 здесь.

...