Sanjay Kairam

Earlier this week, the team at Aardvark unveiled a new paper “The Anatomy of a Large-Scale Social Search Engine” which will be presented in April at WWW 2010. Inspired by and patterned after “The Anatomy of a Large-Scale Hypertextual Web Search Engine“, which describes the PageRank algorithm which drives Google’s search ranking system (which as Aardvark’s blog points out, was also presented at WWW 12 years ago).

The paper, by Aardvark’s Damon Horowitz and Stanford’s Sep Kamvar, focuses mostly on the architecture of the Aardvark system, from the external representations with which users interact to the internal ranking algorithms on which the system runs. Below, I present a short summary of what they report, focusing on the elements I found most interesting:

The Basic Model: Aardvark’s scoring function is similar to PageRank in that both utilize two primary, but somewhat independently considered components: relevance and quality.

• Relevance in the Aardvark model pertains to the probability that a particular user i can answer the given question q based on the identified topics contained in t.
• Quality in the Aardvark model pertains to the overall probability that a user i can return a satisfactory answer to another user j, regardless of the question.

Indexing Topics: Aardvark computes the relevance score by calculating a distribution of knowledge over topics known by the user using the following sources (keyword-y sounding italicized terms are for convenience only and are not used in the paper):

• Explicit Prompting at sign-up for three “starter” topics about which the user has expertise.
• Social Prompting of a user’s friends to provide topics about which they trust the user’s opinion.
• Structured Parsing of the online profile pages connected to Aardvark by the user (e.g. “Interests” on a Facebook profile).
• Unstructured Parsing of the users’ online homepage, blog, or status updates using a linear SVM to extract overall subject area and a named entity extractor to extract more specific topics.

Indexing Connections: Aardvark computes the quality score by building a set of weighted connections between users using characteristics ranging from social proximity to similarities in demographics or behavior, such as:

• Social Connections either in the form of explicitly defined “friend” connections or implicit “network” connections, such as both being part of the Stanford network.
• Demographic Similarity, which likely includes age, gender, and location based on profile information collected by Aardvark.
• Profile Similarity, which seems to include similar movies and other items which might be listed on other profiles, such as Facebook.
• Vocabulary Match, which they explain with the example of “IM Shortcuts” (i.e. I assume this means it is based on the language you use to interact with Aardvark, but I am unsure.)
• Chattiness and Verbosity Match, which relate to frequency and length of messages used when interacting with Aardvark.
• Politeness Match, which basically seems to mean whether or not say “Thanks!” or not.
• Speed Match, which is a measure of responsiveness to other users.

Analyzing Questions: While all of the other components are pre-computed, this part is computed at question time (obviously). The utilize a number of classifiers to classify the question and then a set of mappers to map the question to a set of topics, noting that “the role of the Question Analyzer…is simply to learn enough about the qeustion that it may be sent to appropriately interested and knowledgeable human answerers”. Here are the classifiers they list (with the names used in the paper):

• NonQuestionClassifier: Determines if input is a valid question.
• InappropriateQuestionClassifier: Determines if input is obscene, spam, or otherwise unsuitable for asking.
• TrivialQuestionClassifier: Determines if input is a simple factual question (examples given: “What time is it now?”, “What is the weather?”). If so, the user gets an automatically generated answer via traditional web search.
• LocationSensitiveClassifier: Determines if the question contains location information; if it does, it passes that information along to the Routing Engine

• KeywordMatchTopicMapper: Checks for string matches against user profile topics (the mapper attempts to classify meaningful vs. spurious matches).
• TaxonomyTopicMapper: Classifies question text using an SVM trained on an “annotated corpus of several million questions” (where did they find that?)
• SalientTermTopicMapper: Extracts salient phrases using a noun-phrase chunker and tf-idf and finds “semantically similar user topics”.
• UserTagTopicMapper:Utilizes tags explicitly provided by the asker or other answerers and maps them to user topics.

This description of the routing algorithm comprises the main function of the paper. After some more description of how users interact with the system, the authors provide some interesting data collected over the past several months of use (from the beta launch in March 2009 until October 2009).  Here’s a quick run-down of the more interesting facts that they presented:

• Strong User Growth: As of October 2009, they reported 90,361 user accounts, and users appear to be remaining active (in the study period, over 1/2 the users actively generated content and over 2/3 of the users passively participated).

User Growth on Aardvark (graph taken from the paper).

• Higher Query Contextualization: Aardvark queries average 18.6 words in length while the average query length reported for web search is between 2.2 and 2.9 words (citing previous comparison and characterization studies).  They further state that “98.1% of questions are unique”, though I am unsure as to how exact they are being about matching (I am sure the question “What’s a great restaurant in SF” has been asked 1000 times in different forms). In addition, they report from manual scoring of 1000 randomly selected questions that 64.7% of questions asked have a subjective element, with advice about travel, restaurants, and products being specifically popular.
• Fast, High-Quality Answers: They report that 87.7% of questions get answers and 57.2% received an answer within 10 minutes. They report that 70.4% of answers receiving feedback are rated as “good” and only 15.5% are rated as “bad”. Interestingly, they observe a notable difference in feedback on answers from users within the asker’s social network (76% rated as food) and outside the asker’s network (68% rated as good).

Questions on Aardvark (chart taken from the paper).

Overall, I really enjoyed reading this paper. After using Aardvark for over a year now, it was really interesting to get to peer inside and see how the system works, and a lot of great details were provided about the ranking engine.

One place where I feel that the authors missed the mark was in the cursory side-by-side evaluation which pitted Aardvark against Google for a set of 200 questions randomly selected from the Aardvark system. They report that 71.5% of the questions studied were answered successfully on Aardvark, while 70.5% of the questions were answered successfully on Google. This comparison seems mostly useless as the questions, having been pulled from the Aardvark system in the first place, are ones that were specifically chosen because they are better adapted to what is being called ’social search’. This comparison left me desirous of more investigation into two main questions.

“What makes a search engine ’social’ in the first place?”

The distinction between social and non-social is extremely murky, something Brynn and I discovered when working on our Social Search paper. It has been argued before (one small example here) that Google’s PageRank algorithm is inherently social, as it aggregates information provided by people (links to one another) to rank results. However, it is clear that something seems categorically different between Google and what people perceive to be ’social search’. When it comes down to it, even though everyone is excited about Google’s forays into “Social Search”, there’s nothing all that fundamentally different about Google indexing your blog and your tweets than any other documents extant on the web.

To me, it seems that the key difference is really the change in the direction of interaction. While Google takes a query (question) and compares it against traces of discussion about that question from the past (web documents), systems perceived as ’social’ take a question and attempt to generate new answers in the future. This change in direction is what allows for the higher context that makes ’social’ search answers so much more rich (at least for some questions.)  Perhaps we need a different word to define this phenomenon – ‘real-time search’ seems to get at it more, but has its own problems.  Perhaps something like ‘generative search’? I really don’t know.

“Why do we need a social search engine at all?”

This one seems like the best fodder for a follow-up study by Aardvark. While they do provide a rough breakdown of the types of questions asked on Aardvark (see pie chart above), I think that a comparison might have been much more interesting if they had looked at a variety of classes of user needs and had compared the relative efficacy of searching on Aardvark and a traditional search engine such as Google. It is clear that ’social’ will work much better for some needs and much worse for others, but up to this point, people who talk about social search always seem to use the same types of examples (travel, restaurants, and products, for instance). It would be great to get a clear idea over a wide range of needs and use cases where systems such as Aardvark can provide benefits over existing tools.

Anyways, for those of you interested in ’social search’ and search systems, I encourage you to read this paper and tell me your thoughts!