Approximate Filters using MCP Servers

Overview

This project compares several approximate filter data structures using MCP servers and LLM tool calls.

Approximate filters reduce memory usage by storing compressed summaries instead of full keys.
Because of this trade-off, some filters may return false positives or support limited operations.

The project compares:

Bloom Filter
Counting Bloom Filter
Cuckoo Filter
SuRF (Simplified Version)

An exact hash-set server is also included as a baseline for comparison.

Implemented MCP Servers

MCP Server	Data Structure	Description
`filter-naive`	Exact Set / Hash Table	Exact membership baseline
`filter-bloom`	Bloom Filter	Memory-efficient approximate membership filter
`filter-counting-bloom`	Counting Bloom Filter	Bloom Filter with deletion support
`filter-cuckoo`	Cuckoo Filter	Fingerprint-based approximate filter
`filter-surf`	Simplified SuRF	Approximate prefix/range filter

Project Goal

The goal of this project is to compare how different filter structures behave under the same workload.

The comparison focuses on:

membership query accuracy
false positive rate
memory usage
query latency
insertion and deletion support
prefix and range query capability

All servers expose the same ADT-style interface through MCP tools so that they can be tested consistently.

Scenario

Search Keyword Dictionary Management

The servers simulate a keyword search system.

Examples:

search autocomplete
keyword lookup
blocked-word checking
dictionary membership testing

The same keyword dataset and queries are used across all filters to compare performance and behavior.

ADT

All MCP servers provide the following tools:

Tool	Description
`build(items)`	Build filter from dataset
`insert(x)`	Insert a key
`contains(x)`	Membership query
`delete(x)`	Delete a key if supported
`range_query(lo, hi)`	Range query
`prefix_query(prefix)`	Prefix query
`memory_usage()`	Return estimated memory usage
`false_positive_rate()`	Measure false positive rate

Theoretical / Qualitative Structure Comparison

Structure	False Positives	Delete Support	Prefix/Range Query	Memory Efficiency
Exact Set	No	Yes	Yes	Low
Bloom Filter	Yes	No	No	Very High
Counting Bloom Filter	Yes	Yes	No	High
Cuckoo Filter	Yes	Yes	No	High
Simplified SuRF	Yes	No	Yes	Medium

This table describes the expected qualitative behavior of each structure. It is not a measured benchmark result.

Benchmark Results

Measured results are available in docs/benchmark_results.md.

The benchmark uses fixed synthetic workloads from src/membership_filters/benchmark.py and compares all filters with the same build items and absent-query probes. It reports estimated memory from memory_usage(), measured false positive rate from false_positive_rate(), and average local contains() latency.

Run it locally:

bash

PYTHONPATH=src python -m membership_filters.benchmark

powershell

$env:PYTHONPATH='src'; python -m membership_filters.benchmark

Run the smoke tests:

bash

PYTHONPATH=src python -m unittest discover -s tests

powershell

$env:PYTHONPATH='src'; python -m unittest discover -s tests

Notes

filter-naive is included as the exact baseline.
The SuRF server is a simplified educational implementation, not a full LOUDS-based production SuRF.
The project focuses on comparison and experimentation rather than production optimization.

Example Claude Desktop MCP Configuration

config.json

{
  "mcpServers": {
    "filter-naive": {
      "command": "python",
      "args": ["src/filter_/filter_naive_server.py"]
    },
    "filter-bloom": {
      "command": "python",
      "args": ["src/filter_/filter_bloom_server.py"]
    },
    "filter-counting-bloom": {
      "command": "python",
      "args": ["src/filter_/filter_counting_bloom_server.py"]
    },
    "filter-cuckoo": {
      "command": "python",
      "args": ["src/filter_/filter_cuckoo_server.py"]
    },
    "filter-surf": {
      "command": "python",
      "args": ["src/filter_/filter_surf_server.py"]
    }
  }
}

System Flow

text

Claude / LLM
        ↓
MCP Tool Call
        ↓
mcp_server.py
        ↓
registry.py
        ↓
Selected Filter Class
        ↓
Bloom / Counting Bloom / Cuckoo / SuRF / Exact Set

Flow Description

The LLM sends an MCP tool request.
mcp_server.py exposes the common ADT-style tools.
registry.py selects the requested filter implementation.
The selected filter processes the query.
The result is returned back through the MCP server.

This design allows all filters to be tested through the same interface and workload.

Repository Structure

text

src/
├── filter_/
│   ├── filter_naive_server.py
│   ├── filter_bloom_server.py
│   ├── filter_counting_bloom_server.py
│   ├── filter_cuckoo_server.py
│   └── filter_surf_server.py
│
└── membership_filters/
    ├── base.py
    ├── hashing.py
    ├── mcp_server.py
    ├── registry.py
    └── filters/