# Algorithms and Structures Exploration — TRD ## Status In Progress — 2026-05-17 ## Overview This TRD captures the audit of algorithm and data-structure choices in `@coda/data-structures`, why each one was adopted, deferred, or rejected, and what would justify revisiting the deferred ones. It is the canonical reference for "we already thought about X, here's where that landed." The audit triggered a greenfield review of the package and its consumers. The findings about _how to improve what's there_ live in that review. This TRD covers the broader question: **what algorithms belong in this package, what doesn't, and why**. Context: `@coda/data-structures` is the workspace package for generic in-memory data structures and algorithms. Recent work added segment tree, Fenwick tree, list structures, sorted-collection facade, circular collections, monotonic algorithms, quickselect, MST, APSP, SCC, Bellman-Ford, LCA, multi-source BFS, and non-comparison sorts. `CircularMap` is now the single source of truth for bounded keyed eviction — `@coda/common`'s `LRUCache` is a thin adapter on top of it. ## Goals - Document each algorithm/structure considered, with a verdict and rationale, so future contributors don't re-explore the same ground. - Capture workload-shape evidence for or against probabilistic / sketch algorithms. - Identify integration sites where the package's structures should be adopted but currently aren't. - Record what would change the verdict (e.g., "adopt HLL when we ship cross-process search analytics"). ## Adoption status ### Adopted — in-tree | Structure / Algorithm | Adopted because | | -------------------------------------------------------------- | -------------------------------------------------------- | | Heap (binary + skew) | Pervasive: top-K, priority queue, Dijkstra/Prim, GC | | AA / AVL trees | Sorted-set semantics, range scans, predecessor/successor | | Trie (sequence + string) | FQN lookup, glossary prefix expansion, fuzzy search | | DSU (ArrayDSU / KeyDSU) | Kruskal MST, connected components | | Deque / Queue / Stack (linked + array) | BFS, scheduling, pipelines | | Ring buffer | Bounded position-indexed buffer | | Graph (AdjacencyGraph / SubgraphView) | Schema graph, agent context graph | | Levenshtein / OSA / KMP (`indicesOf`) | Fuzzy matching in search | | BFS variants (neighborhood, path, bidirectional, multi-source) | Graph traversal in search + client viewer | | Dijkstra (lazy heap) | Weighted shortest path; pairs with existing heap | | Topological sort (Kahn level-aware) | Tool dependency ordering | | Monotonic stack / sliding window | Documented utilities; not yet wired | | Quickselect / quickSelectK | Top-N hubs in graph admin; replaces `sort + slice` | | Counting / bucket / radix sort | Available when value distribution is known | | Kruskal / Prim MST | Pairs with existing DSU + heap | | Bellman-Ford | Negative-weight paths; complements Dijkstra | | Floyd-Warshall APSP | Dense graphs, all-pairs | | Tarjan SCC (iterative) | Cycle decomposition without stack overflow | | LCA (general + BST) | Available; no current consumer | | Segment tree (iterative bottom-up) | Range aggregation over arbitrary monoid | | Fenwick tree (BIT) | Prefix-sum specialization with `lowerBound` | | List structures (ArrayList / LinkedList / DoublyLinkedList) | Container forms of the existing node types | | SortedSet / SortedMap | Facade over AVL/AA with Map-like surface | | CircularMap / CircularSet | Bounded keyed eviction with FIFO or LRU | ### Adopted — as npm dependencies (consumed directly) | Package | Purpose | Why not in-tree | | -------------------------------------------------- | ---------------------------------------------- | ------------------------------------------------------------------------------------- | | [`munkres`](https://www.npmjs.com/package/munkres) | Hungarian optimal assignment | Standalone algorithm, no Coda type coupling; consume from npm when a use case appears | | [`cvm-lib`](https://www.npmjs.com/package/cvm-lib) | Streaming distinct-count estimation | Standalone, mergeable across processes | | [`nacci`](https://www.npmjs.com/package/nacci) | k-bonacci sequences with matrix exponentiation | Niche; pull when needed | These are **not currently installed** at any consuming package — `pnpm add` at the site of first use. ### Considered and deferred | Algorithm | Workload it would solve | Why deferred | What would change the verdict | | -------------------------------------------- | ---------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------- | | HyperLogLog | Distinct-count over high-cardinality streams | No streaming distinct workload exists today; permission sets and graph traversals need _exact_ membership; glossary is bounded (~10K entries) | Cross-process search analytics; "unique queries / users / tokens per day" telemetry | | Count-Min Sketch | Approximate frequency, hot-key detection | The one rate limiter ([apps/runner/src/rate-limit/limiter.ts](../../../apps/runner/src/rate-limit/limiter.ts)) is per-user Redis with exact bucket semantics; tool-call frequency keyspace is small (~70 tools) | A "hot queries" surface or per-tenant top-K queries dashboard with bounded memory | | Bloom filter | Fast "have we seen this ID?" against a large reference set | Every `seen.add()` site is bounded and small; the largest reference set (glossary) needs the value, not just membership | A streaming dedup workload (e.g., cross-shard event ingestion) where membership-only suffices | | t-digest / DDSketch | Quantile estimation (p50/p90/p99) | [apps/server/src/mcp/metrics.ts](../../../apps/server/src/mcp/metrics.ts) tracks `total`+`max` only — would gain p99 — but OTLP path already handles external observability. Per-request latencies (Bedrock, DB) are stored per-row in MySQL, queried with SQL aggregations | A request for tail latency on the MCP `coda://server/metrics` resource | | Misra-Gries / Space-Saving (streaming top-K) | Bounded-memory top-K over an unbounded stream | All current top-K workloads are one-shot over a finite result set — correctly served by heap (`getTopK`) or quickselect | An always-on top-K view (e.g., "10 hottest queries this hour" maintained continuously) | | Reservoir sampling | Uniform sample from an unbounded stream of unknown size | No log sampling, no traffic shaping, no fixture sampling | Sampled tracing for high-volume endpoints | | Skip list | Order-statistic queries | AVL/AA already cover the order-statistic need; no rank-query workload found | A workload that benefits from skip list's simpler concurrency story (irrelevant in single-threaded Node) | | Treap / RB tree | Self-balancing BST alternatives | AVL and AA exist and are used | None expected | | Suffix array / suffix automaton | Substring index | KMP-via-`indicesOf` covers the current need; full-text search uses inverted index + BM25 | Substring search workload exceeding what KMP supports | | Aho-Corasick | Multi-pattern substring matching | No multi-pattern workload identified | A regex-engine-grade matcher for log filtering or guardrails | | Wavelet tree | Compressed range-rank queries | No workload identified | Compressed read-only ranked corpora | | Heavy-Light decomposition | Tree path queries | No workload identified | Hierarchical query patterns over a deep tree (org hierarchy?) — speculative | | Mo's algorithm | Offline range queries | No offline batch query workload | Bulk analytics over indexed corpora | | Persistent / functional data structures | Immutable snapshots | Current snapshot model already uses S3-backed bundle artifacts; in-process structures don't need immutable history | A real-time version-stamped data model | ### Considered and rejected (won't pursue) | Algorithm | Why not | | ---------------------------------------------- | --------------------------------------------------------------------------------------------------- | | K-bonacci as in-tree | The `nacci` package exists; if a use case arises, depend on it. Algorithm has no Coda type coupling | | Munkres as in-tree | Same — `munkres` package exists | | CVM as in-tree | Same — `cvm-lib` package exists | | `CircularSet` (already shipped, zero adopters) | Anyone needing a bounded set can use `CircularMap`; trim if no consumer materializes | ## Parallel reducers Investigated whether a fork/join "fan out then combine" abstraction would clean up real call sites. **One candidate worth doing now:** the skill-handler fan-out pattern is repeated identically in three places: - [apps/server/src/ai/skills/contract-overview/handler.ts:30-93](../../../apps/server/src/ai/skills/contract-overview/handler.ts) - [apps/server/src/ai/skills/account-overview/handler.ts:55-89](../../../apps/server/src/ai/skills/account-overview/handler.ts) - [apps/server/src/ai/skills/revenue-overview/handler.ts:62-117](../../../apps/server/src/ai/skills/revenue-overview/handler.ts) Each builds `[name, resilientCall(name, () => h(toolName)(input, headers))]` tuples, `Promise.all`s the inner work, builds `byName = Object.fromEntries(settled)`, and runs `collectErrors(settled)`. The orchestration step is identical; `resilientCall` and `collectErrors` are already factored into `tools/handler-utils.ts`, but the fan-out shape isn't. A `parallelToolFanOut({ tools, input, headers, mapByName })` helper returning `{ byName, errors }` would halve each of these handlers and make a new overview skill a 20-line file. This is a **structural** win, not a perf win — every promise already runs concurrently. The win is "one obvious shape" instead of three copies. **One secondary candidate:** [apps/search/src/engine/engine-factory.ts:298-342](../../../apps/search/src/engine/engine-factory.ts) (`buildAllEngines`) and [packages/search/src/hybrid-search.ts:522-543](../../../packages/search/src/hybrid-search.ts) (stage fan-out) follow the same shape with `Promise.allSettled`. Both are already readable; pick up only after the helper exists. **Where parallel reducers don't fit:** - Embedding chunking ([apps/search/src/embedding/huggingface/embedding.ts:220-244](../../../apps/search/src/embedding/huggingface/embedding.ts)) deliberately runs batches _sequentially_ with yields between to keep the event loop responsive on a single-threaded Node process. Forking to `Promise.all` would harm responsiveness and risk OOM. Correctly left alone. - Search engine fusion is CPU-bound on a single thread; further parallelization buys nothing on Node's main event loop. - True parallelism in Node requires `worker_threads`. No current CPU-bound workload justifies the complexity. ## Adoption opportunities The greenfield review identified several call sites where existing `@coda/data-structures` primitives should be wired in. The full list lives in the review; the highest-impact ones are repeated here for context: | Site | Anti-pattern | Adopt | | ----------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------ | ------------------------------------------------- | | ~~`memory-store.ts:152` + `memory-key-value-store.ts:97`~~ | _Audit flagged "FIFO-as-LRU" bug; reconsidered._ | **Keep FIFO** — see decision log below. | | [apps/server/src/cache/memory-conversation-store.ts:63-98](../../../apps/server/src/cache/memory-conversation-store.ts) | Sorted-array index with O(n) writes | `SortedMap` or `MemorySortedStore` | | [apps/client/src/providers/chat-provider.tsx:97-109](../../../apps/client/src/providers/chat-provider.tsx) | Hand-rolled LRU in React ref | `CircularMap(EvictionPolicy.LRU)` | | [packages/sandbox/src/\_internal/queue.ts](../../../packages/sandbox/src/_internal/queue.ts) | Vendored `LinkedQueue` reimplementation | Import `LinkedQueue` from `@coda/data-structures` | | [packages/search/src/pipeline/pipeline.ts:154](../../../packages/search/src/pipeline/pipeline.ts) | `sort()` + `slice(0, K)` on hot search path | `quickSelectK` or `getTopK` | | [apps/server/src/ai/tools/graphql/schema-index.ts:189](../../../apps/server/src/ai/tools/graphql/schema-index.ts) | `sort()` + `slice(0, K)` on every query | `getTopK(filterMap(...), cmp, k)` | ## Alternatives considered (package-level) ### In-tree implementation vs external npm dependency **Chose in-tree.** Reasons: 1. Internal conventions (`Collection`, `Keyed`, `CompareFn`, structural validation, JSDoc style) need to apply uniformly across the package; importing structures from unrelated external packages forces adapter shims at every boundary. 2. Mixing dep + in-tree creates two sources of truth — consumers of `BinaryHeap` and `SegmentTree` would import from two different namespaces. 3. External-package deps add lockfile / `pnpm audit` / private-registry overhead per dependency. The exception is leaf-y algorithms with no Coda type coupling (`munkres`, `cvm-lib`, `nacci`) — those _are_ npm deps because they don't interact with the package's traits or comparator policy. ### Single `EvictionPolicy` enum vs separate FIFO and LRU types **Chose single enum** (const-object form matching project convention: `EvictionPolicy.FIFO`, `EvictionPolicy.LRU`). Reasons: 1. The underlying algorithm differs by one branch; two classes would duplicate eviction logic. 2. Matches existing patterns (`EngineState`, `GrassHeader`, `OrchardHeader`). 3. Lets `LRUCache` be a thin adapter without choosing the policy at the wrapper layer. ### `LRUCache` in `@coda/common` vs delete and use `CircularMap` directly **Kept LRUCache as an adapter.** Reasons: 1. `LRUCache` implements `SyncCache` — peer of `NullCache`, `NullAsyncCache`. Killing it would force callers to roll their own observability hooks. 2. Eviction listeners (`on("evict", …)`) are a real cache concern, not a data-structure concern. 3. The wrapper is now ~120 lines and adds value over the underlying primitive. ### Monoid abstraction beyond segment tree **Deferred.** The repeated `scores.set(id, (scores.get(id) ?? 0) + delta)` pattern across BM25 / TF-IDF / RRF / WeightedSumFusion is technically monoidal (sum-over-keyed-counters), but the duplication is "keyed accumulator," not "swappable monoid". Generalizing to `Monoid` would add ceremony around five identical `+` operations. Revisit only when: - A second `SegmentTree`-shaped consumer appears (e.g., a Fenwick tree over groups, or a parallel reducer) - A probabilistic sketch with a real `merge()` arrives (HLL, count-min, t-digest) - A parallel-reduce framework needs an associativity contract ## Decision log | Decision | Date | Rationale | | ----------------------------------------------------------------------------------------------- | ---------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | Implement core structures in-tree | 2026-04-?? | Type-system coupling with Coda conventions (Collection / Keyed / CompareFn); avoids external-dep churn | | Add MST / APSP / SCC / Bellman-Ford / LCA / Fenwick / segment / sorts / monotonic / quickselect | 2026-05-?? | Round out graph + range-aggregation + top-K coverage to fill recurring algorithmic gaps | | Drop in-tree munkres / cvm / kbonacci → consume via npm | 2026-05-17 | Standalone leaf algorithms with no Coda type coupling | | Refactor `LRUCache` to delegate to `CircularMap` | 2026-05-17 | Single source of truth for eviction algorithm; LRUCache stays as cache-layer adapter | | `EvictionPolicy` as const-object enum | 2026-05-17 | Matches project convention; ergonomic for IDE autocomplete | | Defer HLL / count-min / bloom / t-digest | 2026-05-17 | No workload-shape evidence in current codebase | | Defer parallel-reducer abstraction (case (B) excepted) | 2026-05-17 | Only fan-out skill handlers currently repeat the shape; broader abstraction premature | | Keep FIFO eviction in `MemoryCacheStore` / `MemoryKeyValueStore` | 2026-05-17 | TTL-primary stores; `maxEntries` is a memory-cap backstop, not an LRU policy. FIFO by insertion order is the documented contract and correct for TTL stores. Audit finding was a false positive — comments updated in both files to make the design choice explicit | | Add `popAndTrim` to `algorithms/heap`; wire Dijkstra/Prim | 2026-05-17 | Removes the "pop + manual array.pop()" footgun for non-heapsort callers. Sub-range `pop` kept as-is for in-place heapsort | | Replace sorted-array conversation index with AVL-backed index | 2026-05-17 | O(log n) writes + cursor seeks instead of three O(n) scans per upsert. Mirrors `ScoredMemberTree` pattern in `MemorySortedStore` | ## Open questions - Should `SearchTree` grow a `find(key: K)` method to support a key-projection variant? (Would clean up `SortedMap`'s sentinel casts and double-walk in `get`.) — Tracked in the greenfield review, finding #3. - Should the namespace re-exports in `index.ts` be removed? Zero consumers use them today, and they defeat tree-shaking. — Greenfield review, finding #5. - ~~Do `memory-store.ts` and `memory-key-value-store.ts` actually want LRU semantics?~~ **Resolved 2026-05-17:** They are TTL-primary caches; FIFO eviction by insertion order is the documented contract and is semantically correct for a TTL store. Comments updated in both files to make the design choice explicit. The audit finding was a false positive — switching to LRU would change the contract, add cost per `get`, and provide marginal benefit since TTL already handles freshness. ## References - Greenfield review — the operational checklist of improvements - [`cvm-lib`](https://www.npmjs.com/package/cvm-lib) — distinct-count estimator (npm dep, when needed) - [`munkres`](https://www.npmjs.com/package/munkres) — Hungarian algorithm (npm dep, when needed) - [`nacci`](https://www.npmjs.com/package/nacci) — k-bonacci sequences (npm dep, when needed) - CVM paper: [https://arxiv.org/abs/2301.10191](https://arxiv.org/abs/2301.10191)