{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T00:36:04Z","timestamp":1791419764634,"version":"4.3.3"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>\n            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\n            <jats:italic>network-aware<\/jats:italic>\n            search. We investigate efficient top-\n            <jats:italic>k<\/jats:italic>\n            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-\n            <jats:italic>k<\/jats:italic>\n            algorithms are too space-intensive, due to\n            <jats:italic>the dependence of scores on the seeker's network.<\/jats:italic>\n            We therefore develop algorithms based on maintaining\n            <jats:italic>score upper-bounds.<\/jats:italic>\n            The\n            <jats:italic>global upper-bound approach<\/jats:italic>\n            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\n            <jats:italic>clustering seekers based on similar behavior of their networks.<\/jats:italic>\n            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\n            <jats:italic>clustering of taggers.<\/jats:italic>\n            Our results are supported by extensive experiments on del.icio.us datasets.\n          <\/jats:p>","DOI":"10.14778\/1453856.1453934","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"710-721","source":"Crossref","is-referenced-by-count":58,"title":["Efficient network aware search in collaborative tagging sites"],"prefix":"10.14778","volume":"1","author":[{"given":"Sihem Amer","family":"Yahia","sequence":"first","affiliation":[{"name":"Yahoo! Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Benedikt","sequence":"additional","affiliation":[{"name":"Oxford University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laks V. S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"University of British Columbia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Julia","family":"Stoyanovich","sequence":"additional","affiliation":[{"name":"Columbia University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Modern Information Retrieval","author":"Baeza-Yates R.","year":"1999","unstructured":"R. Baeza-Yates and B. Ribeiro-Neto . Modern Information Retrieval . Addison-Wesley , 1999 . R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley, 1999."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253302"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1115"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/565117.565143"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102412856"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/239041.239045"},{"key":"e_1_2_1_8_1","volume-title":"Computers and Intractability: A Guite to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A Guite to the Theory of NP-Completeness . W. H. Freeman and Company , 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A Guite to the Theory of NP-Completeness. W. H. Freeman and Company, 1979."},{"key":"e_1_2_1_9_1","volume-title":"HP Labs","author":"Golder S. A.","year":"2006","unstructured":"S. A. Golder and B. A. Huberman . The structure of collaborative tagging systems. Information Dynamics Lab , HP Labs , 2006 . S. A. Golder and B. A. Huberman. The structure of collaborative tagging systems. Information Dynamics Lab, HP Labs, 2006."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1007"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287453"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/582415.582418"},{"key":"e_1_2_1_13_1","volume-title":"Patterns and inconsistencies in collaborative tagging systems: An examination of tagging practices","author":"Kipp M. E.","year":"2006","unstructured":"M. E. Kipp and D. G. Campbell . Patterns and inconsistencies in collaborative tagging systems: An examination of tagging practices . 2006 . Available from http:\/\/dlist.sir.arizona.edu\/1704\/01\/KippCampbellASIST.pdf. M. E. Kipp and D. G. Campbell. Patterns and inconsistencies in collaborative tagging systems: An examination of tagging practices. 2006. Available from http:\/\/dlist.sir.arizona.edu\/1704\/01\/KippCampbellASIST.pdf."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367589"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.18"},{"key":"e_1_2_1_16_1","volume-title":"VLDB","author":"Michel S.","year":"2005","unstructured":"S. Michel , P. Triantafilou , and G. Weikum . Klee: a framework for distributed top-k query algorithms . In VLDB , 2005 . S. Michel, P. Triantafilou, and G. Weikum. Klee: a framework for distributed top-k query algorithms. In VLDB, 2005."},{"key":"e_1_2_1_17_1","volume-title":"HotNets","author":"Mislove A.","year":"2006","unstructured":"A. Mislove , K. Gummadi , and P. Druschel . Exploiting social networks for internet search . In HotNets , 2006 . A. Mislove, K. Gummadi, and P. Druschel. Exploiting social networks for internet search. In HotNets, 2006."},{"key":"e_1_2_1_18_1","volume-title":"AAAI SIP","author":"Stoyanovich J.","year":"2008","unstructured":"J. Stoyanovich , S. Amer-Yahia , C. Marlow , and C. Yu . Leveraging tagging to model user interests in del.icio.us . In AAAI SIP , 2008 . J. Stoyanovich, S. Amer-Yahia, C. Marlow, and C. Yu. Leveraging tagging to model user interests in del.icio.us. In AAAI SIP, 2008."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142520"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367594"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453934","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:09:05Z","timestamp":1672225745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453934"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453934"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453934","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}