Patent ID: 6507846
Filing Date: 2003-01-14
Classification: G06F,Y10S

Abstract:
An indexing system for structured or semi-structured source data, the source data being capable of being represented by a relational data view, the source data comprising data subsets which in the relational view correspond to attributes in one or more tables, each table comprising columns and rows, the indexing system comprisinga tokenizer for accepting the source data and generating data tokens in a token stream representing the source data, the tokenizer comprising means for generating identifier tokens identifying the table and column of the relational view for the data subsets of the source data, the identifier tokens being inserted in the token stream to precede the data tokens for the data subsets to which the identifier tokens correspond, and an index builder for building indexes based on the token stream, the index builder creating token stream indexes which comprise a set of positional indexes for indicating the position of data tokens in the source data, a set of lexicographical indexes for indicating the lexicographical ordering of all tokens, the set of lexicographical indexes comprising a sort vector index and an associated join bit index, and a set of data structures mapping between the lexicographical indexes and the positional indexes, comprising a lexicographic permutation data structure.