Web Search

Overview

• Necessary to find content
• Improve collaboration
• Use for payment

Difference to classical information retrieval

Heterogeneity

• Dynamic content/collection
• Different users (status 2014)
  • 87 % of adults
  • 97 % of 18-29 year old
  • 57 % of 65+ year old
• Languages (status 2013)
  • 55 % English
  • 5 % German
  • Various writing styles
• Document types
  • HTML / XML / CSS / Flash
  • MS Office types
  • PDF / RTF
  • TAR / ZIP
• Query types
  • Informational (find information about topic)
  • Navigational (find specific website)
  • Transactional (find website providing a service)
  • Connectivity (Find connected pages)
  • Statistics (status 2008)
    • Question: Actions of internet users on a typical day
    • 60 % of adults search for information
    • 60 % of adults check their emails
    • 80 % of teens do social networking
    • 62 % of teens get news

Link structure

• Interconnectedness of documents
• Links are not randomly

Size

• Queries per second
  • High number of users
  • Statistics (status 2005)
    • Google: 700 qps
    • MSN: 300 qps
• Index size
  • Statistics(status 2014)
    • Google: 15 trillion
    • Bing: 9 trillion
  • Estimation: ???
• Data size
  • Challenge for crawler
  • Handle new/deleted/updates pages
• Scalability
  • Number of host names (seems to) grow exponentially

Spam

• Spamdexing: Fake relevance of pages
• e.g., Google bombing
• Increase term frequencies

Business model

• Web Search is expensive (storage, hardware, development)
• Business models
  • Advertising model
  • Subscription model
  • Community model
  • Infomediary model

Advertising model

• Show other ads of other companies
• Alternative: Pay people money if they use ad link
• e.g., Google AdSense/AdWords, Microsoft CashBack
• Requirement: Attractive search engine
• Example: Google AdRank

Subscription model

• Customer pays to use search engine
• Requires high quality search engine
• e.g., rent search engine for company’s site

Community model

• Users participate in development of the search engine
• Advantage: Reduced costs
• Handle costs with donations/ads

Infomediary model

• User participates in market studies
• Search engine analyzes users’ behavior
• Analyzed information is sold
• Problem: Privacy

Properties of the Web

Web page size

• Status 2011
• Average of 16 KB
• Average of 512 words
• 68 % of web pages does not change within a week

Index size

• Problems in estimation
  • Duplicates (ignore)
  • Spam (ignore)
  • Dynamic web pages (focus on content)
  • Pages/content that is considered
  • Private sites (e.g., Facebook)
• Challenges
  • Find duplicates
  • Detect spam
  • Handle dynamic sites
  • Handle private sites
• Estimation using samples
  • Two crawls \( C_1, C_2 \)
  • \( P(p\in C_1 \mid p\in C_2) = \frac{|C_1\cap C_2|}{|C_2|} \)
  • \( P(p\in C_1 \mid \text{Web}) = \frac{|C_1|}{|\text{Web}|} \)
  • Assume: Probabilities are equal (sample is representative)
  • \( |\text{Web}| = \frac{|C_1| * |C_2|}{|C_1\cap C_2|} \)
• Practice:
  • Take samples from the index of search engines
  • Samples are not independent
• Layers of the web
  1. Sufrace Web
  2. Deep web/invisible web

Shape (Web graph)

• Directed graph (in- and out-links)
• Distribution
  • \( X_p \): Number of in-links of a page
  • \( P(X_p=k) \propto k^{-2.1} \)
• Shape: Bowtie shape
  • IN: Link into SCC
  • SCC: Central core
  • OUT: Links from SCC
  • Tentrils: Links from IN to nowhere/nowhere to OUT
  • Tube: Directly from IN to OUT
  • Disconnected components

User behavior

• Page Popularity is Zipf distributed
• Incoming traffic is Zipf distributed
• Average query length: 2.4 terms
• Single-term queries: 50 %
• 50 % of users looks on first 20 results
• Term frequency distributed follows power law

Web crawling

Web resources

Identification using URIs

• <scheme>://<authority><path>?<query>#<fragment>
• Normalization
  • Quote characters
  • Case normalization
  • Remove default ports
  • Remove path segments

Retrieval using HTTP

• Protocol for client/server
  • Base: TCP/IP
  • Map hostnames to Domain Name System (DNS)
• Methods:
  • GET (request resource)
  • HEAD (request meta data)
  • POST (submit data)
• Status codes:
  • 2xx Success (e.g., 200 OK)
  • 3xx Redirect (e.g., 301 Moved Permanently, 304 Not Modified)
  • 4xx Client Error (e.g., 404 Not Found, 410 Gone)
  • 5xx Server Error (e.g., 500 Internal Error)

Representation using HTML

• Hypertext Markup Language
• Describe structure of text-based information

