hilbertquery

README

HilbertQuery

HilbertQuery is a high-performance multidimensional range-query engine for decentralized grids. It utilizes 64-bit Hilbert Space-Filling Curves (SFC) to linearize N-dimensional metadata into a 1D search space, enabling $O(\log N)$ discovery in environments where centralized indexing is impossible or undesirable.

Originally developed as the discovery primitive for Project CORTEX (Georgia Tech MSCS), this library is designed to solve the "Analytical Crisis" in a decentralized web -- allowing peers to match based on multiple attributes (e.g., Reputation, Latency, and Task Capacity) without exhaustive network scans.

🚀 The Problem: Beyond Key-Value Lookups

Standard Distributed Hash Tables (DHTs) are excellent at finding a specific key, but they are "blind" to metadata. If you need to find an agent that has:

• Reputation > 80
• Latency < 50ms
• Available RAM > 4GB

...a traditional DHT requires you to scan the entire network ( $O(N)$ ). HilbertQuery maps these dimensions into a single curve, allowing you to generate a mathematical "Budget" of linear ranges that cover your target multidimensional volume.

✨ Key Features

• Memory-Efficient: Utilizes sync.Pool for internal workspaces to eliminate GC thrashing during recursive subdivision.
• Tunable Precision: Includes a unique Budget parameter to balance the trade-off between range precision and memory footprint.
• Safety First: Implements SoftMaxRanges and MaxDepth guards to prevent Out-of-Memory (OOM) errors and stack overflows in sparse datasets.
• Mechanical Sympathy: Optimized bitwise operations for 64-bit coordinate systems.

📦 Installation

go get github.com/Possum/hilbertquery

🛠 Usage

import "github.com/yourusername/hilbertquery"

// Initialize a 3-dimensional Hilbert space with 16 bits of precision per dim
h := hilbertquery.NewHilbert(16, 3)

// Define your tuning knobs
h.Budget = 2000          // Soft cap on range subdivisions
h.SoftMaxRanges = 5000   // Trigger range merging to save memory
h.MaxRanges = 10000      // Hard safety limit

// Define a query volume (e.g., Min/Max coordinates for 3 attributes)
query := hilbertquery.Query{
    Targets: []hilbertquery.Bounds{
        {
            Min: []uint32{80, 0, 4096},   // Min: Rep 80, Latency 0ms, RAM 4GB
            Max: []uint32{100, 50, 16384}, // Max: Rep 100, Latency 50ms, RAM 16GB
        },
    },
    MaxDepth: 12, // Optional: Max depth for recursion to prevent infinite subdivision
    MaxGap: 100,  // Optional: Maximum gap between ranges to consider for merging

}

// Generate the linear ranges to search in your DHT/Database
ranges := h.Execute(query)

for _, r := range ranges {
    fmt.Printf("Search Range: %d - %d\n", r.Start, r.End)
}

⚙️ Performance Tuning: The "Budget" Parameter

The Budget parameter is the primary lever for system architects:

• High Budget (e.g., 20,000): Produces highly precise ranges. This minimizes "false positive" data fetched from the network but increases local CPU/Memory usage during query generation. Recommended for P2P/Decentralized environments where network I/O is the bottleneck.
• Low Budget (e.g., 500): Produces broader, merged ranges. This is faster to compute and uses less memory but may include "empty" space in the results. Recommended for local in-memory filtering.

🔎 Architecture & Dependencies

HilbertQuery is built on top of the excellent jtejido/hilbert library. While the underlying library handles the core bit-manipulation for Hilbert curve mapping, HilbertQuery provides the high-level orchestration layer for:

• Recursive Search: Pruning N-dimensional space to find range intersections.
• Memory Management: Zero-allocation query execution via sync.Pool.
• Range Optimization: Heuristic-based merging to balance precision vs. network/storage overhead.

🎓 Academic Origins

This library was developed by Daniel LeWarne as part of MSCS research at Georgia Tech covering Neural-Inspired Sovereign Grids. The underlying logic provides the "Nervous System" for CORTEX, enabling decentralized participants to locate one another in a multidimensional Hilbert space without relying on a central authority.

📄 License

MIT License. See LICENSE for details.

Documentation

Index

• type Bounds
• type Hilbert
  • func New(bits uint32, dimensions uint32) *Hilbert
  • func (h *Hilbert) Execute(query Query) ([]Range, error)
  • func (h *Hilbert) NewMultiQuery(targets []Bounds) (Query, error)
  • func (h *Hilbert) NewMultiQueryWithMaxDepth(targets []Bounds, maxDepth uint) (Query, error)
  • func (h *Hilbert) NewQuery(target Bounds) (Query, error)
  • func (h *Hilbert) NewQueryWithMaxDepth(target Bounds, maxDepth uint) (Query, error)
  • func (h *Hilbert) QueryIntersection(query Query) ([]Range, error)
  • func (h *Hilbert) QueryUnion(query Query) ([]Range, error)
• type Query
• type Range

Types

type Bounds

type Bounds struct {
	Min, Max []uint32 // Multi-dimensional coordinates
}

type Hilbert

type Hilbert struct {
	hilbert.Hilbert

	Budget float64

	SoftMaxRanges int
	MaxRanges     int
	// contains filtered or unexported fields
}

func New

func New(bits uint32, dimensions uint32) *Hilbert

func (*Hilbert) Execute

func (h *Hilbert) Execute(query Query) ([]Range, error)

func (*Hilbert) NewMultiQuery

func (h *Hilbert) NewMultiQuery(targets []Bounds) (Query, error)

func (*Hilbert) NewMultiQueryWithMaxDepth

func (h *Hilbert) NewMultiQueryWithMaxDepth(targets []Bounds, maxDepth uint) (Query, error)

func (*Hilbert) NewQuery

func (h *Hilbert) NewQuery(target Bounds) (Query, error)

func (*Hilbert) NewQueryWithMaxDepth

func (h *Hilbert) NewQueryWithMaxDepth(target Bounds, maxDepth uint) (Query, error)

func (*Hilbert) QueryIntersection

func (h *Hilbert) QueryIntersection(query Query) ([]Range, error)

NOTE this function has not been tested

func (*Hilbert) QueryUnion

func (h *Hilbert) QueryUnion(query Query) ([]Range, error)

type Query

type Query struct {
	Targets  []Bounds // The actual query filters
	MaxDepth uint     // Optional: Max depth for recursion to prevent infinite subdivision
	MaxGap   uint64   // Optional: Maximum gap between ranges to consider for merging
	// contains filtered or unexported fields
}

type Range

type Range struct {
	Start, End uint64
}