Communications of the ACM · 1983 · 108 citations · 4 references
ComputingComputer ScienceComputer SystemsData StructuresDatabasesInformation RetrievalData Structure AlgorithmsData Structure DesignFile SystemsSearching AlgorithmsAlterationBinary SearchData ProcessingIndex StructuresIndexing StructuresTree StructuresTrie Data StructuresTrie Structures
In data processing problems, files are frequently used which must both be searched and altered. Binary search techniques are efficient for searching large files, but the associated file organization is not readily adapted to the file alterations. Conversely, a chained file allocation permits elcient alteration but cannot be searched efficiently. A file organized into a tree-like structure is discussed, and it is shown that such a file may both be searched and altered with times proportional to s log, N , where N is the number of file items and s is a parameter of the tree. It is also shown that optimizing the value of s leads to a search time which is only 25 per cent slower than the binary search. The tree organization employs two data chains and may be considered to be a compromise between the organizations for the binary search and the chained file. The relation of the tree organization to multidimensional indexing and to the trie structure is also discussed.
4
Edward Fredkin · Communications of the ACM · 1960 · 1.1K citations · Full text
Information Processing Language-V Manual
Nora M. Taylor, Allen Newell · Mathematics of Computation · 1965 · 111 citations
Addressing multidimensional arrays
H. Hellerman · Communications of the ACM · 1962 · 21 citations · Full text