obartunov: (Default)
Слайды с конференции можно скачать с этой странички.
obartunov: (Default)
Слайды с конференции можно скачать с этой странички.
obartunov: (Default)
Как-то не случилось никак дать ссылку на оригинальную работу по базовому алгоритму поиска ближайших соседей.
Ranking in Spatial Databases (1995), Gísli Hjaltason , Hanan Samet.
obartunov: (Default)
Как-то не случилось никак дать ссылку на оригинальную работу по базовому алгоритму поиска ближайших соседей.
Ranking in Spatial Databases (1995), Gísli Hjaltason , Hanan Samet.
obartunov: (Default)
Нашу работу (с Федей Сигаевым) включили в список Инноваций, подготовленный для новой версии 9.1.Пустячок, но приятно :)
Innovation                                                                      
  K-Nearest-Neighbor Indexing                                                   
      permits doing an indexed search of "what's near me".                      
      expected to power a whole new generation of spatial applications          
      Microsoft is working on this, but we're releasing before them.   

На самом деле, это не пустячок, конечно, а почти 1.5 года работы. Целый спектр научных приложений выиграет от этого. Астрономический пример - наблюдения в 9 фильтрах, надо отождествить объекты на снимках. Наивным способом эта задача для миллиардов звезд и миллионов пластинок практически неподъемна и нужно применять adhoc решения, что не очень хорошо для автоматизации процесса кукинга данных. Наш алгоритм не решает проблему пространственной связки (spatial join), но сильно (в тысячи раз) ускоряет поиск ближайших соседей и очень слабо (логарифмически) зависит от размера данных. Во вторник я буду рассказывать об этом на РиТ-е. Не приглашаю, ибо регистрация уже закрыта, мест нет :) Честно говоря, позиция Рит-а меня смущает - 17,000 руб стоимость регистрации на два дня - это уже как-то совсем не народно.
obartunov: (Default)
Нашу работу (с Федей Сигаевым) включили в список Инноваций, подготовленный для новой версии 9.1.Пустячок, но приятно :)
Innovation                                                                      
  K-Nearest-Neighbor Indexing                                                   
      permits doing an indexed search of "what's near me".                      
      expected to power a whole new generation of spatial applications          
      Microsoft is working on this, but we're releasing before them.   

На самом деле, это не пустячок, конечно, а почти 1.5 года работы. Целый спектр научных приложений выиграет от этого. Астрономический пример - наблюдения в 9 фильтрах, надо отождествить объекты на снимках. Наивным способом эта задача для миллиардов звезд и миллионов пластинок практически неподъемна и нужно применять adhoc решения, что не очень хорошо для автоматизации процесса кукинга данных. Наш алгоритм не решает проблему пространственной связки (spatial join), но сильно (в тысячи раз) ускоряет поиск ближайших соседей и очень слабо (логарифмически) зависит от размера данных. Во вторник я буду рассказывать об этом на РиТ-е. Не приглашаю, ибо регистрация уже закрыта, мест нет :) Честно говоря, позиция Рит-а меня смущает - 17,000 руб стоимость регистрации на два дня - это уже как-то совсем не народно.
obartunov: (Default)
Вот что я написал для РИТа, сидя на конференции по СПО (сроки поджимали, Бунин наседал). Кстати, подивился связке Google Nexus One + Ubuntu 10.10 - на андроиде нажал одну кнопку (tethering по USB), и Ubuntu совершенно автоматически подняла коннект с миром через андроидный 3G. Я был потрясен, вспоминая танцы с бубном в прошлые годы !

Эффективный поиск ближайших соседей в PostgreSQL
Олег Бартунов

С необходимостью эффективного поиска ближайших соседей можно встретиться в разных задачах, например, поиск ближайших, к заданной точке , объектов на карте. Задача, на непрограммистский взгляд кажущаяся тривиальной (действительно, человек довольно легко справляется с ней глядя на карту) , на самом деле не имеет общего и доступного решения, что приводит к головной боли разработчиков, которые придумывают ad hoc решения (вставляют костыли). Эти решения, обычно некрасивые, портят настроение творческой натуры программиста, которому требуется посещение пивной, чтобы пережить когнитивный диссонанс :)
Read more... )
obartunov: (Default)
Вот что я написал для РИТа, сидя на конференции по СПО (сроки поджимали, Бунин наседал). Кстати, подивился связке Google Nexus One + Ubuntu 10.10 - на андроиде нажал одну кнопку (tethering по USB), и Ubuntu совершенно автоматически подняла коннект с миром через андроидный 3G. Я был потрясен, вспоминая танцы с бубном в прошлые годы !

Эффективный поиск ближайших соседей в PostgreSQL
Олег Бартунов

