Search

Let there be a set of objects, where each object is characterized by Boolean features. Let logical query or Boolean query denote a query to find objects characterized by a Boolean function by features, for example, “documents with all words ...and any words ...and without words ...”. The terms “object” and “document” are used interchangeably hereinafter. The features may have different semantics, i. e. some features may correspond to the words of the document, some to labels or categories, and some to per-bit time quantum of a document’s date.Although indices executing Boolean queries are well researched in the literature, the common technique of maintaining posting lists is not always acceptable. If the data volume can reach to the order of petabytes, a compact index structure becomes vital.The aim of the research is to suggest a method to build an efficient bitmap index in secondary memory that allows us to update or append data being indexed with high write throughput.We propose an efficient LSM-based index for bitmaps and feature design for practical applications. We also discuss aspects of building of joined indices in order to achieve good scalability. The paper describes the architecture and algorithms of a suggested index and includes results of our experiments that show sustainable performance of our solution., Пусть существует набор объектов, где каждый объект характеризуется логическими признаками. Пусть логический запрос или Булевский запрос обозначает запрос на поиск объектов, характеризуемых логической функцией, по признакам, например, “документы со всеми словами...и любыми словами ...и без слов...”. Термины ”объект“ и "документ” в дальнейшем используются как взаимозаменяемые. Компоненты могут иметь различную семантику, т.е. е. некоторые компоненты могут соответствовать словам документа, некоторые ‒ меткам или категориям, а некоторые — побитовым квантам времени даты документа.Хотя индексы, использующие логические запросы, хорошо изучены в литературе, общий метод ведения списков рассылки не всегда приемлем. Если объем данных может достигать порядка петабайт, компактная структура индекса становится жизненно важной.Цель исследования ‒ предложить метод построения эффективного растрового индекса во вторичной памяти, позволяющий обновлять или дополнять индексируемые данные с высокой скоростью записи. Мы предлагаем эффективный индекс на основе LSM для растровых изображений и дизайн элементов для практических приложений. Мы также обсуждаем аспекты построения объединенных индексов для достижения хорошей масштабируемости. В статье описываются архитектура и алгоритмы предлагаемого индекса, а также результаты наших экспериментов, которые показывают устойчивую производительность нашего решения., Международный научный журнал "Современные информационные технологии и ИТ-образование", Выпуск 1 2022, Pages 134-143