A graph structured text field index based on word fragments

摘要

An indexing technique for text data based on word fragments is described. In contrast to earlier approaches the fragments are allowed to be overlapping and are linked in a directed graph structure reflecting that many fragments (“Superstrings”) contain other fragments as substrings. This leads to a redundant free set of primary data pointers. By classifying the set of Superstrings belonging to a fragment according to the position of the fragment in the Superstring, one gains a novel possibility of supporting exact match-, partial match-, and masked partial match-retrieval by an index. The search strategies for the various retrieval cases are described.