Полнотекстовый индекс для часто обновляющихся библиотек Веретенников А. Б. Уральский федеральный университет им. Б. Н. Ельцина

Инвертированные файлы Для каждого слова сохраняем информацию о его вхождениях в документах: набор записей (ID, P) ID – идентификатор документа, P – позиция. Для каждого слова записи хранятся подряд. Создаются, например, при помощи сортировки. Трудно обновлять.

Обновление индекса 1) Пересоздание индекса (re-build). 2) Слияние (merging). 3) Частичное обновление индекса (in-place update). 4) Весь индекс в оперативной памяти, легко обновляется.

Слияние (merging) Читаем сливаемые индексы и записываем данные в один индекс. Осуществляется когда новый индекс достигает достаточно большого размера. Также изучаются стратегии одновременного создания нескольких индексов, определяются оптимальное количество и размеры индексов.

Слияние (merging) 1) Чтение и запись последовательные. 2) Затраты на сортировку. 3) Объем прочитанных и записанных байт равен суммарному объему индексов. 4) Одновременное создание нескольких индексов требует чтения из нескольких индексов при поиске (большее число обращений к диску). Nicholas Lester. Fast On-Line Index Construction by Geometric Partitioning. In CIKM 05: Proceedings of the 14th ACM international conference on Information and knowledge management, 2005, pp

Частичное обновление индекса (in - place update) При записи инвертированного файла резервируется свободное место после записей одного слова. При обновлении записываем в это свободное место. При необходимости переносим все записи в новое место. Lester, N., Zobel, J., Williams, H., Jan. In-place versus re-build versus re-merge: Index maintenance strategies for text retrieval systems. In: Estivill-Castro, V. (Ed.), Proc. Australasian Computer Science Conf., 2004, pp

Частичное обновление индекса (in - place update), продолжение Хранение записей в виде набора блоков (обычно фиксированного размера). При добавлении данных добавляются новые блоки. Brown, E. W., Callan, J. P., and Croft, W. B. Fast incremental indexing for full-text information retrieval. In Proceedings of the International Conference on Very Large Databases, Santiago, Chile, 1994, pp Tomasic A., Garcia-Molina H., and Shoens K. Incremental updates of inverted lists for text document retrieval. In Proc. ACMSIGMOD Int. Conf. on the Management of Data, Minneapolis, Minnesota, 1994, pp

Частичное обновление индекса (in - place update), проблемы 1) Случайный доступ к диску (достигает количества различных слов в документах, в определенных случаях суммарного количества слов в документах). 2) Фрагментация индекса и падение скорости поиска.

Сравнение Слияние (merge) эффективнее частичного обновления (inplace-update). Lester, N., Zobel, J., Williams, H., Jan. In-place versus re-build versus re-merge: Index maintenance strategies for text retrieval systems. In: Estivill- Castro, V. (Ed.), Proc. Australasian Computer Science Conf., 2004, pp Nicholas Lester. Fast On-Line Index Construction by Geometric Partitioning. In CIKM 05: Proceedings of the 14th ACM international conference on Information and knowledge management, 2005, pp

CLB-индекс 1) Количество дисковых операций снижается за счет кеширования и организации структуры данных. 2) Контролируется фрагментация. (Скорость поиска как в обычных инвертированных файлах).

Эксперимент Создание первоначального индекса на основании некоторого массива документов, и далее добавление в индекс данных различного размера: 1) Создание индекса для базового массива документов. 2) Добавление в индекс небольшого файла. 3) Добавление в индекс 1, 2, 3,..., 9 Мб данных. 4) Добавление в индекс 10, 20, 30,..., 90 Мб данных. 5) Добавление в индекс 100, 200, 300,..., 900 Мб данных. 6) Добавление в индекс 1000, 2000, 3000,..., Мб данных.

Общие результаты Суммарный объем текстов: 143 Гб. Всего документов 1,6 млн. Всего слов: 21 млд. Первоначальный индекс 85.2 Гб. Суммарное время создания и обновления индекса: 9 ч. 46 мин. (средняя скорость обработки ~ Гб/час).

Окружение Процессор: Intel(R) Core(TM) i7 CPU 2.67GHz. Оперативная память: 12 Гб. Жесткий диск : Seagate Barracuda , 7200 RPM, кэш 32 Мб., объем 2 Гб, ST AS. ОС: Microsoft Windows 2008 Enterprise x64 Edition with Service Pack 2. P. S. Максимальное количество оперативной памяти, которое было задействовано: 924 Мб. При чтении/записи на диск отключено кеширование OS.

Создание и обновление индекса Размер Общее Время записи Чтение Запись время индекса кластеров кластеров 85.2 Г 03:16:0601:18: Г 59.4 Г 1.4 К 00:48 00: Г 4.5 М 1.1 М 01:48 01: Г М 5.0 М 02:42 02: Г М 10.0 М 03:10 03: Г М 50.6 М 04:06 03: Г 1.7 Г М 04:28 04: Г 1.8 Г М 08:03 07: Г 2.8 Г 1.0 Г 10:01 08: Г 3.4 Г 4.9 Г 23:44 16: Г 7.6 Г 9.8 Г 42:26 28: Г 12.9 Г

Обновление при малых объемах новых данных Существенные накладные расходы при добавлении в индекс новых данных небольшого размера (1-50 Мб.) Начальная загрузка программы + чтение данных в кеш.

Промежуточный индекс Малые объемы добавляем в промежуточный индекс. Как только место в нем заканчивается перемещаем данные в основной индекс.

Требования к промежуточному индексу : 1) Быстрая запись данных в промежуточный индекс. 2) Время поиска в промежуточном индексе должно быть ограничено задаваемым параметром. 3) Суммарный размер данных, сохраняемых в промежуточном индексе, ограничен заданным параметром.

Параметры FormsCount – число базовых форм в словаре морфологического анализатора. GroupDataSize ~ 500 Кб – 2 Мб. GroupSize ~ 500. GroupsCount = FormsCount / GroupSize. Базовые формы делим на GroupsCount групп.

Промежуточный индекс GroupsCount блоков размером GroupDataSize. В каждом блоке записи для форм определенной группы. Набор записей с полями 1) ID документа. 2) Позиция в документе. 3) ID базовой формы.

Создание и обновление индекса Размер Общее Время записи Чтение Запись время индекса кластеров кластеров 85.2 Г 03:14:29 01:16: Г 59.3 Г 1.4 К 00:14 00: М 72.0 К 1.1 М 00:23 00: М 4.8 М 5.0 М 00:40 00: М 16.3 М 10.0 М 00:48 00: М 27.1 М 50.6 М 01:39 01: М 78.2 М М 03:03 02: М М М 08:17 07: Г 1.8 Г М 09:25 07: Г 2.8 Г 4.9 Г 22:03 15: Г 7.5 Г 9.8 Г 40:07 26: Г 12.8 Г

Общие результаты Суммарное время создания и обновления индекса: 8 ч. 46 мин.

Сравнение по времени Первые два десятка порций (1-100 Мб).

Обращение к диску при обновлении индекса

Промежуточный индекс и слияния (merging) Слияния инвертированных файлов Имеет смысл делать когда оба индекса достаточно большие. Промежуточный индекс Основной индекс большой. Промежуточный индекс мал ( Мб.)

Заключение Рассмотрено решение задачи быстрого обновления полнотекстового индекса, как для больших, так и для малых объемов исходных данных. При этом скорость поиска не снижается.