Inverted signature trees and text searching on CD-ROMs

摘要

Although text searching is an operation common to computers, it is beneficial for us to reexamine its mechanisms in the context of new techniques and technologies for storing data. This paper explores the new storage technology of the CD-ROM and introduces a data structure, called the inverted signature tree, for storing data on a CD-ROM for efficient text searching. An inverted signature tree facilitates rapid access to all sentences in a text file that contain specific search words; in addition, the structure maintains all potential search words in alphabetical order to aid in determining the proper form of a search word. The paper also compares inverted signature trees with the use of text signatures and the B+ tree.