Быстрый поиск по большому массиву неоднородных данных, что выбрать?

Question

[zeka]

Допустим есть 10 миллионов записей, каждая в среднем около 5 килобайт.
Данные в записях не являются текстом и отчасти близки к бинарным, и составления словаря (индексация) для них не представляется возможным.

Необходимо организовать полнотекстовый поиск по этим данным.

Какую систему можете посоветовать для этой задачи, чтобы поиск был максимально быстрым (как хранить данные и как искать по ним)?

UPD:
К вопросу можно подойти с другой стороны, например — распределённые вычисления, GAE тот-же, или Amazon SimpleDB, может у кого был такой опыт?

Comments

[dom1n1k]

Не очень понятно, что значит «не являются текстом и отчасти близки к бинарным», но при этом нужно организовать «полнотекстовый поиск»? Текстовый поиск по не-тексту? Боюсь, без примера данных разговор малопредметен.

[zeka]

Это произвольные последовательности символов, назовём их строки. Под поиском подразумевается — нахождение всех строк в которых содержится запрос, или подстрока.

Как утверждает википедия — «Полнотекстовый поиск — поиск документа в базе данных текстов на основании содержимого этих документов», собственно именно это и необходимо.

Answer 1

[apangin]

Примените идею фильтра Блума:
выберите 10-30 признаков, легко вычисляемых как для запроса, так и для содержимого, которые дают примерно одинаковое распределение true/false на вашем множестве данных. Поиск отфильтруйте по тем записям, где встречаются признаки, обнаруженные в запросе.

Например, можно выбрать признаки вида «существует подстрока из N символов, сумма которых равна K». Очевидно, если такая подстрока присутствует в запросе, то она обязана присутствовать и в искомых записях. Ради интереса я провел эксперимент на jpg-аватарках размером в среднем 4К и подобрал такие пары N и К: (3, 97), (3 98), (3, 99), (3, 102), (3, 104), (3, 105), (4, 161), (4, 173), (4, 178), (5, 247), (5, 251), (5, 255)…

Comments

[zeka]

Спасибо, очень интересный алгоритм, буду изучать.

Answer 2

[wanmen]

Вот тут не плохо написано про полнотекстовый поиск www.mysql.ru/docs/man/Fulltext_Search.html

Comments

[zeka]

Это подразумевает составление индекса, т.е. словаря, а характер и объём данных таков, что это будет абсолютно неэффективно.

Answer 3

[jj_killer]

Тут только «сверху-вниз» возможно. Если данные совершенно случайны и сортировать их не имеет смысла, то другого выхода, наверное, нету. Если все же они поддаются сортировке, то можно попробовать ставить «метки» и искать в промежутке между ними.

Answer 4

[Искандер Гиниятуллин]

10 000 000 записей по 5 000 байт каждая?
Т.е. примерно 50 гигабайт текстовой информации?

Я бы попробовал shpinx, он неплохо переваривает большие объемы текстовых данных
sphinxsearch.com/about/sphinx/

Comments

[Искандер Гиниятуллин]

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

[Искандер Гиниятуллин]

правда если у вас каждая запись 5000 байт без разделителей то сфинкс скорей всего окажется неэффективным

[zeka]

Да, спасибо. Но с индексированием похоже ничего не выйдет.

Answer 5

[YasonBy]

Если Ваши последовательности совершенно случайно имеют отношение к биологии (и даже если нет) — у биоинформатики есть специализированные алгоритмы, типа BLAST.

Comments

[zeka]

Не имеют, но за алгоритм спасибо.

Answer 6

[Jazzist]

Если данных много — найти возможность работать с индексом. Нет других эффективных решений.

Answer 7

[pietrovich]

50Gb относительно случайных последовательностей байтов? Без разделителей? А длинна искомого фрагмента в среднем какая? И насколько часто будут производиться выборки?

Comments

[zeka]

Именно так. Длинна — я думаю около 20-30 символов. Выборки — сложно сказать, но больше нескольких секунд ждать не хотелось бы.

[pietrovich]

Я вообще ни разу не специалист в поисковых технологиях и обработке больших массивов данных, но если разделителей нет, то пытаться индексировать «в лоб» используя движки для поиска в тексте, имхо, бессмысленно. Я бы копал в сторону разбиения на N-граммы, например по 4 байта, и индексировал бы вхождения всех N-грамм. При длине сообщения в 4к мы получим примерно 4k N-грамм на сообщение(из-за сдвига на один, до длинны блока, чтобы выбрать все последовательности). Т.е. изыбточность у нас резко начнет зашкаливать. Но если затем искомую последовательность разбить на такие-же N-грамы то можно будет смело отбросить блоки в которых не присутствуют ВСЕ N-граммы искомой «фразы», а это будет немаленький процент. с учетом соотношения N к длине «сообщения», а потом искать обычным поиском по оставшимся блокам в порядке уменьшения, допустим, количества требуемых N-грамм в блоке.
Как-то так. Вполне возможно что для этого существуют готовые решения, но я их не знаю.

про n-граммы можно погуглить в интернетах или прямо здесь.
вот похожая задачка: habrahabr.ru/blogs/sphinx/61807/