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
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
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.
Type de document :
Communication dans un congrès
ACM Conference on Information And Knowledge Management (CIKM), Oct 2013, San Francisco, United States. 2013
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00927308
Contributeur : Bogdan Cautis <>
Soumis le : dimanche 12 janvier 2014 - 19:59:48
Dernière modification le : lundi 28 mai 2018 - 14:38:02
Document(s) archivé(s) le : samedi 8 avril 2017 - 14:27:36

Fichier

cikm824-maniu.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00927308, version 1

Collections

Citation

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. 2013. 〈hal-00927308〉

Partager

Métriques

Consultations de la notice

404

Téléchargements de fichiers

277