Nano Hash - криптовалюты, майнинг, программирование

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

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

Это текущий запрос: T — таблица, g — поле геометрии, @x — точка для поиска, Numbers — таблица с целыми числами от 1 до 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

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

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

sql sql-server-2008 geospatial nearest-neighbor
26.03.2010

  • Как влияет изменение запроса INNER на более чем TOP(1) на результаты при поиске k записей? (когда ближайший регион содержит только один результат) 26.03.2010
  • Если вы измените внутренний запрос, чтобы выбрать больше регионов, вы можете получить больше результатов, но это не гарантирует больше результатов: другие регионы могут просто содержать один и тот же результат (их размер увеличивается экспоненциально). - например представьте себе поиск вокруг точки, рядом с которой есть одна точка, но нет других точек на сотни километров вокруг - первые области n будут содержать одну и ту же точку. 26.03.2010
  • Было ли когда-либо найдено рабочее решение для этого? Я ищу такое же решение. 14.11.2010

Ответы:


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.

26.03.2010
  • @Smigs - Попробуйте внести поправку, которую я сделал - возможно, где-то там есть неявное приведение к int (хотя я этого не вижу) 26.03.2010
  • Это ошибка в исходном запросе - POWER возвращает тип данных своего первого аргумента (константа 2 интерпретируется как INT). Изменил мой запрос, чтобы отразить это. 26.03.2010
  • @ Эд Харпер, это работает, если вы установите k, например. 40, вы получаете 40 очков обратно. но он возвращает дубликаты, если точки разбросаны по нескольким регионам, потому что регион n содержит все точки в регионе n -1. конечно, их можно потом отфильтровать (в записях есть поле ID), но тогда вы получите меньше k баллов! Однако это выглядит быстрее, чем использование TOP! 26.03.2010
  • @Smigs - я не думаю, что исходный запрос работает так, как рекламируется, для любого значения k, отличного от 1 - это фундаментальная проблема этого подхода. Чтобы избежать этого, внутренний запрос должен искать, исключая содержимое всех предыдущих групп, которые уже были найдены. Это должно быть возможно, но у меня нет времени на это прямо сейчас (по сути, оператор ON в соединении должен учитывать нижнюю и верхнюю границы, а не только верхнюю границу). 26.03.2010
  • @Smigs - я внес еще одну поправку, чтобы отразить мою предыдущую заметку. 27.03.2010
  • @ Эд Харпер - эта поправка не совсем работает, потому что POWER(2, 0) равно 1, поэтому вы никогда не учитываете точки, которые меньше значения @float. Второе предложение должно быть AND (Numbers.n - 1 = 0 OR T.g.STDistance(@x) >= @start*POWER(@p,Numbers.n - 1)), чтобы обойти это. Однако я обнаружил еще одну проблему: поскольку результаты внутреннего запроса не упорядочены по расстоянию, вы можете получить плохие результаты. например при поиске вокруг (0,0): если @start равно 100, а число указывает на (0,0) › @k, точки на (1,1) могут быть возвращены ошибочно, поскольку они находятся в диапазоне @start. 29.03.2010
  • Я попытался изменить предложение OVER на (ORDER BY n, location.eastNorthGeom.STDistance(@g)), но это дает арифметические ошибки переполнения - можно ли сортировать по столбцу с плавающей запятой? 29.03.2010
  • @Smigs - нет ограничений на сортировку по плавающей запятой - где-то там должно быть еще одно неявное приведение к INT - опять же, это не сразу очевидно. n не требуется в ORDER BY функции ранжирования, поэтому я удалил его в приведенном выше коде. Я также включил ваше исправление для первого диапазона расстояний. 29.03.2010
  • @Ed Harper Я обнаружил проблему - POWER(@p,Numbers.n) на самом деле переполняется float. Просто нужно было WHERE numbers.n < [sensible number] в конце внутреннего запроса. 29.03.2010
  • @Smigs - рад, что ты наконец добрался до цели! 30.03.2010
  • @ Генри - спрашивающий принял окончательный ответ (хотя, читая его комментарии, он потребовал дальнейших изменений) - так что да, я думаю, вы могли бы сказать, что он был проверен 19.08.2010
  • @Ed Может быть, вам следует отредактировать ответ, включив в него предложение WHERE, предложенное Sighs @ 29 марта в 12:11? 19.08.2010

    • 2

    Цитата из Inside 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;

    Примечание. Только часть предложения 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;
    24.08.2010
  • У меня больше нет доступа к инструментам для проверки этого ответа, поэтому я не решаюсь отметить его как принятый ответ вместо ответа Эда - извините! 22.06.2012
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..