docs/IMPLEMENTATION.md

Implementation plan

This is the build order. Each phase is independently shippable; later phases assume the artifacts of earlier ones.

Phase 0 — repository skeleton

Create:

README.md
requirements.txt
.python-version                # 3.12
.gitignore                     # data/index, data/raw, node_modules, dist, __pycache__
pyproject.toml                 # pytest config, optional later
pipeline/download.py
pipeline/build_index.py
backend/app.py
backend/graph.py
backend/filters.py
backend/search.py
backend/models.py
backend/load.py
frontend/                      # Vite + React + TypeScript
tests/test_filters.py
tests/test_graph.py
tests/test_search.py
scripts/run.sh
docs/DESIGN.md                 # already written
docs/IMPLEMENTATION.md         # this file

Runtime stack:

• Python 3.12, FastAPI, uvicorn, numpy, pandas, pyarrow, orjson
• SQLite 3 (stdlib) with FTS5
• Node 22, Vite, React 18/19, TypeScript, d3-hierarchy
• Leaflet + a tiny QR library for the phone dialog

No Docker required. scripts/run.sh downloads (if needed), builds the index (if needed), builds the SPA (if needed), and serves everything on :8000.

Phase 1 — download

pipeline/download.py fetches into data/raw/:

1. Hugging Face parquet files from https://huggingface.co/datasets/lukeslp/etymology-atlas/resolve/main/{file}:
   • etymologies.parquet
   • languages.parquet
   • cognate_sets.parquet
   • phonemes.parquet
   • linguistic_features.parquet
2. https://raw.githubusercontent.com/glottolog/glottolog-cldf/master/cldf/languages.csv
3. https://raw.githubusercontent.com/cldf-datasets/wals/master/cldf/languages.csv
4. https://raw.githubusercontent.com/cldf-datasets/wals/master/cldf/codes.csv

Idempotent: skip files whose size matches a recorded .meta.json. Retry with exponential backoff. Fail with a clear message if Hugging Face is unreachable.

Phase 2 — language catalog

Inside build_index.py, build a languages table that actually has families and ISO codes (the published languages.parquet leaves family_name, iso_639_3, and speakers_count entirely null).

Algorithm:

1. Load Glottolog CLDF. Rows with Level == "family" give Family_ID -> family name. Rows with Level in {language, dialect} give glottocode, ISO, coords, macroarea, isolate flag.
2. Load atlas languages.parquet for vitality (status), atlas coordinates (fill if Glottolog coords missing), and phoneme_count.
3. Collect every distinct lang string from etymology lang1 and lang2.
4. Resolve each atlas lang key to a glottocode:
   • If the key is a 3-letter ISO 639-3 code (Lexibank), map via Glottolog ISO639P3code.
   • Else lowercase-name match against Glottolog Name.
   • Else lowercase-name match against atlas languages.name.
   • Else try stripping a parenthetical dialect (persian: tehran -> persian) and retry.
   • Else leave unresolved; still store the atlas key as a first-class language so proto-languages work.
5. Family name: Glottolog family lookup. Fallback: if the key starts with proto-, use the remainder title-cased as a pseudo-family (so proto-germanic groups with Germanic when the family row exists, otherwise "Proto-Germanic").
6. Macroarea: Glottolog, then atlas parquet.
7. WALS join: wals_languages.Glottocode -> atlas glottocode. Store wals_id.
8. Phoneme join: PHOIBLE glottocode. Union inventories when multiple PHOIBLE sources exist for one language.
9. Assign dense integer codes for lang, family, macroarea, status used later as numpy columns.

Write languages SQLite table:

lang_key TEXT PK,
display TEXT,
glottocode TEXT,
iso_639_3 TEXT,
family_id TEXT,
family_name TEXT,
macroarea TEXT,
status TEXT,
latitude REAL,
longitude REAL,
wals_id TEXT,
phoneme_count INTEGER,
resolved INTEGER

Write auxiliary tables:

wals_values(glottocode, feature_id, feature_name, value INT, value_label TEXT)
phoneme_inv(glottocode, phoneme, segment_class, tone INT)
cognate_set(id, words_json, language_count)
cognate_member(set_id, term, lang, glottocode)

WALS value_label comes from codes.csv (81A-2 -> SOV etc.), not the atlas value_name which is only the code id.

Phase 3 — node internment and CSR graph

1. Read etymologies in one pandas load (58 MB parquet; ~1–2 GB peak is acceptable).
2. Drop rows with null/empty term1 or term2.
3. Intern (term, lang) -> dense node_id starting at 0. Process both sides. Preserve original term spelling as term; store term_norm for FTS (NFKC, casefold, strip leading *, map ₂/₃ -> 2/3).
4. Map relationship_type to uint8 via a fixed table (order stable, stored in meta.json).
5. Quantize confidence to uint8 as round(conf * 100).
6. Source to uint8: 0 = etymology-db, 1 = lexibank:iecor.

Reverse CSR (the walk direction):

offsets: int32[n_nodes + 1]
targets: int32[n_edges]      # descendant node ids
rel:     uint8[n_edges]
conf:    uint8[n_edges]
src:     uint8[n_edges]