С необходимостью эффективного поиска ближайших соседей можно встретиться в разных задачах, например, поиск ближайших, к заданной точке , объектов на карте. Задача, на непрограммистский взгляд кажущаяся тривиальной (действительно, человек довольно легко справляется с ней глядя на карту) , на самом деле не имеет общего и доступного решения, что приводит к головной боли разработчиков, которые придумывают ad hoc решения (вставляют костыли). Эти решения, обычно некрасивые, портят настроение творческой натуры программиста, которому требуется посещение пивной, чтобы пережить когнитивный диссонанс :)
Read more... )
obartunov: (Default)
Сегодня Tom Lane закоммиттил наш патч KNNGIST, который добавляет возможность эффективно искать ближайших соседей с использованием GIST-индекса. Пока что закомичена поддержка только для типа point (в CORE) и триграмм (в contrib/pg_trgm), а на contrib/btree_gist у Тома не хватило терпения ("..I lack the patience to fix.."). Ничего страшного, у нас тоже едва хватило терпения почти полтора года пропихивать эту фичу и поддерживать патч. Том, конечно, молодец, понял, что если дальше тянуть, то мы просто-напросто завянем, а Robet Haas еще молодой, чтобы отвечать за свои придирки.
Том немного наехал, что много усилий, а поддержка KNN только для point, но после доработки contrib/btree_gist (надеюсь, что Федя сейчас это сделает), постгрес получит поддержку для всех основных типов. Я думаю, что можно сделать поддержку для ltree, box, polygon?. В качестве "наподумать" рассматриваю tsvector.

Read more... )
obartunov: (Default)
Сегодня Tom Lane закоммиттил наш патч KNNGIST, который добавляет возможность эффективно искать ближайших соседей с использованием GIST-индекса. Пока что закомичена поддержка только для типа point (в CORE) и триграмм (в contrib/pg_trgm), а на contrib/btree_gist у Тома не хватило терпения ("..I lack the patience to fix.."). Ничего страшного, у нас тоже едва хватило терпения почти полтора года пропихивать эту фичу и поддерживать патч. Том, конечно, молодец, понял, что если дальше тянуть, то мы просто-напросто завянем, а Robet Haas еще молодой, чтобы отвечать за свои придирки.
Том немного наехал, что много усилий, а поддержка KNN только для point, но после доработки contrib/btree_gist (надеюсь, что Федя сейчас это сделает), постгрес получит поддержку для всех основных типов. Я думаю, что можно сделать поддержку для ltree, box, polygon?. В качестве "наподумать" рассматриваю tsvector.

Read more... )
obartunov: (Default)
Как всегда это бывает, чем ближе к докладу, тем меньше оказывается есть что рассказать :)
Так и с поиском ближайших соседей, про который я уже писал, который мы (я и Федя Сигаев) должны представить на конференции разработчиков PostgreSQL в Оттаве (Канада). Конференция ежегодная, мы на ней уже выступали много раз, нам дают там обычно 1 час выступления перед всеми ведущими разработчиками, которые все имеют приличное образование и большой experience. Я практически уверен, что им будет достаточно сказать только одну фразу "Вместо использования стека для обхода поискового дерева, мы используем очередь с приоритетами (priority queue)" и дальше только обсудить тонкости конкретной реализации.

Read more... )


Помимо knn мы будем рассказывать про Bloom-индекс и улучшенную оценку стоимости поиска по обратному индексу (gincostestimate), что позволит планеру лучше выбирать что использовать - индекс или seqscan таблицы. Кто интересуется, вот сам тред обсуждения и постинг Тома.
obartunov: (Default)
Как всегда это бывает, чем ближе к докладу, тем меньше оказывается есть что рассказать :)
Так и с поиском ближайших соседей, про который я уже писал, который мы (я и Федя Сигаев) должны представить на конференции разработчиков PostgreSQL в Оттаве (Канада). Конференция ежегодная, мы на ней уже выступали много раз, нам дают там обычно 1 час выступления перед всеми ведущими разработчиками, которые все имеют приличное образование и большой experience. Я практически уверен, что им будет достаточно сказать только одну фразу "Вместо использования стека для обхода поискового дерева, мы используем очередь с приоритетами (priority queue)" и дальше только обсудить тонкости конкретной реализации.

Read more... )


Помимо knn мы будем рассказывать про Bloom-индекс и улучшенную оценку стоимости поиска по обратному индексу (gincostestimate), что позволит планеру лучше выбирать что использовать - индекс или seqscan таблицы. Кто интересуется, вот сам тред обсуждения и постинг Тома.
obartunov: (Default)
Перед PGCon 2010 в Оттаве, где мы будем докладывать о наших разработках, я решил сделать попытку описать алгоритм поиска ближайших соседей в PostgreSQL без привлечения деталей имплементации (это лучше сделает Федя Сигаев), как это я себе представляю.

Постановка проблемы: Для заданой точки в n-мерном пространстве найти к-ближайших соседей среди очень большого количества данных. Большое количество данных означает, что алгоритм должен быть оптимизирован на работу с диском (минимизация количества операций ввода-вывода), и не полагаться на in-memory структуры данных.
Read more... )
obartunov: (Default)
Перед PGCon 2010 в Оттаве, где мы будем докладывать о наших разработках, я решил сделать попытку описать алгоритм поиска ближайших соседей в PostgreSQL без привлечения деталей имплементации (это лучше сделает Федя Сигаев), как это я себе представляю.

Постановка проблемы: Для заданой точки в n-мерном пространстве найти к-ближайших соседей среди очень большого количества данных. Большое количество данных означает, что алгоритм должен быть оптимизирован на работу с диском (минимизация количества операций ввода-вывода), и не полагаться на in-memory структуры данных.
Read more... )

Profile

obartunov: (Default)
obartunov

November 2012

S M T W T F S
    1 23
456789 10
11121314151617
18192021222324
252627282930 

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags