NAME
Data::KDTree::Shared - shared-memory k-d tree (nearest-neighbour + range search)
SYNOPSIS
use Data::KDTree::Shared;
# up to 100_000 points in 2 dimensions
my $kd = Data::KDTree::Shared->new(undef, 2, 100_000);
$kd->add([$lon, $lat], $city_id) for @cities; # each point carries an id
my $near = $kd->nearest([$x, $y]); # { id => ..., dist => ... }
my @k5 = $kd->knn([$x, $y], 5); # 5 nearest, closest first
my @box = $kd->range([$x0, $y0], [$x1, $y1]); # ids inside a bounding box
my @ball = $kd->radius([$x, $y], 3.0); # points within distance 3
# share the index across processes via a backing file
my $shared = Data::KDTree::Shared->new("/tmp/points.kd", 2, 100_000);DESCRIPTION
A k-d tree in shared memory: a spatial index over points in up to 16 dimensions that answers nearest-neighbour, k-nearest, bounding-box, and radius queries far faster than scanning every point. It complements Data::SpatialHash::Shared (a uniform grid, ideal for fixed-radius proximity): a k-d tree adapts to the point density and answers exact k-NN and arbitrary-box queries.
Points are appended in O(1) and each carries a user-supplied 64-bit id (defaulting to its insertion index). To keep queries fast regardless of insertion order, the tree is bulk-built balanced (median split on a cycling axis) the first time it is queried after any insert, so query recursion is O(log n) deep -- there is no risk of a degenerate, deep tree from sorted inserts.
Because the points live in a shared mapping, several processes build and query one index: any process that opens the same backing file, inherits the anonymous mapping across fork, or reopens a passed memfd sees the same points. A write-preferring futex rwlock with dead-process recovery guards mutation; once the tree is built, queries take only the read lock, so many run concurrently. Coordinates are double; a non-finite coordinate croaks. Linux-only. Requires 64-bit Perl.
The index has a fixed capacity; adding beyond it croaks. Memory is capacity * (dims * 8 + 16) bytes for the points plus a build scratch of capacity * 4 bytes and a fixed header.
METHODS
Constructors
my $kd = Data::KDTree::Shared->new($path, $dims, $capacity, $mode);
my $kd = Data::KDTree::Shared->new(undef, $dims, $capacity);
my $kd = Data::KDTree::Shared->new_memfd($name, $dims, $capacity);
my $kd = Data::KDTree::Shared->new_from_fd($fd);$dims is the number of dimensions (1..16) and $capacity the maximum number of points (1..2^24). new and new_memfd croak on an out-of-range $dims or $capacity. When reopening an existing file or memfd the stored geometry wins and the caller's arguments are ignored. An optional file mode may be passed as the last argument to new (e.g. 0660) for cross-user sharing; it defaults to 0600 (owner-only).
Adding points
my $i = $kd->add(\@coords); # id defaults to the insertion index
my $i = $kd->add(\@coords, $id); # attach an explicit 64-bit id
$kd->build; # (optional) force a rebuild nowadd appends one point (an array reference of exactly $dims finite coordinates) with an optional integer $id and returns its insertion index; it croaks if the tree is full or a coordinate is missing or non-finite. build forces the balanced tree to be (re)built immediately; you rarely need it, since queries build automatically after inserts.
Queries
my $near = $kd->nearest(\@point); # { id, dist } or undef if empty
my @knn = $kd->knn(\@point, $m); # up to $m nearest, closest first
my @ids = $kd->range(\@lo, \@hi); # ids whose coords lie in [lo, hi] per axis
my @ball = $kd->radius(\@point, $r); # { id, dist } within Euclidean distance $rnearest returns the single closest point as { id => ..., dist => ... } (Euclidean distance), or undef if the index is empty. knn returns up to $m such hash references sorted by increasing distance. range returns a plain list of the ids of every point inside the axis-aligned box with corners \@lo and \@hi (order unspecified). radius returns { id, dist } hash references for every point within Euclidean distance $r, closest first. All query points and box corners are array references of exactly $dims finite coordinates.
Introspection and lifecycle
$kd->count; # number of points added
$kd->capacity; # maximum number of points
$kd->dims; # number of dimensions
$kd->clear; # remove all points
$kd->stats; # { count, dims, capacity, dirty, ops, mmap_size }
$kd->path; $kd->memfd; $kd->sync; $kd->unlink;clear empties the index. sync flushes the mapping to its backing store (a no-op for anonymous and memfd trees); unlink removes the backing file (also callable as Class->unlink($path)); path returns the backing path (undef for anonymous, memfd, or fd-reopened trees) and memfd the backing descriptor.
SHARING ACROSS PROCESSES
The index lives in a shared mapping, shared the same three ways as the rest of the family: a backing file, an anonymous mapping inherited across fork, or a memfd passed to an unrelated process and reopened with new_from_fd($fd). Any process can add points; the first query after an add rebuilds the shared tree once (under the write lock), and subsequent queries run concurrently under the read lock.
SECURITY
Backing files are created with mode 0600 (owner-only) by default; pass an explicit octal mode (e.g. 0660) as the last argument to new for cross-user sharing. The file is opened with O_NOFOLLOW and O_EXCL, and the header is validated on attach. Any process granted write access is trusted not to corrupt the mapping.
CRASH SAFETY
Mutation is guarded by a futex-based write-preferring rwlock with PID-encoded ownership and dead-owner recovery. Adds are short bounded appends and the bulk build runs entirely under the write lock, so a crash leaves the index consistent up to the last completed operation (a crash mid-build simply leaves it marked for rebuild). Limitation: PID reuse is not detected (very unlikely in practice).
Reader-slot exhaustion (slotless readers): dead-process recovery attributes a crashed lock holder's contribution through its reader-slot. The slot table holds 1024 entries (one per concurrent reader process). If more than that many reader processes share one mapping at once, a reader that cannot claim a slot proceeds "slotless" -- it still takes the read lock but leaves no per-process record. If such a slotless reader is then killed while holding the read lock, its share of the lock cannot be attributed to a dead process, so writer recovery cannot reclaim it and writers may block until the mapping is recreated. Reaching this needs more than 1024 concurrent reader processes on one mapping plus a crash in the brief read-lock window; the dead-process slot reclaim keeps the table from filling with stale entries, so in practice it is very unlikely.
SEE ALSO
Data::SpatialHash::Shared (uniform-grid proximity), and the rest of the Data::*::Shared family.
AUTHOR
vividsnow
LICENSE
This is free software; you can redistribute it and/or modify it under the same terms as Perl itself.