FORMALIZATION OF AN INDEX CONSTRUCTION MODEL FOR SEARCH ENGINES

DOI: https://doi.org/10.23670/IRJ.2022.120.6.007

ФОРМАЛИЗАЦИЯ МОДЕЛИ ПОСТРОЕНИЯ ИНДЕКСОВ ДЛЯ ИНФОРМАЦИОННО-ПОИСКОВЫХ СИСТЕМ

Научная статья

Васяева Н.С.¹, Дегаев М.Н.^2, *

^{1, 2} Поволжский государственный технологический университет, Йошкар-Ола, Россия

* Корреспондирующий автор (worksome[at]ya.ru)

Аннотация

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

Ключевые слова: информационно-поисковая система, информационно-ориентированная сеть, ICN, инвертированный индекс, иерархическое префиксное именование.

FORMALIZATION OF AN INDEX CONSTRUCTION MODEL FOR SEARCH ENGINES

Research article

Vasyaeva N.S.¹, Degaev M.N.^2, *

^{1, 2} Volga State University of Technology Yoshkar-Ola, Russia

* Corresponding author (worksome[at]ya.ru)

Abstract

Recently, the amount of data stored in information computer network has increased significantly; the demand of most data for the end client leads to an increase in the number of search requests in the network, which in turn increases the overall network traffic. In this regard, the overall concept of search engines increases the role of modern information-oriented networks (ICN), which correspond to the template of information-oriented applications and facilitate caching within the network. The article provides a formal representation of the  index structures construction model for «classical» search engines used in ICN networks. The obtained models allow estimating the predicted amount of memory allocated for service charts used in the search process for both approaches, and studying the question of the benefit from the use of the ICN-network approach.

Keywords: search engine, information-oriented network, ICN, inverted index, hierarchical prefix naming.

Введение

Эффективность поиска информации в информационно-поисковых системах (ИПС) напрямую зависит от способа индексации хранимых данных, которых на сегодняшний день существует достаточно много. Одни из них показывают хорошие характеристики при поиске полнотекстовой информации, например, инвертированный индекс, другие – при поиске файлов с изображениями, например, RF-метод [1].

Для ICN-сетей используются другие подходы, основные из которых базируются на применении префиксного именования запросов и использовании специальных таблиц, обеспечивающих одновременно и поиск запрашиваемой информации по префиксам и маршрутизацию запросов и ответов в сети [4].

Многие исследователи в области традиционных ИПС выделяют главные проблемы, возникающие при проектировании таких систем [2]:

• время отклика системы на поисковый запрос пользователя;
• эффективное хранение образа объекта в виде поискового индекса.

Причем первая проблема напрямую зависит от второй. В настоящее время при реализации на практике ICN-сетей обозначенные проблемы еще более усугубляются из-за увеличивающегося объема хранимой информации в кэше и неоптимальных алгоритмов построения индекса [3].

Данная статья посвящена вопросу формализации модели построения индексов для поисковых систем с целью оценки объема памяти, требуемого для хранения индексных структур.

Для оценки индекса в «традиционных» ИПС взят инвертированный индекс, поскольку он является самым популярным в настоящее время для полнотекстового поиска [1]. Данной модели сопоставляется подход иерархического префиксного именования, как наиболее известного в сетях ICN [4], [6].

Формализация модели инвертированного индекса

С точки зрения теории множеств инвертированный индекс можно представить в виде множества пост-листов, сопоставляемых наборам термов (рис. 1).

Для описания формального представления модели инвертируемого индекса используются следующие условные обозначения:

Т – множество термов;

IDdoc – множество документов;

Pos – множество пост листов;

N – общее число термов тезауруса;

T_i– i-ый терм;

 

Рис. 1 – Представление инвертированного индекса множествами

Формализация модели иерархического префиксного именования для ICN сетей

При любой архитектуре ICN сетей (архитектура NDN, Pursuit, SAIL, DONA [4]) для поиска информации в каждом узле сети, участвующем в поиске данных, называемых ContentRouter, используются три базовые структуры (рис. 2):

• таблица пересылки (FIT);
• таблица интересов (PIT);
• таблица хранилищ контента (CS).

Таблица пересылки (таблица информации пересылки) – FIT – связывает запрос или его часть (префикс) с адресом следующего узла сети, которому нужно переслать запрос.

Таблица интересов (ожидающая таблица интересов) – PIT – связывает запрос с адресом источника запроса.

Таблица хранилищ контента (хранилище контента) – CS – связывает запрос с адресом контента в кэш-памяти узла.

Рис. 2 – Представление базовых поисковых таблиц ICN-сетей

Каждый узел сети (конечный узел или маршрутизатор) может одновременно выступать источником запроса, узлом пересылки или хранилищем запрашиваемого контента для разных запросов.

Для описания формального представления рассматриваемых индексных множеств приняты следующие условные обозначения:

Для количественной оценки можно принять следующие допущения, что длина запроса Q_i не превышает 256 символов (256 байт), в качестве адресов (A_i, AI_i) используются традиционные IP-адреса размерностью 4 байта (IPv4) или 16 байт (IPv6), а размерность адреса хранения контента AC_i определяется размерностью шины адреса кэша и составляет 44-64 бита.

При иерархическом именовании запросов на поиск данных в сетях ICN могут использоваться префиксы, т.е. поиск идёт по частичному совпадению, что в итоге позволяет сократить объём хранимых данных в справочных таблицах.

Предложенные аналитические выражения являются многопараметровыми и могут быть использованы при программном моделировании прогнозируемого объёма памяти, отводимого в узлах сети для хранения индексных структур, задействованных в процессе поиска информации в «классических» ИПС и в сетях ICN.

Конфликт интересов Не указан.

Conflict of Interest None declared.

Список литературы / References

1. Манинг К.Д. Введение в информационный поиск / К. Д. Манинг, Р. Прабхакар, Х. Ше – Москва, 2011. – 519 с.
2. Вишняков Ю.М. Модели и методы построения индексов информационно-поисковых системах / Ю.М. Вишняков, С.Н. Юрчук // Известия Южного федерального университета. Технические науки. – 2011. – С. 153–157.
3. Варшавский П.Р. Применение методов поиска решения на основе прецедентов в информационных поисковых системах / П.Р Варшавский, Зо Лин, Аркар Мьо // Программные продукты и системы. Компьютерные и информационные науки. – 2013. – С. 385–392.
4. Xylomenos G. A Survey of Information-Centric Networking Research / G Xylomenos, C.N. Ververidis, V.A. Siris et al // IEEE Communications Surveys & Tutorials. – 2014. – № 2(16). – С. 1024–1049. [Electronic resource] URL: https://ieeexplore.ieee.org/document/6563278 (accessed: 15.04.2022).
5. Hail M. On the Performance of Caching and Forwarding in Information-Centric Networking for the IoT / M. Hail, M. Amadeo, A. Molinaro et al // 13th International Conference on Wired/Wireless Internet Communication 2015, Malaga, Spain. – Pp.313–326.
6. Delvadia K. CCJRF-ICN: A Novel Mechanism for Coadjuvant Caching Joint Request Forwarding in Information Centric Networks / K. Delvadia, N. Dutta, R. Jadeja // IEEE Access. – 2021.
7. Christoforaki M. Text vs. space: Efficient geo-search query processing / M. Christoforaki, J. He, C. Dimopoulos et al // Proceedings of the 20th ACM Conference on Information and Knowledge Management, CIKM 2011, Glasgow, United Kingdom.
8. Dinh N.-T. An Efficient Distributed Content Store-Based Caching Policy for Information-Centric Networking / -T. Dinh, Kim Y. // 6th ACM SIGCOMM Conference on Information-Centric Networking, Macao, China, 24–26 September. – 2019.
9. Carofiglio G. Bandwidth and Storage Sharing Performance in Information Centric Networking / G. Carofiglio, M.Gallo, L. Muscariello // ACM SIGCOMM workshop on Information-centric networking. – 2011. – Pp. 26–31.
10. Psaras I. Modelling and Evaluation of CCN-caching Trees / I. Psaras, R.G. Clegg, R. Landa et al // International Conference on Research in Networking. – 2011. – Pp 78–91.

Список литературы на английском языке / References in English

1. Manning C.D. Vvedenie v informacionnyj poisk [Introduction to search engine] / C.D. Manning, Prabhakar R., H. Sch. – Moscow, 2011. – 519 p. [in Russian]
2. Vishnyakov Y.M. Modeli i metody postroeniya indeksov informacionno-poiskovyh sistemah [Models and methods of search engines index construction] / Y.M. Vishnyakov, S.N. Yurchuk // Izvestiya Yuzhnogo federal'nogo universiteta. Tekhnicheskie nauki. [News of Southern Federal University. Technical sciences] – 2011. – P. 153–157. [in Russian]
3. Varshavskij P.R. Primenenie metodov poiska resheniya na osnove precedentov v informacionnyh poiskovyh sistemah [Application of case-based search techniques in search engines] / P.R Varshavskij, Xo Lin, Arkar Myo // Programmnye produkty i sistemy. Komp'yuternye i informacionnye nauki [Program products and systems. Computer and information sciences]. – 2013. – P. 385–392 [in Russian]
4. Xylomenos G. A Survey of Information-Centric Networking Research / G Xylomenos, C.N. Ververidis, V.A. Siris et al // IEEE Communications Surveys & Tutorials. – 2014. – № 2(16). – Pp. 1024–1049. [Electronic resource]. URL: https://ieeexplore.ieee.org/document/6563278 (дата обращения: 15.04.2022).
5. Hail M. On the Performance of Caching and Forwarding in Information-Centric Networking for the IoT / M. Hail, M. Amadeo, A. Molinaro et al // 13th International Conference on Wired/Wireless Internet Communication 2015, Malaga, Spain. – Pp.313–326.
6. Delvadia K. CCJRF-ICN: A Novel Mechanism for Coadjuvant Caching Joint Request Forwarding in Information Centric Networks / K. Delvadia, N. Dutta, R. Jadeja // IEEE Access. – 2021.
7. Christoforaki M. Text vs. space: Efficient geo-search query processing / M. Christoforaki, J. He, C. Dimopoulos et al // Proceedings of the 20th ACM Conference on Information and Knowledge Management, CIKM 2011, Glasgow, United Kingdom.
8. Dinh N.-T. An Efficient Distributed Content Store-Based Caching Policy for Information-Centric Networking / -T. Dinh, Kim Y. // 6th ACM SIGCOMM Conference on Information-Centric Networking, Macao, China, 24–26 September. – 2019.
9. Carofiglio G. Bandwidth and Storage Sharing Performance in Information Centric Networking / G. Carofiglio, M.Gallo, L. Muscariello // ACM SIGCOMM workshop on Information-centric networking. – 2011. – Pp. 26–31.
10. Psaras I. Modelling and Evaluation of CCN-caching Trees / I. Psaras, R.G. Clegg, R. Landa et al // International Conference on Research in Networking. – 2011. – Pp 78–91.