Jeff's Search Engine Caffè

Notes on Strata 2011: Entities, Relationships, and Semantics: the State of Structured Search

2011-11-08T09:30:00.000-05:00

Daniel Tunkelang moderated a panel on the state of structured search at Strata 2011.

Entities, Relationships, and Semantics: the State of Structured Search

I didn't attend the talk, but I watched the video and took down notes on it for future reference.

Andrew Hogue (Google NY)

- worked on google squared

- QA on google, NER, local search

- (extraction is never perfect) even with a clean db, with freebase. coverage isn't good, 20/200 dog breeds

- if you try to build a se on top of the incomplete db, users hit the limit, fall off the cliff and get frustrated

- Tried to build user models of what people like (for Google+). Do you like Tom Hanks, BIG? In the real-world.
(Coincidentally, Google just rolled out Google+ Pages that represent entity pages)

--> if the universe isn't complete, people, entities, then they get frustrated

--> 1) get a bigger db. 2) fall back gracefully to a world of strings (hybrid systems)

Breck baldwin (alias-i)

- go hunt down my blog post (on march 8 '09 on how to approach new NLP projects)

- the biggest problem is the NLP system in the head vs. reality

- three steps: 1) take some data an annotate it. 10 examples. force fights earlier. #1 best thing. #2 build simple prototypes. info flow is hard. #3 eval metric that maps to the business need

Evan Sandhause (NY Times)

- on the semantic web (3.0)

- the semantic web is a complex implementation of good, simple ideas

- get your toe wet with a few areas: 1) linked data, and 2) semantic markup

- 1) linked data - all articles get categorized from a controlled vocabulary (strong ids tied to all docs). BUT - No context to what those IDs mean. e.g. barack obama is the president of the united states. Kansas city is the capital... you need to link the external data to add new understanding.

-- e.g. find all articles in A1, P1 that mention presidents of the United States

-- e.g. find all articles that occur near park slope brooklyn

2) semantic markup (rdfa, microformat, rich snippets). They use rnews vocab as part of schema.org.

Wlodek Zadrozny (IBM. Watson)

- what are the open problems in QA

- Trying to detect relations that occur in the candidate passages that are retrieved (in relevance to the question)

- Then scores and ranks the candidate answers. Some of it in RDF data. Confidences are important because wrong answers are penalized.

keys to success: 1) data, 2) methodology, testing often 1. QA answer sets from historic archives. (200k qa pairs) 2. collection data sources. and 3. and test (trace) data (7k experiments, 20-700 mb per experiment. lots of error analysis.

- medical, legal, education

Questions

Q: NYT R&D. The trend around NLP. Certain things graduate on reliability. What will these be over the next decade?

-- Andrew. The most interesting thing is QA. Surface answers to direct questions. (harvard college vs lebron james college)

-- statistical approaches to language, (when do we have a good parse, vs. we don't know)

-- Breck - classifiers are getting robust on sentiment, topic classification. breakthroughs in highly customized systems. finely tuned to a domain in ways that bring lots of value.

Query vs. Document centric

-- reason across documents at a meta-level. What can you do when you have great meta-data? (we have hand-checked, clean, data)

-- in Watson, an alternative to high-quality hand curated data is to augment existing sources with data from the web

(see Statistical Source Expansion for Question Answering from Nico Schlaefer at CIKM 2011)

QA on the open web

- Problem - not enough information from users. People don't ask full NLP questions (30 to 1)

- Is there an answer? (Google wins by giving people documents and presenting many possible answers)

Evan - the real-time metadata is needed for the website. They use a rule based information extraction system which suggests terms they might want want to suggest. Then the librarians review the producers tags.

Breck - Recall is hard. In NER and others.

Overall Summary

- Wlodek - QA depends on having the data: 1) training/test data, 2) sources, and 3) system tests

- Evan - Structured data is valuable to get out there, rNews and schema.org. Publishers should publish it! It will be a game changer.

- Breck - 1) annotate your data before you do it. 2) have an eval metric, and 3) lingpipe is free, so use it.

- Andrew - (involved in schema.org, freebase). Share your data. Get it out there. And -- Ask longer queries!

CIKM 2011 Industry: Toward Deep Understanding of User Behavior on the Web

2011-10-27T11:57:00.003-04:00

Toward Deep Understanding of User Behavior on the Web
Vanja Josifovski, Yahoo! Research

Where is user understanding going?

What is the future of the web?
- prevalent - everyone and everything
- mutual understanding

Personalized laptops

Personalization today
- Search personalization. low entropy of intent. Difficult to improve over the baseline
--> effects are small in practice

Content recommendation and ad targeting
- High entropy of intent
- Still very crude with relatively low success rates

How do we need to move to the next level
- more data, better reasoning, and scale

Data today
- searches, page views
- connections: friends, followers, and others
- tweets

The data we don't have
- jetlagged, need a run? need a pint?, worried about government debit?
- the observable state is very thin

How to get more user data?
- Only with added value to the user
- Must be motivated to provide their data

Privacy is not dead, it's hibernating
- the impact of data leaks online is relatively small

Methods
- State of the art as we know it.
- Popular that seem to work well in pratice
--> Learn relationship between features rij = xiCzj
--> Dimensionality reduction (random, topical models, recommender systems rij = uivj)
--> Use of extenral knowledge: smoothing
--> taxonomies

An elaborate user topic model (Ahmed, KDD 2011, Smola et al. VLDB 2010), yet so so simple
- the user behavior at time T is a mixture of his behavior at time t-1 + global overall behavior
- Very simple model

Using External Knowledge
- Aggrawal et all KDD2007, KDD 2010

Is there more to it?

-> What is the relative merit of the methods?

-> They use the data in the same way and are mathematically very similar

Where is the limit?

-> what is the upper bound on the performance increase on a given dataset with this family of algorithms?

Scale

- Today - MapReduce is a limiting barrier for many algorithms

- Need the right abstractions in parallel environments

- Move towards shared in memory, messages passing models (like Giraph)
-- (we'll work this out)

Workflow complexity
- the reality bites Hatch et al. CIKM 2011. Massive workflows that run for hours.

Summary

CIKM
1) Deep user understanding - the tale of three communities

IR:
- Good formalism that function practice
- emphasis on metrics and standard collections

DB
- seamless running of complex algorithms
- new parallel computation paradigms

Towards deeper understanding
1) get users to give you more data by providing value
2) significantly increase the complexity of the models
3) scale in terms of data and system complexity

CIKM 2011 Industry: Model-Driven Research in Social Computing

2011-10-27T11:13:00.002-04:00

Model-Driven Research in Social Computing
Ed Chi

Google Social Stats
250k words per minute on blogger, 360 million words per day
100M+ people take a social action on YouTube

Google+ Stats
40 million joined since launch
2x-3x more likely to share content with one of their circles than to make a public post

Hard to talk about because the systems are changing quite rapidly
Ed joined Google to work on Google+

Social Stream Research
Analytics
- Factors impacting retweetability (IEEE Social computing)
- Location field of user profiles

Motivation for studying languages
- Twitter is an international phenomenon
- How do users of different languages use Twitter?
- How do bilingual users spread information across languages?

Data Collection & Processing
- 62 M tweets (4 week), spritzer feed in april-may june 2010
- Language detection with Google language API + LingPipe
- 104 languages
- Top 10 languages

English - 51%
Japanese - 19 %
Portuguese - 9.6% (mostly Brazil)
Indonesian - 5.6%
Spanish - 4.7%

Sampled 2000 random tweets
- 2 human judges for each of the top 10 languages

Problems with French, German, and Malay.
Accuracy of Language Detection
- Two Types of errors (poor recognition for "tweet English") and for tweets with 1-2 words

Korean - recommend for conversation tweets
German - promote tweets with URLs

English serves as a hub language

Implications - need to understand when building a global network on language barriers
- building a global community
- the need for brokers of information between languages

Visible Social Signals from Shared Items (Chen, et al. CHI 2010/CHI 2011)
- After all day without WIFI, he would like a summary of what's happening in his social stream
- Eddi - Summarizing Social Streams
--> What's happened since you last logged in
--> A tag cloud of entities that were mentioned
- A topic dashboard where tweets are organized into categorizes to drill into

Information Gathering/Seeking
- The Filtering problem - I get 1,000+ things in my stream, but only have time for 10. Which ones should I read?

- The Discovery Problem
-- millions of URLs are posted,

Zerozero88.com
- twitter as the platform
- URLs as the medium
- a personal newspaper that produces personal headlines

URL Sources (from tweets) -> Topic Relevance Model, and Social Network Model

URL Sources
- Consider all URLs was impossible
-- FoF URLS from followee-of-followers
--> Social local news is better
- Popular - URLs that are popular across whole of Twitter
--> popular news is better

Topic Relevance Model
- A user Tweets about things, which creates a term vector profile.
- Cosine similarity with URLs
- Topic Profile of URLs - Built from tweets that contain the URL, but tweets are short and RT makes word frequencies goofy.
- Adopt a term expansion technique, extract nouns from tweet and feed it into a Wikipedia search engine as a topic detection technique

Topic Profile of User
- Self-topic
- Information producer - the things they tweet about
- Information gatherer - what they like to read
- Build profiles from froms and aggregate them.

Social Module
- Take FoF neighborhood, and count the votes for a URL
- Simple counting doesn't work very well.
- Votes are weighted using social network structure

Study Design
- Each subject evaluating 5 URL recommendations from each of the 12 algorithms. Show 60 URLs in a random order and ask for binary rating,

Summary of Results
- Global popularity (1%) -- 32.50% are relevant, not bad, but not good enough
- FoF only - 33% - naiive by itself without voting doesn't work great
- Fof voting method - 65% (social voting only)
- Popularity voting - 67%
- FoF Self-Vote - 72% best performing

Algorithms differ not only in accuracy!
- Relevance vs. Serendipity in recommendations (tension between discovery and affirming aspect)
-> "What I crave is surprising, interesting, whimsy" this is where the value is
-> Two elements two surprise: 1) have I seen this before, 2) non-obvious relationships between things

Design Rule
- Interaction costs determine number of people who participate
- Reduce the interaction costs, then you can get a lot more people into the system
- For Google+ this is key to deliver this to people

Q&A:
Japanese crams more information into a tweet. It is used more for conversation than broadcast in these environments

CIKM Industry talk: Jeff Hammerbacher on Analytical Platforms

2011-10-27T06:35:00.001-04:00

Experiences Evolving a New Analytical Platform: What Works and What's Missing
Jeff Hammerbacher, Cloudera

Built the infrastructure team at Facebook, 0 to 2 PB of data

Take the infrastructure and make it available as open source.

Philosophy
The true challenges in the task of data mining. Creating a data set with the relevant and accurate information, determining the appropriate analysis techniques

Exploratory data processing (IBM)

Taught the data science course at Berkeley earlier this year

1) Store all your organization's data in one place
- data first, questions later
- store first, structure later

Engineers are constrained when you force them to stop and model the data, which is constantly evolving.

Raw storage: $0.4 / GB (67 for 2 TB disk), Single HDFS instance > 50 PB on commodity hardware in one center

Enable everyone to party on the data. Use files because developers are not analysts.

Like the LAMP stack, there is a coherent analytical data management

Better underlying abstractions

Platform - Substrate
- commodity servers (a big warehouse)
-- open compute project (FB open source)
- open source OS
-- Linux
- Open source config management
-- Puppet, Chef
- Coordination service
-- ZooKeeper

Platform - Storage
- Distributed, schemaless storage
--> HDFS, Ceph (UCSC), MapR
- Append-only table storage and metadata
--> Avro, RCFile, HCatalog (Also: Thrift, Protocal Buffers)
- Mutable table storage and metadata
-- HBase

Compute
- Cluster resource management
-- YARN (inter-job scheduling, like grid engine, for data intensive computing)
-- Mesos
- Processing Framworks
-- MapReduce, Hamster (MPI), Spark, Dryad, Pregel (Giraph), Dremel
- High level interfaces
-- Crunch (like Google's Flume Java) , DryadLINQ, Pig, Hive

Platform
Integration
- Tool access
- Data ingest
-- Sqoop, Flume
(Documents ingest is still an area that needs work. There are crawlers, but they're still immature)

Trends
fat servers with fat pipes
2u, 24 gb ram, 12 drives, (bigger nodes)
os support for isolation (VMs have downsides)
Linux containers
-- Google contributed initial patches, used for BORG
Local files system improvements
-- btrfs

language
- scalaql

CIKM 2011 Industry: Freebase: A Rosetta Stone for Entities

2011-10-27T05:50:00.001-04:00

John Giannandrea, Google

What is Freebase?
-> A machine representation of things in the world. (Person, place, thing in the world)
-> Instead of working in the domain of text, we work in the domain of strong identified things
-> Each object has an identifier, once you have it, it will also refer to an identity

Properties - relationships between objects
- edges between the entity ids
- edges are directional
- properties create meaning

Graphs
- encode knowledge

Types
- a categorization of an entity
- An entity can have multiple Types in Freebase
- "Co-types" - Types are a mix-in
- e.g. Arnold (politician, actor, athlete)

The real world is extremely messy.

Knowledge you can use
- the current state
- 25 Million topics (entities)
- 500 million connections
- 2x the size it was last year

>= 10 instances, 5790 types
1772 commons (survived community scrutiny)
4019 bases (people created)

Identity matching
- reconciliation at scale
- Wikipedia, Wordnet, Library of congress terms, Stanford library
- any large open source term they have tried to import into Freebase

-> How? Whatever works. MapReduce, Google Refine, and human judgment
-> This is possible if you know what an entity is. (IBM example)

Freebase as a rosetta stone
- keys
- behind the websites, there is a structured database with keys (relational db with tables that have primary keys)
- all of these keys leak out onto the web, "shakira" in the url
- In the Freebase system they try to collect these keys to link the entity to external websites

URLs and Freebase keys
- accrete the URLs and keys onto the object
- Names are just another key (the entities themselves are the same across languages)

Schema
- Freebase is schema less
- It is fundamentally based on a graph store
- Schema is described in the graph itself, just as the data ("Type: type")
- The person "type" is an entity with an id, "Type:type:person"
- Put the predicates into the graph system so that it can be updated

Google API to Schema Data
- WIKL read ( a query language for inspecting the freebase graph)

How does Google use Freebase?
- "I work in the search division"

Time in Freebase
- everything has a start date and end date

How good is the quality?
- varies depending on the entities (e.g. presidents is high quality, but obscure book there may be some duplicates)
-> 99% accuracy
-> curate the top 100k entries
-> we'd rather not import data than import data that is bad
-> (We imported the open library catalog, which has lots of duplicates. never again.)

Q&A:
Recall
- 25 M entities, 2x from last summer, 100M by next year
- It depends on the domain
- For common queries in search engines, it does very well
- search engines handle lots of queries for celebrities, common places on earth

Confidence on facts
- common criticisms 1) it's not a real database, 2) the assertions are not given weight, it doesn't capture uncertain facts
- you can create a mediated way of doing that in the schema
- how do you deal with controversial facts? 1) careful with type definitions. countries are hard. (use UN definition) unusual categories. FIFA has its own definition. World cups have been played with countries that don't exist.
- for head entities, there are large number of people arguing

Ian - quality 99% accuracy is still 1 million incorrect for 100M.
- sampling rate for how you draw entities. you have a probability of confidence.
(two kinds of sampling: 1) random sample, 2) traffic weighted sampling based on popularity)
- 99% at the 95th percentile

CIKM 2011 Keynote II: Justin Zobel on Biomedicine

2011-10-26T04:30:00.000-04:00

Data, Health, and Algorithmics: Computational Challenges for Biomedicine
by Justin Zobel

(I missed the first part of this talk)

The Central Dogma
- DNA consts of sequence of four bases, A, C, G, T
- The concept of a gene is now uncertain

SNP analysis (Nature 00)
- used PCA

Revolution
- Read DNA directly
- $1000 by the end of 2012

The data is erroful, incomplete, voluminous, ambiguous.

Also, reads are not very random

Within a few years there will be DNA databases of 10-100 terabases, which we will use to find matches to short read data

Challenge: Assembly
- Imagine a million copies of a phone book, a million pages long
- Shredded into tiny pieces, each no more than 20 or 30 characters
- 99.999% are thrown away.
- The task: reconstruct the phone book from the billion remaining pieces

The Problem of assembling short reads.

Genomes are a combinatorial minefield
- vast quantities of repeated material

The genome is cheap, but the analysis is expensive

de Bruijn graph
- Divide 7-base reads into kmers (3mers)
- each node is a kmer, each arc is an overlap

The graph is about 4 terabytes, and it needs to be in memory.

Succint 'Gossamer' representation
- fast access with simple index
- space down by a factor > 10
- cuts the storage down to 32 GB

DNA dictionaries
- there is no grammar for DNA that would allow construction of a parser
- a dictionary of all possible tokens would be impossible large

Dictionary - any representative string
-> solves the text compression problem for DBs

Genetics for diagnosis
-> inference diagnosis based on symptons replaced by ones based on DNA analysis
-> drug effect and health outcome determined directly from historical health records
- Built to simplifly, improve, and automate bureaucratic decisions

'Guardian Angel' clinical decisions
- Electronic health records analyzed on the fly to check whether a mistake is about to be made.

Health at Home
-> health monitoring deeply embedded in our e-lifestyle activities
-> webcam that determines how well you are based on your skin
-> iphone app that tells if your drunk

Computer Science vs heatlth research
- many algorithmic solutions are not biologically meaningful
- spend money on IT and the number of errors is decreased (It saves lives.)

13 of the top 25 questions (Science mag July 2005) are about DNA

The real way to have an impact on medicine is in the clinic -> text mining records. Helping doctors make decisions.

CIKM 2011 Keynote: David Karger

2011-10-25T03:45:00.002-04:00

Creating User Interfaces that Entice People to Manage Better Information
By David Karger (MIT)

History:

HayStack - Per user Information Environments (1999)

Current State of IKM (Information and Knowledge Management)

- We take users with extremely rich landscapes of information and we give them keyboards to barely sketch their interested. Algorithms work really really hard on that sketch.

- We work hard to make computers do IKM well

- People are better than computers at IKM

Question:

- In what ways can we give people the ability to manage more or better information?

- How do we make them want to?

1) Capture more data digitally

2) Collaborate to understand lecture notes

Capture of Information Scraps

- The state of PIM

- The desks all have computers, but we have huge piles of paper (never put into it)

- 27 participants, 5 Orgs, 1 hour in situ interviews

#1 using computer is distracting / impossible

-- people instead just grab random notes to write things down

