Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Yangjun Chen (University of Winnipeg, Canada)

Copyright: © 2018
|Pages: 11

DOI: 10.4018/978-1-5225-2255-3.ch695

Chapter Preview

TopIn 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.

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.

Search this Book:

Reset