Информация являлась и является одним из самых ценных ресурсов. С появлением вычислительной техники в XX-м веке стала актуальна проблема хранения, упорядочивания и поиска информации. Человек пишет книги, сочиняет
музыку, делает фотографии, снимает видео — это только самые популярные
виды информации. Каждый год её количество только увеличивается. В следствие чего возрастает нагрузка на вычислительные машины. Требуются все более быстрые и быстрые алгоритмы. Для каждого отдельного типа информации
стараются подобрать как можно более оптимальный алгоритм.
При хранении информации встает проблема её поиска по нескольким, зачастую числовым, параметрам. Одним из ярких и визуальных примеров является
трёхмерное пространство с заданным в нём множеством точек. Необходимо по
различным интерактивным ограничивающим запросам находить соответствующую им информации [1]. Частным случаем данного примера может быть база
данных, содержащая список людей с их датами рождений. Среди которых, например, требуется находить записи с годами от 1990 до 2000, месяцами от 1 до
7, а днями от 15 до 30.
Ещё во второй половине XX-го века были начаты и ведутся до сих пор разработки алгоритмов для хранения, упорядочивания и поиска элементов трёхмерного пространства [2, 3]. Многие из них основаны на мощном фундаменте
из сбалансированных деревьев, частным случаем которых являются двоичные
деревья поиска [4]. Изменение условий, накладываемых на такие структуры
данных, позволяет варьировать алгоритмическую сложность, балансируя между сложностями операций построения, изменения и поиска.5
Такие структуры данных используются в совершенно различных областях:
от военных тренажеров до симуляции и визуализации различных физических
явлений [5], что только увеличивает к ним интерес.
В настоящее время алгоритмы обработки линейных запросов находят своё
применение в различных областях, от военной промышленности до сферы развлечений. Одним из самых мощных фундаментов данных алгоритмов являются сбалансированные деревья. Для которых введение дополнительных условий
позволяет балансировать между производительностью и потреблением памяти, времени работы для определенного типа запросов. Поэтому была предложена модификация дерева, в которой каждая вершина имеет не более восьми
потомков, а разбивается так, чтобы разность между размером минимального
и максимального потомка была минимальна. И есть основания полагать, что
предложенный алгоритм является хорошей альтернативой для уже существующих, так как работает эффективнее на определённых типах данных. И для
проверки данного предположения был разработан программный комплекс для
численных экспериментов и сравнения производительностей алгоритмов.
В результате проверки на различных входных данных было выявлено улучшение производительности на таких типах данных как: равномерное распределение, распределение в виде сетки, разряженное распределение с большими
одиночными скоплениями. Что подтверждается теоретическими расчетами анализа алгоритма.