Edge term2 -> term1 is appended in input order, then each adjacency list is sorted by (rel, -conf, target) so inherited high-confidence children appear first.

Also build a forward CSR (term1 -> term2) for the inspector. Same arrays, fwd_ prefix.

Per-node numpy (saved in the same npz or a second one):

lang_code:     int32[n_nodes]
family_code:   int32[n_nodes]
macro_code:    int8[n_nodes]
status_code:   int8[n_nodes]
glotto_code:   int32[n_nodes]   # -1 if unresolved
child_count:   int32[n_nodes]   # reverse out-degree

SQLite nodes:

id INTEGER PK,
term TEXT,
term_norm TEXT,
lang TEXT,
child_count INTEGER

FTS5:

CREATE VIRTUAL TABLE nodes_fts USING fts5(
  term, term_norm, lang,
  content='nodes', content_rowid='id',
  tokenize = 'unicode61 remove_diacritics 2'
);

meta.json: relation names, language/family/macroarea vocabularies with counts, example roots, cluster/depth defaults, dataset citation.

Build is a single command, prints timings, refuses to overwrite unless --force.

Phase 4 — filter engine

backend/filters.py is pure and unit-tested with a synthetic graph. No FastAPI imports.

Dataclasses (mirrors the JSON body):

class EdgeFilter:
    relations: frozenset[str]   # empty = default set
    min_confidence: float
    max_depth: int
    max_visit: int

class NodePredicate:
    languages: frozenset[str]
    families: frozenset[str]
    macroareas: frozenset[str]
    statuses: frozenset[str]
    term_contains: str
    term_regex: str | None
    bbox: tuple[float, float, float, float] | None  # minlat, minlon, maxlat, maxlon
    require_coords: bool
    wals: tuple[WalsClause, ...]   # feature_id + allowed int values
    phonemes_have: frozenset[str]
    phonemes_lack: frozenset[str]
    require_tone: bool | None
    keep_unknown: bool

class PathFilter:
    node: NodePredicate
    quantifier: Literal["any", "all", "none", "exactly"]
    exactly_k: int
    relations_any: frozenset[str]
    relations_none: frozenset[str]
    apply_to_root: bool

class TreeQuery:
    term: str
    lang: str
    edges: EdgeFilter
    leaf: NodePredicate
    path: PathFilter
    expand: tuple[str, ...]     # cluster keys to unpack
    cluster_threshold: int
    max_payload: int
    color_by: str

node_ok(node_id, pred, ctx) -> bool:

• Empty predicate fields are no-ops (vacuously true).
• WALS/phoneme lookups go through glotto_code[node_id]; if -1 and pred uses those fields, return pred.keep_unknown.
• Term regex compiled once per query.

path_ok(node_ids, edge_rels, path_filter) -> bool:

• Slice intermediates.
• Quantifier over node_ok on that slice.
• Then AND the relation-any / relation-none checks on edge_rels.

walk(query) -> TreeResult:

1. Resolve root id or return 404-equivalent empty result.
2. BFS using reverse CSR. Skip edges failing Layer A. Store parent[child] = node, parent_edge[child] = edge_index, depth[child].
3. Identify candidate leaves: visited nodes with no kept child in the BFS tree, or depth == max_depth.
4. For each candidate, reconstruct path by parent pointers, test leaf + path filters.
5. Mark surviving nodes.
6. Cluster unmarked-as-expanded high fan-out sibling groups.
7. Hydrate payload rows from SQLite in one WHERE id IN (...) query.
8. Return stats: visited, kept_leaves, clustered, elapsed_ms, truncated flag.

Do not recurse in Python objects; use arrays and deques. This is the hot path.

Phase 5 — FastAPI

backend/load.py on startup:

• mmap graph.npz
• open SQLite with pragma journal_mode=wal; mmap_size=268435456; cache_size=-80000
• load meta.json
• load WALS/phoneme dicts keyed by glotto_code (built once from SQLite into Python dicts; 2k inventories is tiny)
• expose a process-global Atlas object

backend/app.py:

