Redoal

Gesture indexing math library for generating stable index keys from gestures

A library focused purely on gesture indexing mathematics for DHT-based path comparisons and similarity search.

Core Capabilities

1. Gesture Normalization - Remove translation and scale variations
2. Path Resampling - Fixed number of evenly spaced points
3. Shape Descriptors - Hu invariant moments for shape characterization
4. Spectral Embeddings - Laplacian eigenvalues for gesture signature
5. Dimensionality Reduction - PCA for feature compression
6. Spatial Indexing - Morton/Z-order curve for integer keys
7. Multiple Hashing Strategies - Moment, spectral, hybrid, and global vector addressing
8. Multi-Probe Hashing - Query neighboring buckets for improved recall
9. HNSW Index - Approximate nearest neighbor search for fast similarity

Usage Example

Creating a Gesture Key for DHT

use redoal::*;

fn main() {
    // Load or create a gesture (sequence of points)
    let gesture = vec![
        Point::new(0.0, 0.0),
        Point::new(1.0, 0.0),
        Point::new(0.5, 1.0),
        Point::new(0.0, 0.5),
    ];

    // Normalize the gesture (remove translation and scale)
    let normalized = normalize(&gesture);

    // Resample to fixed number of points for consistency
    let resampled = resample(&normalized, 64);

    // Compute spectral signature
    let spectral = spectral_signature(&resampled, 4);

    // Create Morton code for DHT key
    let key = morton2(
        (spectral[0] * 1000.0) as u32,
        (spectral[1] * 1000.0) as u32
    );

    println!("Gesture key: {}", key);
}

Similarity Search with HNSW

use redoal::*;

fn find_similar_gestures(query: &[Point], database: &[(&str, Vec<Point>)]) -> Vec<(&str, f64)> {
    // Normalize and resample query
    let query_norm = normalize(query);
    let query_resamp = resample(&query_norm, 64);
    let query_spectral = spectral_signature(&query_resamp, 4);

    // Compute similarity for each gesture in database
    let mut similarities = Vec::new();

    for (name, gesture) in database {
        let gesture_norm = normalize(gesture);
        let gesture_resamp = resample(&gesture_norm, 64);
        let gesture_spectral = spectral_signature(&gesture_resamp, 4);

        // Euclidean distance between spectral signatures
        let distance = query_spectral.iter()
            .zip(gesture_spectral.iter())
            .map(|(a, b)| (a - b).powi(2))
            .sum::<f64>()
            .sqrt();

        similarities.push((name, distance));
    }

    // Sort by similarity (lower distance = more similar)
    similarities.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
    similarities
}

Multi-Probe Hashing for Improved Recall

use redoal::*;

fn multi_probe_query(points: &[Point]) {
    // Use moment hash for stable partitioning
    let moment_key = hu_moment_hash(points, 10);

    // Generate neighboring keys for multi-probe
    let neighbors = neighboring_keys(moment_key, 3);

    println!("Querying {} buckets", neighbors.len());
    for key in neighbors {
        println!("Bucket: {}", key);
    }

    // Or use adaptive probing
    let keys = adaptive_probe(
        points,
        10,
        5,
        15,
        HashStrategy::Hybrid,
    );

    println!("Adaptive probe found {} keys", keys.len());
}

HNSW Index for Fast Local Search

use redoal::*;

fn hnsw_example() {
    // Create HNSW index
    let mut index = HnswIndex::new(HnswConfig::default());

    // Add gestures to index
    let gesture1 = vec![
        Point::new(0.0, 0.0),
        Point::new(1.0, 0.0),
        Point::new(0.5, 1.0),
    ];

    let norm1 = normalize(&gesture1);
    let resamp1 = resample(&norm1, 64);
    let embedding1 = spectral_signature(&resamp1, 4);
    index.add(&embedding1, "triangle");

    // Query the index
    let query = vec![
        Point::new(0.1, 0.1),
        Point::new(1.1, 0.1),
        Point::new(0.6, 1.1),
    ];

    let norm = normalize(&query);
    let resamp = resample(&norm, 64);
    let embedding = spectral_signature(&resamp, 4);

    let results = index.search(&embedding, 5);

    for (label, distance) in results {
        println!("Found {} at distance {}", label, distance);
    }
}

Mathematical Operations

