Related Searches at LinkedIn
Mitul Tiwari
Joint work with Azarias Reda, Yubin Park, ChristianPosse, and Sam ShahLinkedIn

1Tuesday, August 21, 2012

Who am I

2
Tuesday, August 21, 2012Outline• About LinkedIn• Related Searches‣

Design‣Implementation‣

Evaluation

3
Tuesday, August 21, 2012

LinkedIn by the numbers• 175M+ members• 2+ new user registrations per second• 4.2 Billion people searches in 2011
• 9.3 Billion page views in Q2 2012
• 100+ million monthly active users in Q2 2012

4Tuesday, August 21, 2012

Broad Range of ProductsProfileSearch

People You May Know

NewsSkills

Tuesday, August 21, 2012

Hiring Solutions

Related Searches at LinkedIn• Millions of searches everyday• Goal: Build related searches system at LinkedIn• To help users to explore and refine their queries

6
Tuesday, August 21, 2012

Related Searches at LinkedIn

Tuesday, August 21, 2012

Related Searches• Design• Implementation• Evaluation

8
Tuesday, August 21, 2012

Related Searches• Design• Implementation• Evaluation

9
Tuesday, August 21, 2012

Design

10
Tuesday, August 21, 2012

Design• Signals‣

Collaborative Filtering‣Query-Result Click graph‣

Overlapping terms

10
Tuesday, August 21, 2012

Design• Signals‣

Collaborative Filtering‣

Query-Result Click graph‣

Overlapping terms• Length-bias

10
Tuesday, August 21, 2012

Design• Signals‣

Collaborative Filtering‣

Query-Result Click graph‣

Overlapping terms• Length-bias• Ensemble approach for unified recommendation

10
Tuesday, August 21, 2012

Design• Signals‣

Collaborative Filtering‣

Query-Result Click graph‣

Overlapping terms• Length-bias• Ensemble approach for unified recommendation• Practical considerations
10
Tuesday, August 21, 2012

Design: Collaborative Filtering
Q1

Q2

Q3

Q4

Time
• Searches correlated by time‣

Searches done in the same session by the same user‣

Collaborative filtering: implicit feedback‣

TFIDF scoring to take care of popular queries (e.g. `Obama’)
11

Tuesday, August 21, 2012

Design: Query-Result Clicks
Q1

R1

QnRm

• Searches correlated by result clicks

12
Tuesday, August 21, 2012

Design: Overlapping Terms

Q1

Software Developer

Q2

Software Engineer• Searches with overlapping terms‣TFIDF scoring to give importance to terms
13

Tuesday, August 21, 2012

Design: Length Bias
• Insight: clicks on suggestions one term longer

14
Tuesday, August 21, 2012

Design: Length Bias
• Insight: clicks on suggestions one term longer• Corresponds to refining the initial query• Statistical biasing model to score a longer query

higherTuesday, August 21, 2012

Design: Length Bias
• Insight: clicks on suggestions one term longer• Corresponds to refining the initial query• Statistical biasing model to score a longer query

higherTuesday, August 21, 2012

Design: Ensemble Approach• Need to generate unified recommendation dataset• Analysis to figure out engagement of each signal• Attempted ML approach‣

Minimal overlap across different signals

16
Tuesday, August 21, 2012

Design: Ensemble Approach• Step-wise unionization• Importance based on individual signal performance‣First, collaborative filter‣

Second, queries correlated by query-result clicks‣

Third, queries overlapping terms

17
Tuesday, August 21, 2012

Design: Practical Considerations• System designed for public consumption‣

Strong profanity filters‣

Need to deal with misspellings‣

Languages‣

Remove spammy search queries

18
Tuesday, August 21, 2012

Related Searches• Design• Implementation• Evaluation

19
Tuesday, August 21, 2012

Implementation Challenge• Scale‣175M+ members‣

Billions of searches‣

Terabytes of data to process

20
Tuesday, August 21, 2012

Implementation
SearchBackend
Front
End

Kafka

RelatedSearches
Backend

HadoopHDFSMetaphor

Voldemort• Kafka: publish-subscribe messaging system• Hadoop: MapReduce data processing system• Azkaban: Hadoop workflow management tool
• Voldemort: Key-value store
Tuesday, August 21, 2012

Implementation: Workflow
Query Preprocessing

Pair Formation

GraphFormation

TokenIdentification

CF Scoring

QRQ Scoring

Partial Scoring

Step-wiseUnion

Length Bias
Filter

Step-wise
Union

Tuesday, August 21, 2012

Related Searches• Design• Implementation• Evaluation

23
Tuesday, August 21, 2012

Evaluation• Performance of each signal and combination• How does the system scale?

24
Tuesday, August 21, 2012

Evaluation Cont’d• Offline evaluation‣

Precision-Recall• Online evaluation‣A/B testing to measure engagement‣Performance evaluation25
Tuesday, August 21, 2012

Offline Evaluation• Correct set: set of searches performed by a user inthe following K minutes, here K=1026
Tuesday, August 21, 2012

Online Evaluation• Used A/B testing• Metrics‣

Coverage: queries with recommendations‣Impressions: # of recommendations shown‣

Clicks: Clicks on recommendations‣Click-through rate (CTR): Clicks per impression

27
Tuesday, August 21, 2012

Online Evaluation

Tuesday, August 21, 2012

Evaluation: System Runtime

29
Tuesday, August 21, 2012

Details• Metaphor: a System for Related Search

Recommendations, Azarias Reda, Yubin Park, Mitul
Tiwari, Christian Posse, and Sam Shah. In Proceedingsof the CIKM, 2012.

30
Tuesday, August 21, 2012