Анализ и тестирование индекса RadixSpline

Статья посвящена тестовой реализации индекса RadixSpline и исследованию его производительности при различных параметрах настойки. Индекс RadixSpline относится к категории обученного индекса и предназначен для эффективного поиска в отсортированных данных в структуре ключ – значение. Индекс строится за один проход по данным и состоит из сплайн-аппроксимации с ограниченной погрешностью (GreedySpline) и разреженного индекса (RadixTable). В работе перечислены известные обученные индексы и сравнение их с исследуемым RadixSpline, который выгодно отличается от других тем, что имеет простую структуру и малое количество параметров настройки. Проведен анализ работы RadixSpline и его частей, а также влияние параметров на производительность и объем затрачиваемой памяти. Тестирование реализации показало, что RadixSpline способен значительно сократить время поиска по сравнению с бинарным поиском. Кроме того, при других настройках можно сократить используемую память. В работе предлагаются уточнения в алгоритме RadixSpline и исследование возможности его интеграции в промышленные продукты для работы с большими данными.