PaperlayerView exact revision on arXiv

Source-linked AI summary

Holo-NN: Holographic Nearest Neighbor Search via Compressive Sensing

Bryant Gipson

arXiv:2610.33224v1cs.CRcs.DBcs.IRcs.LG

TL;DR

Private ANN methods face constraints from data-dependent branching and cryptographic communication, motivating linear, non-interactive retrieval. Holo-NN combines localized feature mappings with Compressive Sensing and compares encrypted backends on SIFT-1M. The paper also reports a limitation in multi-neighbor ranking relative to Panther.

  • Problem

    In strict single-server private retrieval, data-dependent branching can leak access patterns, while non-interactive systems are forced into an O(N) scan.

    Source: §1.1 · p. 1

  • Method

    Holo-NN pairs localized feature mappings with Compressive Sensing and an offline holographic matrix to reduce a query to linear measurements.

    Source: §2.3 · p. 5, §7 · p. 12

  • Results

    On SIFT-1M, Holo-NN uses 2.10–11.13 MB CKKS wire in 1 RTT, below Panther’s 92.9 MB, SANNS’s 1.77 GB, and Compass’s 12.2 MB over 8 RTTs.

    Source: §1.4 · p. 3

  • Takeaways & Limitations

    For coverage-focused retrieval with a downstream exact-distance stage, Holo-NN’s reported coverage compares favorably with Panther and SANNS, though the comparison is not strict.

    Source: §6.4 · p. 12

    At M = 500,000, Holo-NN resolves 73.0% of the true ten neighbors, 15.9 points short of Panther, a deficit attributed to the ℓ1 recovery step.

    Source: §6.3 · p. 11

Abstract

from arXiv · show

In the age of AI, privacy-preserving approximate nearest neighbor (ANN) search over high-dimensional embeddings has emerged as a critical yet frustratingly challenging domain, dominated by tradeoffs between speed, privacy, and accuracy. Traditional tree and graph-based indexing structures (e.g., HNSW, ScaNN) rely fundamentally on non-linear operations that are computationally intractable under Fully Homomorphic Encryption (FHE) or blind server-side constraints. In this paper, we introduce Holo-NN (Holographic Nearest Neighbor Search), an algebraic framework that replaces data-dependent branching with a single linear projection. Our key observation is that while distances across a database are dense, neighborhood membership is inherently sparse: only a handful of points ever lie close to a query. By pairing locality-preserving feature transforms with Compressive Sensing, Holo-NN folds the entire database offline into a compact holographic sensing matrix. At query time, encrypted search reduces to a single, non-interactive matrix-vector multiplication---requiring no FHE bootstrapping, no multi-round interaction, and no client-side index state. This turns private retrieval into an embarrassingly parallel, accuracy-tunable computation that runs out of the box on both CPUs and GPUs, scaling efficiently to production databases. We offer a comparison against other state-of-the-art Private ANN algorithms to help situate the method in the broader context of production-grade private retrieval.

1 Introduction

Holo-NN recasts private nearest-neighbor retrieval as sparse-signal recovery, replacing data-dependent branching with offline database precomputation and a linear query. Its contributions include asymmetric feature hashing and encrypted-backend comparisons, with a tunable bandwidth–recall trade-off.

1.1 Motivation & Private Retrieval Landscape

  • Private ANN faces a choice between insecure data-dependent branching or costly multi-round approaches and a non-interactive O(N) scan under strict single-server privacy.Graph and tree methods rely on branching; several cited alternatives use multi-server assumptions or cryptographic overhead.Source: §1.1 · p. 1

1.2 Compressed Sensing

  • Compressive Sensing recovers a k-sparse signal from M ≪ N linear measurements, and Holo-NN targets the nearest-neighbor affinity vector directly rather than reconstructing an underlying signal.Because database features are known in advance, the server’s linear operator can be precomputed offline.Source: §1.2 · pp. 1–2

1.3 Nearest Neighbor Search as Sparse Signal Recovery

  • Although query-to-database distances are dense, nearest-neighbor membership is sparse, and continuous local affinities preserve metric resolution and ranking among adjacent points.The local affinity mass decays toward zero across distant points, supporting sparse recovery.Source: §1.3 · p. 2
  • Holo-NN computes compressed measurements through an offline holographic matrix and a linear query product, with accuracy tunable through measurement design.The framework combines Compressive Sensing with nonlinear feature embeddings for settings where server storage and parallel compute are relatively inexpensive.Source: §1.3 · p. 3

