  We consider in this paper top-k query answering in social tagging systems,
also known as folksonomies. This problem requires a significant departure from
existing, socially agnostic techniques. In a network-aware context, one can
(and should) exploit the social links, which can indicate how users relate to
the seeker and how much weight their tagging actions should have in the result
build-up. We propose an algorithm that has the potential to scale to current
applications. While the problem has already been considered in previous
literature, this was done either under strong simplifying assumptions or under
choices that cannot scale to even moderate-size real world applications. We
first consider a key aspect of the problem, which is accessing the closest or
most relevant users for a given seeker. We describe how this can be done on the
fly (without any pre-computations) for several possible choices - arguably the
most natural ones - of proximity computation in a user network. Based on this,
our top-k algorithm is sound and complete, while addressing the scalability
issues of the existing ones. Importantly, our technique is instance optimal in
the case when the search relies exclusively on the social weight of tagging
actions. To further reduce response times, we then consider directions for
efficiency by approximation. Extensive experiments on real world data show that
our techniques can drastically improve the response time, without sacrificing
precision.
