A general framework for understanding and constructing probabilistic data structures with controlled error rates. This framework can also serve as a foundation for constructing oblivious programs as a composition of oblivious data types and oblivious functions.

The Bernoulli data type concept provides a formalism for reasoning about approximations of data structures that trade space and time complexity for bounded error rates. This framework unifies many existing probabilistic data structures (like Bloom filters) and enables the systematic construction of new ones.

# Configure build with tests
cmake -B build -DBERNOULLI_BUILD_TESTS=ON -DBERNOULLI_BUILD_EXAMPLES=ON

# Build
cmake --build build

# Run tests
cd build && ctest --output-on-failure

📚 Full Documentation (or run mkdocs serve locally)

• Theory

  • Bernoulli Model Overview - Foundational concepts
  • Bernoulli Boolean - Simplest Bernoulli type
  • Bernoulli Set - Probabilistic sets (includes Bloom filters)
  • Bernoulli Map - Approximate functions (includes Miller-Rabin as example)
  • Bernoulli Tuple - Product types with approximation
  • Bernoulli Unit & Void - Degenerate cases

• Implementation

  • Codecs - Encoding/decoding strategies
  • Regular Types - Type theory considerations

• API Reference

  • C++ API Documentation (Doxygen)

# Install MkDocs with Material theme
pip install mkdocs-material

# Serve documentation locally at http://127.0.0.1:8000
mkdocs serve

bernoulli_data_type/
├── include/              # Header-only C++ library
│   ├── bernoulli_bool/   # Bernoulli boolean types
│   ├── bernoulli_set/    # Bernoulli set types (Bloom filters, etc.)
│   ├── bernoulli_map/    # Bernoulli map/function types
│   └── ...
├── tests/                # Google Test suite
├── docs/                 # MkDocs documentation
│   ├── theory/           # Theoretical foundations
│   ├── implementation/   # Implementation guides
│   └── api/              # API reference (Doxygen output)
├── papers-latex/         # Academic papers (LaTeX sources)
└── research/             # Research notes and experiments

This project is under active development. For more information, visit metafunctor.com.