Open AccessCompact 0-complete trees: A new method for searching large files
Author(s) -
Ratko Orlandić,
John L. Pfaltz
Publication year - 1988
Publication title -
osti oai (u.s. department of energy office of scientific and technical information)
Language(s) - English
Resource type - Reports
DOI - 10.2172/6231696
Subject(s) - trie , byte , computer science , overhead (engineering) , key (lock) , ternary search tree , b tree , binary tree , binary search tree , binary number , tree (set theory) , algorithm , data structure , reduction (mathematics) , binary search algorithm , search engine indexing , search tree , theoretical computer science , data mining , search algorithm , tree structure , mathematics , interval tree , information retrieval , arithmetic , combinatorics , geometry , computer security , programming language , operating system
In this report, a novel approach to ordered retrieval in very large files is developed. The method employs a B-tree like search algorithm that is independent of key type or key length because all keys in index blocks are encoded by a 1 byte surrogate. The replacement of actual key sequences by the 1 byte surrogate ensures a maximal possible fan out and greatly reduces the storage overhead of maintaining access indices. Initially, retrieval in binary trie structure is developed. With the aid of a fairly complex recurrence relation, the rather scraggly binary trie is transformed into compact multi-way search tree. Then the recurrence relation itself is replaced by an unusually simple search algorithm. Then implementation details and empirical performance results are presented. Reduction of index size by 50%--75% opens up the possibility of replicating system-wide indices for parallel access in distributed databases. 23 figs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom