{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/31040"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/31040","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Partitioning social networks for data locality on a memory budget","abstract":"\"Typical queries on online social network (OSN) applications are complex and require \"\"feeds\"\" to be compiled with timely information about many friends and friends' friends, which may be stored across many servers. Partitioning the OSN social graph in such a way as to promote data locality, i.e. such that a user's data will be stored on the same server as his friends' data, has proven difficult to do, and many existing OSN partitioning systems do not even attempt this. However, recent work has demonstrated techniques that do achieve data locality for social network queries by placing replicas of user data. We show that exploiting temporal characteristics of user behavior can enable effective partitioning for data locality without replication. We then build on this concept and demonstrate improved data locality by placing replicas sparingly. The result is a system which allows one to allocate a memory budget for replication and in return get a commensurate improvement in data locality.\"","abstract_html":""Typical queries on online social network (OSN) applications are complex and require ""feeds"" to be compiled with timely information about many friends and friends' friends, which may be stored across many servers. Partitioning the OSN social graph in such a way as to promote data locality, i.e. such that a user's data will be stored on the same server as his friends' data, has proven difficult to do, and many existing OSN partitioning systems do not even attempt this. However, recent work has demonstrated techniques that do achieve data locality for social network queries by placing replicas of user data. We show that exploiting temporal characteristics of user behavior can enable effective partitioning for data locality without replication. We then build on this concept and demonstrate improved data locality by placing replicas sparingly. The result is a system which allows one to allocate a memory budget for replication and in return get a commensurate improvement in data locality."","abstract_has_math":false,"creators":["Stein, David"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Lu, Yi"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-05-22T00:23:50Z","date_published":"2012-05-22T00:23:50Z","updated_at":"2026-07-22T22:25:29Z","subjects":["Social networks","Partitioning","Locality"],"languages":["en"],"rights":["Copyright 2012 David Stein"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/31040","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Lu, Yi"]},{"key":"dc:creator","label":"Author","values":["Stein, David"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-05-22T00:23:50Z","2012-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Social networks","Partitioning","Locality"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2012 David Stein"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/31040"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["\"Typical queries on online social network (OSN) applications are complex and require \"\"feeds\"\" to be compiled with timely information about many friends and friends' friends, which may be stored across many servers. Partitioning the OSN social graph in such a way as to promote data locality, i.e. such that a user's data will be stored on the same server as his friends' data, has proven difficult to do, and many existing OSN partitioning systems do not even attempt this. However, recent work has demonstrated techniques that do achieve data locality for social network queries by placing replicas of user data. We show that exploiting temporal characteristics of user behavior can enable effective partitioning for data locality without replication. We then build on this concept and demonstrate improved data locality by placing replicas sparingly. The result is a system which allows one to allocate a memory budget for replication and in return get a commensurate improvement in data locality.\"","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-04-13T21:47:28Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Stein_David.pdf: 1086860 bytes, checksum: fe28bd73bab0aeab36201e6627df4c97 (MD5)","Made available in DSpace on 2012-05-22T00:23:50Z (GMT). No. of bitstreams: 2 Stein_David.pdf: 1086860 bytes, checksum: fe28bd73bab0aeab36201e6627df4c97 (MD5) license.txt: 4061 bytes, checksum: cf4c4667b61311954b4cee98ba7753d6 (MD5)"]},{"key":"dc:title","label":"Title","values":["Partitioning social networks for data locality on a memory budget"]}]}],"canonical_facts":{"dc:contributor":["Lu, Yi"],"dc:creator":["Stein, David"],"dc:date":["2012-05-22T00:23:50Z","2012-05"],"dc:description":["\"Typical queries on online social network (OSN) applications are complex and require \"\"feeds\"\" to be compiled with timely information about many friends and friends' friends, which may be stored across many servers. Partitioning the OSN social graph in such a way as to promote data locality, i.e. such that a user's data will be stored on the same server as his friends' data, has proven difficult to do, and many existing OSN partitioning systems do not even attempt this. However, recent work has demonstrated techniques that do achieve data locality for social network queries by placing replicas of user data. We show that exploiting temporal characteristics of user behavior can enable effective partitioning for data locality without replication. We then build on this concept and demonstrate improved data locality by placing replicas sparingly. The result is a system which allows one to allocate a memory budget for replication and in return get a commensurate improvement in data locality.\"","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-04-13T21:47:28Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Stein_David.pdf: 1086860 bytes, checksum: fe28bd73bab0aeab36201e6627df4c97 (MD5)","Made available in DSpace on 2012-05-22T00:23:50Z (GMT). No. of bitstreams: 2 Stein_David.pdf: 1086860 bytes, checksum: fe28bd73bab0aeab36201e6627df4c97 (MD5) license.txt: 4061 bytes, checksum: cf4c4667b61311954b4cee98ba7753d6 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/31040"],"dc:language":["en"],"dc:rights":["Copyright 2012 David Stein"],"dc:subject":["Social networks","Partitioning","Locality"],"dc:title":["Partitioning social networks for data locality on a memory budget"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:29Z"}