I built a sparse n-gram search index for on-device app memory in Swift (beats SQLite FTS5 and Core Spotlight on query latency in my benchmarks)
I've been working on local-first app memory (chat history, notes, local knowledge stores) and kept running into the same problem: full-text search on-device either means shipping a heavy server-style search stack, or accepting slow linear scans over stored records.
So I built RecallKit — a Swift package that builds a sparse substring inverted index over your app's local records, tuned specifically for iOS-sized memory payloads (not directory-scale corpora).
How it works, briefly:
- Records get chunked into bounded, overlapping spans instead of indexed as one giant blob
- Instead of indexing every substring (which is quadratic), it extracts a sparse family of substrings using a byte-pair weight table, and hashes them with XXH3 into an inverted index
- Literal queries become posting-list intersections, with exact verification at the end so hash collisions can't cause false matches
- Regex queries go through a planner that extracts mandatory literal structure to narrow candidates before falling back to full regex evaluation
It ships with an actor-based service (RecallKitIndexService) with batch upsert/delete, crash-safe rebuilds, background compaction via BGProcessingTask, app-group aware storage, and adapters for closure-based blobs, SQLite, Core Data, and SwiftData.
I included a benchmark app that runs RecallKit side-by-side against a naive scan, SQLite FTS5, Core Data substring fetches, and Core Spotlight. On a 1,000-record synthetic corpus, RecallKit's query latency beat all four — but its cold build cost is the highest of the bunch, since it's doing chunking + sparse extraction + posting-list construction in-process. So it's a build-time-for-query-time tradeoff, and it's most attractive for apps that repeatedly query the same local corpus (steady-state reuse, not one-shot searches).
Repo + full write-up on the algorithm and benchmark numbers: https://github.com/gregyoung14/RecallKit
Would love feedback, especially from anyone who's fought with FTS5 or Spotlight for in-app search before — curious if the tradeoffs here actually match real-world workloads.