1.4 Summary of Contributions

  • Asymmetric FlyHash uses kq > kdb to avoid double-quantization dropouts, while the contribution summary distinguishes feature transforms for Euclidean and semantic manifolds.The paper also presents multi-backend encrypted implementations and a state-of-the-art comparison.Source: §1.4 · p. 3
  • On SIFT-1M, Holo-NN uses 2.10–11.13 MB CKKS wire in 1 RTT, below Panther’s 92.9 MB, SANNS’s 1.77 GB, and Compass’s 12.2 MB over 8 RTTs.The paper reports implementations across four cryptographic backends and compares them against private ANN systems.Source: §1.4 · p. 3

2 Background & Problem Formulation

The paper defines a client–server privacy setting and uses localized feature mappings to make nearest-neighbor affinities suitable for compressed linear recovery. Its background covers the security boundaries, measurement operator, and Euclidean and angular feature liftings.

2.1 Threat Model & Security Setting

  • The client holds a confidential query while an untrusted server hosts the database; retrieval targets approximate nearest neighbors under Euclidean or cosine similarity.The operational setting assumes abundant server storage and parallel compute, with client storage, WAN bandwidth, and multi-round communication as bottlenecks.Source: §2.1 · p. 4
  • Under the stated encryption setting, the server learns nothing about the query, and its linear pass touches measurement channels uniformly rather than following data-dependent branches.The execution is described as data-oblivious, eliminating memory access-pattern leakage.Source: §2.1 · p. 4
  • A single M-dimensional projection leaves an (N − M)-dimensional null space, while adaptive malicious clients issuing O(B) chosen basis queries fall outside the core primitive’s protection.The text calls for rate-limiting, noise flooding, and zero-knowledge proofs to address that case.Source: §2.1 · p. 4

2.2 Compressive Sensing & Restricted Isometry Property

  • Compressive Sensing uses M ≪ N measurements to reconstruct sparse signals, with the measurement operator described through the Restricted Isometry Property.The supplied passage identifies an order-k condition but does not state its full inequality.Source: §2.2 · p. 4
  • The measurement matrix may be drawn from random ensembles, and a pseudorandom function can generate its entries or columns on demand without materializing the matrix.The passage identifies Bernoulli as typically the most efficient choice among the discussed distributions.Source: §2.2 · p. 4

2.3 Kernel Lifting & Distance Approximations

  • Localized feature mappings lift vectors into a larger space where a similarity kernel is represented by a linear inner product.The kernel is described as positive, decreasing with metric distance, and vanishing outside a local neighborhood.Source: §2.3 · p. 4
  • Random Fourier Features approximate a Gaussian RBF whose inner products decay with Euclidean distance, while FlyHash maps angular proximity to overlap between sparse representations.The paper uses these liftings for Euclidean manifolds and directional semantic embeddings, respectively.Source: §2.3 · pp. 4–5

3 The Holo-NN Retrieval Architecture

Holo-NN maps queries and database points into complementary feature spaces so their affinity vector is approximately sparse. An offline server matrix then supports linear query evaluation, followed by client-side sparse recovery and dataset-specific operating-point tuning.

3.1 Feature Projections & Shared Feature Space (F, G)

  • Complementary feature maps preserve local similarity while mean-centering makes background inner products vanish in expectation, yielding an approximately sparse affinity vector.Its largest positive components represent the query’s local Voronoi neighborhood, while the background tail falls below a soft-thresholding floor.Source: §3.1 · p. 5

3.2 Offline Server Database Grating

  • The server pre-multiplies database features by a pseudorandom measurement matrix offline, storing H as M measurement channels across B feature dimensions.The computation is done once during index construction and is embarrassingly parallel, allowing batching or hierarchical partitioning.Source: §3.2 · p. 5

