Prefix-Based Organization (Tries)¶

Organizing data by shared prefixes enables operations proportional to key length rather than collection size, exploiting structural commonality in keys.

Tension Addressed¶

Generality vs. Specialization

Recognizable As¶

Tries/prefix trees; autocomplete systems; IP routing tables; file system path lookup; dictionary compression; any "find all matching prefixes" operation

Canonical Sources¶

Fredkin, "Trie Memory" (1960); Morrison, "PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric" (1968)

Transfers To¶

Networking (routing tables), Text Processing (autocomplete, spell check), Compression (dictionary coding), Bioinformatics (sequence matching)