Challenges

• Spam detection
• Duplicate detection
• Spider trap avoidance
  • Spider trap: Link (invisible for user, excluded for serious crawler) to block IP address of undesired crawler
• Distribute process
• Handle latency problems (slow responses)
• Crawling depth
• Respect site owner’s policies

Crawler

• Architecture
  • Queue of URIs
  • Method for data retrieval/processing
  • Page parser (extract links)
  • Connection to indexer of the search engine
• Algorithm
  1. Initialize queue with seed pages
  2. Retrieve page from the next URI
  3. Extract URIs
  4. Add URIs to queue
  5. Repeat

Features

• MUST-have
  • Robustness
    • Golden rule: For every possible problem, there is a website exhibiting this problem
    • Handle failures (e.g., spider traps)
  • Politeness
    • Do not generate high traffic (traffic is money for the customer)
    • Respect crawling policies (e.g., robots.txt)
• SHOULD-have
  • Distributed
  • Scalable
  • Performance/efficiency (efficient resource usage)
  • Quality (update relevant pages more often than non-relevant)
  • Freshness
    • Continuous mode
    • Crawl proportional to rate of change
    • Ability to update set of pages on demand (e.g., World Cup)
  • Extensible (new data formats, new protocols, modular architecture)

DNS Handler

• Customized local DNS component
• Problem: DNS request is slow (parallel requests, latency)
• Solution:
  • Prefetch DNS information
  • Relaxed policy for DNS updates (i.e., ignore the standard for practical reasons)

Duplicate URI Checker

• Task: Check if URI has been checked (avoid unnecessary fetching)
• Problem: String comparisons are expensive
  • Solution: Fingerprints
  • Fingerprinting
    • Normalize URIs
    • Compute URI hash
    • Insert URI hash into B-tree (efficient search)
• Problem: Amount of storage
  • Solution: Locality
  • Idea: Enforce URI locality to speed up access (URIs with the same hostname are accessed together)
  • Use concatenation of two fingerprints (hostname, rest)
  • Use hash function with continuity

Duplicate Content Checker

• Problem: Near-duplicate detection (e.g., timestamps)
• Normalization:
  • Remove styling information
  • Convert to text-only
  • Drop navigational structures
  • Drop images/dynamic content
• Solution: Shingling
  • Create k-shingles/k-grams (on words) for each document
  • Definition: Documents \( d_1,d_2 \) are near-duplicate iff \( J(d_1,d_2)>0.9 \)
  • \( J(d_1,d_2)=\frac{|S(d_1)\cap S(d_2)|}{|S(d_1)\cup S(d_2)|} \)
  • Problem: Expensive computation \( O(n\log n) \) (sorting, merging)
• Randomized approximation algorithm
  • Hash sets and perform random permutation (uniform distribution)
  • \( J=P(\min(\Pi(d_1)) = \min(\Pi(d_2))) \)
  • Proof: Vector reordering, using relative frequency of (1,1)-columns over not-(0,0)-colums
  • Hashing and permutation forms a new hash function
  • Compare: Drawing with placing back
• Estimation
  • Create sketch of document
  • \( \Psi(d) = (\min(\Pi_1(d)), ..., \min(\Pi_{200}(d))) \)
  • \( J(d_1,d_2)\approx \frac{\text{Overlap}(\Psi(d_1), \Psi(d_2))}{200} \)
  • Using 200 permutations estimates the probability (Law of large numbers)
• Problem: Expensive comparison of sketch of every document to new one
  • Solution: Pruning/Indexing
  • Order pairs \( (\Psi_i(d), id(d)) \) by \( \Psi_i(d) \) in B-Tree
  • For each new document, union documents for each \( \Psi_i(d_{new}) \) in B-Tree
  • Compute Jaccard-index with pruned documents

Focused crawling

• Search engine focuses on specific topic
• Start with manual set of pages
• Use classifier for new pages

Link Analysis

Social networks and prestige

• Reasons for social networks
  • Friendships
  • Trading contracts
  • Authoring and citation
  • Acting
  • Phone calls
  • Infections
• Model: Directed graph
• Important questions:
  • Prestige (e.g., authors)
  • Centrality/Well-connectedness (e.g., countries)
  • Connections between components (e.g., people)
• Prestige
  • Naïve: In-degree of a node

Seeley’s model of Prestige

• Idea:
  • Person’s status is function of the status of the persons he is chosing
  • Number of in-links is correlated to prestige
  • Recursive model
• Model
  • Prestige \( p(v) \in \mathbb{R} \)
  • Constraint: \( p(v) = \alpha \sum_{u\rightarrow v} p(u) \)
  • Equivalent fixpoint condition: \( p=\alpha A^T p \)

Centrality