3.3 Non-Interactive Linear Query Evaluation (y = HF(q))

  • The client sends F(q), and the server computes a single linear evaluation that yields compressed measurements without materializing the full N-dimensional affinity vector.Because the operator is linear, the paper says LHE or Ring-LWE SIMD suffices; deep FHE and bootstrapping are unnecessary.Source: §3.3 · pp. 5–6

3.4 Client Enclave Sparse Recovery & Candidate Reranking

  • The client recovers affinities with a non-negative ℓ1-regularized inverse problem, selects the top K* candidates, and can retrieve payloads or rerank them through a secondary PIR query.Recovery can run locally or in a secure enclave; exact distances are computed locally without revealing candidate support to the server.Source: §3.4 · p. 6

3.5 Offline Index Tuning & Data-Dependent Operating Curves

  • Because effective sparsity and background cross-talk depend on the data manifold, offline validation profiling selects (M, B, K*) along the dataset’s empirical bandwidth–accuracy Pareto curve.The paper contrasts this with guessing M or K* in advance and notes that M scales as O(k_eff ln(N/k_eff)) for fixed sparsity.Source: §3.5 · p. 6

4 Asymmetric Neural Hashing & Geometric Duality

The section addresses false negatives from symmetric hard sparsification by using different query and database encodings. It also argues that the best feature transform depends on data geometry: RFF suits spatially structured Euclidean data, while Asymmetric FlyHash suits crowded semantic hyperspheres.

4.1 The Double-Quantization Pathology in Symmetric Sparse Coding

  • Symmetric top-k pruning can zero out a shared salient anchor when it falls just below either vector’s cutoff, causing false-negative dropouts.Asymmetric FlyHash instead keeps database features ultra-sparse and uses a broader query aperture, with the paper stating that this avoids added communication overhead in plaintext and encrypted deployments.Source: §4.1 · pp. 6–7

4.2 Geometric Duality: Continuous Euclidean RFF vs. Discrete Hyperplane Competition

  • RFF creates physical sparsity on spatially structured Euclidean manifolds, where distant points’ kernel affinities decay exponentially; the reported recovery is high-fidelity.The text gives a local kernel radius proportional to 1/√γ.Source: §4.2 · p. 7
  • On semantic hyperspheres, distance concentration can push RFF neighbor signals below Monte Carlo noise, whereas Asymmetric FlyHash uses k-WTA Voronoi cells to preserve locality and an in-cell Euclidean metric to break ties.The choice depends on data-manifold structure and density, not ambient dimension alone.Source: §4.2 · p. 7

5 Algorithmic ANN Benchmark Evaluation

Across four benchmark suites, Holo-NN’s recall varies with the feature transform, data geometry, and compression level. RFF performs on structured Euclidean data and Asymmetric FlyHash on angular semantic data, while the unlifted MIPS boundary case shows weaker recovery from cross-talk.

5.1 Benchmark Datasets & Experimental Setup

  • The evaluation uses four nearest-neighbor suites and profiles four nominal recall tiers on an RTX 3090 GPU and a six-core Intel Xeon host.Million-vector corpora are divided into 100 blocks; batched GPU FISTA takes under 0.4 s per query with at most 152 MB in GPU VRAM.Source: §5.1 · pp. 7–8

5.2 Multi-Scale Target Recall Benchmark Results

  • 94.10%–100.00% on SIFT-1M and 75.42%–97.79% on MNIST-784 at 10.0%–26.7% sub-Nyquist compression; GloVe-25 reaches 82.60%–97.50% at M/N = 8.03%–25.35%.For practical encrypted deployments with M/N ≤50%, SIFT-1M 1-recall@10 reaches 98.5%; pushing unclustered SIFT-1M to 100.0% crosses M/N > 100%.Source: §5.2 · p. 8
  • Last.fm-64, evaluated without feature lifting or a sparsification mechanism, reaches 57.60%–93.30% recall, with background cross-talk marking a boundary of applicability.The four suites cover Euclidean SIFT-1M and MNIST-784, angular GloVe-25, and maximum-inner-product Last.fm-64.Source: §5.1 · p. 7, §5.2 · p. 8

6 Encrypted Retrieval System Implementation & SOTA Comparison

Holo-NN implements private retrieval as a linear encrypted matrix-vector product across four backends, then compares their latency, bandwidth, and retrieval quality with other private ANN systems. Its measurements show efficient, low-wire retrieval, but also a distinction between finding neighbors and ranking them precisely.

