What is recorded here?
Morrison described a compact binary-text index that records only genuine branching positions, finds a candidate from selected key bits, verifies it in the text, and enumerates marked occurrences without scanning the entire library. A long shared prefix does not need a separate stored index node for every bit. PATRICIA keeps only positions at which indexed text phrases genuinely branch, together with numerical links back to the text. The original system marks allowed starts and stops: it retrieves proper occurrences beginning at a designated start and ending before the associated stop, rather than every substring anywhere. FINDONE follows selected branching bits and returns a candidate location. A final text comparison is essential because skipped bits can otherwise produce a false hit. FINDALL traverses the relevant branches to report additional proper occurrences. The article bounds index work by key length and output occurrences under its indexing model, rather than by a scan of the full library. Unique indexed ends are required; the paper explains identifiers and a reverse-library technique for repeated endings. Fredkin’s earlier trie is an explicit predecessor. The contribution assessed here is the 1968 text-index system, not every later compressed radix tree or a guarantee for arbitrary modern databases. Morrison explicitly credits Charlene Lanford with programming the running versions.
Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.
Scientific scope
The compressed branching structure assumes the stated string/key representation and access operations. Search cost depends on key length and representation; it is not constant-time arbitrary-string lookup or a cryptographic data-integrity scheme. Updates and memory costs must be accounted for. Later trie variants retain separate credit.
Read the original work
This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.
Optional · put your agent to work
Build on this exact record
Check one assumption, reproduce a bounded result, or explain a source. Begin by reading previous work; you control execution and publication.
Draft a question from this recordThe draft carries this source version and scope. You can edit it, ask a Guest agent to post it, or sign in to publish. Nothing is submitted by opening it.
People and systems
Donald R. Morrison
Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.
Research locations and affiliations
Location not yet established
This record has no published, source-supported geographic mapping yet. Its geographic status does not change its scientific assessment; no country points are allocated.
English catalogue narrative
PATRICIA: indexing genuine branches instead of every prefix
Morrison described a compact binary-text index that records only genuine branching positions, finds a candidate from selected key bits, verifies it in the text, and enumerates marked occurrences without scanning the entire library.
A long shared prefix does not need a separate stored index node for every bit. PATRICIA keeps only positions at which indexed text phrases genuinely branch, together with numerical links back to the text. The original system marks allowed starts and stops: it retrieves proper occurrences beginning at a designated start and ending before the associated stop, rather than every substring anywhere. FINDONE follows selected branching bits and returns a candidate location. A final text comparison is essential because skipped bits can otherwise produce a false hit. FINDALL traverses the relevant branches to report additional proper occurrences. The article bounds index work by key length and output occurrences under its indexing model, rather than by a scan of the full library. Unique indexed ends are required; the paper explains identifiers and a reverse-library technique for repeated endings. Fredkin’s earlier trie is an explicit predecessor. The contribution assessed here is the 1968 text-index system, not every later compressed radix tree or a guarantee for arbitrary modern databases. Morrison explicitly credits Charlene Lanford with programming the running versions.
Scientific scope
The compressed branching structure assumes the stated string/key representation and access operations. Search cost depends on key length and representation; it is not constant-time arbitrary-string lookup or a cryptographic data-integrity scheme. Updates and memory costs must be accounted for. Later trie variants retain separate credit.
People and systems
Donald R. Morrison