Efficient network aware search in collaborative tagging sites

Sihem Amer Yahia, Michael Benedikt, Laks V.S. Lakshmanan, Julia Stoyanovichy

    Research output: Contribution to journalArticlepeer-review


    The popularity of collaborative tagging sites presents a unique opportunity to explore keyword search in a context where query results are determined by the opinion of a network of taggers related to a seeker. In this paper, we present the first in-depth study of network-aware search. We investigate efficient top-k processing when the score of an answer is computed as its popularity among members of a seeker's network. We argue that obvious adaptations of top-k algorithms are too space-intensive, due to the dependence of scores on the seeker's network. We therefore develop algorithms based on maintaining score upper-bounds. The global upper-bound approach maintains a single score upper-bound for every pair of item and tag, over the entire collection of users. The resulting bounds are very coarse. We thus investigate clustering seekers based on similar behavior of their networks. We show that finding the optimal clustering of seekers is intractable, but we provide heuristic methods that give substantial time improvements. We then give an optimization that can benefit smaller populations of seekers based on clustering of taggers. Our results are supported by extensive experiments on del.icio.us datasets.

    Original languageEnglish (US)
    Pages (from-to)710-721
    Number of pages12
    JournalProceedings of the VLDB Endowment
    Issue number1
    StatePublished - 2008

    ASJC Scopus subject areas

    • Computer Science (miscellaneous)
    • General Computer Science


    Dive into the research topics of 'Efficient network aware search in collaborative tagging sites'. Together they form a unique fingerprint.

    Cite this