## Web Search ### Overview - Necessary to find content - Improve collaboration - Use for payment ![](images/websearch.png) ### 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 ![](images/webgraph.png) #### 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 - ``://?#`` - 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 ![](images/crawlerarchitecture.png) ##### 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 ![](images/urichecker.png) ##### 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 2. 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