Boundary-Based Incremental Search (BBIS)

Code and experiments for Boundary-Based Incremental Search for Large-k Continuous k-Nearest Neighbor Queries.

Overview

A continuous k-nearest neighbor (kCNN) query retrieves the kNN set at every location along a query segment. The set changes at locations called split points, where one point leaves the set and another enters it. Existing methods examine large leaving and entering candidate sets, resulting in numerous perpendicular bisector computations that substantially degrade query performance for large k.

We distill a general incremental search framework from existing kCNN algorithms and develop two strategies within this framework. Boundary-Based Candidate Reduction uses Voronoi adjacency to identify boundary candidates, shrinking the candidate sets and thereby reducing bisector computations. Incremental Candidate Maintenance dynamically maintains boundary candidates, enabling efficient candidate generation throughout the query. We combine these strategies to develop Boundary-Based Incremental Search (BBIS) and evaluate it on segment and trajectory queries.

Contents

run_ablation_formal.sh     Run the experiments
include/                  C++ headers
src/                      Algorithms and required index/storage code
experiments/cnn/          Experiment programs and scripts
indexes/                  Extract separately downloaded indexes here
queries/                  Segment and trajectory paths
plots/                    Experiment and query-path plots
scripts/                  Build and redraw published figures
results/paper-final15/    Final 15-query measurements and paper figures
results/                  New experiment outputs

Dependencies and build

The paper's experiments were conducted on an ARM-based Mac with 10 logical CPUs and 16 GiB RAM, running macOS 15.5.

The instructions below are for macOS. The release was also tested on macOS 15.2 / Apple Silicon with Apple Clang 16.0.0, CMake 4.3.1, GEOS 3.14.1 and Python 3.14.6. Building requires a C++17 compiler, CMake 3.20 or later, and GEOS. Plotting requires NumPy and Matplotlib; requirements.txt lists the tested versions.

Install Xcode command-line tools if needed, then run from the project root:

brew install cmake geos python
python3 -m venv .venv
.venv/bin/python -m pip install -r requirements.txt
bash scripts/build.sh

If CMake cannot locate GEOS:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release -DCMAKE_PREFIX_PATH="$(brew --prefix geos)"
cmake --build build -j4

The project builds the included spatial-index library and links it to GEOS.

The build script selects Release mode with C++17 and -O3 -DNDEBUG. The query library also uses -ffp-contract=off to preserve the experiment's floating-point calculations.

Download the indexes

Prebuilt R-tree and VoR-tree indexes are distributed separately from the GitHub repository.

Index download: Google Drive.

Download the index archive and extract it into indexes/ in the project root. The extracted layout should be:

indexes/
├── uniform/
├── normal/
├── germany/
├── france/
└── usa/

For example, the Uniform indexes include indexes/uniform/rtreepip_600w_uniform.idx and indexes/uniform/rtreepip_600w_uniform.dat, together with the corresponding VoR-tree files. Keep the .idx, .dat and .unbounded files together in their distribution directories.

The indexes occupy approximately 12.68 GiB after extraction. The 10 query CSV files are included in queries/, with 15 paths in each file. See indexes/README.md for the datasets and index sizes.

Published results

The final measurements used in the paper are included in results/paper-final15: 150 parameter settings, seven methods, 15 planned queries per group, 1,023 completed groups and 27 timed-out groups. This snapshot contains per-query records, summary CSVs, and the 24 final charts plus the shared legend in PDF and PNG. The figures are copied unchanged from the final experiment.

To redraw the final figures without running any queries:

.venv/bin/python -B scripts/render_paper_figures.py

This writes the redrawn figures to results/replotted-final15/. Replotting uses the included CSV files and requires only the Python dependencies. Use a separate output directory when running new experiments.

Run the experiment

After downloading the indexes, try one Uniform segment query at k=100 and length 0.05 with all seven methods:

bash run_ablation_formal.sh --output results/quickstart --case 'segment_length_uniform_00_*' --queries 1 --run

To run all experiments and generate the figures:

bash run_ablation_formal.sh --output results/formal --run --render

The script runs all seven methods on five datasets: Uniform, Normal, Germany, France and USA. Each query run records execution time, I/O, boundary tests and point participation counts.

Parameter	Values for segment and trajectory queries
k	10, 100, 500, 1000, 1500
Synthetic data size	2, 4, 6, 8, 10 million
Real data size	20%, 40%, 60%, 80%, 100%
Query length	0.05, 0.10, 0.15, 0.20, 0.25
Queries per condition	15

There are 150 parameter settings, each tested with seven methods. Each experiment varies one parameter while keeping the others at their default values: k=100, 6 million synthetic points or 60% of the real dataset, and query length 0.15. Query length means the segment length for segment queries and the total path length for trajectory queries. Each trajectory has eight equal-length segments.

For each workload and parameter setting, all methods use a common set of 15 distinct queries (IDs 0–14), with each query executed once per method. Results are checked at nine positions per segment. The script runs query 0 for all methods and settings, then query 1, and so on. Each method has a total time limit of queries × 600 seconds under each setting: 9,000 seconds for 15 queries. When that limit is reached, the current query is stopped and the remaining queries for that method and setting are skipped.

