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

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

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

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

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

5 Слияние (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

6 Частичное обновление индекса (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

7 Частичное обновление индекса (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

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

9 Сравнение Слияние (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

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

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

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

13 Окружение Процессор: 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.

14 Создание и обновление индекса Размер Общее Время записи Чтение Запись время индекса кластеров кластеров 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 Г

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

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

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

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

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

20 Создание и обновление индекса Размер Общее Время записи Чтение Запись время индекса кластеров кластеров 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 Г

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

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

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

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

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