SearchEngine

A Rust workspace containing two text-search projects:

1. search-engine/ — a hybrid search engine combining BM25 keyword retrieval with HNSW vector (semantic) search, evaluated on the MS MARCO passage ranking benchmark.
2. minigrep/ — a small, parallel grep clone built as a warm-up project.

---

Hybrid Search Engine

A search engine that fuses two complementary retrieval strategies:

• BM25 — classic keyword/lexical matching over an inverted index.
• HNSW vector search — semantic similarity using 384-dimensional embeddings from the all-MiniLM-L6-v2 transformer model (run locally via ONNX Runtime through the fastembed crate, no GPU required).

A custom vector-dominant fusion algorithm combines both: vector similarity is the primary signal, and BM25 acts as a selective booster for documents both methods agree on plus a small set of strong exact-keyword matches.

Results (MS MARCO, 50K+ docs, ~260 evaluated queries)

Method	MRR	NDCG@10	R@100	p50 latency
BM25	0.72	0.75	0.94	0.16 ms
Vector	0.88	0.89	0.98	3.94 ms
Hybrid	0.89	0.90	0.99	7.14 ms

Throughput: BM25 ~1,891 QPS, Vector ~245 QPS, Hybrid ~132 QPS — all sub-20 ms at p99.

The hybrid approach beats both BM25-only and vector-only, confirming the two signals are complementary. Because vector scores are the base signal, hybrid quality is guaranteed to be at least as good as vector-only.

Architecture

INDEXING (offline, per document):
  Document -> Analyzer -> Inverted Index   (for BM25)
  Document -> Embedder -> HNSW Graph       (for vectors)

QUERYING (online, per query):
  Query -> Analyzer  -> BM25 Scorer  -> top-K
  Query -> Embedder  -> HNSW Search  -> top-K
  Query -> Both      -> Fusion       -> top-K

Key components (search-engine/src/):

• Analyzer (analyzer.rs) — whitespace tokenizer → lowercase → punctuation removal → stop-word filtering → stemming. The same analyzer is used for indexing and querying, which is critical for term matching.
• Inverted index (index.rs) — HashMap<term, Vec<Posting>>; each posting stores doc id, term frequency, and positions. Tracks corpus statistics (total docs, total tokens) for BM25.
• BM25 scorer (scoring.rs) — saturating term frequency with document-length normalization. Tunable k1 (default 1.2) and b (default 0.75).
• HNSW index (vector_index.rs) — multi-layer navigable small-world graph for approximate nearest-neighbor search over 384-dim embeddings, using cosine similarity. Defaults: M=16, ef_construction=100, ef_search=100.
• Embeddings (embeddings.rs) — all-MiniLM-L6-v2 via the fastembed crate, with batch (parallel) embedding for fast indexing.
• Hybrid fusion (lib.rs) — vector-dominant fusion with cross-retrieval boosting and an RRF tiebreaker (see below).
• Benchmark harness (bench.rs, data_loader.rs) — MS MARCO loading, latency measurement, and quality metrics (MRR, NDCG@10, Precision/Recall@K).
• Persistence — bincode serialization for both indices; config stored as JSON.

Hybrid fusion strategy

BM25 scores and vector similarities live on completely different, differently-shaped scales, so naive averaging doesn't work well. Instead, the engine (search_hybrid) does:

1. Fetch ~20× candidates from both BM25 and vector search.
2. Normalize vector scores to [0, 1] and use them as the base score.
3. Cross-retrieval boost: if BM25 also ranks a doc in its top 20, add a bonus based on the combined rank quality (up to +0.25). Disagreement is ignored, so BM25 noise can't hurt quality.
4. Include the top few BM25-only results (not found by vectors) with low scores, to capture exact keyword matches.
5. Apply a tiny RRF (k=60) tiebreaker for near-identical scores.

alpha (recommended 0.3–0.5) controls BM25 boost strength.

Getting started

Prerequisites: a recent Rust toolchain (cargo). On first run, the fastembed crate downloads the all-MiniLM-L6-v2 ONNX model into search-engine/.fastembed_cache/.

use search_engine::{SearchEngine, SearchConfig};

let mut engine = SearchEngine::create("my_index", SearchConfig::default())?;

engine.add_documents_batch(&[
    ("doc1".into(), "Rust is a systems programming language".into()),
    ("doc2".into(), "Cosine similarity measures the angle between vectors".into()),
])?;
engine.commit()?; // persist to disk

let bm25   = engine.search("rust language", 10)?;        // keyword only
let vector = engine.search_vector("rust language", 10)?; // semantic only
let hybrid = engine.search_hybrid("rust language", 10, 0.5)?; // fused

Reopen a persisted index later with SearchEngine::open("my_index").

Running the benchmark

The benchmark (src/bin/benchmark.rs) expects MS MARCO passage-ranking files under search-engine/data/msmarco/:

data/msmarco/collection.tsv     # docid \t passage
data/msmarco/queries.dev.tsv    # qid   \t query
data/msmarco/qrels.dev.tsv      # qid 0 docid relevance

It evaluates 500 queries against all relevant docs plus 50K random negatives, then writes a report to benchmark_results/:

cd search-engine
cargo run --release --bin benchmark

Why Rust?

• Zero-cost abstractions: high-level iterator/trait code compiles to efficient machine code.
• Memory safety without a garbage collector — predictable p99 latency (no GC pauses), which matters for a search engine holding large indices in memory.
• The type system rules out whole classes of bugs (use-after-free, data races) at compile time.

Further reading

generate_doc.py generates a detailed technical reference PDF covering BM25, HNSW, the fusion algorithm, evaluation metrics, complexity analysis, and design tradeoffs. Build it with:

pip install fpdf2
python generate_doc.py   # writes Search_Engine_Technical_Reference.pdf

---

minigrep

A parallel command-line text search tool (minigrep/src/main.rs) that searches files and directories for a pattern, with colorized, match-highlighted output.

cd minigrep
cargo run -- <pattern> <path> [flags]

Flags:

• -i — case-insensitive (also enabled via the CASE_INSENSITIVE env var)
• -r — recurse into subdirectories
• --no-color — disable ANSI color output

Files and directory entries are searched in parallel via rayon, and the tool uses a custom typed error enum (MiniGrepError) for clear, actionable messages.