-- Interfaces for Staying in the Flow (Ben Bederson, Ubiquity 2004

-- (Being "in the zone', in the flow)

#2 chimeras fight between apps

-- Meeting notes with TODOs and follow up meetings

#3 Diverse information forms don't fit apps

Types of information

TODOs, meeting Notes, Name and Contact information

#4 Want in view at right time --workflow integration

Costs to digital capture

- costs: effort to choose place, imposted schema, entry time is a distraction

Fixes: no organization, plain text, in the browser, cross-computer sync offline+online

list.it (open source mico note tool for Firefox.
--> 25,000 downloads, 16,625 registered users, 920 volunteers, 116k contributed notes

Types of notes:
TODOs, Web bookmarks, Concat information
median time to write something is 7.4s
median number of lines is 4

35% - ease/speed
20% simplicity
20% direct replacement for post-its

Detour: Note Science
-- How do people keep and acccess information in list-it?

3 coders
first clustered, identified 4 archetypes

MISC - MIT Open Scrap Corpus (available online)

NB: Classroom Discussion
Stellar Classroom discussion tool
- 50 most active classes made 3275 posts
-- no heavily populated posts
- Nb: forum in context (happen in the margin of lecture notes)
- Highlight a section of the post, write a comments
--> Implicit context (how do I get 3 from 1)

Benefits - Discuss as you read without existing note view
-- Context is clear because the PDF content is there
-- annotations create a heat map of lecture notes

15 classes, 4 different universities
(Annotation required), usage of the tool doubled over the term.
--> they liked seeing that they weren't the only one that was confused.
--> rich interaction

NB specific benefits
--> "Why?"
--> The social benefits outweighted the use of paper

FEEDME
- Artificial Collaborative Filtering

Vast amounts of content, how do we get the good stuff
machine learning recommenders - users rate what they read, content recommendation, collaborative filtering (find people with similar likes, predict what they will like)

Effort
- have to read lots of junk to train system
- have to spend energy now for future benefit
- many users won't ever get started

Quality
- ML algorithms imperfect
- Deliver reading irrelevant content, worry about what is missed

Alternative: People

Email is dominant in information sharing
Median 6 - people do want more relevant links
Sharers are reluctant to spam their friends
(unsure of relevance, may have seen it already, too much effort)

Fixes
-> let them use email, reasssure sender that content is relevant. Aand that the recipient isn't overloaded. One-click sharing

Firefox plugin
1. recoomend recipients to reduce time and effort for sharing
(uses ML to find people to recommend)

One-click thanks

Recommendation Algorithm
-- rochio classifier

Assessment
- two week study for $30
- 60 google reader users recruited on blogs
- Viewed 85k posts, shared 713 posts
- Significant increase in sharing

Recipients were happy - 80.4% of the posts contain novel content

Recommendations Useful

Do overload indicators help
- 1/3 of subjects with them said they were favorite feature
- 30 of shares resulted a thanks

Machine filtering
- have to read stuff

Structured Data
We all know structured data is good.
it supports
-> rich vizualizations, filtering, sorting, queries, merge data

Epicious (old version)
-> filter by ingredient, cuisine, part of meal

Mere mortals just write text or HTML

Structured data takes skill
- design a data model,

Plain authors are left behind
-> less power to communication effectively

Coping: Information Extraction
- Entity Recognition, Coference, relationship extraction

Imperfect, so errors creep in.

Alternative: Give regular people tools that let people author structured data
-> to communicate well

Do we need this? Yes.

Approach
- HTML is the language of the web
- Extend it to talk about data
- Anyone authoring HTML should be able to author data and interactive visualization
- Edit data-html in web, blogs, wikis

(like spreadsheets)

Publishing data is easy, just put a spreadsheet online. rows are items, columns are properties

Data
Items (recipes)
- Each has properties, Title, source magainze, publication date, etc...
- Vizualization - a collection of a view of data items
-- bar chart, sortable list, map, thumbnail set

Bound to peroperties
- sort by property

Facets for filtering information
-> specificy a property, user clicks to select
-> templates -> format per item.
- HTML with "fill in the blanks"

Key primitives of a data page
Data - a spreadsheet

Exhibit javascript library

1800 websites using exhibits
hobby stores, science
(lots of strange hobbyists)
Veggie guide to Glasgow

Not very scalable (fast for < 100 items)

Side effects - the data is out there. (structured data is the side effect)

Wibit
Datapress - data visualization inside the blog
DIDO - WYSIWYG editor

Conclusion
- People are powerful information managers
In each case, it's about giving people the tools to be information managers

Wait, There's more
--> manage structured data by making it look like a spreadsheet
--> Atomate -> help users translate incoming data data into structured data

We work hard to make computers do IKM well,
Don't assume people are passive IK consumers
Give people tools that can encourage active engagement in IKM

All the links are at haystack.csail.mit.edu/blog

Questions:
The success of exhibit came from why HeyStack didn't succeed. It's not the only measure of success that lots of people use a tool. It's still an interesting piece of research.

Twitter Acquires Julpan Real-Time Search Engine

2011-09-21T14:01:00.004-04:00

Today, Julpan (a stealth-mode search engine) announced it is being acquired by Twitter. (see TechCrunch coverage)

There are not a lot of public details, but here are a few.

Julpan is a real-time search engine based in NYC. It focuses on analyzing social and real-time information from news, Twitter, and other sources. It was founded in mid-2010 by Ori Allon. Ori is an Ex-Googler from the search quality team (Google acquired his patented thesis work called Orion, see the Google feature post.).

Sadly, pending the integration with Twitter, the Julpan search products (Newsgrep and LiveBite) are no longer available online.

SIGIR 2011 Best Paper Award

2011-07-26T13:11:00.002-04:00

The SIGIR 2011 best paper awards were announced.

The winner is:

Find It If You Can, A Game for Modeling Different Types of Web Search Success Using Interaction Data

M. Ageev, Q. Guo, D. Lagun, and E. Agichtein

Honorable mention goes to:

Enhanced Results for Web Search

Kevin Haas, Peter Mika, Paul Tarjan and Roi Blanco

See also the notes from the SIGIR 2011 keynote addresses by Qi Lu and ChenXiang Zhai.

SIGIR 2011 Keynote ChenXiang Zhai: Beyond Search: Statistical topic models for text analysis

2011-07-26T12:07:00.002-04:00

ChengXiang Zhai gave the second keynote address at SIGIR 2011 held this week in Beijing.

Here are the notes from my friend and fellow UMass grad student Michael Bendersky (follow him on @bemikelive). Also, be sure to check out his workshop on Query Representation and Understanding.

Be sure to read Michael's notes from Qi Lu's first keynote talk on the Future of the Web & Search.

Beyond Search: Statistical topic models for text analysis

Complex Task Completion Flow
- Multiple Searches → Information Synthesis & Analysis → Task Completion
- Sometimes the process above is iterative

Examples of complex tasks
• What laptop to buy?
• What’s hot in database research?
• What do people say in blogs on a certain topics? How does the topic coverage change over time?
• What people like/dislike about “Da Vinci Code”?
Can we model complex tasks in a general way?
Can we solve them in a unified framework?
How do we bring users into the loop?
Proposed solution – Statistical Topic Models
- Generative model
- Captures language models shifts based on topics
- Language model serves as a convenient topic representation
- Every document has a lot of contextual data (metadata)
o Author
o Communities
o Location
o Author’s occupation
o User labels
Any combination of contextual data can induce partition over the documents
We should make topics depend on context variables
o Text is generated from a contextualized PLSA model
o Fitting such a model enables a wide range of analysis tasks on a document
Applications of contextual topic models
o Social Network Analysis can aid to derive more coherent topic models
o Opinion mining – integration of expert reviews and personal opinions
• Take into account the well-formed and faceted design of expert reviews to impose context on personal opinions, which come from a variety of unstructured sources (blogs, micro-blogs, review sites, comments)
• Derive integrated expert/personal opinions on different aspects
• Infer aspect ratings and weights
Using topic models to go from search engine to analysis engine
o Tasks
• What is a task?
• How is task different from information need/intent?
• How do we help users to express tasks
o What does ranking mean in analysis engine?
o How to evaluate the output of the analysis engine?
o Operators to allow analysis of search results
-- Select, Split, Intersection/Union, Interpret, Rank, Compare
• Operators can be combined, similar to SQL/InQuery languages

SIGIR 2011 Keynote Talk: Qi Lu and The Future of the Web & Search

2011-07-26T11:23:00.003-04:00

Qi Lu, the president of Microsoft's Online Services Division gave the first keynote address at SIGIR 2011 happening this week in Beijing. He laid out Microsoft's vision for the future.

I am in San Francisco at Twitter, but luckily my friend and fellow UMass grad student Michael Bendersky is taking notes (follow him on @bemikelive). Also, be sure to check out his workshop on Query Representation and Understanding.

Future of the Web & Search

Agenda
- Perspective of the web/IT industry
- Future of search
- Role of IR
- Challenges
- Opportunity
The heritage: web of documents
The future:
- Social web - Facebook profiles, like buttons
- Geospatial web: Mobile devices
- Temporal web: Collection of information over time, real-time microblogging
- Application web: Fundamental design of the browser doesn’t support new application models
IT industry of the future
- Devices + cloud services
- Changing the user intent capturing from rigid keyboard/mouse/keywords combination to more natural modalities
• Understanding the natural language
• Voice recognition
- On mobile devices
- In living room products
• Body gestures - Microsoft Kinect
• Image/Audio/Video capturing
Vision: of the future of search
o Empower people with knowledge
o Re-organize the web for search to unlock the full potential of the web
• Better discovery
• More informed decisions
• Easier task completions
Role of IR
o Understanding user intent
o Modeling web of the world
• People/places/things
• Relations
o Task completion & decision making
o Incentive engineering for making people do more things on the web
Challenges
o Measurement, evaluation & self-correction
• Some things are inherently hard to evaluation: objectiveness, design, opinions
• Search results have profound influence on the way people perceive the world
• It is important that they have no inherent bias or skew

o Privacy

o Lack of
• Tools & understanding in existing disciplines
• Training & development if cross-disciplinary talent

o Barriers for academia research
• Access to data
• Computing infrastructure
• Funding
• Not just based on company agenda
• Funding projects based on pure creativity
Opportunities
• Opportunities for key breakthroughs in the areas of
• Serendipitous discovery (e.g. Hunch.com)
• Information theory for the age of the web and social networks
• Science of big data

• Broadening collaborations
• Research
• Development (API/tools)
• Investment (Training & Development)

• Vibrant community

Follow #sigir2011 for more news, although given the censorship in China, the results are very sparse.

Inside ACL: Building Watson DeepQA keynote Address by David Ferrucci

2011-06-21T08:00:00.001-04:00

This morning David Ferrucci gave the Association for Computation Linguistics (ACL) 2011 keynote talk. Michael Bendersky is attending the conference and was very generous to send me his notes on the first keynote talk. Be sure to read his paper, Joint Annotation of Search Queries. Here are his notes from the talk,

Building Watson: An Overview of the DeepQA Project

What’s the difference between playing chess and understanding human language?
- People find chess difficult and natural language easy
- Many non-scientists don’t realize how difficult human language understanding really is
Computers are good at
- Understanding formulas
- Understanding structured query languages
Computers are bad at
- Parsing ambiguous natural language
The system challenges
- Open domain
- Complex language
- High precision
- Accurate confidence – only buzz in when you’re very confident
- High speed
Core technologies
- Deep parsing – using a proprietary IBM technology that has been developed over the last 20 years
- Relation detection
- Multiple parse interpretations
- Multiple query formulations per parse
Co-reference resolution
- The entire research was driven by a single end-to-end metric – how much the proposed solution improves the Jeopardy game
- Some improvements on a single algorithm might be redundant or harmful in the overall solution
Jeopardy is open-domain – not using ontologies that were crafted specifically for Jeopardy
- Using general resources: Wordnet, YAGO
Learning from Reading
- Parsing sentences in the text
- Generalization and Statistical Aggregation
Some questions require decomposition and synthesis
- Using techniques to decompose questions into parts
- Synthesis of answers from different parts
- Helps in answering questions that involve puns/rhyming
Some questions require finding a missing link between concepts
- Using spreading activation to find links
- eg, link between “shirt”, “tv remote”, “telephone” -> buttons
Metrics for performance evaluation
- Plot x- % answered, y – Precision
- Winners clouds – answered at least 50% of the questions, precision 80-92%
- The goal was to get Watson into the winner cloud – achieved and went over the cloud by the Jeopardy game
Great leaps in performance from 2007. In the beginning, breaking even in the game seemed like an accomplishment
Watson is self-contained. Deciding what content to use is very hard – the amount of hardware is limited.
Guidelines
- Specific large hand-crafted methods won’t cut it
- Combining intelligence from diverse methods using machine learning techniques
- Massive Parallelism is a Key Enabler
DeepQA – QA system underlying Watson
- Many components for parsing and multiple answer generation
- Logistic regression to weight the different features and rank the answers
Search systems used: Indri & Lucene. Both were modified to reduce run-time
Work process
- All group members working in the same open space room
- NLP researchers, IR researchers, ML researchers, linguists, statisticians
- 8,000 experiments – all documented with tools that allow analysis by question/algorithm/features
Run-time
- Single CPU time for answering a question – 2 hours
- Scaled out to 3,000 CPU’s – 2-3 seconds
- Enabled by the built-in parallelization of the algorithms

What I find particularly striking is the deep analysis of a contained corpus, particularly the analysis to find various kinds of missing links. The hardware is limited and the corpus is very circumscribed in order to run complex and expensive algorithms - and it results in significant improvements!

How would you develop a system for the real-time web where what's meaningful is constantly in flux?

Ultimately, the true test of DeepQA will be how it generalizes to domains beyond Jeopardy. I hope this is just the beginning for Watson.

Thanks again to Michael for his notes. Look for more highlights from ACL coming soon!

Google Inside Search Event today

2011-06-14T12:56:00.007-04:00

Today is a big press event on search at Google, Inside Search. Be sure to check out the "Evolution of Search" timeline at the bottom of the page.

Check out the new Search Globe, a visualization of worldwide search.

A big theme of the event is:

"Breaking down the barriers to knowledge"
- Make it faster and easier to enter queries across all platforms - especially mobile. Combining voice search and translation across all search platforms.

On Search and Knowledge re-org.

Amit - the classic data hierarchy:

Data

Information

Knowledge

Search has taken an amazing job of taking the billions and billions of pages of data and turning it into information. We are now setting our sights on knowledge - the relationship of things to one another.

You can watch the live stream and Danny Sullivan is live blogging.

More as it develops.

Watch me Compete on MasterChef Season 2 TONIGHT

2011-06-06T18:22:00.003-04:00

Set your DVRs and tune in to the premier of Fox's MasterChef today, Monday, at 8pm. I am competing to be America's next MasterChef! For more on my cooking, read my modernist cooking blog, CookingPhD.

Masterchef is cooking meets American Idol for amateur cooks. I was selected as one of 100 final contestants flown to LA out of 40,000 people that auditioned for the show. Watch me cook my signature dish for Gordon Ramsay, Graham Elliot, and Joe Bastianich.

Here is quick promo video, with me searing my signature smoked duck at 2:11:

A bunch of the cast will be tweeting on #masterchef.

The second part of the premier will air tomorrow, Tuesday at 8pm!

(The episodes should also be on Hulu at some future date)

Jeff, aka @cookingphd

Twitter Releases Search+ Relevance based search

2011-06-01T15:03:00.004-04:00

Today marks a significant milestone for real-time search. The results are now ranked based on relevance instead of purely based on recency. The announcement was made by CEO Jack Dorsey at the All Things D conference earlier today. A key important feature is that the new search incorporates rich media results, as mentioned on their blog announcement,

Not only will it deliver more relevant Tweets when you search for something or click on a trending topic, but it will also show you related photos and videos, right there on the results page. It's never been easier to get a sense of what's happening right now, wherever your curiosity takes you.

Danny Sullivan has an article covering the release and what "relevance" means in the context of real-time search:

Relevance for us today is using a combination of signals, your follower graph, who you follow, who’s following you. Another aspect is just looking at the content itself and the resonance of the content,” Mike Abbott, Twitter’s vice president of engineering.

The Twitter Engineering blog has on the update has more detail on the evolution of Twitter search since the original Summize days. Here is a small excerpt on what is needed to provide personalized relevance and filtering:

Static signals, added at indexing time
Resonance signals, dynamically updated over time
Information about the searcher, provided at search time

The post has more details worth reading on the infrastructure that goes into the search
For more news on twitter search be sure to follow @twittersearch.

Inside Search: New Official Google Search Quality Blog

2011-05-18T18:41:00.003-04:00

Today, Amit Singhal, head of search quality announced the creation of a new Inside Search blog. It is an extension of the, This Week in Search column that highlights new features and product announcements. As Amit writes,

...we got feedback that people wanted their search news and information as it happens, not just weekly. So, we’re starting Inside Search as a place where you can find regular updates on the intricacies of search and our team. We have more engineers working on search than any other product, and each one of us has stories to tell.

I look forward to hearing from a wide variety of voices on the team. With more than 500 improvements last year, it can be difficult to keep up with the changes, it's sometimes useful to have them pointed out more explicitly.

Perhaps it will also lead to a bit more transparency in search ranking and quality at Google. At least there is an official place for voices to speak publicly.

NY Times: The Stanford Facebook App Class

2011-05-07T13:01:00.005-04:00

The NY Times today reports has an article, The Class That Built Apps, and Fortunes. The Stanford FB app class is CS377W: Creating Engaging Facebook Apps. The class was taught by BJ Fogg, David McClure, and Dan Greenberg.

One take away from the class is an important reminder from BJ Fogg,

What smart people do, what engineers tend to do, is overthink and from the beginning we said to do simple things. But, the inclination is to do something fancier, more complicated. What happened over time was that the students teams discovered that over time is that the complicated things never worked, that simple things took off.

It was a hugely popular class, with hundreds of people interested in it. From the NYT article,

Working in teams of three, the 75 students created apps that collectively had 16 million users in just 10 weeks.

A key component of the class is the social aspect of the applications being built. The class is part of the Stanford Persuasive Tech Lab. From the lab's description,

Our lab specializes in persuasion via technology, so this is naturally our focus when studying Facebook. We want to understand the how motivation and influence operate on Facebook.

It was a big experiment in virality. As student Johnny Win describes it,

The hardest part of any project is to find the initial traction that will get you users and engagement and build from there. Rather than building a road to the moon, build the first step.

The students learned important lessons. You need people to use a product you build. It's great to capture attention, but it's more important to do something meaningful. There are enough punch the monkey, hot or not, and similar apps to waste your time on. Create apps that people solve a problem that matters. For example, an application like ReCaptcha that helps to digitize books and fight spam.

The efforts of the Stanford persuasive tech lab have taken on important projects: Health, Peace Dot, and others. I hope that the students were also taught the principles that motivate these projects as part of the app course in addition to how to create popular apps.

From Search to Knowledge at Google

2011-05-07T11:47:00.010-04:00

Techcrunch reports that Search as high-level product group in Google no longer exists. As part of Google's re-org under new CEO Larry Page, the search group has been renamed the "Knowledge Group". Search Engine Land is reporting on the promotion of Alan Eustace from the SVP of Engineering and Research to Google’s Senior Vice President, Knowledge. My understanding is that this represents an expanded view of the products in search. Beyond helping people find information, the group's goals include,

... enhancing people’s understanding and facilitating the creation of knowledge.

Although all the details are not public, it sounds as if Udi Manber leads the engineering team on information products that are not core search. The details are speculation on my part, but his responsibilities may include products like Knol, Freebase, and Aardvark. It might also include some of Google's data management tools: Google Refine, Fusion Tables, and Public Data Explorer.

Does this mean that search is no longer a "core" product at Google? I don't think so. Instead, it indicates an astute awareness that search needs to be tied to other projects that manage information - social QA, Wikipedia-like knowledge bases, structured data, and other information tools.

In the academic world, we should also consider information retrieval in the context of tools and communities that create and share information: digital libraries, NLP, information (and relation) extraction, and the semantic web. These are all inter-connected components of the information processing and knowledge management ecosystem. As Google's re-org to create a "Knowledge" team indicates, these communities need to communicate and coordinate effectively towards a broader vision of helping people find, create, analyze, and share information.

Watch me on Fox's MasterChef USA Season 2

2011-05-04T15:30:00.004-04:00

Fox announced that I am one of the 100 contestants chosen for the new season of MasterChef!

Read the MasterChef announcement on my cooking and recipe blog.

Greplin: Personal Search for the Social Network Era

2011-04-28T09:17:00.009-04:00

Greplin is a cloud search service that indexes your social network and personal information stored in web services. It provides a central hub for searching all your online data. Greplin is a small startup company with six engineers. Instead of building its own cluster, it leverages Amazon EC2 for indexing capacity. The TechCrunch article reports today that:

They’ve now indexed some 1.5 billion documents. And they’re indexing about 30 million new documents per day.

The TechCrunch article exaggerates the scale issue. The more significant scale issues relate to query volume, and the article does not report on those numbers. Furthermore, a large component of the documents Greplin indexes are short FB and Twitter updates. Greplin has more relaxed indexing requirements than real-time search: in the FAQ Greplin says it can take up to 20 minutes or even up to a day to index your documents.

My current Greplin index has approximately 54,000 documents. It has 30k from Gmail, 7k from Facebook, 17k from Twitter, and around 500 from LinkedIn. The basic search functionality seems reasonable enough. It is very snappy with search as you type. The advanced search capabilities are a bit limited. For example, search by date is missing.

Greplin is still in its infancy. The search interface could benefit blending document results from different sources into a more unified result list. For example, see the recent work on "aggregated" and "federated" search [e.g. A Methodology for Evaluating Aggregated Search Results from ECIR 2011]. Furthermore, I would like a faceted search UI to support exploratory search. They could learn a lot by looking at the extensive research on Personal Information Management (PIM) and Desktop search, like Jamie Teevan's research along with Sue Dumais' work on Landmarks and Stuff I've Seen. (For more on PIM - you can also read Jinyoung Kim, one of my labmates).

I have significant reservations concerning my data privacy. Do I trust Greplin with my indexed data? It needs at least partial copies to show snippets of results. At least it claims I can delete my indices for a service at any time. However, it is a very coarse mechanism. There is no version of a robots.txt for my personal data so that I can specify mechanisms for "do not index" or "do not cache" at a granular level.

I have a few invites. If you want to try it out leave a request in the comments.

ECIR 2011 Best Paper Awards and Other Highlights

2011-04-19T16:42:00.009-04:00

First up are the best paper awards which were announced tonight. There were two awards, one for best paper and one for best student paper:

A User-oriented Model for Expert Finding by Smirnova and Balog (best paper)
A Methodology for Evaluating Aggregated Search Results. by Arguello, Diaz, Callan, and Carterette. (best student paper)

The paper Learning Models for Ranking Aggregates by Craig MacDonald and Iadh Ounis was also nominated.

The best poster prize was A novel reranking approach inspired by quantum measurement by Zhao et al. (via Owen Phelan).

An trend at the conference is the handling of ranking and evaluating "aggregate" results, aka "blended" results or "universal search" where results from multiple verticals are blended into a single presentation. In addition to the above two papers, there is:

Smoothing Click Counts for Aggregated Vertical Search by Janwon Seo, et al.

Other trends in the conference appear to be:

Crowd sourcing evaluation (an entire session)
Realtime and Microblog (Twitter) applications (multiple papers across tracks)

The DDR 2011 workshop on diversity in document retrieval also proved popular. The proceedings are available for download. There is a fair bit of discussion on Twitter, #ddr2011.

There are two other papers from UMass that I want to highlight:

SIGIR 2011 Results

2011-04-07T23:25:00.004-04:00

Today, the SIGIR paper acceptance/rejections were sent out. What was your result? Let me know in the comments. What did you think of the review quality? Will there be a new influx of new submissions to online journals for rejected papers?

This year there were 545 papers submitted and 108 were accepted (19.8%). Despite controversy that some papers might not receive oral presentations, all papers will have full presentations.

Instead of complaining about the reviewers of my rejected paper, I would instead like to thank the reviewers for their time and consideration, regardless of the outcome, because writing reviews takes a lot of time and effort.

My congratulations to the accepted authors. I look forward to the papers.

WWW 2011 Day 2: More Workshops and Tutorials

2011-03-29T10:17:00.004-04:00

This is more on the WWW conference in India this week. I'm not attending, but I wanted to point out a few things that caught my attention. Today there are more tutorials and workshops. See also the workshops and tutorials from Day 1.

Workshops

Social Media Engagement (SoME 2011) - It focuses on how to measure user engagement (captivated and motivated to participate) and satisfaction with social media.

SemSearch 2011 - The fourth workshop on Semantic Search. The most interesting aspect of the workshop is the data challenge. What I find most compelling is the manually constructed "List" or "Type" queries that are more complex than the other entity queries. The manually constructed queries utilize the attributes and relationships, which make semantic data unique, e.g. [Japanese-born players who have played in MLB where the British monarch is also head of state].

Tutorials

Social Media Analytics - is being taught by Jure Leskovec from Stanford. The slide materials are available online. Last fall he also taught a related class, Social and Information Network Analysis. He is current teaching a class on Mining Massive Datasets.

Web-Based Open Domain Information Extraction is being presented by Marius Pasca from Google. He will be giving a related tutorial, Web Search Queries as a Corpus at the upcoming ACL conference in Portland.

Latent Variable Models on the Internet - Amr Amhed and Alex Smola are presenting work on using Graphical Models on web data. From the description, we will describe inference algorithms for collaborative filtering, recommendation, latent dirichlet allocation, and advanced clustering models.

Social Recommender Systems - Ido Guy and David Carmel from IBM Research are giving a tutorial on social recommender systems. See also the recent SRS2011 workshop which was also organized by Ido.

WWW 2011 this week

2011-03-28T10:10:00.005-04:00

The WWW 2011 conference is happening this week in Hyderabad India. I'm not attending, so drop me a message or an email with notes or highlights.

Be sure to check out the full program.

Today is Tutorial and Workshop day,

Relevant Tutorials

Ranking on Large-Scale Graphs with Rich Metadata by Bin Gao, Taifeng Wang, and Tie-Yan Liu from MSR Asia.

- For a preview see their tech report, Semi-Supervised Ranking on Very Large Graph with Rich Metadata

Distributed Web Retrieval by Ricardo Baeza Yates from Yahoo! Research Barcelona.

Selected Workshops

USEWOD2011 - 1st International Workshop on Usage Analysis and the Web of Data

This workshop will investigate the synergy between semantics and semantic-web technology on the one hand and analysis and mining of usage data on the other hand.

WICOW/AIRWeb Workshop on Web Quality (WebQuality 2011)

It is encouraging to see a discussion beyond blatant spam to more subtle issues of authority, credibility, and reputation.

Temporal Web Analytics Workshop
TWAW focuses on temporal data analysis along the time dimension for Web data that has been collected over extended time periods.

Stay tuned for more news WWW later this week!

Evgeniy Gabrilovich wins 2010 Karen Spärck Jones Award

2011-03-04T06:00:00.003-05:00

The British Computing Society IRSG announced that the winner of the 2010 Karen Spärck Jones Award goes to Evgeniy Gabrilovich. Evgeniy is Senior Research Scientist and Manager of the NLP & IR Group of Yahoo! Research.

He will present a keynote talk at the upcoming ECIR 2011 conference later this month. His presentation will be Ad Retrieval Systems in vitro and in vivo: Knowledge-Based Approaches to Computational Advertising.

Congratulations Evgeniy! I have heard a lot of great things from Yahoo! Research interns who worked under his guidance.

Google's War on Content Farms: Project Big Panda

2011-03-03T19:24:00.004-05:00

In late February Google launched a significant update to its ranking algorithm to address "shallow content" pages. The change has been referred to as the "Farmer" update externally and internally it is known as "Panda".

Amit Singhal and Matt Cutts posted about the change on the Google blog, Finding more high quality sites in search. It reduced the rankings of "low quality sites" that aggregated content from other websites and didn't add a significant amount value to users. According to the post the update effected 11.8% of queries. They also launched the Chrome Blocklist Extension to let people block websites from their Google results. The O'Reilly Radar published an article with a very good overview of the discussion.

What is behind the change? The most informative article is a recent Wired interview by Stephen Levy, The ‘Panda’ That Hates Farms. It interview Matt Cutts and Amit Singhal who managed the update.

What was the answer? In short, they built a document quality classifier trained on lots of rater data. Here are some of the questions they asked raters from the article:

Would you be comfortable giving this site your credit card?
Would you be comfortable giving medicine prescribed by this site to your kids?
Do you consider this site to be authoritative?
Would it be okay if this was in a magazine?
Does this site have excessive ads?

These questions seem to ask about the authoritativeness and trust of the content on a page. The results were also confirmed by an 84% overlap between sites downgraded in the change and those that people blocked using the Chrome extension, even though it is not used as a feature in update.

How did Google become overrun with almost-spam content? Amit sheds a bit of light on the question in one of his answers:

So we did Caffeine in late 2009. Our index grew so quickly, and we were just crawling at a much faster speed. When that happened, we basically got a lot of good fresh content, and some not so good. The problem had shifted from random gibberish, which the spam team had nicely taken care of, into somewhat more like written prose. But the content was shallow.

The interview then gets bogged down in bigger issues around editorial process and transparency, which are important but not as technically interesting.

HeyStaks launches: Social and Collaborative Web Search App

2011-03-02T09:39:00.004-05:00

Heystaks is a collaborative search startup that launched publicly yesterday at DemoCon. Heystaks has a browser / iPhone app that lets you share your search experiences. It lets you save searches and pages you find into "Staks" and then share them with your "Search Buddies".

VentureBeat has an article covering their launch which you should probably check out. Here is the video from their website:

HeyStaks v4 from HeyStaks on Vimeo.

The chief scientist at the company is Barry Smyth, a professor at the University College Dublin.

It's a bit early for a full review, but I tried it out and it seems promising. I have some privacy concerns about browser toolbars that save and share my search history, especially when the service is oriented towards public sharing of the information.

HeyStaks reminds me of the failed Yahoo! Search Pad, but with a more social focus, and it works across search engines. I hope it has better luck.

I would like to see the service evolve to have more collaboration in the search beyond saving and sharing results. For example some deeper integration that Gene Golovchinsky, Jeremy Pickens, and others have been advocating. See their paper, Algorithmic mediation for collaborative exploratory search which won the best paper award at SIGIR 2008.

My congratulations to Heystaks on the launch. I look forward to Chome and Android apps versions that I hope will be soon to follow.

News Highlights: Bing Price search, Yahoo! Boss, Google Data Publishing, and more

2011-03-02T09:29:00.003-05:00

Here is a round up of news from around the web:

Bing adds price recognition to its query support. You can now search for "digital camera under $200" and it will automatically add the price filter. It is a good step in the right direction. How about something a bit harder? "Canon 12 MP Camera under $200" with the manufacturer and megapixel attribute restrictions.

Google announced the public release of the Dataset Publishing Language (DSPL), a representation language for the data and metadata of datasets.

We created this format to address a key problem in the Public Data Explorer and other, similar tools, namely, that existing data formats don’t provide enough information to support easy yet powerful data exploration by non-technical users.

Yahoo! announced the Yahoo! Search Boss v2.0 API for the new Bing based search.
Congressmen beats Watson in a round of Jeopardy.

Scala tip: Check out REPL for interactive debugging.

WhistlePig: A minimalist real-time search engine

2011-03-01T09:12:00.004-05:00

William Morgan recently announced the release of Whistlepig, a real-time search engine written in C with Ruby bindings. It is now up to release 0.4. Whistlepig is a minimalist in memory search system with ranking by reverse date. You can read William's blog post for his motivations for writing it. Here is a description from the current readme:

Roughly speaking, realtime search means:
- documents are available to to queries immediately after indexing, without any reindexing or index merging;
- later documents are more important than earlier documents.

Whistlepig takes these principles to an extreme.
- It only returns documents in the reverse (LIFO) order to which they were
added, and performs no ranking, reordering, or scoring.
- It only supports incremental indexing. There is no notion of batch indexing or index merging.
- It does not support document deletion or modification (except in the
special case of labels; see below).
- It only supports in-memory indexes.

Features that Whistlepig does provide:
- Incremental indexing. Updates to the index are immediately available to
readers.
- Fielded terms with arbitrary fields.
- A full query language and parser with conjunctions, disjunctions, phrases, negations, grouping, and nesting.
- Labels: arbitrary tokens which can be added to and removed from documents at any point, and incorporated into search queries.
- Early query termination and resumable queries.
- A tiny, <>

Palantir: Next Gen Platform for Information Analysis

2011-02-28T10:59:00.009-05:00

Palantir is a very ambitious ~~new~~ tech company building a high-powered information analysis platform. They currently have products targeted for the government and the financial industries. Their product is a highly specialized enterprise data system to support intelligence and business analysts.

What does Palantir do?

... the most central hard problem that we address in trying to enable the analyst is data modeling, the process of figuring out what data types are relevant to a domain, defining what they represent in the world, and deciding how to represent them in the system. At Palantir we make sure our data model (ontology) is both flexible and dynamic, and that it mirrors the concepts people naturally use when reasoning about the domain.

The platform handles both structured and unstructured information and performs extraction and data integration. See their infrastructure page and white videos for a few more details.

Their data platform handles objects. An Object in their platform has four object components:

- Properties: text object attributes

- Media: images, video, and binary data

- Notes: free text

- Relationships: links between objects

Clients can specialize this generic object to have specific types using their "Dynamic Ontology" tool to define the semantics. Their platform has one fixed schema with 5 tables: object, property, notes, media, and object-object. An object is linked to one or more data sources which is critical for data lineage and access controls.

A key component of the platform is search over the objects. According to their blog, their scenario has two differentiating features from web search:

Realtime indexing and querying – we need information to be available immediately as it changes in the system.
Leak-proof access controls – we need the search engine to help us make sure that we don’t have information leaking across access control boundaries.

They go into more detail on their modifications to Lucene for their use cases in two blog posts, Search with a Twist Part I and Part II. From the comments, it sounds like they are using a custom branch of Lucene 2.4.

Palantir's platform combines data processing over large heterogenous datasets, filtering, mapping, visualization, and search in unique ways to create a compelling toolset. It built an intelligence platform that the Government could not do themselves by recruiting a team of uber-geek talent lured by hip silicon valley panache worthy of James Bond.

Google "Recipe View" Search Disappointing and Dangerous

2011-02-25T11:23:00.013-05:00

Today Google announced Recipe View in a blog post. It is a specialized view of search results restricted to recipes. Recipe View lets you search for recipes without adding text to your query. It searches over recipes from most of the major recipe websites. Google is using semantic data that is marked up using the rich snippets format. I'm very excited by the idea. I want to like it, but I don't. Let me explain.

It is exciting to see structured data being leveraged by Google for recipe search. Exploratory search and faceted metadata offer a lot of potential to improve food search. However, I'm disappointed by Google's incarnation. The biggest feature the interface adds is the ability to restrict the results by whether or not a recipe contains a particular ingredient. I don't think that this is very interesting or useful. Did anyone who really cooks use this? The other facets are similarly lacking in utility. Calories aren't as meaningful as sodium, sugar, and fat content. They could have considered useful facets: chef/publisher, cuisine, vegan/vegetarian, gluten-free, cooking technique, complexity, etc... but they ignored these. Clearly, they didn't put much effort or thought into this revision.

More importantly, I think that Google Recipe View vertical is currently dangerous and detrimental. When activated, it effectively excludes content from blogs and small website publishers. These websites do not use the rich snippet format. Rich snippet markup provides additional metadata, but it should not be required to be included in Recipe View. It is pretty easy to automatically identify whether or not a page contains a recipe using a text classifier and search logs. Personally, I find that content from these websites to often be the most useful and interesting. Until Google fixes this issue, webmasters and publishers should consider if it is worth their effort to adopt.

I would send Google Recipe View back to the kitchen... it's under cooked and lacks seasoning.

Note: I recently started a food blog, which does not use rich snippet markup (yet).

WSDM 2011 - Best paper awards

2011-02-11T13:41:00.004-05:00

Best paper award: Unbiased Offline Evaluation of Contextual bandit based News Article Recommendation Algorithms by Lihong Li, Wei Chu, John Langford and Xaunhui Wang

Best student paper award: Correcting for Missing Data in Information Cascades by Eldar Sadikov, Montserrat Medina, Jure Leskovec and Hector Garcia-Molina

"Bing Dialogue Model"by Harry Shum - Second WSDM 2011 Keynote

2011-02-10T22:55:00.006-05:00

The 2nd keynote talk at WSDM 2011 was an intriguing peak at the Bing's model of user intent, by Harry Shum, VP of Search Product Development, Microsoft.

* Challenges at launch
* Google market share has been steadily growing from 2005-2008 (Bing launch)
* Google is a consumer brand and a habit

* Bing gained 5.1% query traffic share (worldwide) since launch

* 3 elements of Search Quality
1) Relevance

Ranking based on meaning not keywords
Direct answers

2) Speed

Reduce effort to complete tasks
Direct answers
Fewer clicks

3) Ease of Use (User experience)

Intuitive query interface
Relevance is hard

* Demo of Bing features

1) “Quick access” – surfacing customer service phone # for query {delta airline}

2) Enhanced movie results for query that match movie titles )
* Rent, buy, watch online, reviews, posters

3) Microsoft Academic Search
* Faceted interface: filter results by author, venue
* Summary pages for author information
* Academic activity
* Co-author graph
* Disambiguation of author names

4) Summary of important information for queries that match geo-locations
* Weather
* Overview of tourist destinations
* Maps

5) Parsing natural language queries
* Parse the query {flight to Taipei feb 12 returning feb 13} to provide fast access to Bing Travel

6) Music search
* Enhanced results for queries that match musician names
* Preview songs, lyrics, bio

7) Facebook Integration
* Results that were liked by Facebook friends
* Surface Facebook profiles in searches of matching friend names

* Internet searchers are becoming more Task Centric
* Decision Making: 66% people are using search to make decisions
* Top search tasks: Entertainment, Games, Health, Travel, Shopping, Directions,…

* Tasks are becoming more sophisticated
* Longer queries
* Longer sessions

* 10 blue links are no longer sufficient
* Instead there’s a need for organized “Whole Page” experience
* Search Paradigm Shift
* From “hit or miss” model to “dialogue” model
* Understanding query intent
* Incorporating structured data into search results
* Relevance on the session level
* Minimize the effort to complete task

* Bing Dialogue Model (see the image above)

* Four levels of dialogue

1) Query level
* Query auto-completion
* Spelling correction
* Interaction with user in mobile devices with touch screens

2) Document level
* Title, snippet, deep links presentation
* Extended document preview on hover over the result

3) Page level
* Quick Tabs for relevant verticals
* Entity-based result summary
* Algorithmic results
* Related query suggestions
* Search history

4) Session level
* History-aware results comparisons

"Mining Billion-node Graphs: Patterns, Generators and Tools" Christos Faloutsos - First WSDM 2011 Keynote

2011-02-09T22:27:00.005-05:00

Christos Faloutsos, Professor at Dept. of Computer Science, CMU, gave an excellent keynote this morning on pattern mining in large scale graphs. Below is a brief summary of this keynote.

· Why should we care about graphs?

o Internet Map

o Predators network in nature

o Social networks

· Patterns in Graphs

o What is normal/abnormal?

o Which patterns hold in large datasets?

· Types of patterns

o Graphs are *not* uniformly distributed

o Power law in the degree distribution

o Power law in the eigenvalues of the adjacency matrices

o Triangle law. (Triangle is a three node clique in the graph).

§ Power law in the distribution of triangles in graphs

§ #triangles = 1/6*SUM(EV^3) (EV= Eigenvalue of the adjacency matrix of the graphs)

· Can be used to speed up computation over large graphs

o EigenSpokes

§ Principal component analysis shows that many large scale graphs are usually loosely connected tight communities

· Patterns on weighted graphs

o Weights are super linear in the in-degree of the graph

· Time evolution in graphs

o Surprisingly, graph diameter shrinks over time as the graph grows

o NODES(t+1)=2*NODES(t)

o EDGES(t+1) = 1.6*NODES(t+1)

o Node popularity over time (eg. visits to blog posts)

§ Drop off in popularity is power law with exponent 1.6

o Duration of tasks (eg., duration of phone calls)

§ The longer the task has taken so far, the longer it is expected to take in the future

§ Similar to log-logistic distribution in survivability analysis

· Tools for anomaly detection in graphs

o Egonet of the node –neighbors of the node and the edges between them

§ Examining the features of the egonets can be used to detect anomalous nodes

o Belief propagation can be used for fraud detection

· Scalability

o Map-Reduce for graphs

§ PEGASUS – tool for parallelizing computation of various graph characteristics for large graphs (using Hadoop)

· Graph Radius

o 14 for a web graph of 1.4B nodes

o Many loosely connected tight communities

· Connected components

o Giant connected component ~ 1B nodes

o Many disconnected nodes

o Many suspicious connected components (link spam)

WSDM 2011 coverage

2011-02-07T19:02:00.005-05:00

As I am attending WSDM 2011 in Hong Kong to present a paper, I will be taking over Jeff's blog for the next week. Expect posts about invited talks by Christos Faloutsos and Harry Shum, best paper award updates and more.

Comment if you have any wishes or questions.

Michael Bendersky

Forget the Superbowl, Host a Watson Jeopardy Party

2011-01-27T06:13:00.004-05:00

The IBM Watson Jeopardy contest is happening February 14th, 15th ,16th. The time to start planning your party is now!

Buy a Watson Poster now to start advertising.

It will be human vs. machine showdown and costumes are encouraged! Perhaps an stick-on Lemur tattoo might be appropriate.

For food consider:

- Robot 'Chips' - homemade potato chips tossed in herb salt

-"Buzz in" Mousse - A chocolate-coffee mouse with chocolate covered espresso beans

- A jeopardy themed cake with a robot chasing a human (think Bender from Futurama)

- 'Deconstructed' Techno-Style boneless buffalo wings

Leave more suggestions in the comments!

(For some more details on how Watson works read, Building Watson: An Overview of the DeepQA Project - AI Magazine).

Also read Stephen Baker's new book, Final Jeopardy. The eBook is available on Amazon now and the first chapter is free to read. The last chapter will be released after the match.

Sofia-ML and Maui Two Cool Machine Learning and Extraction libraries

2011-01-26T13:03:00.005-05:00

Niranjan recently suggested I check out Sofia-ML as a fast tool for some learning to rank applications. From the description,

The suite of fast incremental algorithms for machine learning (sofia-ml) can be used for training models for classification, regression, ranking, or combined regression and ranking. Several different techniques are available. This release is intended to aid researchers and practitioners who require fast methods for classification and ranking on large, sparse data sets.

It is written in C/C++. One nice feature is that it supports the LETOR feature file format for ranking. They describe some of the algorithms in Large Scale Learning to Rank from NIPS where they presented algorithms for fast learners for approximate SVMs. The Combined Regression and Ranking (CRR) work was presented as a paper at KDD 2010.

The other package I recently discovered was Maui-Indexer. Maui-Indexer is an extension of the KEA key phrase extractor.

... it allows the assignment of topics to documents based on terms from Wikipedia using Wikipedia Miner. Maui also has many new features that help identify topics more accurately.

You can read more about it on the web page and read the publications.

Microsoft Research Spelling Corrector Challenge

2011-01-19T10:56:00.002-05:00

Microsoft is sponsoring the Speller Challange, a competition to create the best search query correction service. The contest started on Monday and will run until May 27th. It appears to be an initiative to spur use of its web n-gram service, which includes query log n-grams.

The training dataset that they provide is based on the TREC Million Query Track. The speller challenge team annotated a sample of the track logs and has it available for download. The dataset contains 5892 queries, 311 mispelled queries, and 1122 queries that have some suggested spelling change. The challenge will be evaluating using the Expected F1 (EF1) score, the harmonic mean of precision and recall.

I am a bit skeptical about the training dataset. First, the number of mispellings is significantly lower than I would expect. It is also quite small. The website appears to offer a place for contestants to share data, the "Team datasets", so it's possible that some teams could annotate a larger dataset. Also, the non-mispelling "suggestions" are not clearly described. I think these need more explaining and differentiation from query reformulations. To put this into more context, here is a very brief overview of query correction.

According to several studies of search queries, approximately 10-15% of search queries contain spelling errors. For example an important paper in the area is Spelling correction as an iterative process that exploits the collective knowledge of web users. Beyond spelling correction, there has been a recent trend towards other types of query reformulations: stemming, substitutions, and query expansion.

If you want an easy way to get started, consider the LingPipe toolkit, which has a tutorial and is offering a special license for the competition. You may also be inspired by Peter Norvig's 21 line spelling corrector in Python.

Seeking Summer Internship Opportunities

2010-12-10T10:00:00.005-05:00

I am beginning to explore internship opportunities for the summer of 2011.

I am an applied researcher whose interests are search in specialized domains and building search tools to solve complex information needs. My experience includes search in the engineering domain, medical search, local business objects, food and recipes, and information extraction on book data. My work often involves processing of large datasets using distributed processing frameworks such as Hadoop and PIG.

I am looking for opportunities that fit with my background and preferably include research that could lead to a publishable paper in a major conference.

If you know of any opportunities that would be appropriate, please contact me via email. My CV is available from my website (Word, PDF).

Several of my fellow PhD students here in the CIIR are also seeking internships, so I would be happy to pass along any appropriate opportunities.

New Book: Mining of Massive Datasets

2010-12-08T17:19:00.003-05:00

Anand Rajaraman and Jeffrey D. Ullman have put together a new ebook, Mining of Massive Datasets. The book builds on the course materials for the Stanford CS345 course "Web Mining" and the CS246 class, Mining Massive Data Sets.

From the ToC, the book covers:

An introduction to data mining
Large-scale processing with distributed file systems and MapReduce
Similarity search: nearest neighbor, minhashing, LSH, etc...
Algorithms for mining streaming data
(Web) Graph analysis: Pagerank, HITS, and spam detection
Frequent Itemset algorithms
Clustering Algorithms
Advertising on the web
Recommendation Systems

It is an interesting blend of material that are not usually taught together. I look forward to examining it in more detail.

Barriers to Entry in Search Getting Lower

2010-12-07T15:47:00.006-05:00

The Mim's Bits column in the MIT Tech Review has an article, You, Too Can Be the Next Google. In the article, Tom Annau, the CTO of blekko (see my previous post) argues that computing power is growing faster than the amount of 'useful' and 'interesting' content on the web.

"Web search is still an application that pushes the boundaries of current computing devices pretty hard," says Annau. But Blekko accomplishes a complete, up-to-the-minute index of the Web with less than 1000 servers...

To be more efficient, they are more careful about what they crawl by:

Avoiding crawling spam and splog content
Using a "split-crawl" strategy that refreshes different genres of content at different rates to ensure that blogs and news are refreshed often.

I'm not sure blekko's "efficiency" techniques are particularly interesting or novel. However, I do think that overall the ability to crawl and index the entire web is getting easier, especially with distributed crawlers (like Bixo).

"Whether we succeed or fail as as startup, it will be true that every year that goes by individual servers will become more and more powerful, and the ability to crawl and index the useful info on the Web will actually become more and more affordable," says Annau.

The recent Mei and Church paper in 2008, Entropy of search logs: how hard is search? with personalization? with backoff?, analyzed a large search engine log to determine the size of this 'interesting' part of the web. They find that they can encode the URLs from search logs using approximately 22 bits, millions of pages. As they say,

Large investments in clusters in the cloud could be wiped out if someone found a way to capture much of the value of billions with a small cache of millions.

In principle, if you knew these pages and had a way of accurately predicting which ones change, then the price of search can be significantly reduced. In the paper, they go on to highlight that a personalized page cache or one based on profiles of similar users offers an even greater opportunity. In short, there is great opportunity for small very personalized verticals.

I think the main reason that blekko needs a modest number of servers is that its query volume is small. One of the key reasons that Google and other web search engines need thousands and thousands of computers is to support very fast query latency for billions of queries per day from hundreds of millions users around the world. To pull this off Google keeps its search index in memory (see Jeff Dean WSDM 2009 keynote).

Google Fixes DecorMyEyes.com Problem

2010-12-01T15:42:00.002-05:00

This afternoon Amit Singhal, from Google Search Quality, wrote a blog post about how Google fixed the recent DecorMyEyes.com fiasco. The store was broken by the NY Times article exposing how a disreputable merchant gained high ranking by being mean to his customers. He gained links and reputation by being written up negatively on many popular and important sites.

What's interesting is Amit's post is the insight into how Google's team approached solving the problem.

1) Only blocking the site would not solve the underlying problem.

2) Sentiment analysis wouldn't solve the problem because reputation was coming from neutral news sites with solid reputations. Google has not yet found a useful way to incorporate sentiment into ranking.

3) Expose the reviews and ratings next to the results, but this would not actually alter the ranking.

Their new secret undisclosed fixed detected the problematic merchant and several hundred other bad apples.

Lectures on User Behavior Modeling and Implicit Feedback from Query Logs

2010-11-30T12:21:00.003-05:00

I am one of the TAs for the graduate IR course at UMass this semester. I recently gave two lectures on modeling user behavior and utilizing implicit user feedback from logs.

User Behavior Modeling. I covered models of information seeking behavior. Then, I went over the Google 3M (micro-, meso-, and macro-) characterizations of interactions. We looked at how we learn about these various levels of interactions through field and lab studies, instrumented panels, and query logs.

Implicit User Feedback. We finished up query log analysis including query classification, applications like disambiguation and trends. Most of the time was spent on interpreting clickthrough and browsing behavior to generate preference and relevance data.

If you want to learn more, a lot of the lectures build on materials from Eugene Agichtein's tutorial on Inferring User Intent at WWW 2010. If you want more detail, their intent project is a good place to start.

Call for participation of Academic IR community in Lucene

2010-11-30T11:27:00.003-05:00

Otis Gospodnetic, a committer on the Lucene project put out a call on the SemaText blog for greater engagement of academia with the open source Solr/Lucene community. In particular, he is seeking ideas for advanced topics that would be worth of a MS/PhD thesis that would be implemented and contributed to the community.

If you have ideas, please add it to the public idea spreadsheet he started. I strongly you to go there and contribute.

Lucene is the most widely used search engine library. If important new academic ideas that improve retrieval get incorporated, the impact would be huge.

However, historically, the Lucene community and academia has been kept very separate. Instead, the research teams have developed their own systems, the fragmentation is apparent if you look at my list of open source search libraries.

Lucene's ranking algorithms are dated and it is inflexible and difficult to change. Because it is so widely adopted, it is hard to modify and extend in radical ways. If academia is going to get involved, some of these issues need to be addressed, and a lot of it is straightforward engineering work that would enable it to be a better research platform.

Susan Dumais CIKM 2010 Keynote: Temporal Dynamics in Information Retrieval

2010-11-04T14:45:00.002-04:00

I am still catching up on a backlog of items from last week.

Here are more of Michael's notes from Susan Dumais' keynote presentation at CIKM 2010 that addressed the impact of time on web search. Gene also has his notes from the presentation.

Change in IR

New documents and queries

Query volume changes seasonally/periodically

Document content changes over time

User interactions change over time (e.g., anchor text, page visits)

Relevant document for query change over time, “Hurricane Earl” (Sept. 2010 vs. before/after)

But -> evaluation corpora is usually static

Digital dynamics are relatively easy to capture, however tools for interacting with information are static (Browsers/search engines)

Characteristics of Web page change

Adar et al. (WSDM, 2009)

Measuring web page change in a large web crawl

33% of web pages changed over a period of 11 weeks

66% of visited pages changed over 5 weeks, 63 changed every hr

Avg. time between changes – 123 hr.

.com pages change more often than .gov,.org

Knot point – the place on the change curve where the page stabilizes over time; Characterizes the way pages change

Term-level changes

Looking at characteristic term for the page and their “staying power”, e.g. “cookbooks” & “ingredients” have a high staying power for allrecipes.com, “barbeque” is more transient

Revisitation Patterns on the Web

60-80% of the pages you visited, you’ve already seen before
4 revisit patterns:

Fast - Navigation within site
Hybrid - High quality fast pages
Medium - Popular homepages/mail & web applications
Slow - Entry pages, bank pages, accessed via search engines

Revisitations & Search (Teevan et al, SIGIR 2007, Tyler et al., WSDM 2010)

Repeat query 33%
Repeat click 39%

Relationships between revisits and change (Adar et al., CHI 2009)
- Monitor change
- Effect change is not related to change
- Change can interfere with re-finding
- The more visitors the page has, the more often it changes
- Three pages: nytimes.com, woot.com, costco.com
  - Similar change patterns, but different revisit patterns:
  - NYT – fast revisit
  - Woot – medium revisit
  - Costco – slow revisit
Diff-IE – Building support for understanding change
- Browser toolbar that highlights content that was changed since the last visit
- Non-intrusive and personalized --- changes that are of interest to you, not to the publisher of the page
- Helps to uncover unexpected important content
- Facilitates serendipitous encounters
- Helps to understand page dynamics
- Will be publicly available later this month from
- http://research.microsoft.com/en-us/projects/diffie/default.aspx
- Research surveys show that Diff-IE drives more revisitation
  - Driving visits to pages that change frequently
Leveraging Temporal Dynamics for IR (Elsas & Dumais, WSDM 2010)
- Use document change rate to set document priors
- Use term longevity to weight terms
- Evaluation using static data
- Ongoing evaluation collection (Understanding Temporal Query Dynamics, to appear in WSDM 2011)

Yahoo! Open Sources S4 Real-Time MapReduce framework

2010-11-03T16:30:00.003-04:00

Today Yahoo! announced the release of a new real-time MapReduce framework written in Java called S4. From the website,

S4 is a general-purpose, distributed, scalable, partially fault-tolerant, pluggable platform that allows programmers to easily develop applications for processing continuous unbounded streams of data.

For more technical details you can read the technical overview or check out the code on github. The example application keeps counts of hash tags in a Twitter stream.

The framework was previously announced at a Y! lab event which discussed processing in Y!'s advertising platform.

Google Open Sources Sawzall

2010-11-03T16:20:00.002-04:00

Google today open sourced sawzall, see the original publication. From its description,

Sawzall is a procedural language developed for parallel analysis of very large data sets (such as logs). It provides protocol buffer handling, regular expression support, string and array manipulation, associative arrays (maps), structured data (tuples), data fingerprinting (64-bit hash values), time values, various utility operations and the usual library functions operating on floating-point and string values. For years Sawzall has been Google's logs processing language of choice and is used for various other data analysis tasks across the company.

Components of Compelling Vertical Search

2010-11-03T12:31:00.010-04:00

In this post, I will discuss key components of successful topic-specific vertical search. I was motivated to write it by the launch of blekko earlier this week.

Blekko is marketing its ability to slice the web up into verticals using slashtags. Blekko's slashtags define a list of hosts or page to focus a search. But, that is not enough to be successful. Search in a vertical needs to provide a significantly different experience from general web search. A compelling vertical search engine has the following key components:

Vertical specific ranking. A focused topic should define and utilize ranking features unique to the vertical. It may as simple as the topical classification score for a page. It often requires applying information extraction to identify meaningful document fields. It should also leverage vertical-specific static rank features. For example, use a technique like topic-specific pagerank, an author/source popularity score, or other features.
Rich results. The result objects should be presented in a way that uses the structured and semantic information from the topic. For example, simple examples of this include presentations that use data from Google Rich Snippets and SearchMonkey. This may include topic-specific metadata like authors, political perspectives, addresses, or aggregated user rating scores.
Faceted UI. A vertical should exploit structured metadata for exploratory search. It should allow you to flexibly combine keyword search and structured attribute restriction to limit the search space by: price, airline, manufacturer, genre, date, etc... See the CHI 2006 tutorial and the relevant section from Marti Hearst's Search UI book on eBay Express.
Domain knowledge. A restricted topical domain should model important relationships between objects and concepts to improve retrieval. For example, it should use a Freebase-like knowledge base of objects and their attributes. In a recipe search engine, it would would model ingredients and relationships such as contains:gluten or is kosher.
Task Modeling. A key benefit of a narrow domain is that it should allow users to accomplish complex tasks more easily. It should provide tools and interfaces to more directly allow users to get things done.

Of course, it needs to keep up with web search engines in ranking, comprehensiveness, and freshness, which are all key components of search quality.

For more of my thoughts on these issues, you can see the slides from my ECIR 2008 Industry Day talk The Challenge of Engineering. Vertical Search.

Overall, creating a compelling vertical experience currently requires a lot of hard work and painstaking curation. It requires a deep understanding of the tasks that users perform. It requires modeling the topic and domain objects in meaningful ways. Combining these elements together is difficult to do well. It is extremely hard to do at the scale of the entire web across all topics.

Blekko Launches: Brings Transparency to Relevance Ranking

2010-11-01T14:19:00.017-04:00

blekko launched its public beta on Monday. blekko is a new web search engine that focuses on creating an open and transparent process around search engine relevance ranking. blekko is attempting to differentiate itself as the open alternative to "closed" search engines and involve greater public participation in the ranking process.

Creating blekko is an impressive feat because they built their own system from the ground up to crawl, index, and rank a multi-billion page search index. This is hard to do well. They have accomplished a lot in short period of time, so I am excited about the changes we'll see as they evolve. I hope that they will take the risks that other search engines can't afford. One of their risky moves is opening up their ranking features.

Open vs. Closed Ranking