Run the same command again to continue an interrupted experiment. Completed queries are kept. Before continuing, the script checks that the settings, input files, source code and compiled programs still match the saved run. Use a new output directory after changing them.

Without --run, the command writes the experiment plan and result summaries. Add --render to create figures from the results. BUILD_DIR selects another build directory, and PYTHON_BIN selects another Python interpreter; defaults are build/ and .venv/bin/python.

Use --case to select experiment settings by their IDs. The pattern segment_k_* selects all segment experiments that vary k; repeat --case to select more groups:

bash run_ablation_formal.sh --output results/selected --case 'segment_k_*' --run --render

The comparison figures use all five datasets with the same settings and methods. When running a smaller selection, omit --render.

Algorithm names

Command name	CSV algorithm name	Figure label
tao	Tao	Tao
hu	HuKCnn	Hu
tpcnn	TPCnn	TP
bbis	BBIS	BBIS(Full)
bbis_cr	BBIS-CR	BBIS(IE)
bbis_i	BBIS-I	BBIS(I)
bbis_e	BBIS-E	BBIS(E)

The BBIS implementation is in include/algorithm/cnn/bbis.h and src/algorithm/cnn/bbis.cc. Figures show the methods in this order: Tao, Hu, TP, BBIS(I), BBIS(E), BBIS(IE), BBIS(Full).

For the current kNN set S, IBP(S) and EBP(S) denote its interior and exterior boundary points, respectively. The four ablation configurations are:

Method	Leaving candidates	Entering candidates	Incremental Candidate Maintenance
BBIS(I)	IBP(S)	Obtained through TP pruning	No
BBIS(E)	All k points in S	EBP(S)	No
BBIS(IE)	IBP(S)	EBP(S)	No
BBIS(Full)	IBP(S)	EBP(S)	Yes

All four configurations use the same VoR-tree and initial kNN search.

For trajectory queries, Tao and Hu traverse the R-tree for the whole trajectory and maintain a separate interval list for each segment. TP and the BBIS variants process consecutive segments in order, carrying the endpoint kNN set to the next segment. All four BBIS configurations carry their boundary candidate sets across segment joins and recompute bisector intersections for the new segment. BBIS(I) obtains entering candidates through TP pruning on each new segment. Within a segment, BBIS(I), BBIS(E) and BBIS(IE) reconstruct their candidate sets at each split point, while BBIS(Full) maintains them incrementally.

Measurements

Query time includes the initial kNN search, candidate processing, heap operations and storing result intervals in memory. It covers the entire elapsed time from the start of query execution until the results are returned. Index loading, correctness checks, CSV writing and freeing the results take place outside the timer.

Caches used by the algorithms are cleared between queries. On macOS, the storage code uses F_NOCACHE and disables read-ahead when reading index data.

boundary_tests counts point–point bisector tests and point–MBR tests. An MBR is a tree entry's minimum bounding rectangle; TP-based searches use these tests to prune tree entries. I/O counts disk-page reads. We also report Points participating per split point to measure the number of points involved in computing a single split point. When all queries for a method and setting finish, time and I/O are averaged over those queries. Methods that exceed the time limit are marked TLE.

Results and plots

Each run stores its settings in plan.json, parameter combinations in cases.csv, query results and logs in blocks/, and averaged results in summary/. summary/audit.json lists how many groups of queries have finished, timed out or remain to be run. After all methods have processed the first N queries, or reached their group budget, their summaries are saved in stages/round_NN/. With the default 15-query plan, stages with N < 15 summarize the first N queries. Under the default 15-query plan, all stages use the target group budget of 9,000 seconds.

File in summary/	Contents
query_results.csv	Per-query time, I/O, split counts and counters
aggregated_results.csv	Mean time and I/O for methods that finished all queries
boundary_test_results.csv	Point–point and point–MBR test totals
participation_results.csv	Mean point participations per final split, including leaving and entering components, for all seven methods
batch_status.csv	Completed-query counts and status for each method and setting

--render saves PDF and PNG figures in figures/ for time, I/O, boundary tests and total point participations per split point. The participation plots vary k, data size and query length for both segment and trajectory queries. Query counts and time budgets are stored in the figure metadata. Timed-out groups are marked × in front of the bars.

To draw query paths:

.venv/bin/python -B plots/plot_query_geometry.py queries/segments/segment_L0.15.csv queries/trajectories/trajectory_M08_T0.15.csv --output results/query_geometry.png

Inputs and attribution

The query seed is 20261016. Starting points are sampled uniformly in the unit square. If a proposed direction would take a path outside the square, another direction is sampled. All methods use the same paths. Experiments that vary k or dataset size also reuse those paths. Experiments that vary query length keep the same starting points and scale the paths along their original directions.

The spatial-index infrastructure derives from libspatialindex; its copyright and MIT notices remain in the source and LICENSE. Real-data indexes derive from OpenStreetMap POIs obtained through Geofabrik. See THIRD_PARTY_NOTICES.md.