6 Encrypted Retrieval System Implementation & SOTA Comparison

  • The encrypted protocol precomputes H offline, encrypts the lifted query, evaluates H against it, then decrypts measurements and runs FISTA for candidate IDs.An optional Batch PIR re-query fetches the top K* payloads for local exact-distance reranking.Source: §6 · p. 8, §6.2 · p. 10

6.1 Degree-1 Blind Linear Arithmetic & Compiler Optimizations

  • Because H is plaintext and the query is a degree-1 ciphertext, server evaluation uses plaintext-ciphertext operations at multiplicative depth 1 and requires zero bootstrapping.HEIR synthesizes diagonal ciphertext rotations and hoists plaintext weights; the section also reports 100% Top-1 parity for its four-block Wikipedia result.Source: §6.1 · pp. 8–9
  • HEIR/Cheddar evaluates an 8,192 × 8,192 block in 12.58 ms on RTX 3090 and 5.33 ms on H100, completing four Wikipedia blocks in 50.5 ms server compute.For the Wikipedia deployment, the report gives 100% Top-1 parity with plaintext and a 0.134 s end-to-end query.Source: §6.1 · p. 9, §6.2 · p. 11

6.2 End-to-End Encrypted Deployment (Wikipedia 500k)

  • On Wikipedia-500k, four-core CPU LinPIR completes end-to-end in 3.29 s, versus 32.9 s for 12-thread CPU CKKS, a reported 10.0× end-to-end speedup, and needs zero persistent server-side rotation keys.Source: §6.2 · pp. 9–10

6.3 State-of-the-Art Comparison

  • At M = 300,000, Holo-NN (LinPIR) matches Panther’s 92.9 MB wire traffic with 91.1 MB in one round trip, while HEIR-GPU CKKS uses 5.37 MB in 0.82 s on SIFT-1M.Against Compass’s 12.2 MB, Panther’s 92.9 MB, and SANNS’s 1.77 GB, HEIR-GPU CKKS is the lowest-wire single-server cryptographic system measured when session rotation keys can be registered; comparisons are at published operating points.Source: §6.3 · p. 11
  • Holo-NN’s 10-r@10 remains below Panther’s: 61.6% at M = 300,000 versus 88.85%, although its top-50 candidate set covers 92.0% of the true neighbors.The paper attributes the ranking gap to ℓ1 recovery on correlated neighbor features, not the measurement operator; it recommends understanding the current method as high-coverage rather than precise ranking.Source: §6.3 · p. 11, §6.4 · p. 12

6.4 Recall versus Bandwidth, and the Limits of ℓ1 Ranking

  • The bare 1-RTT FISTA sweep shows 1-recall@10 rising from 63.4% to 98.5%, while 10-recall@10 rises from 33.3% to 73.0% and remains unsaturated.At M = 300,000, increasing the cutoff to fifty recovers 92.0% of the true ten neighbors from a candidate set 20,000× smaller than the database; correlated features explain why ℓ1 recovery can favor one representative.Source: §6.4 · p. 12

7 Conclusion

Holo-NN recasts approximate nearest-neighbor retrieval as an underdetermined linear compressive-sensing problem, using an offline-compressed database representation for blind, privacy-preserving retrieval. Its linear, single-round design has no client-side index state or preprocessing stream, and can serve as a candidate-generation component or be used inline in machine-learning settings.

7 Conclusion

  • Holo-NN precomputes a degree-1 compressed database representation and retrieves with one linear operator using M ≪ N measurements in a single non-interactive round trip.The design requires no client-side index state or preprocessing stream.Source: §7 · p. 12
  • Asymmetric FlyHash removes the double-quantization loss that a symmetric sparse code would incur on high-dimensional semantic manifolds.Source: §7 · p. 12
  • Holo-NN also works as a generic high-confidence approximate nearest-neighbor algorithm in plaintext, while its blind form is a single-round private linear operation.Source: §7 · p. 12
  • The framework may serve as a candidate-generation component or be used directly in-line in machine-learning settings.Source: §7 · p. 13

Related papers

Loading 2610.33224v1…