---
# System prepended metadata

title: Information Retrieval & Web Search
tags: [UCR]

---

# Information Retrieval & Web Search
###### tags: `UCR`
## Introduction
* Difference between database & documnets
    * Database: Made up of well-defined fields, has schema
* Documents vs records
    * The query must be compared to the text of entire documnets
* IR tasks
    * Ad-hoc search
        * Find relevant documnets for an arbituary text
    * Filtering
        * Identify relevant user profile for a new document
    * Claasfication
        * Identify relevant user labels for documents
    * Question answering 
        * GIve a specific answer to a question
### Issues
* Relevance
* Evaluation
* User & information needs
* Spam
    * Affect the efficiency of seach engine
### Components
Web => Spider -> (Documents Corpus) -> IR System ->(Ranked Documents)
* Indexing process
    * Inversion: Core of indecxing process
    * Index Distribution: Provides interface and parsers fro query language (Many change becuz ppl are lazy to type)
* Indexing process
    * Text acquisition: Identify and stores documents for indexing
        * Feeds: Real-time stream of documents
        * Conversion: Convert variety of documnets into a consistent text plus 
    * Text transormation: Transforms text to
        * Stopping: remove common words
        * Stemming: Group nwords derived from a common stem
        * Link Analysis: Makes use of links and anchor 
## Retrieval model
### Older models
* Boolean retrieval
    * True or False, simpest form of ranking
    * Specified using boolean operators: AND, OR, NOT
    * Advantage
        * Predictable
        * Features can be incorporated
    * Disadvantages 
        * Difficult complex query, 
        * No ranking, not suitable for web search 
* Search by numbers
### Vector Space Model
* Documnets & queries are represented by a vector of term weights
* Collections are represented by a matrix of term weights
* Use cosine correlation (more difficult to compue the angle)
    * The angle is smaller when the value of cosine is larger
::: info
For query "UCR Riverside", "UCR" and "Riverside" have same similarity, but "UCR" is more specific
:::
* Can be represented as bag of words, no ordering of the words
* Advantages
    * Simple framework for rating 
* Disadvantage 
    * Assumptions of term independence
    ::: info
    If Q = "UCR Riverside Football", D1 = "UCR Riverside" D2 = "UCR football"
    Vector space model gives the same score, but `P(Riverside|UCR) > P(football|UCR)`, D2 is better
    On the other hand, Q = "UCR play", D1 = "UCR game", D2 = "UCR potato", but vector space model failed to find the similarity of "play" and "game" 
    :::
#### Term weights
* Tf-idf
    * Inverse document frequency measures importance in collection
    ::: info
    In previous example, "UCR" has higher inverse frequency than "Riverside"
    :::
    * TF-IDF weights: Normalization
#### Relevance feedback
* Pseudorelevance feedback
    * Don't ask user anything but atomatically do the query
* Optimal feedback
    * Maximize the differnce between the average vectors representing relevant document than that of non-relevant documents.
### Probability Ranking Principles
* Bayes Classifier
    * A document D is relevant if `P(Relevant|D) > P(Non-relevant|D)`
    * Using likelihood ratio
    * Split document toward the words
### Contigency table

### BM25
* Effective ranking Algorithm based on binary independence model
## Language model
* Unigram
* Bigram
    * Decide the next word based on the previous words
    * But more complicated
    * Example
        * I: `P(0.9)P(I|play) = 0.2`, Play`P(0.1)P(I|play) = 0.9`
### LMS for retrieval
* Probability of generating the query text from a document language model
    * `D->LM(D)`, compute `P(Q|LM(D)`
* Smoothing
    * Prevent 0 score
    * Less smoothing for big documents, more smoothing for small documents
        * 
    * Jelinek-Mercer Smoothing
    * Dirichlet Smoothing
## Machine learning models
* If user choose D2, then `S(D2, Q)` > `S(D1, Q)` and `S(D2, Q)` > `S(D3, Q)`
## Web Crawler
* From seed
* Implemented as a queue, push to hyperlink ina page to the end of the queue
* Robots.txt file on the root can be used to controll crawler
    * Disallow and allow
* Sitemaps
    * Contains URLs and Relevant meta, generated by web server administrator
### Freshness
* Web pages are constanly being added, deleted and modified
    * Web crawler must continously revisit pages it has already crawled
    * Stale copies no longer reflect the real content 
