Stochastic Indexing Primitives for Non-Deterministic Molecular Archives
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917230248198144 |
|---|---|
| author | Alpay, Faruk Sarioglu, Levent |
| author_facet | Alpay, Faruk Sarioglu, Levent |
| contents | Random access remains a central bottleneck in DNA-based data storage. Existing systems typically retrieve records by PCR enrichment or other multi-step biochemical procedures, which do not naturally support fast, massively parallel, content-addressable queries.
We introduce the Holographic Bloom Filter (HBF), a probabilistic indexing primitive that stores key-pointer associations as a single high-dimensional memory vector. HBF binds a key vector and a value (pointer) vector using circular convolution and superposes bindings across all records. A query decodes by correlating the memory with the query key and selecting the best matching value using a margin-based decision rule.
We give construction and decoding algorithms and a probabilistic analysis under explicit noise models (memory corruption and query/key mismatches). The analysis provides concentration bounds for match and non-match score distributions, explicit threshold and margin settings for a top K decoder, and exponential error decay in the vector dimension under standard randomness assumptions.
HBF offers a concrete, analyzable alternative to pointer-chasing molecular data structures, enabling one-shot associative retrieval while quantifying trade-offs among dimensionality, dataset size, and noise. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_20921 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Stochastic Indexing Primitives for Non-Deterministic Molecular Archives Alpay, Faruk Sarioglu, Levent Data Structures and Algorithms 68P05, 68P20, 68W20, 68P10 E.1; F.2.2; H.3.3 Random access remains a central bottleneck in DNA-based data storage. Existing systems typically retrieve records by PCR enrichment or other multi-step biochemical procedures, which do not naturally support fast, massively parallel, content-addressable queries. We introduce the Holographic Bloom Filter (HBF), a probabilistic indexing primitive that stores key-pointer associations as a single high-dimensional memory vector. HBF binds a key vector and a value (pointer) vector using circular convolution and superposes bindings across all records. A query decodes by correlating the memory with the query key and selecting the best matching value using a margin-based decision rule. We give construction and decoding algorithms and a probabilistic analysis under explicit noise models (memory corruption and query/key mismatches). The analysis provides concentration bounds for match and non-match score distributions, explicit threshold and margin settings for a top K decoder, and exponential error decay in the vector dimension under standard randomness assumptions. HBF offers a concrete, analyzable alternative to pointer-chasing molecular data structures, enabling one-shot associative retrieval while quantifying trade-offs among dimensionality, dataset size, and noise. |
| title | Stochastic Indexing Primitives for Non-Deterministic Molecular Archives |
| topic | Data Structures and Algorithms 68P05, 68P20, 68W20, 68P10 E.1; F.2.2; H.3.3 |
| url | https://arxiv.org/abs/2601.20921 |