Information Retrieval

Boolean retrieval

Simplest form of information retrieval. information retrieval needs to be fast, accurate and often be able to rank the results according to their relevance to the query.

1. Naive linear search or grepping
2. Incidence matrix (indexing)
   • document vs term matrix
   • is sparse i.e. many elements are 0s
3. Inverted index
   • data structures: variable length array vs linked list
     • variable length array is better when documents are not frequently updated
     • linked lists are more efficient when frequent updates are required
     • hybrid representation can also be used
   • compact representation of incidence matrix
4. Intersect operation
   • sort in ascending order to list size
   • after every merge the intermediate list will be of the least possible length
5. Boolean operations
   • and, or, not
   • proximity
6. Want to do
   • use natural language instead of specific queries
   • changes in postings of inverted index to accomodate “proximity” operations
   • rank the retrivals

Term vocabulary and postings list