Characterizing the Influence of Domain Expertise on Web Search Behavior. Ryen W. White, Susan T. Dumais, Jaime Teevan. WSDM 2009

•  Look up
• maximum-margin averaged perceptron (Collins, M. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. EMNLP 2002) 

Disorder Inequality: A Combinatorial Approach to Nearest Neighbor Search. Navin Goyal, Yury Lifshits, Hinrich Schütze. WSDM 2008

• Ideas
• "combinatorial" setting: only comparisons between similarity scores allowed.
• two randomized algorithms for nearest-neighbor search, requiring O(n^2) and O(nlogn) space for preprocessed data