precinct

Approximate nearest-neighbor search over region embeddings (boxes, balls).

Point-ANN indices (HNSW, FAISS) index points; R-trees index regions but collapse above ~10 dimensions. Region embeddings -- axis-aligned boxes, balls -- represent concepts as volumes, and trained ones live in 64-200 dimensions, so neither tool fits. precinct is the high-dimensional index for regions-as-objects: it answers three queries over a region corpus.

• nearest -- the k regions closest to a point, by true point-to-region distance (center index + rerank).
• membership (containing) -- the regions that enclose a point. Candidates come from a power-distance lift that ranks regions by extent, so a large general concept is found even when its center is far from the point -- the case a center-only index misses.
• subsumption (subsumers / subsumees) -- the regions that contain, or are contained by, a query region (a concept's hypernyms / hyponyms).
• overlap (overlapping) -- the regions that intersect a query region (the conjunction primitive: concepts sharing members).
• region similarity (nearest_region) -- the regions nearest a query region.

Retrieved regions carry their own scoring: Region::log_volume (generality) and Region::entailment_prob (the soft subsumption probability vol(self ∩ other) / vol(other), the box-lattice conditional).

Install

[dependencies]
precinct = "0.5"

or cargo add precinct.

Usage

use precinct::{AxisBox, RegionIndex, SearchParams};

// Build an index of 2-d boxes
let mut idx = RegionIndex::new(2, Default::default()).unwrap();
idx.add(0, AxisBox::new(vec![0.0, 0.0], vec![10.0, 10.0])); // general concept
idx.add(1, AxisBox::new(vec![4.0, 4.0], vec![6.0, 6.0]));   // specific concept
idx.add(2, AxisBox::new(vec![20.0, 20.0], vec![21.0, 21.0]));
idx.build().unwrap();

// nearest region to a point inside only the general concept
let nearest = idx.search(&[1.0, 1.0], 1, Default::default()).unwrap();
assert_eq!(nearest[0].0, 0);

// membership: regions enclosing [5, 5]  -> {0, 1}
let enclosing = idx.containing(&[5.0, 5.0], Default::default()).unwrap();

// subsumption: regions that contain a small probe box -> the more general concepts
let probe = AxisBox::new(vec![4.5, 4.5], vec![5.5, 5.5]);
let subsumers = idx.subsumers(&probe, Default::default()).unwrap();

SearchParams::overretrieve controls the over-retrieval factor (default 10x). Increasing it trades query latency for recall.

Updatable index (store feature)

store::UpdatableIndex wraps the region index in a durable, segmented store (segstore): incremental add/delete, a write-ahead log, checkpoint, compaction, and crash recovery. Per-segment RegionIndexes are cached by stable segment identity, so a mutation rebuilds only the new or changed segments, not the whole corpus; segments are searched and merged, and like the underlying HNSW the merged result is approximate. Opt-in; the default build does not depend on segstore.

Recall

Recall@k measured against an exhaustive point-to-region scan.

Real data, examples/glove_concepts (50K GloVe-6B-50d vectors clustered into 5,000 concept boxes, the bounding box of each cluster of related words):

Real data, examples/geo_regions (177 Natural Earth country boxes, [lon, lat] point queries): recall@3 92.9% over a world grid, and the nearest region by surface distance correctly diverges from the nearest by center (a South Pacific point resolves to Chile, far from any centroid). Fetch either dataset with the matching scripts/fetch_*.sh.

Synthetic box datasets (uniform-random centers, varied widths, examples/recall_gap):

The point ANN backend is vicinity (HNSW).

License

MIT OR Apache-2.0