Module	Function	Purpose
point	Point::new(x, y)	Create 2D points with floating-point coordinates
normalize	normalize(points)	Center gesture at origin and scale to unit size
resample	resample(points, n)	Resample to n evenly spaced points
moments	hu_moments(points)	Compute Hu invariant moments (7-value shape descriptor)
spectral	spectral_signature(points, k)	Compute k Laplacian eigenvalues
pca	pca(data, k)	Dimensionality reduction to k principal components
morton	morton2(x, y)	Convert 2D coordinates to 64-bit Morton code
hashing	hu_moment_hash()	Moment-based hashing for DHT
hashing	spectral_hash()	Spectral-based hashing
hashing	hybrid_hash()	Combined moment+spectral hashing
hashing	vector_to_dht_key()	Global vector addressing
hashing	neighboring_keys()	Multi-probe hashing
hashing	adaptive_probe()	Adaptive query planning
hnsw	HnswIndex	Approximate nearest neighbor search

Hashing Strategies

Moment Hash (Stable)

• Uses Hu invariant moments
• Translation and scale invariant
• Good for broad gesture categories
• Coarse partitioning

Spectral Hash (Precise)

• Uses Laplacian eigenvalues
• More sensitive to small changes
• Better for fine-grained similarity
• Requires multi-probe for robustness

Hybrid Hash (Balanced)

• Combines moment and spectral features
• Weighted fusion for optimal balance
• Good default choice

Global Vector Addressing

• Directly maps embeddings to DHT keys
• No intermediate hashing
• Most precise but requires careful quantization

Multi-Probe Hashing

To handle hash instability and improve recall:

// Basic multi-probe
let key = hu_moment_hash(points, 10);
let neighbors = neighboring_keys(key, 3); // Query 3 neighboring buckets

// Adaptive probing
let keys = adaptive_probe(
    points,
    10,      // quantization bits
    5,       // min peers
    15,      // max peers
    HashStrategy::Hybrid, // hash strategy
);

LSH Index

For efficient similarity search using Locality-Sensitive Hashing:

use redoal::{Point, normalize, resample, spectral_signature, lsh::LSHIndex};

// Create LSH index with default parameters (4 tables, 8 dimensions, 12 projections)
let mut index = LSHIndex::new(4, 8, 12);

// Process gesture and extract spectral embedding
let gesture = vec![
    Point::new(0.0, 0.0),
    Point::new(1.0, 0.0),
    Point::new(0.5, 1.0),
];

let norm = normalize(&gesture);
let resamp = resample(&norm, 64);
let spectral: Vec<f32> = spectral_signature(&resamp, 8)
    .iter()
    .map(|x| *x as f32)
    .collect();

// Insert gesture into index
index.insert(spectral);

// Query for similar gestures
let query = vec![
    Point::new(0.1, 0.1),
    Point::new(1.1, 0.1),
    Point::new(0.6, 1.1),
];

let norm_query = normalize(&query);
let resamp_query = resample(&norm_query, 64);
let spectral_query: Vec<f32> = spectral_signature(&resamp_query, 8)
    .iter()
    .map(|x| *x as f32)
    .collect();

let results = index.query_knn(&spectral_query, 3);
for result in results {
    println!("Found similar gesture: {:?}", result);
}

LSH Features

• Deterministic Initialization: Fixed seeds for reproducible results
• Multi-table Indexing: 4 tables by default for improved recall
• Projection-based Hashing: ≤64 projections (u64 bit limit)
• L2 Distance Ranking: Always rank results by distance
• Multi-probe Search: Query neighboring buckets for better results
• Vector Normalization: Built-in normalization support

LSH Usage Example with Multi-probe

let mut index = LSHIndex::new(4, 8, 12);

// Insert gestures
let gesture1 = vec![1.0, 0.5, 0.3, 0.2, 0.1, 0.05, 0.03, 0.02];
let gesture2 = vec![1.1, 0.4, 0.35, 0.15, 0.12, 0.04, 0.02, 0.01];
index.insert(gesture1);
index.insert(gesture2);

// Query with multi-probe (checks neighboring buckets)
let query = vec![1.05, 0.45, 0.32, 0.18, 0.11, 0.045, 0.025, 0.015];
let results = index.query_knn_multi_probe(&query, 3, 2); // k=3, probe 2 bits

HNSW Index

For fast local similarity search on peers:

let mut index = HnswIndex::new(HnswConfig::default());
index.add(&embedding, "gesture_label");
let results = index.search(&query_embedding, 10);

Dependencies

• nalgebra - Linear algebra and matrix operations
• ndarray - Multi-dimensional array support
• itertools - Iteration helpers
• rand - Test data generation

Testing

Run tests with:

cargo test

All tests pass, demonstrating correct implementation of gesture indexing mathematics and distributed search capabilities.