RangeSearch

RangeSearchNd

Проект предоставляет инструменты для эффективного поиска точек в $n$-мерном гиперпараллелепипеде (диапазоне) со сторонами, параллельными осям координат (nD Range Search).

Реализованные алгоритмы:

• KD-Tree (по книге М. де Берга «Вычислительная геометрия»)
• Range Tree (по книге М. де Берга «Вычислительная геометрия»)
• Boost R* Tree (интеграция из boost::geometry для сравнения производительности)

Requirements

• Система сборки: CMake (>= 3.15), Ninja
• Компилятор: C++23
• Зависимости C++: Boost, Qt5
• Тестирование и бенчмарки: Google Test (gtest), Google Benchmark (gbench)
• Анализ данных: Python3 (с пакетами numpy, matplotlib, scipy)

Build

# Конфигурация проекта
cmake -S . -B build -G Ninja -DCMAKE_EXPORT_COMPILE_COMMANDS=ON -DCMAKE_COLOR_DIAGNOSTICS=ON

# Компиляция 
cmake --build build -jN

Запуск и использование (Usage)

1. Модульное тестирование

Запуск модульных тестов для проверки корректности работы KD-Tree и Range Tree:

./build/tests/run_tests

Корректность алгоритмов валидируется методом Brute-Force на случайных наборах данных размерностью вплоть до 12 измерений.

2. Базовые бенчмарки

Запуск стандартного замера производительности для трех алгоритмов:

./build/benchmarks/run_benchmarks

Измеряется время построения деревьев и время выполнения поисковых запросов. Поиск тестируется на диапазонах, включающих в себя фиксированный процент точек от общего пространства пространства (1%, 5%, 10%, 25%, 50%, 75%, 100%).

2.1 Построение графиков

Для исследования зависимостей (время поиска от размера диапазона и от количества точек в структуре для 3D пространства) используйте расширенный флаг --findvary:

# 1. Запуск расширенных бенчмарков с экспортом в JSON
./build/benchmarks/run_benchmarks --benchmark_format=json --benchmark_out=benchmark_results.json --findvary

# 2. Настройка Python окружения
python3 -m venv .venv
source .venv/bin/activate
pip install numpy matplotlib scipy

# 3. Генерация графиков по результатам замеров
python analysis/analyze.py

После выполнения скрипта в папке analysis/plots/ будут сохранены два графика:

• search_vs_n.png — зависимость времени поиска от $N$ точек в дереве.
• search_vs_range.png — зависимость времени поиска от объема окна выборки.

4. Графический интерфейс (GUI)

Проект содержит интерактивное десктопное приложение, написанное на Qt5:

./build/src/RangeSearch

Возможности GUI:

• Загрузка собственного файла с точками из интерфейса.
• Визуальное интерактивное выполнение Range Search запросов.
• Встроенный вывод графиков производительности стандартного бенчмарка.

Benchmarks

Результаты для 3D пространства.

1. Время построения деревьев

CPU Time, затраченное на аллокацию и сборку структуры, а также эмпирически вычисленная асимптотическая сложность.

Алгоритм	N = 10,000	N = 100,000	Асимптотика (Big-O)
Boost R* Tree	1.02 ms	15.8 ms	$\approx 9.35 \cdot N \log N$
KD-Tree	1.75 ms	21.4 ms	$\approx 12.97 \cdot N \log N$
Range Tree	72.8 ms	1059 ms	$\approx 632.39 \cdot N \log N$

2. Время выполнения запроса (Range Search)

Время поиска целевых точек внутри $n$-мерного параллелепипеда. Замеры проведены для дерева фиксированного размера ($N = 10 000$ точек). Диапазон поиска варьируется от 1% до 100% от общего объема пространства.

Алгоритм	Малый диапазон (1%)	Средний диапазон (50%)	Полный охват (100%)
Boost R* Tree	0.048 us	9.92 us	93.0 us
KD-Tree	0.368 us	14.0 us	82.4 us
Range Tree	0.055 us	3.23 us	36.8 us

3. Графики