код pl / sql для запроса ближайшего соседа без индекса для таблицы с точечными данными в Oracle - PullRequest
Новая
       21

код pl / sql для запроса ближайшего соседа без индекса для таблицы с точечными данными в Oracle

1 голос
/ 04 апреля 2011

Я пытаюсь построить процедуру для получения k ближайших соседних точек к точке с выбранным идентификатором.Мне нужно сделать это без использования каких-либо пространственных функций локатора, таких как sdo_geometry или nn.

В основном у меня есть таблица в Oracle с ID, Data_X, Data_Y.скажем, у меня есть 10 записей в моей таблице, и мне нужно 3 ближайших точки к вымышленной точке target_x, target_y.

нам нужно вычислить евклидово расстояние каждой точки в таблице с моей заданной вымышленной точкой.Я просто не знаю алгоритм в pl / sql, который бы возвращал мне идентификаторы ближайшего соседа.

Ответы [ 2 ]

3 голосов
/ 04 апреля 2011

Рассчитайте расстояние (Пифагор) между каждой точкой и выбранной точкой и порядок по расстоянию.Псевдо sql: 

select id from points
order by sqrt(sqr(Data_x - target_x) + sqr(Data_y - target_y))

Первые 3 строки являются ближайшими 3 точками.

2 голосов
/ 04 апреля 2011

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

Если производительность становится проблемой, вы, вероятно, могли бы взглянуть на создание бедняковпространственный индекс по данным.Это не будет так просто, как «создать индекс», но это может сработать.

Правильный метод - создать собственный индекс, но это будет просто изобретать колесо sdo_geometry, путь, который вы сказали вамхочу избежать.

Простой, но грубый метод (отказ от ответственности: это просто идея, не проверенная) может заключаться в создании индекса на основе функций, который группирует все точки в2D пространство в квадратные блоки.Вы в основном создаете индекс для сопоставления каждой пары (x, y) со списком блоков.Каждый блок будет иметь определенную ширину и высоту, и для выполнения поиска вы сначала должны определить, какую сетку блоков нужно искать, а затем запросить только список точек в этой сетке.

Пример индексабудет выглядеть примерно так: 

CREATE INDEX grid_block_i ON points (TRUNC(Data_X/100), TRUNC(Data_Y/100), id);

То, какое значение вы замените на 100, будет зависеть от диапазона значений, которые принимают ваши очки.Вам нужно разделить плоскость на большое количество блоков сетки, чтобы индекс был достаточно избирательным;но не такой большой, что типичный запрос должен будет искать слишком много блоков, чтобы найти кандидатов.

Вы можете использовать индекс выше, используя такой запрос: 

select id
from (select id, Data_X, Data_Y
      from points
      where TRUNC(Data_X/100) BETWEEN TRUNC(:target_x/100)) - :threshold
                                  AND TRUNC(:target_x/100)) + :threshold
      and   TRUNC(Data_Y/100) BETWEEN TRUNC(:target_y/100)) - :threshold
                                  AND TRUNC(:target_y/100)) + :threshold
     )
order by sqrt(sqr(Data_x - :target_x) + sqr(Data_y - :target_y))

Затем вы можетеset: порог, чтобы в основном исключить большой набор блоков точек из запроса.Я считаю, что если значения для функционального индекса (т.е. 100) и порога установлены правильно, вы увидите, что запрос использует индекс на основе функций для получения небольшого набора кандидатов вместо вычисления расстояния для каждой отдельной точки втаблица.

Недостатком является то, что если: слишком низкий порог, запрос может не возвращать строк.С другой стороны, это может быть полезной функцией, в зависимости от ваших потребностей.

...