• Radius \( r(v)=\max_w d(v,w) \)
• Cut: Number of edges which disconnects two vertices when removed
• Defintions
  1. Center: \( c(G) = \arg\min_v r(v) \)
  2. Erdös-number
  3. Smallest set of vertices that decomposes the graph
• Applications
  • Citation graph: Center nodes are very influential
  • Epidemics/espionage/terrorist communication (use cuts)

Co-citation

• \( cites(u,v) \land cites(u,w) \Rightarrow \text{v and w co-cited by u} \)
• Formal
  • Adjacency matrix \( A \) for \( a_{ij} = 1 \iff \text{cites}(d_i,d_j) \)
  • Co-citation index matrix: \( A^T A \) (measure of relatedness/number of documents citing both documents i and j)
• Multidimensional scaling
  • Clustering algorithm for co-citation index
  • Similar to SVD
  • Embed documents into low-dimensional space
  • e.g., reveals social structures between communities

Basis

• Assumptions
  1. Hyperlink is signal of quality/popular interest
  2. Anchor text of a link describes target
• Algorithms
  • PageRank (Page, 1998)
  • HITS (Kleinberg, 1999)

PageRank

• Page et al., 1998
• Idea: Assign query-independent measure of prestige/popularity to Web resources
• Solution: Use Seeley’s model of prestige (prefer in-links from high quality resources)
• Components
  • Random surfer model yields stochastic matrix
  • Perron-Frobenius theorem yields unique stationary probability vector \( p \)
  • Formula fits Seeley’s mode of prestige
• Importance
  • PageRank is only one component in ranking (e.g., anchor texts, phrases, proximity)
  • Addressing link spam is important
• Improvement
  • Remove navigational links (quality assumption does not editorial judgement, i.e., link means a recommendation)
  • Remove nepotistic links (e.g., sites by same author, hard to detect)

Random Surfer model

• 90 % of time, surfer clicks random hyperlink
• 10 % of time, surfer types in a random URI
• PageRank is long-term visit rate of nodes
• Use transition matrix
  • Probabilities to move from page \( i \) to page \( j \)
  • Sum of rows equals 1
• Problems:
  • No equal probability for link-choosing (usually topic-driven)
  • Back button/bookmarks are not considered
• Algorithm
  1. Choose a random page \( d \) (uniform distribution)
  2. Choose random number \( p \)
  3. If \( p > \lambda \land deg^+(d)>0 \), randomly choose an out-link, continue at (2)
  4. If \( p < \lambda \lor deg^+(d)=d \), choose a random page, continue at (2)

Convergence

• Transition matrix \( T \) (Markov chain)
• Probability: \( p_{t+1} = T^T * p_t \)
• Probability vector converges iff t limits infinity
  • \( p=T^T * p \)
  • \( p = \lim\limits_{t\rightarrow \infty} p_t \)
  • \( p \) is eigenvector \( T_T \) with eigenvalue \( 1 \)
  • Perron-Frobenius theorem because \( \lambda > 0 \) and therefore \( T \) has only positive entries
  • \( p \) is stationary probability vector

Computation

• Compute eigenvalues
  • Power iteration
  • Iteratively compute \( p_{i+1}=A^T * p_i \)
  • Normalize \( p_{i+1} \)
  • Converges against eigenvector with largest eigenvalue (in this case, the stationary vector)
• Use Map and Reduce

Topic-sensitive PageRank

• Problem: Resource can be important in a local view/specific topic
• Uses set of topics/classification to assign topics
• Topic-sensitive PageRank is compute on set of each topic

HITS

• Kleinberg el al., 1999
• Hyperlink Induced Topic Search
• Patent assigned to IBM
• Idea: Assign query-dependent hub score and authority score to Web resource
  • Hub: List of links to authorities
  • Authority: Definitive high-quality information
  • Page can be hub and authority
• Advantage
  • Query-dependent
  • Uses subset of Web graph
• Disadvantage
  • Expensive (computation at query time)

Formalization

• Important: Connection to SVD
• Root set: Compute using standard IR system
• Base set \( V_q \): Root set and neighbors of root nodes
• Authority score:
  • \( a = \alpha A^T h \)
  • Proportional to sum of hub scores linking to it
  • Eigenvector of \( a=\alpha\beta A^TA a \)
• Hub score:
  • \( h=\beta A a \)
  • Proportional to sum of authority scores to which it links
  • Eigenvector of \( h=\alpha\beta AA^T h \)
