Skip to Main content Skip to Navigation
Conference papers

Network-aware Search in Social Tagging Applications: Instance Optimality versus Efficiency

Silviu Maniu 1 Bogdan Cautis 2, 3, 4
2 OAK - Database optimizations and architectures for complex large data
Inria Saclay - Ile de France, LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : We consider in this paper top-k query answering in social applications, with a focus on social tagging. This problem requires a significant departure from 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 algorithms that have 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 revisit 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 precomputations) 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, addressing the applicability issues of the existing ones. Moreover, it performs significantly better in general and is instance optimal in the case when the search relies exclusively on the social weight of tagging actions. To further address the efficiency needs of online applications, for which the exact search, albeit optimal, may still be expensive, we then consider approximate algorithms. Specifically, these rely on concise statistics about the social network or on approximate shortest-paths computations. Extensive experiments on real-world data from Twitter show that our techniques can drastically improve response time, without sacrificing precision.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Bogdan Cautis Connect in order to contact the contributor
Submitted on : Sunday, January 12, 2014 - 7:59:48 PM
Last modification on : Thursday, July 8, 2021 - 3:48:45 AM
Long-term archiving on: : Saturday, April 8, 2017 - 2:27:36 PM


Files produced by the author(s)


  • HAL Id : hal-00927308, version 1


Silviu Maniu, Bogdan Cautis. Network-aware Search in Social Tagging Applications: Instance Optimality versus Efficiency. ACM Conference on Information And Knowledge Management (CIKM), Oct 2013, San Francisco, United States. ⟨hal-00927308⟩



Les métriques sont temporairement indisponibles