File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Network-aware search in social tagging applications: instance optimality versus efficiency

TitleNetwork-aware search in social tagging applications: instance optimality versus efficiency
Authors
Issue Date2013
PublisherACM Press.
Citation
Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM), San Francisco, USA, 27 October-1 November 2013, p. 939-948 How to Cite?
AbstractWe 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 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, 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.
Persistent Identifierhttp://hdl.handle.net/10722/201105
ISBN

 

DC FieldValueLanguage
dc.contributor.authorManiu, Sen_US
dc.contributor.authorCautis, Ben_US
dc.date.accessioned2014-08-21T07:13:34Z-
dc.date.available2014-08-21T07:13:34Z-
dc.date.issued2013en_US
dc.identifier.citationProceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM), San Francisco, USA, 27 October-1 November 2013, p. 939-948en_US
dc.identifier.isbn9781450322638-
dc.identifier.urihttp://hdl.handle.net/10722/201105-
dc.description.abstractWe 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 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, 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.-
dc.languageengen_US
dc.publisherACM Press.en_US
dc.relation.ispartofACM International Conference on Information and Knowledge Managementen_US
dc.titleNetwork-aware search in social tagging applications: instance optimality versus efficiencyen_US
dc.typeConference_Paperen_US
dc.identifier.emailManiu, S: smaniu@cs.hku.hken_US
dc.identifier.doi10.1145/2505515.2505760-
dc.identifier.scopuseid_2-s2.0-84889594345-
dc.identifier.hkuros232983en_US
dc.identifier.spage939-
dc.identifier.epage948-
dc.publisher.placeNew York, N.Y.-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats