...

У некоторых людей возникает вопрос, что бы такое и эдакое почитать ! Замечательно, что у нас есть друзья, которые могут подсказать, но чаще всего вы остаетесь наедине с самим собой и компьютером. Когда-то я решил написать скрипт, который бы мне рекомендовал книги для чтения, учитывая коллективный опыт посетителей онлайн библиотек. Я взял дамп базы данных lib.rus.ec, который был доступен для скачивания, преобразовал его в любимый постгрес, использовал амазоновский алгоритм item-item collaborative filtering ( гуглите ) и накатал sql скрипт, который на основе оценок читателей like-dislike вычисляет матрицу рекомендации. Для доступа к вебу я написал перловый скрипт, который по bookid выдает сортированный по похожести список рекомендованных книг. По-умолчанию, скрипт выдает похожести для книги Стругацких "Понедельник начинается в субботу". Так как я этим занимался в качестве упражнения, то все очень просто и никаких гарантий :) Было бы хорошо прикрутить его к flibusta.net, которой я теперь пользуюсь, но у меня нет данных о ее базе и где можно получить регулярный доступ к ней.

Достал скрипт и стряхнул пыль, можно попробовать. Сам веб-интерфейс.
( для любителей SQL )

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

( Read more... )


Помимо knn мы будем рассказывать про Bloom-индекс и улучшенную оценку стоимости поиска по обратному индексу (gincostestimate), что позволит планеру лучше выбирать что использовать - индекс или seqscan таблицы. Кто интересуется, вот сам тред обсуждения и постинг Тома.

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

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