k-nn search ( Поиск ближайших соседей)
May. 4th, 2010 01:24 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
obartunovПеред PGCon 2010 в Оттаве, где мы будем докладывать о наших разработках, я решил сделать попытку описать алгоритм поиска ближайших соседей в PostgreSQL без привлечения деталей имплементации (это лучше сделает Федя Сигаев), как это я себе представляю.
Постановка проблемы: Для заданой точки в n-мерном пространстве найти к-ближайших соседей среди очень большого количества данных. Большое количество данных означает, что алгоритм должен быть оптимизирован на работу с диском (минимизация количества операций ввода-вывода), и не полагаться на in-memory структуры данных.
Для того, чтобы найти ближайшую точку к запросу можно пойти наивным способом - перебрать все точки с подсчетом расстояния до запроса, потом отсортировать по возрастанию расстояния. Понятно, что производительность такого алгоритма в основном определяется временем последовательного чтения данных с диска (при условии, что вычисление расстояния - это не многомерный интеграл :). Однако, этот подход не экономит операции ввода-вывода и в дальнейшем я его рассматривать не буду.
Лирическое отступление про индексы.
Известно, что если требуется работать с большим количеством данных, то наилучший путь - это разбить пространство данных (ОДЗ) на обозримое количество частей, каждая из которых содержит обозримое количество данных, с которым уже можно легко работать (поиск). Способов разбиения существует большое количество ! Главное - это то, что разбиение не зависит от запроса и определяется только данными (иногда и порядком поступления данных), так что можно один раз сегментировать данные и только поддерживать его при обновлении данных.
Большая страна не может эффективно управляться из центра, требуется делегирование полномочий федеральным образованиям,которые в свою очередь делятся на области, края, районы и тд. Современная Росиия представляет собой иерархическое дерево,
Для наглядности рассмотрим пример разбиения двумерного пространства данных на непересекающиеся прямоугольники, организованные как дерево. Во внутренних узлах находятся прямоугольники,которые покрывают все унаследованные (от родительского узла) прямоугольники или точки, если это концевой узел (листья). Таким образом, поиск начинается с корневого узла, который включает все, потом на тот прямоугольник, который удовлетворяет условию поиска и тд., пока не доходит до самих данных на концевом узле. На рисунке видно, что сначала корневой узел делится на два больших прямоугольника соответственно {1,3,4,8} и {2,5,6,7,9}. Прямоугольник {1,3,4,8} сам разбивается на два концевых узла с точками {1,3,4} и {8}. Чтобы найти точку 8 достаточно прочитать 3 страницы, при этом полностью исключить целую ветку {2,5,6,7,9} и концевой узел {1,3,4}, т.е.экономим чтение 4-х страниц ! Кстати, надо учитывать, что чтение здесь не последовательное, т.е. эти страницы могут находится в случайных местах и требуется позиционирование считывающей головки (в постгресе считается, что стоимость такого чтения в 4 раза дороже последовательного чтения).
Подобное дерево называется поисковым деревом, или более известным термином - индексом. Внизу приведено популярное поисковое дерево R-tree (дерево прямоугольников), которое несколько отличается от рассматриваемого тем, что прямоугольники могут перекрываться.
Алгоритм поиска ближайших соседей.
Однако, для поиска ближайших соседей к заданной точке Q (красная точка) этот поисковый алгоритм не годится, так как в конце концов нам придется прочитать все узлы, чтобы добраться до всех точек, отсортировать по расстоянию. А тут уж проще просто последовательно прочитать таблицу как в наивном подходе и это будет сильно быстрее.
Известное решение - это использование другой стратегии обхода, не DFS (Depth First Search), а BFS (Best First Search), когда выбор следующего узла определяется каким-нибудь критерием, например, минимизацией расстоянием до точки. Мне нравится описание [3]. Ниже я коротко опишу эту стратегию обхода.
Введем очередь с приоритетами (PQ, priority queue), которая содержит два типа объектов - точки из концевых узлов и прямоугольники с внутренних узлов, причем они отсортированы по ключу (расстоянию от заданной точки). Для прямоугольника ключом является минимальное расстояние от точки до ближайшей грани (нижний предел для всех расстояний точек внутри этого прямоугольника. Если прямоугольник содержит заданную точку, то расстояние равно 0) . Каждый раз, когда мы достаем точку из очереди, то мы выдаем ее как (очередной) результат. Если мы достаем прямоугольник, то мы добавляем в очередь все его дочерние прямоугольники или точки, если это прямоугольник с концевого узла. Таким образом, любая точка,которая выдается до прямоугольника, будет ближе любой точки этого прямоугольника. Для красной точки, очередь будет выглядеть так:
Обход поискового дерева (BFS, цифрами указаны порядковый номер обхода дерева): root-{2,5,6,7,9}-{5,6,7,9}-{5,9}-{1,3,4,8}-4-5-{6,7}
Понятно, что этот процесс можно остановить (если нашли требуемое количество записей) и возобновить в любой момент, процесс инкрементальный.
Итак, новая стратегия обхода позволяет получить k-ближайших соседей не обходя все дерево, причем время выполнения запроса практически не зависит от размера данных ! А это значит, что выигрыш алгоритма только растет с ростом базы. С ростом к время выполнения запроса растет, так как приходится посещать больше узлов и в предельном случае, когда запрашивается вся база, приближается к варианту с последовательным сканом всей таблицы.
Log-Log зависимость времени выполнения запроса (ms) от количества ближайших соседей для 2млн географических точек. На втором графике приведено кол-во прочитанных страниц поискового дерева.
Видно, что для реальных значений 10-100 выигрыш составляет 2-3 порядка !
Для базы 7.2 млн записей выигрыш для 10 ближайших соседей достигает уже 4943.451/1.097, 4500 раз ! При этом было прочитано 26 страниц индекса, по сравнению с 25 для 2 млн. базы.
Возможные оптимизации
Как это реализовано в PostgreSQL
Проблемы
Rtree (rectangle tree) для городов Греции (по данным Rtreeportal).
( полная версия
Ссылки:
[1] Nick Roussopoulos, Stephen Kelley, Frederic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79.
[2] G. R. Hjaltason and H. Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems 24, 2 (June 1999), 265-318.
[3] http://blogs.msdn.com/devdev/archive/2007/06/07/k-nearest-neighbor-spatial-search.aspx
Постановка проблемы: Для заданой точки в n-мерном пространстве найти к-ближайших соседей среди очень большого количества данных. Большое количество данных означает, что алгоритм должен быть оптимизирован на работу с диском (минимизация количества операций ввода-вывода), и не полагаться на in-memory структуры данных.
Для того, чтобы найти ближайшую точку к запросу можно пойти наивным способом - перебрать все точки с подсчетом расстояния до запроса, потом отсортировать по возрастанию расстояния. Понятно, что производительность такого алгоритма в основном определяется временем последовательного чтения данных с диска (при условии, что вычисление расстояния - это не многомерный интеграл :). Однако, этот подход не экономит операции ввода-вывода и в дальнейшем я его рассматривать не буду.
Лирическое отступление про индексы.
Известно, что если требуется работать с большим количеством данных, то наилучший путь - это разбить пространство данных (ОДЗ) на обозримое количество частей, каждая из которых содержит обозримое количество данных, с которым уже можно легко работать (поиск). Способов разбиения существует большое количество ! Главное - это то, что разбиение не зависит от запроса и определяется только данными (иногда и порядком поступления данных), так что можно один раз сегментировать данные и только поддерживать его при обновлении данных.
Большая страна не может эффективно управляться из центра, требуется делегирование полномочий федеральным образованиям,которые в свою очередь делятся на области, края, районы и тд. Современная Росиия представляет собой иерархическое дерево,
Для наглядности рассмотрим пример разбиения двумерного пространства данных на непересекающиеся прямоугольники, организованные как дерево. Во внутренних узлах находятся прямоугольники,которые покрывают все унаследованные (от родительского узла) прямоугольники или точки, если это концевой узел (листья). Таким образом, поиск начинается с корневого узла, который включает все, потом на тот прямоугольник, который удовлетворяет условию поиска и тд., пока не доходит до самих данных на концевом узле. На рисунке видно, что сначала корневой узел делится на два больших прямоугольника соответственно {1,3,4,8} и {2,5,6,7,9}. Прямоугольник {1,3,4,8} сам разбивается на два концевых узла с точками {1,3,4} и {8}. Чтобы найти точку 8 достаточно прочитать 3 страницы, при этом полностью исключить целую ветку {2,5,6,7,9} и концевой узел {1,3,4}, т.е.экономим чтение 4-х страниц ! Кстати, надо учитывать, что чтение здесь не последовательное, т.е. эти страницы могут находится в случайных местах и требуется позиционирование считывающей головки (в постгресе считается, что стоимость такого чтения в 4 раза дороже последовательного чтения).
Подобное дерево называется поисковым деревом, или более известным термином - индексом. Внизу приведено популярное поисковое дерево R-tree (дерево прямоугольников), которое несколько отличается от рассматриваемого тем, что прямоугольники могут перекрываться.
Алгоритм поиска ближайших соседей.
Однако, для поиска ближайших соседей к заданной точке Q (красная точка) этот поисковый алгоритм не годится, так как в конце концов нам придется прочитать все узлы, чтобы добраться до всех точек, отсортировать по расстоянию. А тут уж проще просто последовательно прочитать таблицу как в наивном подходе и это будет сильно быстрее.
Известное решение - это использование другой стратегии обхода, не DFS (Depth First Search), а BFS (Best First Search), когда выбор следующего узла определяется каким-нибудь критерием, например, минимизацией расстоянием до точки. Мне нравится описание [3]. Ниже я коротко опишу эту стратегию обхода.
Введем очередь с приоритетами (PQ, priority queue), которая содержит два типа объектов - точки из концевых узлов и прямоугольники с внутренних узлов, причем они отсортированы по ключу (расстоянию от заданной точки). Для прямоугольника ключом является минимальное расстояние от точки до ближайшей грани (нижний предел для всех расстояний точек внутри этого прямоугольника. Если прямоугольник содержит заданную точку, то расстояние равно 0) . Каждый раз, когда мы достаем точку из очереди, то мы выдаем ее как (очередной) результат. Если мы достаем прямоугольник, то мы добавляем в очередь все его дочерние прямоугольники или точки, если это прямоугольник с концевого узла. Таким образом, любая точка,которая выдается до прямоугольника, будет ближе любой точки этого прямоугольника. Для красной точки, очередь будет выглядеть так:
1:{1,2,3,4,5,6,7,8,9} - корень, содержит точку Q, расстояние от корня до Q равно 0,
2:{2,5,6,7,9}, {1,3,4,8} - рут удаляем из очереди и добавляем его детей, учитывая расстояние
3:{5,6,7,9}, {1,3,4,8}, {2} - {2,5,6,7,9} заменяется на {5,6,7,9} и {2},
которое помещается в конец очереди как самое далекая от Q.
4:{5,9}, {1,3,4,8}, {2}, {6,7}
5:{1,3,4,8}, 5, {2}, {6,7}, 9
6:{1,3,4}, {8}, 5, {2}, {6,7}, 9
7:4, {8}, 5, {2}, {6,7}, 3, 1, 9
8:5, {2}, {6,7}, 3, 8, 1, 9 - точка 4 удаляется из очереди как самая близкая !
9:{6,7}, 3, 2, 8, 1, 9 - выдаем точку 5,прямоугольник с точкой 2 заменяем на точку 2
10:3, 2, 8, 1, 9, 6, 7 - все, этот упорядоченный список уже можно выдавать.
Обход поискового дерева (BFS, цифрами указаны порядковый номер обхода дерева): root-{2,5,6,7,9}-{5,6,7,9}-{5,9}-{1,3,4,8}-4-5-{6,7}
Понятно, что этот процесс можно остановить (если нашли требуемое количество записей) и возобновить в любой момент, процесс инкрементальный.
Итак, новая стратегия обхода позволяет получить k-ближайших соседей не обходя все дерево, причем время выполнения запроса практически не зависит от размера данных ! А это значит, что выигрыш алгоритма только растет с ростом базы. С ростом к время выполнения запроса растет, так как приходится посещать больше узлов и в предельном случае, когда запрашивается вся база, приближается к варианту с последовательным сканом всей таблицы.
Log-Log зависимость времени выполнения запроса (ms) от количества ближайших соседей для 2млн географических точек. На втором графике приведено кол-во прочитанных страниц поискового дерева.
Видно, что для реальных значений 10-100 выигрыш составляет 2-3 порядка !
Для базы 7.2 млн записей выигрыш для 10 ближайших соседей достигает уже 4943.451/1.097, 4500 раз ! При этом было прочитано 26 страниц индекса, по сравнению с 25 для 2 млн. базы.
Возможные оптимизации
Как это реализовано в PostgreSQL
Проблемы
Rtree (rectangle tree) для городов Греции (по данным Rtreeportal).
( полная версияСсылки:
[1] Nick Roussopoulos, Stephen Kelley, Frederic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79.
[2] G. R. Hjaltason and H. Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems 24, 2 (June 1999), 265-318.
[3] http://blogs.msdn.com/devdev/archive/2007/06/07/k-nearest-neighbor-spatial-search.aspx
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2010-05-07 06:41 pm (UTC)no subject
Date: 2010-05-07 08:56 pm (UTC)no subject
Date: 2010-05-08 10:31 am (UTC)Скажите, а как можно собрать PostgreSQL c последней версией knn-gist (очень хочется попробовать), а то я немного запутался изучая различные ветки mailing list'ов?
no subject
Date: 2010-05-08 11:28 am (UTC)Только на CVS HEAD не накладывается (мы заморозили девелопмент. когда поняли, что в 9.0 не попадаем), вы можете сами ручками доправить или взять из CVS версию за февраль. Она тогда еще 8.5 называлась.
no subject
Date: 2010-05-08 05:34 pm (UTC)CREATE INDEX pv_idx ON pt USING gist (p,v); set enable_seqscan = off; set enable_indexscan = on; explain SELECT p FROM pt ORDER BY p <-> '5.0,5.0'::point LIMIT 10; QUERY PLAN --------------------------------------------------------------------------------------- Limit (cost=10000000507.10..10000000507.12 rows=10 width=16) -> Sort (cost=10000000507.10..10000000532.10 rows=10000 width=16) Sort Key: ((p <-> '(5,5)'::point)) -> Seq Scan on pt (cost=10000000000.00..10000000291.00 rows=10000 width=16) (4 rows)Что я делаю не так?
no subject
Date: 2010-05-08 06:47 pm (UTC)Вы еще explain analyze лучше пробуйте.
no subject
Date: 2010-05-09 08:40 am (UTC)no subject
Date: 2010-05-09 09:16 am (UTC)no subject
Date: 2010-05-08 12:43 pm (UTC)