An Efficient and Effective Index Structure for Query Evaluation in Search Engines

An Efficient and Effective Index Structure for Query Evaluation in Search Engines

Yangjun Chen (University of Winnipeg, Canada)
DOI: 10.4018/978-1-5225-7598-6.ch127

Abstract

In this chapter, the authors 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. The authors 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 indices, when inserting or deleting documents, is discussed in great detail.
Chapter Preview
Top

Background

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.

Complete Chapter List

Search this Book:
Reset