Inverted File Tree Machine: Efficient Multi-Key Retrieval for VLSI (Very Large Scale Integration)

摘要

In the paper the authors review index structures suggested for implementation on silicon. These structures do not efficiently support multi-key retrieval. The authors present two variants of the inverted file tree machine as efficient VLSI solutions to the problem improving query time of previous machines at least by the factor number of attributes specified in the query. Concerning nonredundant and redundant insertions and deletions plus multiple deletions, the authors suggest two phase methods to handle these update operations while continuously pipelining following operations. Both variants are compared with respect to their performance and space requirement. Furthermore, the authors describe a large class of multi-key queries all of which are handled on the machine with the speed up factor number of specified attributes.