CSCE 470 Lecture 7

« previous | Monday, September 9, 2013 | next »

Ranking Results Quickly

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} be 1 billion.

If we compute the cosine similarity for a query over all billion documents, our running time is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)} to compute scores and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n \log{n})} to sort results.

Instead, if we use a max heap with $k$ elements, we can perform Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} insertions in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n \log{k})} time, and then read off the elements of the heap.

Tiered Index

Multiple indices:

• Tier 1 has "good" documents
• Tier 2 has "okay" documents
• Tier 3 has unknown documents

Goal: if we can find the first Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} results from Tier 1 and/or Tier 2, we're good. (No computation)

There are still many components we haven't covered yet:

• Positional Indexes
• Spelling Correction
• k-gram indexes for wildcard queries and spelling Corrections
• Document Caching
• Word Proximities
• etc.

Evaluation

Measurable metric from a test user base

• Personal friends and family (tiny)
• Lab test group? (small)
• Blind tests from randomly sampled users/clients (A/B testing)? (large)
• Opt-in for all users (really large)
• Even larger audiences...

Metrics

By order of difficulty of measure:

• how fast is the search? (easy)
• Number of clicks or page views
• Click behaviors
• Do users buy stuff?

Bottom-line: User Happiness vs. Company Happiness

We're going to approach this with a simplified list of metrics:

• Precision
• Recall
• F-Measure
• NDCG

All only focus on relevance