Boolean Retrieval

Boolean Retrieval

• Information Retrieval (IR) broadly means retrieving information, like typing a credit card number.
• Academically, IR is finding unstructured material (usually text documents) that satisfies an information need within large, computer-stored collections.
• IR used to be mainly for professionals like librarians and paralegals.
• It is now common for millions to use web search engines or email search daily.
• IR is becoming the main way to access information, surpassing traditional database searches.
• IR includes various data types and information problems beyond the core definition.
• "Unstructured data" lacks a clear, semantically overt structure, contrasting with structured data like relational databases.
• Almost no data are truly "unstructured," especially text, which has linguistic structure.
• Most text has explicit markup for structure (headings, paragraphs, footnotes), like web page coding.
• IR aids "semistructured" search, such as finding documents with "Java" in the title and "threading" in the body.
• The IR field covers browsing, filtering, and further processing document collections.
• Clustering groups documents based on content, like arranging books by topic.
• Classification assigns documents to categories based on topics, information needs, or age groups, often done automatically after manual classification.
• IR systems differ in scale: web search (billions of documents), personal retrieval (Apple's Spotlight), and enterprise search (corporation documents).
• Web search involves gathering documents for indexing, efficient systems, and handling hypertext.
• Personal retrieval handles diverse document types and requires low maintenance and resource usage.
• Enterprise search covers internal documents, patents, or research articles on dedicated systems.
• A term-document matrix and the idea of a term-document matrix are introduced using a simple IR problem.

Example of Information Retrieval Problem

• Imagine you are working with Shakespeare's Collected Works and want to find plays containing "Brutus" and "Caesar" but not "Calpurnia."
• The simplest method is a linear scan of documents, known as "grepping".
• Grepping is effective, especially on modern computers, and allows wildcard pattern matching.
• Grepping is sufficient for simple queries on modest collections like Shakespeare's works, which are under one million words.
• More is needed to process large document collections quickly, given the rapid growth of online data (billions to trillions of words).
• More flexible matching operations are required.
• Implementing queries with inexact word distances, such as "Romans NEAR countrymen," using grep is impractical, where NEAR is defined as "within 5 words" or "within the same sentence".
• Ranked retrieval is needed to find the best answer that contains the words in a large document collections.
• To avoid linear scanning, documents are indexed in advance.
• A binary term-document incidence matrix records whether each Shakespeare play contains each word.
• This matrix represents terms (usually words) as indexed units, though they can also be things like "I-9" or "Hong Kong."
• Each term has a vector showing documents it appears in, and each document has a vector showing its terms.
• To answer "Brutus AND Caesar AND NOT Calpurnia," vectors for "Brutus," "Caesar," and "Calpurnia" are taken and the last is complemented and a bitwise AND operation is then run.
• The results, "Antony and Cleopatra" and "Hamlet", are obtained through bitwise operations.
• The Boolean retrieval model uses Boolean expressions (AND, OR, NOT) to pose queries.
• The model views each document as a set of words.
• A realistic scenario involves N = 1 million documents, each about 1,000 words long (2-3 book pages).
• The document collection is about 6 gigabytes (GB) if it is assumed there are 6 bytes per word.
• There might be M = 500,000 distinct terms in these documents.
• The goal is to create a system for the standard ad hoc retrieval task, which provides documents relevant to a user's one-off query.
• An information need is the user's topic of interest, distinct from the query (what the user enters).
• A document is relevant if the user finds it valuable and related to their information need.
• The effectiveness of an IR system is assessed by precision (relevance of returned results) and recall (fraction of relevant documents returned).

Inverted Index

• Detailed relevance and evaluation measures are discussed in Chapter 8.
• A naive term-document matrix (500K x 1M) is too large for memory.
• The matrix is sparse (few nonzero entries) because each document contains only 1,000 words, leading to primarily zero values.
• A better representation is to record only the 1 positions.
• The inverted index is central to information retrieval, mapping terms back to document parts where they occur.
• The inverted index is a dictionary of terms (vocabulary or lexicon) - each term has a list showing where it occurs.
• A posting in the list records a term's appearance in a document, and the list is called a postings list or inverted list.
• The collection of all posting lists are postings where the dictionary is sorted alphabetically and each postings list is sorted by document ID
• The reasons behind its helpfulness are discussed in Section 1.3.
• Alternatives are considered in Section 7.1.5.

Building an Inverted Index

• To enable fast retrieval, the index should be built in advance.
• The major steps are:
  • Collect documents to be indexed.
  • Tokenize the text into a list of tokens.
  • Perform linguistic preprocessing to create normalized tokens which are indexing terms.
  • Index the documents where each term occurs by creating an inverted index of a dictionary and postings
• Terms and normalized tokens are similar to words.
• A basic inverted index is built through process of sort-based indexing.
• With a document collection, each document has a unique serial number known as the document identifier (docID).
• During the construction of the index, successive integers can be assigned to each new document as it is encountered or the indexing input can be considered as of pairs of a term and docID.
• The list is sorted so that the terms are alphabetical, this is done to reach the required representation.
• Multiple occurrences of terms are then merged.
• The result is then split into a dictionary and postings.
• This organization reduces storage needs because a term often occurs in various documents.
• The dictionary records statistics, like the document frequency (number of documents containing the term), which is useful for improving the search efficiency and models of ranked retrieval.
• Postings are secondarily sorted by docID for efficient query processing and an inverted index structure created.
• The index pays for storage of a dictionary and posting lists.
• Postings lists are much larger, so each is kept in memory.
• A fixed length posting list would be wasteful because some words show up often and others not so much.
• Good choices for in-memory postings lists are singly linked lists or variable arrays which extends out when crawling web pages and updating documents.

Processing Boolean Queries

• More advanced indexing strategies win out by requiring more pointers.
• More memory caches increase the speed on modern day processors.
• Extra pointers can be encoded in the lists.
• Updated are relatively infrequent, variable arrays are more compact and faster.
• A hybrid scheme makes use of a lists of fixed length arrays for each term.
• To minimize size and number of disk seeks posting lists are stored on disk as a continuous run of postings without explicit pointers.
• To process a query with an inverted index and Boolean retrieval model for a conjunctive query, locate Brutus, retrieve postings, locate Calpurnia in the dictionary.
• The intersection operation needs to efficiently intersect lists to find documents which contain both terms.
• There is a merge algorithm of maintaining pointers into lists, walking through simultaneously and comparing the docID which takes 0(x + y) operations.
• It is key that postings be sorted using a single global ordering to be able to use this algorithm.
• The intersection operation can be used to process complex operations too with Query optimization being the process of selecting the workload and ordering it the correct way.
• The standard method of processing is to organize terms in order of increasing document frequency starting by intersecting the smallest postings lists.
• The frequency of terms is kept in the dictionary to make ordering possible before accessing any postings list

Extended Boolean Models

• Disjunctive terms' query is processed in the increasing order of the size of each disjunctive term
• The evaluation and storage in memory of intermediate statements must be done to preform queries.
• Merging posting lists can be used for conjunctive queries, it intersects each retrieved list with current intermediate result in memory from the least frequent term posting list.
• A standard heuristic is to process the terms in order of increasing document.
• An asymmetric operation is a result from the intermediate list being read from disk as the intersection happens and the list may also be shorter.
• Using operators to define that two terms in a search query must occur close to each other in a document are proximity operators, where the measuring can be done by limiting the number of words in between.
• The legal search service Westlaw uses Boolean search.
• "trade secret” /s disclos! /s prevent /s employe! where /s prevents the discovery of trade secrets and disclos! /s is an employee action
• The given queries show the precision used. Unlike web search, spaces represents a disjunction and typical queries can be defined.
• Boolean queries are precise: A document either matches the query or it does not.
• It can return the documents in reverse chronological order for greater control over information which is often a popular method.
• And operators tend to produce a high a precision rate and using OR operators produces a low one as well.
• It can be difficult or impossible to find a middle ground
• An inverted index is looked for and the model is understood including linear merges and query optimization.
• The set of terms is better to determine in the dictionary and tolerant retrieval is provided because of word choices and errors.
• It is often useful to search for compounds phrases and proximities to answer term frequency information is recorded in post lists to accumulate evidence.
• Effective ways to rank document results is wanted but generally just retrieve a set of documents.
• These additions use technology that supports information
• Ad hoc searching over documents is becoming more popular
• Emphasizing free text and the existing technologies power web engines