As-You-Type Social Aware Search

• Published in: ACM transactions on intelligent systems and technology 2017-09, Vol.8 (5), p.1-31
• Main Authors: Lagrée, Paul, Cautis, Bogdan, Vahabi, Hossein
• Format: Article
• Language: English
• Subjects: Computer Science; Data Structures and Algorithms; Information Retrieval
• ISSN: 2157-6904; 2157-6912
• DOI: 10.1145/3035969

Modern search applications feature real-time as-you-type query search. In its elementary form, the problem consists in retrieving a set of k search results, that is, performing a search with a given prefix, and showing the top-ranked results. In this article, we focus on as-you-type keyword search over social media, that is, data published by users who are interconnected through a social network. We adopt a “network-aware” interpretation for information relevance, by which information produced by users who are closer to the user issuing a request is considered more relevant. This query model raises new challenges for effectiveness and efficiency in online search, even when the intent of the user is fully specified, as a complete query given as input in one keystroke. This is mainly because it requires a joint exploration of the social space and traditional IR indexes, such as inverted lists. We describe a memory-efficient and incremental prefix-based retrieval algorithm, which also exhibits an anytime behavior, allowing output of the most likely answer within any chosen runtime limit. We evaluate our approach through extensive experiments for several applications and search scenarios. We consider searching for posts in microblogging (Twitter and Tumblr), for businesses (Yelp), as well as for movies (Amazon) based on reviews. We also conduct a series of experiments comparing our algorithm with baselines using state-of-the-art techniques and measuring the improvements brought by several key optimizations. They show that our solution is effective in answering real-time as-you-type searches over social media.