• \( \alpha,\beta \): Proportionality constants
• Use principal eigenvectors (hubs/authorities in largest linked community)
• Computation
  • Power iteration
  • SVD (\( U \) contains eigenvectors of \( AA^T \), \( V \) contains eigenvectors of \( A^TA \)
• Problem: Ambiguous/polarized query
  • Base set contains disconnected components
  • Principal eigenvector are hubs/authorities in largest linked community
  • Solution: Don’t use strictly the principal eigenvectors

Spamdexing

• Goal: Rank Web resource unjustifiably high (e.g., SEO)
• Idea: Find weaknesses in ranking algorithms + exploit weaknesses
• Techniques:
  • Content spam (change page content)
  • Link spam (change link structure)
• Important:
  • Create good content
  • Costs in cheating search engine is higher than benefit
  • Rule: Link is recommendation

Content Spam

• TF-IDF / Google Bombing
  • Add keywords to content/title/URI/anchor text
  • Add related high quality content (e.g., Wikipedia) to your site
  • Countermeasure:
    • Classification (Problem: Feature selection)
    • Detection of hiding the text
• Cloaking
  • Distinguish between IP addresses (deliver different page to crawler then to user)
  • Types: IP-cloaking, User-Agent-cloaking
• Doorway pages
  • Automatic redirect from different pages to cheating page
  • Different pages are optimized for specific queries

Link spam

• Idea: Improve rank by getting in-link from other pages
• Problem: Hard to detect
• Countermeasures:
  • Remove pages with similar in-links (comment spamming/Google bombing)
  • Remove copies of high quality content (honeypot)
  • White-list of good pages (use distance to white-list pages as indicator of trustworthiness)

Comment spam

• Spam comment section of indexed high quality forums (e.g., blogs, Wikis)
• Countermeasure: CAPTCHA
• Countermeasure against CAPTCHA:
  • Character recognition algorithms
  • Crowd-solving CAPTCHAs

Link farms

• Large set of pages with links to each other
• Set out-links to high quality pages (e.g., high hub score)
• Result: High authority scores

Honeypots

• Copy high quality content pages (e.g., copy Unix documentation, Wikipedia)
• Add hidden links to your target

Buy expired domains

• Monitor DNS records & buy expired domain
• Replace page with redirect to your page

Google’s hardware

• Data from 2007
• Custom-built servers
• 7 % of all internet traffic generated by GOogle
• Server rack:
  • 40-80 commodity class PC servers
  • 12 V battery
  • Unstable but cheap
• Challenges
  • Deal with failures
  • Avoid data loss
  • Guarantee 100 % uptime
• Sources:
  • https://www.youtube.com/watch?v=Ho1GEyftpmQ
  • https://www.youtube.com/watch?v=XZmGGAbHqa0

Metasearch

• Similar to Boosting: Combine strengths/weaknesses of multiple search engines
• Metasearch engine uses result lists
• Problem:
  • \( k \) ordered result lists of size \( n \)
  • Task: Aggregate results into single ranking with some constraints (similar to social choice theory)
• Assumptions
  • Search engines are independent
  • Search engines have similar quality
• Aggregation methods
  • Majority rule
  • Borda count
• Application
  • Search engine with maximum recall
  • Other queries don’t work well

Aggregate quality

• Pareto efficiency:
  • If every search engine ranks \( p_a \) over \( p_b \), \( p_a \) is ranked higher than \( p_b \) in aggregate ranking
• Non-dictatorship:
  • Aggregate ranking should be unequal to the ranking of any search engines
• Independence of irrelevant alternatives
  • If A is ranked higher than B, adding C to the individual search engines does not change the ranking of A and B
• Kenneth Arrow’s impossibility theorem
  • 1951
  • If there are more than two different pages to be ranked, there is no deterministic aggregation algorithm that satisfies Pareto efficiency, Non-dictatorship and independence of irrelevant alternatives

Aggregation method

Majority rule

• Assumption: All search engines ranked the same pages
• For each pair \( (a,b) \) count the number of search engines ranking \( a \) higher than \( b \)
• \( (c_{ij})=|\{s\mid\text{rank}_s(i)>\text{rank}_s(j), \text{s is search engine}\}| \)
• Rank is given by product of rows
• Problem: Cycles

Borda Count

• Assign to each result in each ranking a score
• \( \text{score}_\text{ranking i}(a) = \text{rank}(a) \)
• \( \text{score}(a) = \sum_i \text{score}_\text{ranking i}(a) \)
• Advantages
  • Easy
  • Can handle unranked results
  • Can weight search engines result
• Disadvantages
  • Tie
  • Assumes uniform degradation of relevance

Kendall’s Tau

• Measure for the agreement of two result sets
• \( \tau \in [-1,1] \)
• Both results contain the same \( m \) elements
• For each pair of results count if the ordering is the same in both result sets
• \( p_+ \): Number of agreeing pairs
• \( p_- \): Number of disagreeing pairs
• \( \tau = \frac{p_+-p_-}{\binom{m}{2}} = \frac{2(p_+-p_-)}{m(m-1)} \)

Privacy

• Problem: AOL Dataset (users were de-anonymized)
• Netflix: Matching with IMDB dataset