  We present in this paper a novel approach for as-you-type top-$k$ keyword
search over social media. We adopt a natural "network-aware" interpretation for
information relevance, by which information produced by users who are closer to
the seeker is considered more relevant. In practice, this query model poses new
challenges for effectiveness and efficiency in online search, even when a
complete query is given as input in one keystroke. This is mainly because it
requires a joint exploration of the social space and classic IR indexes such as
inverted lists. We describe a memory-efficient and incremental prefix-based
retrieval algorithm, which also exhibits an anytime behavior, allowing to
output the most likely answer within any chosen running-time limit. We evaluate
it through extensive experiments for several applications and search scenarios,
including searching for posts in micro-blogging (Twitter and Tumblr), as well
as searching for businesses based on reviews in Yelp. They show that our
solution is effective in answering real-time as-you-type searches over social
media.
