General

  • Definitions Information retrieval
    1. Find material of unstructured nature that satisfies as information need from large collections
    2. Retrieval of information from collection of written documents satisfying a user information need expressed in natural language
  • Types
    • Web search
    • Enterprise, institutional, and domain-specific search
    • Personal information retrieval
  • Requirements
    • Efficiency (process large collections fast)
    • Scalability (system should work with large collections)
    • Expressiveness (powerful querying model)
    • Ranking (return the best match)
    • Effectiveness (high result quality)
  • Tasks
    • Adhoc retrieval (standard IR task, answer arbitrary queries)
    • Standing queries (monitor a set of document periodically)
  • Effectiveness (quality of IR result)
    • Precision (Fraction returned relevant of returned documents)
    • Recall (Fraction returned relevant of real relevant documents)

Motivation

  • Observation
    • 80 % of business uses unstructured data
    • 80 % of data is unstructured format
    • 7 million web pages added per day
    • Unstructured data doubles every three months
  • Information flood needs to be managed

Libraries in the world

History

  • Sumerian archives
    • 3000 - 2000 BC
    • 25000 clay tablets
  • The Great Library of Alexandria
    • 300 BC
    • 750000 scrolls
  • Gutenbergs Movable type
    • 1450 AD
  • Monastic libraries
    • 1475 AD
    • Hand-copying ancient texts
  • German National Library
    • 25 million items
  • Library of Congress
    • 164 million items
  • British Library
    • 170 million items
    • World’s largest library

Catalogs and metadata

  • Task: Describe data
  • Classical catalog
    • Author/editor
    • Keywords/subject

MeSH

  • Metadata for the MEDLINE database
    • Life science and biomedical information database
    • 26 million references
    • Items are manually indexed
  • Medical Subject Headings
  • 27000 subject headings (called descriptors)

Dublin Core Metadata

  • Small set of metadata to describe information resources
  • Can be used with HTML (meta or link tag)

Full text search and indexing

  • Use metadata to judge the relevance of a document
  • Requires a powerful metadata set
  • Needs to be simple
  • Problem: Manual work is expensive
  • Modern information retrieval: Automatically index documents

History of information retrieval

  • 1957
    • Hans-Peter Luhn
    • Use words as indexing unit
    • Document similarity by overlap
  • 1960/1970
    • Gerard Salton
    • SMART system (vector space model)
  • 1992
    • Westlaw (legal research service, Boolean model)

Definitions

  • Document
    • Base unit of an IR System
    • Coherent passage of free text
  • Document collection/corpus
    • \( N \) documents
    • Set of documents
  • Information need
    • The topic the user wants to know sth. about
    • Refers to individual cognitive state (background knowledge)
  • Query
    • What the user communicates to the computer
    • Formal query language
  • Relevance
    • Document is relevant, if the user finds it matching his information need
    • Binary concept
  • Dictionary
    • Index data structure
  • Vocabulary
    • Index terms
  • Term-document incidence matrix
    • Matrix indicating that a term \( t_i \) occurs in a document \( d_j \)
    • Problem: Too huge to store in memory
    • Solution: Inverted index
  • Inverted index
    • Observation: term-document matrix sparse
    • Mapping from term to postings list
    • Posting: Document ID
    • Postings list: List of document IDs
    • Index consists of dictionary and postings list
  • Term frequency \( tf(d, t) \)
    • Number of occurrences of term \( t \) in document \( d \)
  • Document frequency \( df(t) \)
    • Number of documents containing that term
    • Length of postings list
  • Collection frequency \( cf(t) \)
    • Number of occurrences of \( t \) in the complete collection
  • IR Model
    • Components
      • Query language
      • Internal representation of documents
      • Internal representation of queries
      • Ranking function (\( r:Q\times D\rightarrow \mathbb{N} \))
    • Optional: Mechanism for relevance feedback
  • IR System
    • Application which implements an IR model, a query interface, relevance feedback, an index structure
    • Application to support an user

../_images/querying.png

Difference to data retrieval

  • Data retrieval
    • Clearly defined conditions
    • Query stated in query language
    • Well-defined result set
  • Information retrieval
    • Ill-defined information need
    • Query stated in natural language
    • Result list