• /api/* routes
• / and assets from frontend/dist if present
• gzip via Starlette GZipMiddleware
• CORS *
• orjson response class
• request timing header X-Query-Ms

Validation: pydantic models matching TreeQuery. Unknown relation names 422. Empty suggest query returns the curated examples.

Phase 6 — frontend

Vite React TS. Single page.

State

URL is the source of truth. useQueryState (hand-rolled) serializes:

q, lang, depth, conf,
rels (comma),
view (tree|radial|map|table|stats),
color,
leafLang, leafFam, leafArea, leafWals, leafPh,
pathLang, pathFam, pathArea, pathMatch, pathRelAny,
expand

Changing any of these (except camera) refetches /api/tree. Camera is session-only.

Components

File	Responsibility
App.tsx	Shell, URL state, data fetching, layout mode (desktop vs mobile)
SearchBar.tsx	Combobox suggest, language disambiguation, / shortcut
FilterPanel.tsx	Three tabs: Graph / Leaves / Path. Multi-selects, sliders, quantifier, keep-unknown
FilterChips.tsx	Compact removable chips; the mobile summary of the query
TreeCanvas.tsx	Canvas camera + pointer/touch + hover path
layout.ts	d3-hierarchy tidy / radial, cluster stub sizing
render.ts	Draw edges, nodes, labels, LOD, minimap, DPR
MapView.tsx	Leaflet markers from hydrated coords
TableView.tsx	Sort, filter-in-view, pagination, CSV button
StatsView.tsx	Small-multiple bars for the current payload
Inspector.tsx	Desktop drawer / mobile sheet
Legend.tsx	Color encoding
Examples.tsx	First-run cards
PhoneQR.tsx	LAN origin QR
api.ts	fetch wrappers
types.ts	shared TS types matching pydantic
colors.ts	relation + family palettes
pwa.ts	service worker registration

Canvas details

• Offscreen node array {x,y,r,id,kind,color,label}.
• devicePixelRatio cap at 2 for mobile GPUs.
• Hit test: grid[(gx<<16)^gy] lists of node indices.
• Path highlight: walk parent from hovered id, draw those edges last.
• Cluster stubs drawn as rounded rects with count.
• Empty state when the query yields only the root: explain which layer dropped the descendants.

Mobile chrome

[ search ................. ] [filters n]
[ tree | radial | map | table ]
<canvas flex>
[ inspector sheet handle ]

Bottom sheet uses a drag handle, 40% default height, snap to 90% for filter editing.

PWA

manifest.webmanifest: name "Reverse Etymology Atlas", standalone, theme color ink navy, 192/512 icons (simple SVG-generated PNGs checked in or generated at build).

Service worker: cache-first for /assets/* and /, network-first for /api/*.

Phase 7 — tests

Synthetic graph in tests/conftest.py:

PIE *kaput -> Latin caput (inherited)
Latin caput -> Old French chef (inherited)
Old French chef -> English chief (borrowed)
Latin caput -> English capital (derived)   # no French hop
Latin caput -> French chef (inherited)
French chef -> English chef (borrowed)

Cases:

• No filters: all descendants present.
• Leaf language English: chief, capital, chef (English); French chef excluded; Latin kept as ancestor.
• Leaf English AND path any French/Old French: chief and English chef kept; capital dropped.
• Path none French: capital kept; chief dropped.
• Path all Romance family: depends on assigned families in the fixture.
• Relation construction without borrowed: English chef and chief disappear.
• Quantifier exactly 1.
• Cluster threshold unpack.
• Cycle: A->B->A does not infinite loop.
• Suggest ranks exact over prefix.
• API 404 on unknown root.

Run with pytest -q. The synthetic atlas is built in-memory; no parquet required.

Optional smoke: if data/index/graph.npz exists, one test queries Latin mater and asserts at least one inherited Romance daughter.

Phase 8 — run, measure, polish

1. python pipeline/download.py && python pipeline/build_index.py
2. cd frontend && npm install && npm run build
3. uvicorn backend.app:app --host 0.0.0.0 --port 8000
4. Hit /api/suggest?q=mater, /api/tree for Latin mater, depth 3.
5. Confirm elapsed_ms in the budget.
6. Resize to 390px and check sheets, pinch, chips.
7. README: citation, how to run, filter semantics, license.

File-level backend notes

backend/graph.py

• class CSR: offsets, targets, rel, conf, src
• class Atlas: n, reverse, forward, node_traits, sqlite, meta, wals, phonemes, lang_index
• children(node, edge_filter) -> iterator of edge indices

backend/search.py

• Parameterized FTS: nodes_fts MATCH ? with prefix q*, fallback LIKE for 1-character queries (FTS5 is weak there).
• Limit 20.

Frontend performance notes

• Debounce suggest at 80 ms, tree refetch at 150 ms for slider drags.
• AbortController cancels in-flight tree requests when the query changes.
• Do not React-render every canvas frame; canvas is an imperative module.
• Table view windows 100 rows; full payload stays in memory (max 2500).

Risks and mitigations

Risk	Mitigation
other + compounds + cognates can turn affix queries into large bushy trees	Cluster stubs; max_visit; users can uncheck noisy relation types per query
Empty atlas family column	Glottolog enrichment
Lexibank ISO keys vs Wiktionary names	Dual resolver; show both in suggest
Cognate cliques	Cognates excluded from reverse walk by default; inspector only
Mobile canvas jank	DPR cap, LOD, cluster, 2500 node cap
Hugging Face download flaky	Retry, documented mirror paths, skip if files exist
WALS sparse coverage	keep_unknown toggle, fail-closed default

Acceptance criteria

• Design and this plan committed.
• Index builds from the published parquet files without manual cleanup.
• Searching mater + language Latin shows Romance inherited daughters.
• Leaf filter English + path filter French keeps only English descendants whose path includes French.
• Toggling cognates/compounds/other changes the tree.
• Map, table, stats, radial all consume the same filtered payload.
• Layout is usable at 390px width with touch pan/zoom.
• Filter unit tests pass without the full dataset.
• README documents run steps and CC BY-SA citation.