* HTTP has HEAD to help checking for page changes 
* A age of page is a Poisson event
### Focus Crawling 
* Attempts to download on ly those pages that are about a particular topic 
* Use a text classifier
### Crawling Deep Web
* Site that are difficult to crawl
* Private sites
    * No incoming links
* Form results
    * Data can only obtain after putting some data into a form
* Scripted pages
    * Generated by scripts 
* Some contain may hidden behind 
    * e.g. Forms
### Distributed Crawling
* Every machine has its own queue
    * May contain duplicates
    * Solution: Hashing
        * Threads exchange hashes of URLs
### Desktop crawling
* Search your own computer
    * Not popular
        * Now most files on the cloud
        * Provided by OS
* Documents Feed
### Conversion 
* Since texts are stored in hundreds of incompatible file format, a convertion tool is needed
* Character Encoding 
    * Encoding: UTF-8, ASCII, etc.
    * A major source of imcompatibility
    * Many other language contain more glyphs
        * Solution: unicode
### Storing webpages
* File system
* Databases
    * Don't need SQL
        * Don't need to join
* NoSQL
* BigTable
    * No query language
    * Only row level transaction
    * Stored in replicated file system accessible by all BigTable server
        * Transactions are stored in a shared file system
### Noise Removal
* There are outlying content block
* Finding Content block
    * Find index i and j maximize both the number of tags below i and above j
## Indexing
Given a keyword, return which document contaions the keyword
* Access to full documents is slow
* Inverted frequency
    * Storing How many keywords in each documents
* Compression
    * Reason: The list can be long
* Document-at-a-time
    * Need more random access
    * But save memory
* Term-at-a-time
    * No random access
    * Need large memory space
        * Need to keep track of partial score
### Optimization Techniques
* WAND algorithm
    * Subroutine: keep pointer
* Skipping
* Threshold method
    * Variant of **term-at-a-time**
* Merging
    * merging address limit memory problem
## MapReduce
* Distributed Indexing
    * A paradism to work across multiple machines
    * Ensure the entries with same key aggragrate on the same machine
    * Mapper and reducer may on the same machine
* Hadoop on top of HDFS
    * A distributed file system
    * Good at 
        * Very large read-only or append-only files
        * Sqeuential access
    * Disadvantages
        * Multiple small files
    * files are stored as blocks and replicated
    * Reducers wait until all mappers finish
    * RR: Used to define own worker
    * There may be **combiners** between mappers and reducers
        * Goal: Minimize the pairs need to be shuffled
        * Do some grouping
## Quizes
* Twitter crawler
```
Insert some user to Q
While Q not :
    Get user u from Q
    Add to Tweets getTweets(u)
    Insert into Q getFollower(Q)
    Insert into Q getFollowee(Q)
```
* Map Reduce
    * Mapper
    ```
    Eliminate duplicate
    emit (w,1)
    ```
    * Reducer
    ```
    Count pair
    emit(w, count)
    ```
    * Combiner: (Same as reducer)
## PageRank
* Traditional IR Ranking
    * Pages are not sufficiently self-descriptive
* Link analysis
    * Assumptions 
        * If the page points to p are good, p is also a good page
* Google paper
    * Hub: Page points to good authorities
## Evaluation
* Relevance judgements are difficult to compute
* Pooling
    * Top K results obtained by various algorithms or models are merged into a pool
* Query Log
    * Used for both tuning and evaluating of search engines
    * Not accurate: Don't like the page and go back 
* Tricky to share query workload 

## QA

#### 1.What are the differences between IR and DB search?  What are the challenges of IR search?
Ans: Database: Made up of well-defined fields, has schema, text reversly.

#### 2.list 4 types of content used in IR applications
Ans: 
* Ad-hoc search
    * Find relevant documnets for an arbituary text
* Filtering
    * Identify relevant user profile for a new document
* Claasfication
    * Identify relevant user labels for documents
* Question answering
    * GIve a specific answer to a question

#### 3.list and define 5 types of applications of IR
Ans:
* Link analysis
* Ranking
* Web crawl


#### 4.list 2 example of query refinement technique
Ans:
* smoothing method


#### 5.list 4 issue of search engine
Ans:
* Noise of the page (or spam)
* Relevance
* Evaluation
* User & information needs




