Abstract
In this chapter, we discuss an efficient and effective index mechanism for search engines to support both conjunctive and disjunctive queries. The main idea behind it is to decompose an inverted list into a collection of disjoint sub-lists. We will associate each word with an interval sequence, which is created by applying a kind of tree coding to a trie structure constructed over all the word sequences in a database. Then, attach each interval, instead of a word, with an inverted sub-list. In this way, both set intersection and union can be conducted by performing a series of simple interval containment checks. Experiments have been conducted, which shows that the new index is promising. Also, how to maintain indexes, when inserting or deleting documents, is discussed in great detail.
TopBackground
In order to efficiently evaluate such queries, indexes need to be established. It is well known that English texts typically contain many different variants of basic words, by using variant word endings such as ‘ing’, ‘ed’, ‘ses’, and ‘ation’. All the variants of a word should be regarded as a match and therefore it is efficient for an index only include these basic words, or say, stems. Different algorithms have been developed to extract stems from documents. Among them, the algorithm proposed by Lovins (1968) is widely used.
Key Terms in this Chapter
Signature File: A set of signatures (bit strings) with each created for a document by superimposing (bitwise OR) all the word signatures. To find all the documents that contain a set of key words, we will first generate a query signature by superimposing all the query word signatures and then search the signature file to find its matching ones.
Trie: (Also called digital tree and sometimes radix tree or prefix tree as they can be searched by prefixes) an ordered tree data structure that is used to store a dynamic set of strings like texts and documents.
Set Intersection: (Denoted as A n B, where A and B are two sets) the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements.
Search Engine: A software used by the Internet to search data (as text or a database) for specified information; also, a sever on the World Wide Web that uses such software to locate key words in other sites.
Interval: A pair of integers [ a , b ] where b denotes the rank of v in a post-order traversal of a trie. Here the ranks are assumed to begin with 1, and all the children of a node are assumed to be ordered and fixed during the traversal. In addition, a denotes the lowest rank for any node u in the subtree rooted at v . Its purpose is to check the reachability. Let [ a , b ] an [ c , d ] be the intervals associated with v and u , respectively. If [ c , d ] ? [ a , b ], then u is reachable from v through a path in the tree.
Set Disjunction: (Also called set union, denoted as A ? B, where A and B are two sets) the set of elements which are in A , in B , or in both A and B .
Inverted List: (Also referred to as postings file or inverted file) an index data structure associated with a key word w , storing a set of document identifiers, which contain w . Its purpose is to allow fast full text searches, at a cost of increased processing when a document is added to the database.