Как структурировать индекс для опережающего типа для чрезвычайно большого набора данных с использованием Lucene или аналогичного?

Question

У меня есть набор данных с более чем 200 миллионами записей, и я собираюсь создать специальный бэкэнд для поддержки решения с опережением типа. Lucene представляет интерес, учитывая его популярность и тип лицензии, но я открыт и для других предложений с открытым исходным кодом. Я ищу советы, рассказы из окопов или даже более точные прямые инструкции о том, что мне понадобится, насколько это касается оборудования и структуры программного обеспечения. Требования:

Должно иметь:

• Способность начинаться начинается с сопоставления подстроки (я набираю 'st', и она должна совпадать с 'Stephen')
• Возможность очень быстро возвращать результаты, я бы сказал, 500 мс - верхняя граница.

Приятно иметь:

• Возможность подачи информации о релевантности в процесс индексации, чтобы, например, более популярные термины возвращались раньше других, а не только в алфавитном порядке, в стиле Google.
• Соответствие подстроки в слове, например, (st будет соответствовать 'bestseller')

Примечание:

• Этот индекс будет использоваться исключительно для опережающего ввода и не должен обслуживать стандартные поисковые запросы.
• Меня не беспокоит вопрос о том, как настроить интерфейс или AJAX, если индекс можно запрашивать как службу или напрямую через код Java.

Голосование за любую полезную информацию, которая позволяет мне приблизиться к решению на уровне типа предприятия

Answer 1

Если каждая запись относительно мала (менее нескольких слов), вы можете попробовать структуру данных Trie:

http://en.wikipedia.org/wiki/Trie

Он создан для облегчения быстрого сопоставления префиксов и относительно компактен. Я использовал эту структуру данных для точной функции автозаполнения, которую вы ищете, и я знаю других, которые сделали это для веб-сайтов массового производства. По моему опыту, вы можете ожидать время отклика в десятки миллисекунд для одного запроса.

Вы можете реализовать Trie самостоятельно довольно легко, или есть загрузки, которые вы можете скачать. См

Где найти стандартную реализацию карт на основе Trie в Java?

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

Answer 2

Тебе может не понадобиться что-то слишком причудливое. Ваш список «должен иметь» можно встретить с помощью простого механизма базы данных (например, BerkeleyDB или ESENT). Поместите все слова в таблицу, а затем используйте поиск для поиска слов.

B-дерево со страницами размером 8 КБ должно получить не менее 250 строк / страницу, что приведет к 1-му листу страниц, при этом B-дерево будет иметь высоту 3. Даже с диском ноутбука со скоростью вращения 5400 об / мин задержка ввода-вывода меньше чем 15 мс, так что в худшем случае вы сможете получить результаты через ~ 50 мс в худшем случае (полностью не кэшированные данные и медленный диск).

(Я создал приложение typeahead, которое использует класс PersistentDictionary на основе ESENT. С записями по 200 КБ я получаю ответ ~ 35 мс для первого поиска, когда данные вообще не кэшируются. После выполнения множества запросов ответ время падает до ~ 5 мс).

Для поддержки большого количества одновременно работающих пользователей вы можете добавить больше кеша или более быстрых дисков. Полное кеширование всех данных, вероятно, возможно (8 ГБ ОЗУ вполне доступны в наши дни), и данные о типе заголовка, безусловно, будут достаточно маленькими, чтобы поместиться на SSD, что обеспечит смешное количество операций ввода-вывода в секунду. Я мог бы пойти на SSD, потому что это даст большую производительность, даже когда кэш холодный (например, после перезапуска).

Решение на основе движка базы данных должно быть чрезвычайно быстрым.

Answer 3

Вот как мы это делаем в SOLR:

Ключ к поиску, если у вас есть правильный тип данных с соответствующими фабриками фильтров.

Установите тип данных в вашей схеме с именем textPrefix

Пример:

<!--
 This type is used for type ahead style searching and starts with searching. 
-->
−
<fieldType name="textPrefix" class="solr.TextField" positionIncrementGap="1" sortMissingLast="true">
−
<analyzer type="index">
<tokenizer class="solr.KeywordTokenizerFactory"/>
<filter class="ISOLatin1AccentFilterFactory"/>
<filter class="solr.LowerCaseFilterFactory"/>
<!-- Remove non alpha-numeric characters -->
<filter class="solr.PatternReplaceFilterFactory" pattern="[^a-zA-Z0-9 ]" replacement="" replace="all"/>
<filter class="solr.TrimFilterFactory"/>
<!-- Remove leading "the "-->
<filter class="solr.PatternReplaceFilterFactory" pattern="^the\s" replacement="" replace="all"/>
<filter class="solr.TrimFilterFactory"/>
<filter class="solr.EdgeNGramFilterFactory" minGramSize="1" maxGramSize="6"/>
</analyzer>
−
<analyzer type="query">
<tokenizer class="solr.KeywordTokenizerFactory"/>
<filter class="ISOLatin1AccentFilterFactory"/>
<filter class="solr.LowerCaseFilterFactory"/>
<!-- Remove non alpha-numeric characters -->
<filter class="solr.PatternReplaceFilterFactory" pattern="[^a-zA-Z0-9 ]" replacement="" replace="all"/>
<filter class="solr.TrimFilterFactory"/>
<!-- Remove leading "the "-->
<filter class="solr.PatternReplaceFilterFactory" pattern="^the\s" replacement="" replace="all"/>
<filter class="solr.TrimFilterFactory"/>
</analyzer>
</fieldType>

Затем в документе схемы создайте новое поле данных следующим образом:

<field name="CustomerNamePrefix" type="textPrefix" indexed="true" stored="false"/>

Затем сохраните копию Имени клиента в этом поле CustomerNamePrefix.

Теперь, когда вы запрашиваете это поле, вы можете просто использовать первые буквы имени, и оно даст вам наилучшее совпадение для этих букв. В зависимости от того, как вы выполняете запрос, вы можете повысить результаты, основываясь на других факторах в вашем документе.

Пример: * * один тысяча двадцать-одна

http://solrserver:8080/solr/select/?q=CustomerNamePrefix:jame&q.alt=*:*&start=0&rows=10&mm=1