CSCE 470 Lecture 2

« previous | Wednesday, August 28, 2013 | next »

Abstract IR Architecture

Query → Query Representation
+ Document → Document Representation → index
= hits

Term-Document Incidence Matrix

Rows = terms

Columns = document IDs

$M_{ij}$ is 1 if term $i$ appears in document $j$, 0 otherwise

There will be very few ones and very many zeroes, so this will be a sparse matrix

Sorting Keys

• Linear search ($O\left(n\right)$)
• Lexicographically ordered: binary search ($O\left(\log {n}\right)$)
• Hash Map ($O\left(1\right)$)

Boolean queries:

AND, OR, NOT

Represent rows of matrix as vector, perform corresponding bitwise operations on vector to get results

no ranking

Index

Throw away all the zeroes, only keep the ones

Dictionary maps term keys to a collection of documents.

Boolean query operations now become set operations (union, intersect, complement)

Search optimizations now come in to play