The kdtools package exports a C++ header implementing sorting and searching on ranges of tuple-like objects without using trees. Note that searching and sorting are supported on mixed-types. It is based on a kd-tree-like recursive sorting algorithm. Once sorted, one can perform a range- or nearest-neighbor- query. More details are here. Methods and benchmarks are here.

library(kdtools)
x = kd_sort(matrix(runif(400), 200))
plot(x, type  = 'l', asp = 1, axes = FALSE, xlab = NA, ylab = NA)
points(x, pch = 19, col = rainbow(200, alpha = 0.25), cex = 2)
y = kd_range_query(x, c(1/4, 1/4), c(3/4, 3/4))
points(y, pch = 19, cex = 0.5, col = "red")

Native Data Frame Support

The core C++ header implements sorting and searching on vectors of tuples with the number of dimensions determined at compile time. I have generalized the package code to work on an arbitrary data frame (or any list of equal-length vectors). This sorting and search works on any times that are equality-comparable and less-than-comparable in the C++ STL sense.

Note: Switching to C++17 broke CI (I’d be grateful for a pull-request fixing this as I cannot make heads-nor-tails of the required configuration). The code builds and checks fine on my systems.

CRAN status CircleCI build status AppVeyor build status Coverage status DOI