High-performance MinHash, LSH indexing, b-bit compression, streaming deduplication & document clustering for MoonBit

minhash

lsh

deduplication

similarity

jaccard

moon add Hjyyutr/moon-minhash@0.1.0

Download zip

Author

Hjyyutr

Version

0.1.0

License

Apache-2.0

Repository

github.com/Hjyyutr/moon-minhash

Last updated

2 hours ago

Downloads

README

#moon-minhash

Deterministic MinHash, LSH indexing, text similarity, and streaming deduplication for MoonBit applications.

moon-minhash is a pure MoonBit toolkit for workloads that need to compare many documents without materializing every pairwise comparison. It combines configurable tokenization, MinHash and SimHash fingerprints, LSH candidate retrieval, exact verification, snapshot persistence, sharding, and evaluation utilities behind small package-level APIs.

#Core capabilities

Tokenization and normalization: character, word, and CJK n-grams; Porter stemming; stop-word filtering; Rabin CDC; streaming token windows; bounded chunks and frequency maps.
Hashing and signatures: FNV-1a, MurmurHash3, xxHash32, SipHash-2-4, universal hash families, MinHash, SuperMinHash, Weighted MinHash, seeded signature ensembles, and confidence intervals.
Search and indexing: configurable analysis pipelines, LSH banding and multi-probe lookup, deterministic ranking, pagination, batch ingestion, transactions, integrity checks, and index analytics.
Storage and scale-out: versioned checksummed snapshots, length-prefixed snapshot frames, snapshot diffs, b-bit MinHash compression, HyperLogLog, shard routing, balance reports, and merge utilities.
Deduplication and evaluation: batch and streaming deduplication, Union-Find clustering, policy validation, precision/recall/F1, ranking metrics, and threshold sweeps.

#Quick start

Install the MoonBit stable toolchain, then run the repository example:

moon run src/cli

The CLI performs one local end-to-end run: analysis, MinHash comparison, indexed search, snapshot encoding/decoding, and retrieval evaluation. The package can also be imported from MoonBit code using the module name in moon.mod.

#CLI

The executable entry points are deliberately small and reproducible:

# End-to-end search and persistence example
moon run src/cli

# Runtime benchmark suite; output is CSV
moon run src/bench_cli

Example CLI output:

moon-minhash: deterministic similarity index demo
documents=3, signature_length=64, approximate_similarity=0.6875, search_hits=1, snapshot_bytes=244, restored_documents=3, f1=1

#Architecture

src/
├── app/          reusable end-to-end application facade
├── tokenizer/    normalization, n-grams, CDC, stemming, streams, windows
├── hash/         non-cryptographic hash families and digest bundles
├── minhash/      MinHash, weighted/super signatures, ensembles, estimates
├── lsh/          banded and SimHash indexes with diagnostics
├── pipeline/     deterministic analysis, streaming, reports, validation
├── model/        records, configurations, results, limits, and aggregates
├── index/        document index, transactions, snapshots, pagination, health
├── codec/        validated snapshots, frames, inspection, and diffs
├── compress/     b-bit signatures, storage metrics, HyperLogLog
├── similarity/   edit, set, vector, and multi-metric similarity profiles
├── dedup/        batch/streaming deduplication and graph clustering
├── shard/        routing, distribution, balancing, and shard merge support
├── eval/         confusion matrices, ranking metrics, and threshold sweeps
├── cli/          end-to-end executable
└── bench_cli/    benchmark executable backed by src/bench

The main data path is:

DocumentRecord → Analyzer → DocumentFeatures → LSH candidates
                                      ↓                 ↓
                              Snapshot codec      exact verification
                                      ↓                 ↓
                              restore/index      SearchHit ranking

#Benchmarks

src/bench measures real runtime work with MoonBit's monotonic clock. It does not embed fixed timing claims; each invocation reports its own elapsed microseconds and derived operations per second.

Captured locally on 2026-08-19 with Moon 0.1.20260814 / moonc 0.10.8+8606a5800 on Windows, scale 1:

Workload	Iterations	Elapsed (µs)	Operations/s	Checksum
hash-24-word	20	245.3	81,532.82	4,205,139,225
analyze-document	20	9,762.2	2,048.72	1,185,206,067
index-search-32	20	18,600.9	1,075.22	20
snapshot-encode-16	20	3,300.6	6,059.50	20

Re-run the benchmark on the target machine before comparing numbers across environments:

moon run src/bench_cli

#Tests

The test suite covers deterministic outputs, Unicode and empty input, invalid configuration, duplicate IDs, truncated/corrupt snapshots, pagination boundaries, compression shapes, shard routing, ranking cutoffs, streaming resets, and transaction/integrity paths.

moon fmt --check
moon check --deny-warn
moon test --deny-warn
moon check --target all --deny-warn
moon test --target wasm --deny-warn
moon test --target js --deny-warn

The repository also includes a reproducible source counter:

.\tools\source_stats.ps1

At the time of this verification, the working tree contained 111 hand-written .mbt files and 10,435 lines: 8,205 production lines, 2,004 test lines, 215 benchmark lines, and 11 CLI lines. The script reports the exact current counts by category and does not count generated .mbti files.

#CI

.github/workflows/ci.yml installs the current MoonBit stable toolchain, prints the complete toolchain version, resolves dependencies, checks formatting, compiles all targets with warnings denied, runs native tests on Ubuntu and macOS, runs WebAssembly and JavaScript tests on all matrix entries, and verifies that moon info produces no interface diff. The workflow uses read-only repository permissions and disables checkout credential persistence.

#License

moon-minhash is distributed under the Apache License 2.0.

Site source Report issue Packages Build queue Skills Statistics