{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T10:22:45Z","timestamp":1770546165899,"version":"3.49.0"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,4]]},"abstract":"<jats:p>The popularity of social-networking sites has increased rapidly over the last decade. A basic functionalities of social-networking sites is to present users with streams of events shared by their friends. At a systems level, materialized per-user views are a common way to assemble and deliver such event streams on-line and with low latency. Access to the data stores, which keep the user views, is a major bottleneck of social-networking systems. We propose to improve the throughput of these systems by using social piggybacking, which consists of processing the requests of two friends by querying and updating the view of a third common friend. By using one such hub view, the system can serve requests of the first friend without querying or updating the view of the second. We show that, given a social graph, social piggybacking can minimize the overall number of requests, but computing the optimal set of hubs is an NP-hard problem. We propose an<jats:italic>O<\/jats:italic>(log<jats:italic>n<\/jats:italic>) approximation algorithm and a heuristic to solve the problem, and evaluate them using the full Twitter and Flickr social graphs, which have up to billions of edges. Compared to existing approaches, using social piggybacking results in similar throughput in systems with few servers, but enables substantial throughput improvements as the size of the system grows, reaching up to a 2-factor increase. We also evaluate our algorithms on a real social networking system prototype and we show that the actual increase in throughput corresponds nicely to the gain anticipated by our cost function.<\/jats:p>","DOI":"10.14778\/2536336.2536342","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"409-420","source":"Crossref","is-referenced-by-count":33,"title":["Piggybacking on social networks"],"prefix":"10.14778","volume":"6","author":[{"given":"Aristides","family":"Gionis","sequence":"first","affiliation":[{"name":"Aalto University and HIIT, Espoo, Finland"}]},{"given":"Flavio","family":"Junqueira","sequence":"additional","affiliation":[{"name":"Microsoft Research, Cambridge, UK"}]},{"given":"Vincent","family":"Leroy","sequence":"additional","affiliation":[{"name":"Univ. of Grenoble and CNRS, Grenoble, France"}]},{"given":"Marco","family":"Serafini","sequence":"additional","affiliation":[{"name":"QCRI, Doha, Qatar"}]},{"given":"Ingmar","family":"Weber","sequence":"additional","affiliation":[{"name":"QCRI, Doha, Qatar"}]}],"member":"320","published-online":{"date-parts":[[2013,4]]},"reference":[{"issue":"2","key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1006\/jagm.1999.1062","article-title":"Greedily finding a dense subgraph","volume":"34","author":"Asahiro Y.","year":"2000","unstructured":"Y. Asahiro , K. Iwama , H. Tamaki , and T. Tokuyama . Greedily finding a dense subgraph . Journal of Algorithms , 34 ( 2 ): 203 - 221 , 2000 . Y. Asahiro, K. Iwama, H. Tamaki, and T. Tokuyama. Greedily finding a dense subgraph. Journal of Algorithms, 34(2):203-221, 2000.","journal-title":"Journal of Algorithms"},{"key":"e_1_2_1_2_1","first-page":"8","volume-title":"Proc. of ICWM","volume":"14","author":"Cha M.","year":"2010","unstructured":"M. Cha , H. Haddadi , F. Benevenuto , and K. P. Gummadi . Measuring user influence in Twitter: The million follower fallacy . In Proc. of ICWM , volume 14 , page 8 , 2010 . M. Cha, H. Haddadi, F. Benevenuto, and K. P. Gummadi. Measuring user influence in Twitter: The million follower fallacy. In Proc. of ICWM, volume 14, page 8, 2010."},{"key":"e_1_2_1_3_1","first-page":"139","volume-title":"Proc. of APPROX","author":"Charikar M.","year":"2000","unstructured":"M. Charikar . Greedy approximation algorithms for finding dense components in a graph . In Proc. of APPROX , pages 139 - 152 , 2000 . M. Charikar. Greedy approximation algorithms for finding dense components in a graph. In Proc. of APPROX, pages 139-152, 2000."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1145\/1281100.1281118","volume-title":"Proc. of PODC","author":"Chockler G.","year":"2007","unstructured":"G. Chockler , R. Melamed , Y. Tock , and R. Vitenberg . Constructing scalable overlays for pub-sub with many topics: Problems, algorithms, and evaluation . In Proc. of PODC , pages 109 - 118 , 2007 . G. Chockler, R. Melamed, Y. Tock, and R. Vitenberg. Constructing scalable overlays for pub-sub with many topics: Problems, algorithms, and evaluation. In Proc. of PODC, pages 109-118, 2007."},{"issue":"3","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A greedy heuristic for the set-covering problem","volume":"4","author":"Chvatal V.","year":"1979","unstructured":"V. Chvatal . A greedy heuristic for the set-covering problem . Mathematics of Operations Research , 4 ( 3 ): 233 - 235 , 1979 . V. Chvatal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233-235, 1979.","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1327452.1327492","article-title":"Mapreduce: simplified data processing on large clusters","volume":"51","author":"Dean J.","year":"2008","unstructured":"J. Dean and S. Ghemawat . Mapreduce: simplified data processing on large clusters . Communications of the ACM , 51 ( 1 ): 107 - 113 , 2008 . J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107-113, 2008.","journal-title":"Communications of the ACM"},{"issue":"4","key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","article-title":"A threshold of ln n for approximating set cover","volume":"45","author":"Feige U.","year":"1998","unstructured":"U. Feige . A threshold of ln n for approximating set cover . Journal of the ACM , 45 ( 4 ): 634 - 652 , 1998 . U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634-652, 1998.","journal-title":"Journal of the ACM"},{"key":"e_1_2_1_8_1","volume-title":"Social networks that matter: Twitter under the microscope. First Monday, 14(1-5)","author":"Huberman B. A.","year":"2009","unstructured":"B. A. Huberman , D. M. Romero , and F. Wu . Social networks that matter: Twitter under the microscope. First Monday, 14(1-5) , 2009 . B. A. Huberman, D. M. Romero, and F. Wu. Social networks that matter: Twitter under the microscope. First Monday, 14(1-5), 2009."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1145\/1150402.1150479","volume-title":"Proc. of KDD","author":"Leskovec J.","year":"2006","unstructured":"J. Leskovec and C. Faloutsos . Sampling from large graphs . In Proc. of KDD , pages 631 - 636 , 2006 . J. Leskovec and C. Faloutsos. Sampling from large graphs. In Proc. of KDD, pages 631-636, 2006."},{"issue":"2","key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","article-title":"The structure and function of complex networks","volume":"45","author":"Newman M. E.","year":"2003","unstructured":"M. E. Newman . The structure and function of complex networks . SIAM review , 45 ( 2 ): 167 - 256 , 2003 . M. E. Newman. The structure and function of complex networks. SIAM review, 45(2):167-256, 2003.","journal-title":"SIAM review"},{"key":"e_1_2_1_11_1","first-page":"831","volume-title":"Proc. of SIGMOD","author":"Silberstein A.","year":"2010","unstructured":"A. Silberstein , J. Terrace , B. F. Cooper , and R. Ramakrishnan . Feeding frenzy: selectively materializing users' event feeds . In Proc. of SIGMOD , pages 831 - 842 , 2010 . A. Silberstein, J. Terrace, B. F. Cooper, and R. Ramakrishnan. Feeding frenzy: selectively materializing users' event feeds. In Proc. of SIGMOD, pages 831-842, 2010."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536336.2536342","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T14:45:03Z","timestamp":1689345903000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536336.2536342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":11,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.14778\/2536336.2536342"],"URL":"https:\/\/doi.org\/10.14778\/2536336.2536342","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,4]]}}}