Google's "closed policy" is a difficult issue that has garnered significant criticism. For example, at ECIR 2008 in a QA with Amit Singhal, Daniel Tunkelang questioned the need to rely on security through obscurity. (For an updated perspective now that Daniel works at Google read his recent post on Google and Transparency). In response to a EU inquiry, Amit Singhal laid out the underlying philosophy of Google's ranking,

Algorithmically-generated results.
No query left behind.
Keep it simple.

Although Google uses signals from humans in the form of links and click through on search results, it does not actively involve humans in the search process. Blekko is going to be different.

As a first step involving users in ranking, blekko allows users define their own search experience using "slashtags". Founder Rich Skrenta describes this on a recent blog post, on crowdsourcing relevance,

We're starting by letting users define their own vertical search experiences, using a feature we call slashtags. Slashtags let all of the vertical engines that people define on blekko live within the same search box. They also let you do a search and quickly pivot from one vertical to another.

You can contrast Google's philosophy with Blekko's, here are the first 3 of 11 points in Rich Skrenta's post,

Search shall be open
Search results shall involve people
Ranking data shall not be kept secret
...

A philosophy is great, but it doesn't matter if your results suck. Blekko just launched, so let's take a closer look.

Blekko's ranking

I tried blekko and it is a very solid first effort. To experiment, I re-ran a variety of searches from my Google web history. I didn't conduct thorough experiments, but my impression is that the ranking and coverage is very reasonable, but not as good as Google or Bing's. SELand has a more comprehensive review with a side-by-side comparison with Google.

One frustration I encountered using blekko is that slashtags autofired and my query was automatically restricted to a vertical when it was overly restricted. This limited scope led to missing key relevant results and I manually backed off several times to the /web. Slashtags create added complexity which leads to problems.

I'd like to point out a few queries where I found that blekko's relevance particularly stumbled and could improve, [carbonell mmr] and [iron cook northampton]. Neither of these are easy queries. The first is somewhat ambiguous and the second is about a small local event. What I find hopeful with blekko is that I can begin to understand the underlying reason for failure. I clicked on "rank stats" or you can use the /rank tag, e.g. [carbonell mmr /rank]. For each result blekko also provides an "seo" link to see static rank features, http://www.ml.cmu.edu/mlpeople/affiliatedfaculty.html. As an IR researcher I find open access to this feature data very exciting. However, for the average searcher this level of detail is distracting and unnecessary. The "openness" features need to earn their real estate by being actionable, but right now they don't do that.

Instead of cluttering the search UI, I would like to see blekko be more open by providing the data through an API. It would let academics and searchers use this raw material to rerank results in new and novel ways.

On "Crowdsourcing relevance"

Slashtags are operators that can both restrict a search and change its ranking. They currently allow you to sort the results by /relevance or /date. Users can define slashes that tag hosts as relevant to topic. I started a slashtag on information-retrieval. However, restricting a query to a set of hosts using slashtags is a bit like performing surgery with a chainsaw. In the end you are missing key bits. This approach has several problems:

The granularity of hosts is too coarse. The amount of content relevant to a topic could be a single page or section of website.
Recall. A slashtag cannot be mantained by people in real-time and will miss relevant content.
The semantics of a slashtag are not well defined and it is not obvious how to combine them, e.g. a combine a topic slashtag with a /date ranking.

The claim is that slashtags reduce spam by limiting search to a restricted set of trusted websites. However, I don't think that the impact of spam on search results is very compelling. Search engines are quite good at identifying and incorporating implicit user feedback to reduce the impact of irrelevant (spammy) results. There needs to be a more compelling reason.

Using slashtags doesn't address several key issues in crowdsourcing ranking. The first is that they doesn't address the obvious need to involve people in making relevance assessments on the results in a systematic way. Secondly, the core of search ranking is determining what features indicate relevance for a query and how they should be combined. blekko is not currently surfacing a way to change either of those aspects.

It remains to be seen how you could really let users change the relevance in meaningful ways and more importantly, measure the utility to everyone. It may be that academia could play some role in creating and testing features.

Presentation

blekko's "10 blue links" search UI feels outdated. Modern search engines are incorporating rich results into SERPs. The "Universal Search" results blend images, videos, maps, even places and people. I hope that this is an area where we see blekko evolve quickly to catch up.

Overall

I won't be switching to blekko for regular use. I find the level of ranking information and features that they share very exciting and compelling. Because I can see the ranking pieces, it compels me to jump in and help make things better, because I can. However, I question the utility of the information for average users and the ability to deeply engage the public in useful ways to improve ranking.

Slashtags are fun to play with, but are they useful? Slicing the web into groups creates mini vertical search experiences. However, using the tags adds complexity that may not be necessary most of the time. The value offered by the slashtag verticals is quite limited right now. I hope that slashtags will evolve to allow users to do more curation and add more value as blekko matures.

CIKM 2010 Jamie Callan Keynote: Search Engine Support for Software Applications

2010-10-27T15:38:00.005-04:00

I am not at CIKM, but Michael Bendersky sent me his notes from Jamie Callan's keynote address. Gene also gave his writeup on the FXPal Blog.

Jamie Callan: Search Engine Support for Software Applications

Motivation: SE (search engine) as a "language DB"
- Computer Assisted Language Learning
- Q&A
- Read-the-Web
IR typically assumes a "user" is a person
Software applications are a new challenging class of SE users
There are very low expectations from a SE from an application "user" perspective
- E.g., SE's are mostly used for keyword search
Recall-Precision tradeoff avoids SE's from using a highly structured query language (like Indri)
- BOW query - high recall/low precision
- Structured query - low recall/high precision
Motivation II: using rich language/information resources
- Wordnet, Freebase, Dbpedia, ...
- SE's are not very good at using them
Structured queries and documents are well-studied IR topics, but
- Do we really understand them?
- Maybe the basic structures, but not the more advanced ones
Document = structured object
- Metadata:
- Fielded text: title, chapters, sections, references
- Relations to other documents
Example application: REAP Project: Computer Assisted Language Learning
- Find interesting documents/passages for students based on their language level
- Use a structured Indri query language to find relevant documents or document parts
A typical approach to fields
- Exact Boolean match on the attributes
- Can be brittle.
Another type of document structure
- Text annotations in documents (POS, semantic labeling, co-referencing)
- Annotations can be considered to be "small fields"
Problems with retrieval with text annotations
- Annotations are not always 100% accurate / ambiguous
  - Missing annotations
  - Wrong annotation boundaries
  - Conflated annotations: white/JJ house/NN should be white/NP house/NP
- Term weighting in short fields is hard - need to take field length normalization into account.
- Problem of multiple matches: combining evidence from different fields from the same type is not a solved problem.
Relations among documents/entities
- Hyperlinks & RDF
- XML
Relational Retrieval (Lao & Cohen 2010)
- Example for use: journal recommendations, expert finding
- Some parts of metadata are "domain knowledge" --- they really reside outside the documents.
- How to model domain knowledge as an integral part of the documents
Inferred knowledge: Read-the-Web project
- How to integrate the accumulated knowledge in SE's
- Entity search is one example
- General purpose solutions are still in progress.

More CIKM coverage soon.

Ray Ozzie on the future of computing

2010-10-25T20:22:00.005-04:00

Ray Ozzie leaving Microsoft as Chief Architect. In a farewell memo, dawn of a new day, he points to the future,

Instead, to cope with the inherent complexity of a world of devices, a world of websites, and a world of apps & personal data that is spread across myriad devices & websites, a simple conceptual model is taking shape that brings it all together. We’re moving toward a world of 1) cloud-based continuous services that connect us all and do our bidding, and 2) appliance-like connected devices enabling us to interact with those cloud-based services....

It’s the dawn of a new day – the sun having now arisen on a world of continuous services and connected devices.

What does this shift imply for search? We are already seeing growth in mobile search. People are searching more because they have the capability. And these searches tend to be more local in nature because people are more often looking for actionable information now.

One possibility is what Eric Schmidt described as autonomous search. In this model the retrieval system is proactive, responding to queries, but also actively notifying the user due to changes in the environment. The might describe such a system is an "intelligent information agent".

Twitter Launches Lucene Real-Time Search Architecture

2010-10-07T09:33:00.002-04:00

The Twitter Search engineering team announced that they launched a New Twitter search Architecture. The previous system was based on the original Summize search system that Twitter acquired in 2008. The old technology was a MySQL-based system that became difficult to scale. I'm really amazed that they were able to make a MySQL search work for this long.

According to the blog, the new search system was designed to handle over 1,000 TPS (Tweets/sec) and 12,000 QPS (queries/sec) = over 1 billion queries per day . Besides the challenging query volume, the data needs to be available quickly, a tweet needed to be searchable in less than 10 seconds.

They turned to Lucene, a popular open source search library. To meet their latency and query serving requirements they needed to make extensive modifications to Lucene's core,

That’s why we rewrote big parts of the core in-memory data structures, especially the posting lists, while still supporting Lucene’s standard APIs. This allows us to use Lucene’s search layer almost unmodified. Some of the highlights of our changes include:
significantly improved garbage collection performance
lock-free data structures and algorithms
posting lists, that are traversable in reverse order
efficient early query termination

Their post says that these contributions will be rolled into Lucene and the Lucene realtime branch. It is a tantalizing overview and I would really like to see pointers to the details (e.g. JIRA issues).

The main benefit to users is that the new system is much more scalable and can support an index that is twice as large as previous versions which means that you can search for tweets further back in time.

An interesting parallel is that LinkedIn recently released LinkedIn Signal, which is a mashup of Twitter data with LinkedIn social network data for professionals. For details on how that system works, see their Signal Under the Hood post. One of the key components is the Zoie real-time search system built on top of Lucene.

Twitter Talk at UMass: Discovery and Emergence

2010-09-28T14:05:00.008-04:00

Today Abdur, the Chief Scientist at Twitter gave a talk, Discovery and Emergence here at UMass. The talk was interactive with lots of questions. It was similar to the one he presented at SIGIR Social Media Workshop last year. If you read it, be sure to read Jon's comment. Here are a few of my notes from the talk, which focused heavily on the Trending Topics feature.

A few key points to remember. First we have to keep in the forefront:

It's not about the technology, it's how it enriches our lives and makes it better.

The Data
160 Million accounts. 90 million tweets per day. 16.7 gb of tweets. > 1000 tps
200,000 time line rps, 3GBs outbound data, 1 B queries per day

Tweets are searchable within seconds and the data is kept forever.

About 30% of search traffic is generated by clicks from trending topics.

In 1ms answer the following about a tweet:
- what language is this tweet?
- where was this tweet posted from?
- what are the entities in this tweet?

Every X min answer the following:
- Which tweets should you ignore?
- What topics are trending and where?

A key problem is how to evaluate the quality of trending topics. What makes one topic 'better' than another?

One of the coolest things I saw from the talk was the vizualization of the World Cup tweets, which was on their blog, World Cup 2010: A Global Conversation. It was created by Miguel Rios, whose work you can check out on his website.

Abdur ended with an admonition to researchers to think about the impact of their work,

Why does your research matter? Will it make the world a better place?

ECML PKDD 2010 Data Challenge: Measuring Web Data Quality

2010-09-21T12:13:00.003-04:00

Yesterday the ECML PKDD Data Discovery challenge results were presented. See the website for the papers of the winning participants. The winning team used a bagged C4.5 decision tree for learning given the features.

A high level overview of the challenge from the website describe the challenge,

In this year's Discovery Challenge we target at more and different aspects. We want to develop site-level classification for the genre of the web sites (editorial, news, commercial, educational, "deep web", or Web spam and more) as well as their readability, authoritativeness, trustworthiness and neutrality.

The challenge dataset consists of 23M pages from 99K hosts in the .eu domain. Read the assessment guidelines.

The competition involves three tasks, see the full description of tasks. Here is a summary:

1. Classification task (English)

Web Spam
News/Editorial
Commercial
Educational/Research
Discussion
Personal/Leisure
Neutrality: from 3 (normal) to 1 (problematic)
Bias: 1 flags significant problems
Trustiness: from 3 (normal) to 1 (problematic)

2. Quality task (English)
Quality is measured as an aggregate function of genre, trust, factuality and bias and spam has lowest (0) quality

3. Multilingual quality task (German and French)
Same as task 2, but for non-English.

The interesting aspect of the challenge is that it moves away from spam/not spam labels to assessing more complex aspects of the quality of information.

A lesson in defining topic-based communities

2010-09-17T17:26:00.002-04:00

There is a post on the stack overflow blog on how they are managing communities, Merging Season. At the heart of discussion: What is the right size of domain for a topic-based community? They are against one giant community, as they say:

Yahoo! Answers. Monumentally popular, enormous traffic, and containing absolutely no useful information, Yahoo! Answers is actually more of a teenage chat room than a place to get real answers.

They also highlight failed attempts to bring the Ubuntu and Unix community sites together to make a single community. The process of defining a "topical community" reminds me of the problems we have in IR when we define a "topic based vertical" to apply domain knowledge in retrieval. From their blog:

Communities consist of concentric circles. You share more with people in the inner circle than you do with people in the outer circles, but if you were in a strange place, you’d seek out people even from the larger circles. If you’re building a community (or a Stack Exchange site), it’s not immediately obvious which level is going to work...

They are developing rules that use the size and degree of overlap between communities to guide the process. It will be interesting how this plays out and what lessons we can use to apply to IR.

Google Scribe: Autocomplete beyond queries

2010-09-13T13:32:00.005-04:00

Overshadowed by the Google Instant last week, a labs project called Google Scribe was launched. See some information on the help page.

Here is an example what it did with the initial words and accepting all further suggestions:

Jeff Dalton is a researcher at the University of California at Berkeley...

An amusing example. I'm actually quite surprised it autocompleted "researcher" correctly. However, Scribe got the university wrong. It looks like UC Berkeley wins the web popularity contest.

Overall, Scribe appears to be a straightforward application of web n-gram language models covered in an AJAX interface. Some of its mistakes demonstrate the drawbacks of not utilizing long range word dependencies and topical context. Still, an interesting step towards more autocompletion. I think there may be interesting opportunities to improve effectiveness by leveraging custom language models built from my other documents and web history.

AJAX Results as you Type: Google Instant

2010-09-08T13:12:00.009-04:00

Google announced Google Instant on their official blog.

Google Instant - "Search at the speed of thought". Google Instant is results as you type with a new AJAX view of Google's search results. It takes the autocomplete feature a step further and sends the most probable search to the server to fetch the results. A few optimizations to make it possible:

Prioritizing searches - the biggest optimization is to run only the most probable searches.
User state - shortcut in process searches that are obsolete to avoid running all searches to completion
Result caches - improved result caching

Overall, Google claims that instant search saves 2-5 seconds per query. It took some really committed engineers at Google, including Ben Gomes, to make it possible. Kudos!

It is worth noting that many of these ideas have been in the community for awhile. For example, it reminds me of the CompleteSearch system, which has been around since SIGIR 2006. CompleteSearch has some novel prefix based search capability which is still beyond what Google rolled out today.

Autonomous Search: Did you know?

2010-09-07T14:28:00.013-04:00

Eric Schmidt, CEO of Google gave a keynote address at IFA, a consumer electronics show in Germany. The keynote was covered in an article by paidContent. He emphasizes "mobile first" as very important. According to him, the new and most interesting applications are happening on smart phones.

This leads to what Eric describes as "autonomous search",

Ultimately, search is about finding what you want right now and The next step of search is doing this automatically. And so when I'm walking down Berlin and I like history my smart phone is doing searches constantly - did you know? did you know? did you know? This occurred here, this occurred there.

Because it knows who I am, it knows what I care about, and it knows where roughly where I am. This notion of autonomous search, the ability to tell me things I didn't know, but I'm probably very interested in, is the next great stage in search.

See also an earlier interview with Amit Singhal on the Evolution of Search. Many of these future search applications share ground in common with the field of Agent Planning in AI. One company taking an initial step in this direction is Siri (read me previous post on Siri and Darpa's CALO project), a task oriented virtual assistant for your iPhone. You could reframe much of what Eric described as "Intelligent Search". Tom Gruber, the CTO of SIRI, describes some principles from Intelligence at the Interface:

It knows a lot about you.
It understands you in context.
It is proactive.
It gets better with experience.

I think one of the key things that is new in "autonomous" or "intelligent" search is that the system proactively surfaces interesting information to the user and assists the user in performing actions. A key challenge is how to perform rigorous evaluation in such an immature and developing area. The task is a significant departure from some of the more traditional adhoc search tasks and requires a much richer user model.

GraphLab: Beyond MapReduce for Parallel Machine Learning

2010-08-20T12:20:00.003-04:00

A team at the CMU Select Lab recently released a new software package, called GraphLab that provides an alternative to the MapReduce paradigm for developing Machine Learning algorithms. The work is described in the paper,

Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin, and Joseph M. Hellerstein (2010). "GraphLab: A New Parallel Framework for Machine Learning." Conference on Uncertainty in Artificial Intelligence (UAI). (PPT slides)

From the description on the website,

GraphLab provides a similar analog to the Map in the form of an Update Function. The Update Function however, is able to read and modify overlapping sets of data... In addition the update functions can be recursively triggered with one update function spawning the application of update functions to other vertices in the graph enabling dynamic iterative computation...

The GraphLab analog to Reduce is the Sync Operation. The Sync Operation also provides the ability to perform reductions in the background while other computation is running. Like the update function sync operations can look at multiple records simultaneously providing the ability to operate on larger dependent contexts.

Other than the paper, you can read the details page more information.

I need to think about this more.

Yahoo! Labs Interview: Towards Web Object Search

2010-08-11T12:53:00.003-04:00

The Yahoo! Search blog has an interview with Dr. Ben Shahshahani of Y! labs on search. The questions in the interview cover real-time search, the use of social data, and object retrieval.

The interview begins with an introduction that search is moving beyond 10 links to a federated model that that blends objects from different verticals, also known as "Universal Search" by Google. He then continues about the increasing role that structured data is playing on the web. He says,

Now, the other thing that has been happening is an integration of structured data and unstructured data, so structured meaning that there are particular attributes to different entities. We have a pretty active technology and science effort in trying to understand the main object, attributes, and relationships – not just the text on a web page...

Later, he continues the thread when it comes to answering specific user intents,

Once a query comes in, the question is: “what is the intent” or “what are the common intents of the users submitting this query?” To answer that question, we use a variety of ways to understand the query – a lot of the queries are about objects... Objects are things in the real-world. They can be events, a location, a person or a product. Our active effort in understanding attributes and their relationships helps us find out the things you can do with those objects.

The last quote reminded me of the great presentation given by Eugene Agichtein at the Query Representation and Understanding workshop at SIGIR, Inferring User Intent from Interactions with the Search Results. As I recall, Eugene used search logs gathered from toolbar data to analyze different object attributes and tasks associated with different types of objects from the log. However, I don't recall all the details and the slides are not online.

Disclosure: I am an intern at Y! this summer working on object retrieval, so I'm a bit biased.

Quick Links of the Day: Blekko, Silicon Valley History, and I hate your paper, and P!=NP

2010-08-10T03:45:00.003-04:00

Blekko - Daniel has a Blekko preview from the beta. See also Michael Arrington's post on SE Land. From Daniel's post:
Rather, they are a way for users to “spin” their search results using a variety of filters. For example, [climate /liberal] and [climate /conservative] return very different results, because they are restricted to different sets of sites... In addition to providing a set of curated slashtags, Blekko allows users to define their own slashtags by specifying the sets of sites to be included.
This is a very primitive means of creating mini vertical search engines. My first instinct is that slashtags remind me of Rollyo where you can "roll your own" by restricting search to a group of websites.
I Hate Your Paper - an article by New Scientist that looks look at how the reviewing process is broken and some ways that journals are exploring possible reforms. (thank Hany)
A historical perspective on the evolution of Silicon Valley by Russell Jurney
An in case you've been living under a rock, the P != NP proof attempt by HP labs, see #pnp.

NY Times Article: Bing Kicks Google in the Pants

2010-08-02T04:41:00.003-04:00

The NY Times has an article on a new search "cold war" between Bing and Google. I think the article is pretty poorly done. The author paints Bing as an innovative upstart giving Google a "kick in the pants" and forcing it to play catch up. It selectively uses facts to misportray reality for the sake of a good story. The author fails to mentions areas where Google is innovating and Microsoft is playing catch up: mobile search, visual search, real-time search, social search, and others.

On valid point where I think Microsoft has done well is in it's vertical strategy as a means of differentiation. As the article says,

Microsoft has tried to attract people like Mr. Callan by excelling at answering frequently asked questions, like those related to travel, health, shopping, entertainment and local businesses. For example, Bing has flight search and prediction tools that reveal price fluctuations for certain routes, and advises customers whether to buy or wait. Bing Health uses data from sources like the Mayo Clinic and Healthwise...

Recorded Future: Trend and event spotting from real-time news data

2010-07-29T09:48:00.004-04:00

Yesterday Wired featured an article, Google, CIA Invest in ‘Future’ of Web Monitoring. The article stretches the truth a bit when it says that Google is doing business with the CIA. The link is tenuous, that both companies are interested in predictive analytics on news and real-time data. The subject of the article is a small Cambridge based company, Recorded Future. From the article's description,

Recorded Future strips from web pages the people, places and activities they mention. The company examines when and where these events happened (“spatial and temporal analysis”) and the tone of the document (“sentiment analysis”)... Recorded Future maintains an index with more than 100 million events, hosted on Amazon.com servers.

For a more detailed look at what the company is doing, take a look at the white paper published on the company blog, A whitepaper on temporal analytics. You can also read the Predictive Signals blog by Bill Ladd, the Chief Analytic Officer at Recorded Future.

Recorded Future is not alone in this field. For example, the Living Knowledge Project is also working on future prediction of news events from web data.

The people working in this field should be aware of the wealth of previous research analyzing event data in news. For example, the DARPA TIDES program on Topic Detection and Tracking (TDT). See James Allan's book, Topic Detection and Tracking for an overview. You can also look at some of Victor Lavrenko's work, specifically on TDT and AEnalyst for financial market prediction from news.

Quick Links of the Day: KDD Cup, Task Oriented Search, ScalaNLP, SIGIR

2010-07-29T04:13:00.000-04:00

Any of these stories could be a full blog post. But, for now I'll just have to give you a few quick pointers:

SIGIR 2010 Industry day videos - complete videos of all the talks, via Noisy Channel.

ScalaNLP - A new NLP package in Scala from the Berkeley and Stanford NLP teams. Scala is hip new language for NLP that runs inside the JVM. See also the factorie project from UMass's IESL lab.

KDD Cup Challenge Results - This year's competition asked participants to predict student performance on mathematical problems from logs of student interaction with Intelligent Tutoring Systems.

TabCandy - from Matthew Hurst. Create groups of tabs for task-oriented search. Create a "save for later" group of tabs. Share "groups of tabs" across platforms and with your friends - "group browsing".

How Google Builds APIs from Google I/O

Research vs. Reality - Discuss.

KDD 2010 Coverage, Best Paper Awards

2010-07-27T04:00:00.003-04:00

KDD 2010 is being held in Washington D.C. this week. I'm not attending, but everyone can participate because the keynotes are being streamed live. The keynote at 9am EST is from David Jensen from UMass Amherst, giving a talk on Computational Social Science.

Yesterday, was the first day of papers. Two that garnered lots of discussion on Twitter are:

Suggesting Friends Using the Implicit Social Graph

In this paper, we describe the implicit social graph which is formed by users' interactions with contacts and groups of contacts, and which is distinct from explicit social graphs in which users explicitly add other individuals as their "friends".

It won honorable mention in the industry paper category. Look for "Got the wrong Bob" and "Don't forget Bob" features in GMail labs.

Overlapping Experiment Infrastructure: More, Better, Faster Experimentation

In this paper, we describe Google’s overlapping experiment infrastructure that is a key component to solving these problems. In addition, because an experiment infrastructure alone is insufficient, we also discuss the associated tools and educational processes required to use it effectively.

The awards were also announced, see the KDD awards for the full list.

Best Research Paper:
Connecting the Dots Between News Articles

In this paper, we investigate methods for automatically connecting the dots - providing a structured, easy way to navigate within a new topic and discover hidden connections. We focus on the news domain: given two news articles, our system automatically finds a coherent chain linking them together. For example, it can recover the chain of events starting with the decline of home prices (January 2007), and ending with the ongoing health-care debate.

Best Industry/Government Paper
Optimizing Debt Collections Using Constrained Reinforcement Learning

In this paper, we propose and develop a novel approach to the problem of optimally managing the tax, and more generally debt, collections processes at financial institutions...We re port on our experience in an actual deployment of a tax collections optimization system based on the proposed approach, at New York State Department of Taxation and Finance.

SIGIR 2010 Workshops: CrowdSourcing for Search Evaluation

2010-07-27T03:32:00.004-04:00

Last Friday was SIGIR workshop day. First up is the workshop on CrowdSourcing for Search Evaluation. It focuses on using Amazon's Mechanical Turk (MT) and similar service to provide judgments. I did not attend this workshop, but heard positive things from the attendees. The workshop is organized by Matt Lease, Vitor Carvalho, and Emine Yilmaz.

The presentations and papers in the program are available online. Here are a few I want to highlight:

A main highlight was the CrowdFlower keynote:
Better Crowdsourcing through Automated Methods for Quality Control
CrowdFlower provides commercial support for companies performing tasks on Mechanical Turk. Everyone had great things to say about this talk that kept people enthralled even though it was the end of the day; some said it was the best talk of the conference.

The other keynote was:
Design of experiments for crowdsourcing search evaluation: challenges and opportunities by Omar Alonso. Don't miss the slides from Omar's ECIR tutorial. They also had a paper at the workshop,

Detecting Uninteresting Content in Text Streams, which looked at using crowdsourcing to evaluate the 'interestingness' of tweets. They found that most tweets, 57% were not interesting. The found that generally, tweets that contain links tend to be interesting (81% accuracy) and that those without links that were interesting generally contained named entities.

Omar, Gabriella Kazai, and Stefano Mizzaro are working on a book on crowdsourcing that will be published by Springer in 2011.

My labmate, Henry Feild, presented a paper, Logging the Search Self-Efficacy of Amazon Mechanical Turkers.

Be sure to read over the rest of the program, because there are other great papers that I haven't had a chance to feature here.

SIGIR 2010 Industry Day: Being Social: Context-aware and Personalized Info. Access

2010-07-22T10:35:00.004-04:00

Being Social: Research in Context-aware and Personalized Information Access @ Telefonica
Xavier Amatriain, Karen Church and Josep M. Pujol, Telefónica

Context overload

- the device of the future for information seeking is no longer the desktop

- it is mobile: iPad, mobile phone.

- Mobile phones are "personal"

- Mobile users tend to seek "fresh" content

Where is the nearest florist?

-- this is pretty easy

-- where is that raelly cool cocktail bar I went to last month? (harder)

-- What bout discovery?

-- Interesting things close to me? Events?

Can we improve the search and disvery expdeirence of mobile users using social information?

Social Search Browser - SSB

- Karen Church

- iPhone web application + Facebook app

- displacies queries/questions by other users in that location

- users can post and interact with queries from others

SSB was a tool for helping and sharing....

A tool for supporting curiousity... an extension to my social Network

But!

Crowds are not always wise. Predictions based on large datasets that are sparse and noisy.

User feedback is noisy

- you can trust if something is excellent, but not necessary the other way around.

"Trust Us - We're Experts

- "It is really only experts who can reliably account for the decisions"

- The Wisdom of the Few - SIGIR '09

Expert-based CF

An expert = individual that we can trust to have produced thtoughful, consistent, and reliable evaluations (ratings) of items in a given domain.

Working prototypes

- Music recommendations, mobile geo-located recommendations...

Summary

- Sometimes the experts are better than your direct social network.

SIGIR 2010 Industry Day: Lessons and Challenges from Product Search

2010-07-22T09:18:00.005-04:00

Lessons and Challenges from Product Search

Daniel Rose, A9

Different Domains, Different Solutions

- Traditional IR,

- Enterprise search

- Web search

- Product Search

How are the issues different? Let's go back to user goals...

The Goals of Web Search

- Understsanding user goals in web search paper (WWW 2004). Manually clustered queries until they were stable.
- Done at AltaVista in 2003 (not completely representative queries)
- Most product queries fell into other categories

Why do people search on Amazon?

- When they want to buy something?

Even ignoring the non-buying issues..

The Goals of the product Search

- Depends on where you are in the buying funnel.

-- Top: awareness, then Desire, then Interest, finally Action

St. Elmo Lewis, 1898

- Provide the right tools at the right stage in the process.

[roller coaster]

- toys and games

- sort by average customer review

- sort by price (is actually hard: new vs. used, amazon vs. third-party, etc...)

Different Tools for Different Stages

- Product search shows more fluid movement between searching and browsing behavior (relying on faceted metadata)

- Because of the nature of the search task?

- Because of the interfaces?

What Amazon Queries Look Like

- [which old testament book best represent the chronological structure]

- [shipping rates for amazon]

- [long black underbust corset] - still looking

- vs ISBN number -> about to buy it

(mostly one word, most the name of a thing. except "generator")
top 10 across the us
(kindle, kindle fire, skyrim, mw3, sonic generations, cars 2)

queries in frequency deciles, by category
US, books, electronics, apparel
--> very diverse, mispelling, miscategorization, all levels of the buying funnel

Context is King

- Some facets for Dresses vs. Digital Cameras

- The problem of facet selection

- Not a one size fits all UI solution for different facet types

- We can interpret your query in a smarter way: [timberland] boots inside shoes is a brand

- Timberland in music -> Timbaland the band (context dependent spelling correction)

Amazon is a MarketPlace...

- So search must be realtime

-- new products

-- new merchants

-- prices being changed all the time
-- items going in and out of stock all the time

Structured Data: "It's a gift... and a curse"

- Unlike the web search, we know the semantics of different bits of text

- We know what fields are important for customers (e.g. brand)

- A large degree of quality control (less adversarial problems)

- We don't have to do sentiment analysis to know if a review is positive/negative

A Curse

- Search engine needs to have both DBMS-like "right answer" behavior and IR-like "best answer" behavior

- Tradiontional IR mechanisms don't always work well for structured data

-- e.g. naive tf x idf doesn't work well (see BM25F)

What happens when one of the fields is order of magnitudes bigger than others?

-- Search inside the book vs. brand name

- What happens when you don't have all the fields all the time? (missing data)

-- ratings, reviews correlate with user satisfaction, but it may not be there

Search Inside the Book
- how often do you want to surface full-text matches vs. filter them out
- (example query: [byte-aligned compression])

Using Behavioral Data

- Powerful source of information for any search engine

- When is using behavioural data an invasion of privacy (or just plain creep), and when is it better for users?

- Customers of a business seem more comfortable with that business learning from past behavior.

Interpreting Behavioral Signals

Example: Are search result clicks good and bad?

- How many clicks are best?

-- 1: the customer found what their are looking for right away

-- many: comparison shopping and are looking around at multiple items

-- zero: the search result contained all the information necessary

Also, some items are inherently "click attractive", e.g. a book with a sexy cover

- "Why is the web so hard... to evaluate" (from snippet evaluation at Yahoo!) 2004

Evaluating Product Search Relevance

Common argument

-- Customers to to a shopping site to buy stuff

-- if a search engine change leads to customers buying mor stuff, they must have had their search need met more effectively.

-- Therefore, relevance can be measured by how much customers buy.

What's wrong with this argument?

-- besides ignoring the rest of the buying funnel, and that someone is ready to buy.

The A/B Test Mystery

- Compare ranking algorithms A and B

- Assign half of users A and half to B

- And the end the avg. revenue is higher in A than B.

-> algorithm A could be better than B, or Algorithm A could be recommending higher priced items than B

-> Algorithm A could be recommending completely unrelated, but very popular items.

So How to do Evaluation?
- A/B tests, automated metrics, editorial relevance assessments (possibly crowdsourced).
- Use all of them!

Lessons from IR

One idea: Generalizing the buying funnel

- The information seeking funnel

- Wandering: no information seeking goal in mind

- Exploring: have a general goal, but not a plan on achieving

-Seeking: have started to identify info needs that must be satisfied, but needs are open-ended

-Asking: have a very specific information need corresping to a closed class question

- Published in: The information seeking funnel, in Information-seeking support systems workshop 2008.

Summary

- Start thinking about how to meet user needs before user knows she has a need

- Offer different interaction mechanisms for different parts of the information seeking process

- Let type of content influence the way search works

- Design for realtime

- Interpret behavioral data carefully

- Exploit structure when have it

- Exploit context when you have it

(My Thoughts and Questions)
- The world is not only Amazon. What about linking the products to external sources, like consumer reports, dpreview and other sites?
--> Amazon enhanced Wikipedia (e.g. Orson Scott Card)
- Social, how is amazon incorporating social search?
--> delicate balancing act with Facebook and other sources

- Do you try and leverage mentions of products on book review sites? or within other books?
- I recently went to barnes and noble and saw the new Orson Scott Card book, one of my favorite authors. Why didn't Amazon surface that to me? (support for subscribing to authors) Or, "buy the new top picks from this month's Cook's Illustrated"...
- From my perspective, the recommendation quality of Amazon has decreased over time despite more of my data. Does this reflect a shift in emphasis?

Microsoft Releases Learning to Rank Datasets

2010-07-22T06:59:00.004-04:00

Microsoft Research announced that it is releasing a new MS LTR dataset.

We release two large scale datasets for research on learning to rank: MSLR-WEB30k with more than 30,000 queries and a random sampling of it MSLR-WEB10K with 10,000 queries.

136 features have been extracted for each query-url pair.

The dataset is a retired dataset. What makes this quite interesting is that the features have been released. You can see the feature list.

SIGIR 2010 Industry Day: Machine Learning in Search Quality at Yandex

2010-07-22T05:26:00.005-04:00

Machine Learning in Search Quality at Yandex
Ilya Segalovich, Yandex

Russian Search Market

- Yandex has 60+% market share

- It's all about small attention to details about the search

A Yandex overview

- started in 1997

- no 7 search engine in the world by # of queries

- 150 million queries per day

Variety of Markets

- 15 countries with cyrillic alphabet

- 77 regions in Russia

-> different culture, standard of living, average income, for example: Moscow, Magadan

-> large semi-autonomous ethnic groups (tatar, chech, bashkir)

-> neighbouring bilingual markets

Geo-specific queries

- Relevant result sets very significantly across regions and countries

pFound

- a probablistic measure of user satisfaction

- optimization goal at Yandex sinces 2007

- Similar to ERR, Chapelle 2009 --> hopefully someone can fill in the exact formula

- pFound, pBreak, pRel

Geo-specific Ranking

query -> query + user's region

- may need to build a specific formula for countries/region because of the variance and missing/lacking features in some of them.

Alternatives in Regionalization

- separate local indices or unified indx with geo-coded pages

- one query or region specific query

- query based local intent detection vs. results based local intent detection

- single ranking function vs. co-ranking and re-ranking of local results

- train one formula or train many formulas on local pools

Why use MLR?

Machine learning as a conveyor

- Some query classes require specific ranking

- many features

MatrixNet

A learning method

- boosted decision tree, "oblivious" trees.

- optimize for pFound

- solve regression tasks, train classifiers

Complexity of ranking formulas

20 bytes - 2006

14 kb - 2008

220 kb - 2009

120 MB - 2010

A sequence of More and More complex rankers

- pruning with the static rank (static features)

- use of simply dynamic features (such as bm25)

- complex formula that uses all the features available

- potentially up to million of matrices/trees for the very top documents

- see camazoglu, 2010 early exit optimization

Geo-dependent queries: pFound

- a big jump in 2009 in Quality

- 3x more local results than competitors in Russia, than #2 player

Lessons

- MLR is the only to regional search: it provides us the possiblity of tuning many geo-specific models at the same time.

Challenges

Complexity of the models is increasingly rapidly

-> don't fit into memory!

MLR is in its current setting does not fit well to time-specific queries

-> features of the fresh content are very sparse and temporal

Opacity of results of the MLR

- The backside of ML

Number of featuers grows faster than the number of judgments

-> hard to train ranking

Learning from clicks and user behavior is hard

Tens of GB of data per day!

Yandex and IR

- Participation and Support

- Yandex MLR at IR context

SIGIR 2010 Industry Day: Query Understanding at Bing

2010-07-22T04:48:00.008-04:00

Query Understanding at Bing

Jan Pederson

Standard IR assumptions

- Queries are well-formed expressions of intent

- Best effort response to the query as given

Reality: queries contain errors

- 10% of queries are mispelled

- incorrect use of terms (large vocabulary gap)

Users will reformulate

- if results do not meet information need

Reality: If you don't understand what's wrong you can't reformulate. You miss good content and go down dead ends

- Take the query, understand what is being set and modify the query to get better results

Problem Definitions

- Best effort retrieval

-- Find the most relevant results for the user query

-- Query segmentation

-- Stemming and synonym expansion

-- Term deletion

Automated Query Reformulation

- Modify the user query to produce more relevant results for the inferred intent

-- spell correction

-- term deletion

-- This takes more liberty with the user's intent

Spelling correction

Example: blare house

- corrected to "blair house". There is a "recourse link" because the query was changed to back out.

Stemming

- restaurant -> resturants

- sf -> san francisco

Abbreviations

-> un jobs -> united nations (may already be there in anchor text)

- utilize co-click patterns to find un/united nations for that page

- it is especially important for long queries, tail queries

- not so good: federated news results for the query. Is the same query interpretation being used consistently? The news vertical did not perform expansion and there is a problem.

Term Relaxation

[what is a diploid chromosome] -> "what is a" is not important from the SE matching, it introduces noise

[where can I get an iPhone 4] -> where is an important part of the query. Removing "where" misses the whole point of the query

[bowker's test of change tutorial] -> test of symmetry is the correct terminology. How do you know that it is the incorrect terminology? If you relax it to "bowker's test" you get better results

Key Concepts

- Win/Loss ratios

-- wins are queries whose results improve

-- losses are queries whose results degrade

- Related to precision

-- but not all valid reformulations change results

- Pre vs. Post result analysis

-- Query alternatives generated pre-results

-- Blending decisions are post results

Query Evaluation

"Matching" level 0/l1/l2 -> inverted index, matching and ranking. Reduce billions to hundreds of thousands of pages. Much of the loss can occur here because it never made it into the candidate set. Assume that the other layers that use ML, etc... will bubble the correct results to the top.

"Merge" layer L3 -> the blending with multiple queries will be brought together

Federation layer L4 -> top layer coordinating activity

An important component is the query planner in L3 that performs annoation and rewriting.

Matching and Ranking

L0/l1 - 10^10 docs. l0 - boolean set operations, l1- ir score (a linear function over simple features like bm25, simple and fast, but not very accurate)

L2 reranking - 10^5 docs - ML heavily lifting: 1500 features, proximity

L3 reranking - 10^3 - federation and blending

L4 -> 10^1

Learning to rank Using Gradient Descent (for L2 layer)

Query Annotation

NLP Query annotation

- offline analysis

- Think of the annotations as a parse tree

Ambiguity preserving

- multiple interpretations

Backend independent

- shared

Structure and Attributes

- Syntax and semantics (how to handle leaf nodes in the tree)

Query Planning

[{un | "united nations"} jobs] -> l3-merge(l2-rank([un jobs]), l2-rank(["united nations" jobs])

[{un| "united nations"} jobs] -> l3-cascade(threshold, l2-rank([un jobs]), l2-rank(["united nations" jobs])

-- the second is less certain and conditional

Design Considerations

Efficiency

- one user query may generate multiple backend queries that are merged in L3

- Some queries are cheaper than others

-- query reduction can improve performance

Relevance

- L3 merging has maximal information, but is costly

Multiple query plan strategies

- Depending on query analysis confidence

Query Analysis Models

Noisy Channel Model

argmax{P(reqire | query) } = arg max{ P(rewrite)P(query| rewrite)}

-- bayes inversion

- example: spelling

-- languagel model: likelihood of the correction

-- translation model: likelihood of the error occurring

Language Models

Based on Large-scale text mining

-- unigrams and N-grams (to favor common previously seen things, they make sense)

-- Probability of query term sequence

-- favor queries seen before

-- avoid nonsensical combinations

1T n-gram resource

-- see MS ngram work here in SIGIR

Translation Models

- training sets of aligned pairs (mispelling/correction; surface/stemmed)

Query log analysis

-- session reformulation

-- coclick-> associated queries

-- manual annotation

(missed the references, but see: Wei et al, Pang et al., Craswell)

Summary

- 60-70% of queries are reformulated

- Can radically improve results

Trade-off between relevance and efficiency

- rewrites can be costly

- win/loss ratio is the key

Especially important for tail queries

- no metadata to guide matching and ranking

SIGIR 2010 Industry Day: Search Flavours at Google

2010-07-22T03:43:00.011-04:00

Search Flavours: Recent updates and Trends

Yossi Matias

Director of Israel R&D Center, Google

Solution for the search problem: imitate a person

Wish list

- knows everything

- language agnostic

- always up to day

- context sensitive

- understands me

- Good sense of timing

- Good sense of scope

- Smart about interaction

(Suggest answers to questions I didn't ask or didn't ask accurately)

In short, things we expect from people when we interact from experts or friends. This is subtle.

Demo of things

- auto suggest of weather; an intelligent guess at what the user will ask

- flight information for ua 101

- weather in the suggestion

- This is new because the user does not have a chance to finish the question

- How do we understand the feedback when they don't have any feedback (except to maybe stop typing)

- Being local [restaurant] (implicit context)

- world cup (now is a general answer, but a week or two ago it was very different)

- new forms of information: user generated content in real-time, Twitter

- [whale] it turns out there was a whale jumping on the ship

- Google trends shows hot topics

Greater Depth With Real-Time

- Example of an earthquake.

- Two minutes after an earthquake, tweets were surfacing in the results before a formal announcement

How?

-- quick slide showing a chart, which he's not going into

Social Circle Personalization

- someone I know blogs about something or a picture, surface it

Understanding: What does Change mean?

- change = to adjust (adjust the brightness) , or convert, or switch all depending on the context

Paul McCartney Concert

- uploading real-time video from the concert

- A few may be good, but we don't want 300 clips all from the same concert

Web translation

- language agnostic

- NY Times translated into china

- translated search

- automatic captioning (translation of obama speech to add arabic captions)

Search by voice... any Voice

- People are starting to use it.

- How do you do it for any person, any language?

- The combination of voice search and translation is almost like science fiction

- This is a significant technology worth paying attention to

Search by Sight

- Google Goggles

- Mobile is important for contextual understanding (location)

- Phones are starting to take on behavior of smart agents

- 10 or 20 results are not useful on a smart phone, "im feeling lucky" is important

The power of data

- 1.6 billion Internet users

- A billion searches a day on Google worldwide

- He started working in ML and data mining

- From a research perspective there is a massive benefit of working with it

Trendonomics

Timeliness

- how to leverage trends of data, such as user search to derive insights

- Google insights for Search

- Trends over time, location, etc.

- Identify outbreaks of flu: find queries that correlate with CDC reports

- Google could predict the outbreak two weeks ahead of CDC, a heads up of something happening now.

- Nowcasting: forecasting the present based on information from the past

- Hal Varian: Predict economic indicators before they were published by the Govt.

Real Estate

- Using stastical models to provide up to the minute information on where we are on economic indicators for sectors of real-estate.

- It doesn't always work, but it's helpful

2010 World Cup - new Search

- popularity of David Villa, etc...

- South Africa, and sponsors getting attention

Researching Search Trends Time-Series

- Forecasting. Seasonality is a common case. Many queries have strong seasonal components (yearly/ weekly cycles)

- we can use time-series prediction models to forecast

- (e.g. skiing, sports)

- Define notions of how predictable and regular the search queries are

- About half the search queries are predictable in a 12 month ahead forecast with a mean abs prediction err of 12% on average

Health, Food & Drink, and .. are quite seasonal.

- Categories are more predictable than individual queries

Deviation from modeled prediction

- US automative industry, forecasting: august o8 - July 09

- The maintance and parts was ahead of forecast, new sales were below

See papers (a big long list...)

...

What can search predict? many publications by Hal Varian

There is no API, but it is possible to download. They are encouraging collaboration with researchers.

Big themes of the talk:

- real-time is expected ('local'), mobile access

SIGIR 2010 Best Paper Award Winners

2010-07-22T03:04:00.003-04:00

The best paper awards were awarded last night at the banquet.

Best Paper Award

Assessing the Scenic Route: Measuring the Value of Search Trails in Web Logs, R. White, J. Huang

In this paper, we present a log-based study estimating the user value of trail following. We compare the relevance, topic coverage, topic diversity, novelty, and utility of full trails over that provided by sub-trails, trail origins (landing pages), and trail destinations (pages where trails end). Our findings demonstrate significant value to users in following trails, especially for certain query types. The findings have implications for the design of search systems, including trail recommendation systems that display trails on search result pages.

Best Student Paper

A comparison of general vs personalized affective models for the prediction of topical relevance, I. Arapakis, K. Athanasakos, J. Jose

The main goal is to determine whether the behavioural differences of users have an impact on the models' ability to determine topical relevance and if, by personalising them, we can improve their accuracy. For modelling relevance we extract a set of features from the facial expression data and classify them using Support Vector Machines. Our initial evaluation indicates that accounting for individual differences and applying personalisation introduces, in most cases, a noticeable improvement in the models' performance.

SIGIR Industry Day: Baidu on Future Search

2010-07-22T03:03:00.011-04:00

Future Search: From Information Retrieval to Information Enabled Commerce

William Chang, Baidu

Two commerce revolutions

- 1995 the first web search engines (ebay, amazon, etc...)

- China miracle

Early History of IEC

- Early shippers: created corporations, but more important there is a futures market

- Commerce: coming together to trade: trading goods and information

- Local: Yellow pages created in 1886

- Local classified ads in papers

- Mail order: Sears catalogue in 1888 for farming supplies (enabled by efficient postal service)

- Credit cards: consumer production and data mining

- Development of "advertising science": print, radio, tv

I.E.C in our Daily Lives

- Restaurant menus

- Zagat, Michelin

- Shopping guides, supermarket aisles

Technology and Internet

- Walmart: real-time transaction tracking and inventory management; scale and speed

- Amazon: user generated reviews and recommendations, common business platform

- eBay

- Craigslist

Search Engines

- Y! Directory

- Lycos Crawler, Altavista big index, Excite HotBot

- Infoseek (1996-1999) where he worked

- OR queries

- Phrase inference and query rewriting

- Banner ads tied to search keywords

- real-time addurl

- anti-spam (adversarial IR)

- hyperlink voting and anchor text indexing

- log analysis and query suggestion

- Goto.com / Overture paid placement

- Google ad platform: AdWord, AdSense

Search as Media

Working 'defintion of a media company (1997)

A media company's business is to help other businesses build brands, and a brand is the total loyalty of the company's customers. A "new media company" does this by leveraging the interactive nature of the Internet to enable users to communicate with one another..."

China Economics

China Background

- reality: only 15% of Internet users earn 5000/year

- inflation at 5% spurts of hyper-inflation

- education and personal aspiration: virtually no illiteracy, but there is a problem with brain drain (about a million of the best and brightest left and never came back)

- competition is fierce in school and in work

- gender equality: one child policy

- entrepreneurial spirit

The Economy

- GDP is growing 10% annually

- Despite a tradition of honoring "old brands" there are few new domestic brands and little marketing know-how

- Domestic commerice is still nascent, lacking IEC tools (no yellow pages or directories that work)

The Prize

- Highly developed Internet in user and usage count: 420 million users, 85% broadband, the average spends 20/week on the internet

- Sitra (sp?) the expedia of China

- Micropayments are made via phone bills: even children use it to buy games online

The Money

- Half the Internet population is under 25

- Tencent QQ is an IM used by everyone, virtual currency, with real economics

- Online games: Shanda, Giant etc:

- Taobao/Alibaba already 1% of GDP, dominates B2C goods

- Baidu web search dominates B2C services (health, education... help on cramming)

- China mobile: everyone uses it, and for almost everything

- Ctrip: integration of online, mobile, offline services

Baidu

- Aladdain: Open Search Platform (allows webmasters to submit query and content pairs)

-- rich results that form an application

- iKnow (2005) an open Q&A platform: the largest in the world

-- has many partner websites, all with a Q&A panel on their website

- Ark: Open product database

- Map++ (embed yellow page like information on a map)

Baidu Aladdin:
Travel

- On the result page, there is a full panel with airline reservation

Housingr, Shopping

A few more ideas:

- The average chinese worker spends 2-3 hours per day on public transportation. They spend the time playing games or reading "new literature". This is an opportunity for mobile shopping recommendation

- Shopping malls are almost impossible to navigate. There are no directories or ways to find things

Conclusions

- Depends critically on information quality and security: spam

- Users demand quality, but there are still not solid reliable brands

- There are new novel business models to explore: a trillion dollar opportunity

SIGIR 2010 Keynote: Donna Harman on Cranfield Paradigm

2010-07-21T03:08:00.014-04:00

Is the Cranfield Paradigm Outdated?
by Donna Harman, NIST

Cranfield 1 - (1958 - 1960?)

- Missed most of this due to a late bus.

Cranfield 2 - 1962-1966

Goal: learn what makes a good descriptor

new user model: researcher wanting all documents relevant to their question

Documents: 1400 recent Papers in aeronautical engineering

Questions gathered from authors of the papers, asking for the basic problem the paper addressed and also supplemental questions that could have been put to an information services

Full relevance assessments at 5 levels

- complete answer to a question

- high degree of relevance... necessary for the work

- useful as background

- minimal interest, historical interest only

- no interest

Hundreds of manual experiments using different combination of the index terms specificicity, etc., etc.

Metrics used were recall ration and precision ratio (set retrieval)

The results said we could just use the words in the document (used title and abstract)

Cranfield paradigm (defined)

- Faithfully model a real user application, in this case searching appropriate abstractions with real questions

- have enough documents and queries to allow significant testing on results

- building the collection before the experiments in order to prevent human bias and enable re-usability

- define a metric that reflects real user

Continuation in SMART project

- Mike Keen spent time at Cornell working on new collections

- (a description of SMART Test Collections)

- They found there was only a 30% agreement between questioners and assessors, but there was no significant difference in how the systems ranked.

Continuation in TREC

- In 1990 DARPA asked NIST to build a new test collection for the TIPSTER project

- User model: intelligence analysts

- large numbers of newspaper articles

- TIPSTER Disk 1 and 2 (mixed short and long documents to force people to focus on length normalization and scale up to full-text from abstracts)

- Topics 1-50 were training topics. Topics 51-100 were created by one person

Relevance Judgments

- Used pooling (took the top 100 docs from each run).

Overlap for 8 years of Adhoc

- The queries from Trec-1 to Trec-8 got progressively narrower with few relevant documents

What is relelvant?

- Back to the user model

- A document is relelvant if you would use it in a report in some manner

- This means that even if only one sentence is useful, the document is relevant

- "Duplicates" also relevant as it would be very difficult to define and remove these

How complete is the relevant set? (Tipster)

- some relevant documents are not in pools

- But, lack of bias in pools is crucial so that systems that don't contribute to the pool can be fairly judged

Other Relevancy issues (Tipster)

- Relevancy is time and user dependent

- learning issues, novelty issues

- user profiles issues such as prior knowledge, reason for doing search, etc...

- TREC picked the broadest definition of relevancy for several reasons

- it fit the user model well

- it was well-defined and thus likely to be followed

- thousands of documents must be judged quickly (300 documents per hour)

- (Keep these lessons in mind when using Mechanical Turk)

TREC Genomics Track

- User Model: medical researchers working with MDELINE and full-text journals

Topics: Started with a user survey looking for questions

- Included topics based on 4 generic topic type templates and instantiated from real user requests

System response

- ranked list of up to 1000 passages (pieces of paragraphs)

TREC Legal Track

- Very dependent on user model. It is modeled after actual legal discovery practice with topics and relevance judgments don by lawyers

- Documents: 7 millions messy XML records on tobacco

- Topics: hypothetical complaints

- Relevance judgments: from pool created by sampling

- Metrics: set retrieval, F @ k

Others: NTCIR, ImageCLEF, INEX - the requirements are all determined by the user model

TREC Web Tracks

- Initially used ad hoc user model, just scaled up to 100 GB

- Then scaled to 426 gigabytes

- judgments unlikely to be complete

- possible bias in relevant documents

Cranfield Paradigm outdated??

- Faithfully model a real user application

- However, we need to think outside the current implementations of Cranfield paradigm to find new user models for the web

User Tasks and Types

- Trec-6, Allan et al. on ranked linked vs. vizualization

- Bhavnani, TREC 2001: med librarians a and cs studnets

- White, Dumais, and Teevan: Large-scale log studies looking at how domain experts search such as vocabularly, resources, et...

- Alonso and Mizzaro SIGIR '09 -- Interesting results on what users find important qualities of result sets

- Lin & Smucker, SIGIR '09: PubMed study

- Using logs to determine goals: Rose and Levinson, WWW 2004 manually classified search goals from the Y! logs

- Others...

- Guo, White, Dumai, Wang & Anderson at RIAO 2010: predicting query performance based on user interaction features

Diversity study using logs

Clough, et al. SIGIR '09 poster, work in WSCD '09 to study diversity, ambiguity in MS log

- Size of wikipedia article on the topic and query reformulations indicated diversity

Bendersky & Croft WSCD'09 - work on describing long queries.

How can we apply these lessons?

Ad hoc experiments must continue

- There are many different access needs that are basically traditional ad hoc retrieval; specific tasks, long queries, etc...

- Scores in Robust, etc. still not good. We know that there are "easy" things that could be done to improve results significantly: you need to be better at term weighting, stemming, needs relevance feedback, etc...

- However, we need to think more about other information access methods, especially on the web/mobile phone, etc.

ClueWeb 09

- If we are going to do "ad hoc" retrieval, where can we enough "enough" of the "right" topics?

- How do we get relevance judgments; is it possible to sample and still have "reusable"?

- Is reusable important; how do we reconcile the fact that users nly look at the top (the web user model) with the reusability of a collection?

- search engines only judges the very top

What else should we look at in web track?, Specific subsets of the web.

Retrofit TREC etc. collections

User Simulation

- Lin & Smucker suggested hat Cranfield is only one model for user simulation; that new test collections could be built for other user models

- We have log studies, plus examples of feature tables from log studies to provide some reality

Cranfield Paradigm not outdated

- We still need to work on ad hoc!

- But, we have to look at new web user models

-- focus on specific web queries where we can contribute (e.g. not 'britney spears')

- We also need to think outside the ranked list mindset; surely that is not all there is!!

Amit Singhal on the Evolution of Search: Searching without Searches

2010-07-20T08:34:00.003-04:00

Engadget has an article covering a presentation (no details provided) given by Amit Singhal on the evolution of search. Most of the interview outlines the evolution of search towards multimedia, real-time search, etc... Most of it has been well covered in the past. One interesting note is that Amit outlines his vision for one possible future direction of search.

Your phone knows about your shopping needs because they're in your to-do list and it knows about your meetings because they're in your schedule. All it needs is your location (which, of course, it has) and some local area information, and it'll ping out a message advising you that you can just pop down the road, buy that wooden stick, and be back in time for your 2PM with Marty from the Synergy Department.

The search engine detected an implicit information need from your to do list that it could satisfy efficiently. It's still a distant dream.

SIGIR 2010 Keynote Address: Refactoring Search by Gary Flake

2010-07-20T03:29:00.014-04:00

SIGIR 2010 coverage is starting. You can also follow the coverage on Twitter, #sigir2010. Here are the raw notes from the first keynote address.

Refactoring Search by Gary Flake
- aka Zoomable UIs, IR, and the Uncanny Valley

- Bing search meets Pivot.

DeepZoom Seadragon demo

- 50 gigs of scans of the seattle intelligencer, 600 dpi

- a proof of concept.

Microsoft Pivot

- take raw data; combine it with metadata for faceted navigation

- A look at Census data on death. A very novel way of navigating the dataset

- Between search and browsing.

Web Search Retrospective

What's worked well:

- instant answers

- spell correction

- vertical tabs

- query suggestions

- query completion

- grouping results

- The biggest improvement is in overall index scale

- Some improvement in core relevance

- But, this list is actually pretty modest

What hasn't worked as well

- Natural language queries

- richer representations for results

- richer presentation for one result

- clustering (visual or otherwise)

A lack of fluidity is part of the problem

Grokker (RIP, 2009)

- The sexiest search experience that no one was going use.

Instead of discreet shifts from one query to the next, can we make it a more fluid interactive process.

Uncanny Valley

- As you increase the sophistication it becomes mre pleasing until it becomes "too real" and then they feel like zombies.

Discrete vs. Continuous Interactions

CGI: stick figures -> The Simpsons -> Toy Story -> Polar Express -> Avatar

UIs: text terminal -> web 1.0 -> Rich client -> over ambitious ajax -> Good Zoomable UIs

Search: Grep -> Altavista -> present day search engines -> Grokker -> ???

Surpassing the unvacnny valley is exceedingly difficult because it requires excellence in science, technology, and.

Our dilemmas

- We are already familiar with the dilemma of precision and recall.

- There exists a similar dilemma around scale, fluidity, and complexity.

Zoomable UIs and Similarities to IR

DoopZoom items

* each tile is an image file

* each level is a set of image files in a folder

* each pyramid is a set of folders with image tiles for each level

DoopZoom collections

* thumbnails are packed onto shared tiles

* loading 100s of images requires loading few tiles.
* very simple: hierarchical file structure with XML description and metadata (no db)

- The fidelity of the experience is independent from the size of the object.

- The trick on the back end is to build the pyramid on the backend

The net outcome is that the user feels in control. "It's like having super human powers" to change levels of

Why user control is essential

- they feel empowered to explore

- Actions are more clearly invertible

Lessons from ZUIs to apply to IR

- Preprocess on the backend

- Assume the front end can do a lot

- Build UI around continuous interactions

- Use asynchronous I/O between endpoints

- Use the two in combination to reinforce one another (left versus right brain)

Higher level goals

- Turn the present discrete mode of interaction of search into a continous dialogue

- Support fluid interactions that are powerful, informative, and fun

- Scale to thousands of items within the user / client interactions

The biggest challenge is in dynamic generation of collections on the backend

Server-side IR problems

- ranking, facet determinations

- cleaning / augmenting bipartite graph

Pivot + search architecture

- Uses the Bing API + thumbnail cache to use Pivot to explore search results

- The UI supports a novel way of analysing a larger corpus of pages across multiple queries.

-- e.g. dpreview.com is prominent across multiple different queries about camera reviews

First: do no harm

- Linear order must be obvious

- First result or instance answer is prominent

- First 4 or so items are easily visible

- Preserve title / url / description format

Next modestly improve

- handle more results: > 50

- basic n-gram extraction

...

Not done

- Documents classes as facets

- Document similarity as synthestic facets

- Folksonomies and community tags

- Federation and verticals

Viciious cycle of the web

- easy to create -> more people create

- More stuff created - harder to find good stuff

....

What's the cure?

We desperately need a mode of interaction where the whole of the data is greater than the sume of the parts.

Wisdom > knowledge > information > data

Q&A

- For facets: word frequency with stop words from abstracts and titles (with just a little cleanup)

Headed to SIGIR 2010

2010-07-19T04:57:00.002-04:00

I'm leaving for Geneva today to attend SIGIR. I look forward to seeing you there! I will be live-blogging the keynote talks (subject to WiFi availability) and providing other coverage. I will also be tweeting.

Today is tutorial day. The main talks start tomorrow. To get started, here are the best paper nominees from the website.

A comparison of general vs personalized affective models for the prediction of topical relevance, I. Arapakis, K. Athanasakos, J. Jose
Assessing the Scenic Route: Measuring the Value of Search Trails in Web Logs, R. White, J. Huang
Caching Search Engine Results over Incremental Indices, F. Junqueira, R. Blanco, E. Bortnikov, R. Lempel, L. Telloli, H. Zaragoza
Comparing the Sensitivity of Information Retrieval Metrics, F. Radlinski, N. Craswell
Extending Average Precision to Graded Relevance Judgments, S. Robertson, E. Kanoulas, E. Yilmaz
Information Based Model for ad hoc information retrieval, S. Clinchant, E. Gaussier
Multi-style language model for web scale information retrieval, K. Wang, J. Gao, X. Li
Properties of Optimally Weighted Data Fusion in CBMIR, P. Wilkins, A. Smeaton

The Impact of TREC and its Future Directions

2010-07-16T09:40:00.005-04:00

This week NIST released a report on the Economic Impact Assessment of TREC.

In section 6 they report the results of a survey where stakeholders were asked to rate the importance of the different TREC tracks. The most important tracks were Adhoc Track with 77% rating it very important and the Web Track with 74%. Other highly rated tracks were the TrecVid and Q&A tracks. In contrast, the Spam Track (mainly email) and Speech track were ranked at the bottom.

Here are few highlights from the conclusion. In monetary terms:

As described in Section 6, $16 million of discounted investments have made by NIST and others in TREC have resulted in $81 million in discounted extrapolated benefits or a net present value of $65 million.

The report continues to say that the same rate of benefit may not continue because much of the growth happened in the late 90s with the rapid expansion of the PC and the use of the Web.

The other main section I found interesting was the possible future directions:

Several trends in survey responses emerged; 37 respondents indicated that TREC should expand into new tracks, 20 said TREC should develop new evaluation methods, and 17 said TREC should develop new data sets. Common suggestions were the following:
Focus on more user behavior data (e.g., social data, Twitter, geographically based) to improve on the Interactive track.
Continue to look at multimedia search techniques (e.g., pictures, video).
Expand into more focused search areas (e.g., chemistry, drug design, evidence-based medicine).
More broadly, several respondents suggested that TREC should work with industry to increase their participation in the TREC workshops, as well as to solicit data that they might allow the TREC audience to use, thus increasing the usefulness of TREC results...

Google Funds Digital Classics Research on Google Books

2010-07-14T07:34:00.003-04:00

Today Google announced that is providing almost 1 million dollars to researchers working on projects in the digital humanities.

The first award winners are listed in the blog entry. In particular I want to highlight Gregory Crane's award on classics. They previously worked to release a collection of high quality scans for 500 important classics works which are available for download.

Also, congratulations to David Mimno from UMass with David Blei for , The Open Encyclopedia of Classical Sites.

SELand Interview with Johanna Wright from Google on Directions in Search

2010-07-09T09:40:00.005-04:00

SELand has an interview with Johanna Wright, Google’s Product Management Director for Web Search. While I think some of the questions were marginally interesting, one part of the interview caught my attention:

...users are finding things like event dates and locations right in their search results—information that someone could “use” to go to an event. With more recent innovations like our updated answers feature, we’ve moving beyond ranking webpages to actually extract and understand structured information from across the web. Do a search today for [barack obama birthday] and you don’t just get a website, you get the answer, sourced from across the web.

It is interesting to see the emphasis on exploiting structured and semantic data in search. However, overall there is really nothing new in the interviw. It's mostly a rehash of the company line on previous product rollouts related to Universal Search, real-time search, etc...

Google gets into Travel: ITA Acquisition

2010-07-05T11:51:00.001-04:00

I use ITA software quite regularly when planning trips. However, it caught me by surprise when Google announced late last week that it was buying them. The acquisition was announced on the Google blog.

Google is trying to make travel easier. From the post:

... finding the right flight at the best price is a frustrating experience; pricing and availability change constantly, and even a simple two city itinerary involves literally thousands of different options. We’d like to make that search much easier... Once we’ve completed our acquisition of ITA, we’ll work on creating new flight search tools that will make it easier for you to search for flights, compare flight options and prices and get you quickly to a site where you can buy your ticket.

Google Scholar and Microsoft Academic Search Updates

2010-07-02T03:53:00.003-04:00

Google Scholar announced yesterday a new feature to allow search within a citing articles.

Microsoft has also re-released the Microsoft Academic Search from MSR Asia. The MAS search has a faceted search interface which allows filtering by author, conference, and journal. In addition, it goes beyond searching papers by providing a page for each author. This is quite useful and it has interesting visualizations to show citations over time and connections to other authors.

It's great to see improvements in this area. Scholarly research is still far too difficult and we have a long way to go in making the search tools more capable.

2010 Hadoop Summit

2010-07-01T10:31:00.001-04:00

Yesterday was the 2010 Y! Hadoop Summit. Be sure to read Ryan Rosario's coverage. Many of presentation talks are linked from the Agenda page and via the YDN slideshare channel. I'll highlight a few presentations that caught my attention:

XXL Graph Algorithms - by Sergei Vassilvitskii Connected component analysis in large graphs

Mining Billion-node Graphs: Patterns, Generators and Tools - Jimmy Lin's presentation on experience computing PageRank on a section from the ClueWeb09 web graph.

Hopefully, the morning talks will also be made available online.

Eclipse Helios Release - Improved C++ and Web tools

2010-06-30T05:44:00.004-04:00

Every June we look forward to a new version of Eclipse. Earlier this month we had the release of, Eclipse 3.6 aka Helios.

Get started with a tour from IBM developerworks. A few participating plugins worth highlighting:

EGit - an Eclipse plugin for the GIT version control system.

Linux Tools - A full featured C and C++ IDE building on the older CDT development toolkit.

Javascript Development Tools - Updated and improved javascript development and debugging

ICML 2010 and Yahoo! Learning to Rank Workshop

2010-06-29T06:24:00.006-04:00

Last week was ICML 2010 in Haifa. You can read the Hal's coverage on NLPers. The conference also had two workshops of note, the Yahoo! Learning to Rank Workshop and the Machine Learning Open Source Software (mloss) workshop. I'm going to focus mainly on the LTR workshop, but be sure to check out the mloss site for more details.

One highlight of YLTR was Chris Burges' MSR team winning track 1 with LambdaMART. They given an overview of their method in a recent tech report:

From RankNet to LambdaRank to LambdaMART: An Overview

LambdaMART is the boosted tree version of LambdaRank, which is based on RankNet. RankNet, LambdaRank, and LambdaMART have proven to be very successful algorithms for solving real world ranking problems: for example an ensemble of LambdaMART rankers won Track 1 of the recent Yahoo! Learning To Rank Challenge.

The other winning teams were from the Russian search company, Yandex. See the company blog post on the topic (via Google translate). You can also read the presentations from the top leaders:

BagBoo: Bagging the Gradient Boosting by Dmitry Pavlov and Cliff Brunk
YetiRank: Everybody Lies by Andrey Gulin and Igor Kuralenok
I find YetiRank particularly interesting because they show that modeling error and uncertainty in relevance judgments can improve model effectiveness.

The two teams' methods are related to those used by Yandex for it's ranking.

Google Indexing gets high on Caffeine

2010-06-09T04:20:00.003-04:00

Last August, I wrote about Google testing the new Caffeine infrastructure. Today, Carrie Grimes announced on their blog that the new indexing system is complete.

Caffeine provides 50 percent fresher results for web searches than our last index... Our old index had several layers, some of which were refreshed at a faster rate than others; the main layer would update every couple of weeks. To refresh a layer of the old index, we would analyze the entire web, which meant there was a significant delay between when we found a page and made it available to you.

With Caffeine, we analyze the web in small portions and update our search index on a continuous basis, globally...

My congratulations to the search infrastructure team. It sounds like a significant milestone!

SIGMOD 2010 live stream

2010-06-08T04:12:00.004-04:00

Just a quick note to say that I'm back from holiday. I'm settled in Barcelona for the summer, so the posting time schedule may be slightly shifted.

The SIGMOD 2010 conference is underway this week. The papers are online at the ACM DL, SIGMOD page. The keynote talks are being streamed live. Today is a keynote talk by Jon Kleinberg at 8:30am EDT.

Also, in case you've been living under a rock (like me), you can catch up on the WSDM 2010 videos that have been online for awhile.

Traveling...

2010-05-20T04:33:00.004-04:00

You've probably noticed the lack of updates around here. I am travelling. I'm currently in London on my way to Barcelona. I'll be in Barcelona this summer for internship at Yahoo! Research. My project there will likely involve search over semantic web data, in the vein of the work at the SemSearch Workshop.

I expect it will be early June before I'm settled and get back to a more regular schedule.

OpenLibrary relaunch, LSH on MapReduce, and WWW Inferring User Intent Tutorial

2010-05-10T11:41:00.004-04:00

A couple quick links from late last week to share.

OpenLibrary Relaunch- A redesigned OpenLibrary website was launched last week, designed by Caterina Flake. The new site is like Wikipedia meets a Library catalog. See their blog for details.

LikeLike - An implementation of LSH written for Hadoop. There isn't much documentation on how it is parallelizing the computation.

Inferring Web Searcher Intent Tutorial - The slides from Eugene Agichtein's WWW 2010 tutorial are now available. The first part of the tutorial provides an overview of user task and behaviour models. The second part focuses on utilizing implicit feedback from clicks and other interaction activity.

Best Paper Awards and Nominees at WWW 2010

2010-05-01T00:29:00.003-04:00

Matt Lease kindly sent me the best paper award information. (You should check out the grad IR class he is teaching this semester). Unfortunately, I can't find them all available online yet.

Best Poster Award

How much is your Personal Recommendation Worth

Paul Dütting, Monika Henzinger and Ingmar Weber

SourceRank: Relevance and Trust Assessment for Deep Web Sources Based on Inter-Source Agreement (PDF)

Raju Balakrishnan and Subbarao Kambhampati

Best Student Paper

Privacy Wizards for Social Networking Sites (PDF)
Lujun Fang, Kristen LeFevre

Best Paper nominees

Factorizing Personalized Markov Chains for Next-Basket Recommendation (winner)

Steffen Rendle (Osaka University), Christoph Freudenthaler, and Lars Schmidt-Thieme (University of Hildesheim).

A Refreshing Perspective of Search Engine Caching (PDF)
Flavio Junqueira, Berkant Barla Cambazoglu, Vassilis Plachouras, Swee Lim, Baoqiu Cui, Scott Banachowski

AdHeat: An Influence-based Diffusion Model for Propagating Hints to Match Ads

Hongji Bao, Ed Chang

Danah Boyd WWW keynote: Privacy and Publicity in Big Data

2010-04-29T12:43:00.004-04:00

Today Danah Boyd's gave an address on the Privacy and Publicity in the context of big data at WWW 2010 . Danah released a crib sheet summary on her website, which you should read. Here are Michael's notes from the talk.

Privacy concerns are everywhere

Big data (Social data created
by people) magnifies these concerns

Data is cheap today

Making sense of the data, however, is still hard
Accessing and processing it an ethical way is not investigated

Methodological issues

Big data introduces more
questions than answers
Ethnography tries to answer
some of these “why” questions

Social Sciences Approach
– 4 key points

Bigger is not always better
Not all data equal
“What” != “Why”
Be careful in interpretations

Sampling

The way you sample affects
your results – hard to create truly random representative sample
Big data doesn’t mean
“the whole of the data”
No matter how many tweets
you have, your sample is always biased

Oversampling users who tweet
frequently

Not all data are equal

What does your network represent?
Types of social network

Articulated
Behavioral
Personal

Data from Facebook is not
necessarily more accurate that other social (smaller) network

Facebook friends != person’s social network
Frequency of conversation != personal closeness

What != Why

Correlation does not mean causation
Even if your model points that there are two connected events doesn’t mean one causes
the other
Results need to be interpreted

Technology can corrupt social
science research by making simplifying assumptions and ignoring how
the context in which original results were obtained

Uncertainty principle applies

Networks are made of people,
not of abstract nodes on the graph
Data in the network is about
real people’s lives

Just because data is accessible
doesn’t mean that using it is ethical!

Privacy is context
Walls (Technology) have
ears (and mouths)

Five point for privacy security

Security through obscurity

Violated more and more by
technology
Technologies change people’s
behavior

Not all is meant to be publicized

Do we all want to become
“digital micro-celebrities” and fear the “digital paparazzi”?

PII vs. PEI (Personal Identifiable
vs. Embarrassing Information)

Algorithms have a hard time
discerning PII & PEI

Data out of context is a
privacy violation
Privacy is not access control

People care about privacy

But they all also care about
publicity – a right to be in public

Facebook

Facebook users have an impression
that “Facebook is more private than MySpace”
Newsfeed – publicizing
implicit (but accessible) content in explicit way

Initially controversial,
became a great success
Created a set of norms in
the “Facebook world”

Beacon – people are vessels
for advertisements

Was a failure, ended in
a user lawsuit

New default privacy settings

Research shows that people
do not understand their privacy settings in Facebook
In fact, their mental map
of settings doesn’t match the actual settings

Slow changes from private
to public

Users are like frogs who
are slowly “cooked” and do not realize it
Data from 3^rd
party sites is slowly aggregates

Tastes, web actions
are made public

Opt-out is the norm at Facebook

People do not understand
what they implicitly agree to

Regulations

Involvement from governments
(esp. from Europe,Canada)
Researchers --- need to
understand the consequences of their analysis

Search is Dead! Long Live Search Panel at WWW 2010

2010-04-28T16:10:00.006-04:00

Continuing the WWW 2010 coverage, this after there was a panel, Search is Dead! Long Live Search. You can see a poor quality video stream of the panel. The following are the notes from my labmate, Michael. You can also see the discussion on Twitter, #searchisdead.

Search is dead! Long Live Search.

Search for 10 blue links is already dead

A failure case is if a user sees just the 10 blue links

There is much more diverse data sources and presentations than links to web pages

Intense competition to get the tail queries right

You miss everyone if you miss the tail
It doesn’t take much to get into the tail – 1 or 2 more keywords

Enormous need to resurface implicit structured information for keyword queries
How to satisfy the tail?

10 blue links are not enough
Show structured data not
just for popular queries, but for tail queries as well: maps for “historical houses in Raleigh”
UI challenge

Change in how people produce content

From newswire docs to webdocs to blogs to Twitter

Searches that don’t work

Book Search
Wikipedia
Images
Complex queries

Capturing user behavior activity

Reformulations given by users are more likely to be clicked than automatically generated ones.
Better tools for capturing
how users interact with the results

Facets

Already are used in some vertical domains by Bing
Automatically extracting facets from raw text

Caveat: are they meaningful?

Are users getting used to facets? The “jury is still out”
Can become exponentially complex

Mobile Search

Voice search is a big change

Penalty for longer queries go down – natural language processing will become more important
Surprising finding – people tend to type (not speak) longer queries on mobile

Recognizing long stateless speech utterances is hard

Lots of apps

Tail queries can be better served by niche apps
How to integrate results between apps?

Geo-information

Comes for free in phones and has to be used by a successful search engine

Social Search

We already do social search by using click data
Can we do better using social networks?
Are applications like Aardvark effective?

Yahoo! Expands Restaurant Vertical with Menu information

2010-04-28T15:12:00.008-04:00

For those of you who know me, you know that I love to cook, and to eat. So I was excited when today the Yahoo!Search blog highlighted the addition of a new feature to that allows you to search for a specific dish at local restaurants. The post makes vague reference to information extraction from menus:

By extracting structured content – in this case, menu items – from unstructured web pages and matching them to restaurant entities, Yahoo! Search can return results of restaurants near you that serve the dish you crave for when you enter the name of the dish in the search box. You can also try this experience in Yahoo! Local.

I tried a search for roasted chicken, san francisco. I expected Zuni Cafe and their world famous roasted chicken with bread salad. However, I was disappointed and the vertical did not trigger. Giving it another shot, I tried burger northampton, ma. My favorite burger joint, Local Burger is second on the list; right after burger king. Not horrible, but not great either. The local ranking could be improved.

I love the idea, but it still needs work. First, I usually don't think of a specific dish when I'm picking a restaurant, unless it's pizza or a burger and its pretty obvious in these cases. What I would really love to see are search options that let me find restaurants with menus that cater to specialty diets. For example, find me a restaurant with options that are gluten-free, low sodium, kosher, dairy-free, etc... This is important because like many other people I know, my mom has celiac disease and other dietary restrictions.