{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/46650"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/46650","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Storage and processing systems for power-law graphs","abstract":"Large graphs abound around us - online social networks, Web graphs, the Internet, citation networks, protein interaction networks, telephone call graphs, peer-to-peer overlay networks, electric power grid networks, etc. Many real- life graphs are power-law graphs. A fundamental challenge in today’s Big Data world is storage and processing of these large-scale power-law graphs. In this thesis, we show that graph processing can be made faster and graph storage can be made more efficient by using techniques that leverage the structure of the underlying power-law graphs. To this end, we present two systems. First, we present LFGraph, which is a fast, distributed, in- memory graph analytics platform. LFGraph leverages the structure and characteristics of power-law graphs in order to reduce communication overhead, and to balance communication and computation load. This makes analytics faster on power-law graphs. Next, we present Bondhu, which is a disk layout manager for graph databases. Bondhu exploits the fact that most real-life power-law graphs are also small-world and these exhibit strong com- munity structure. Bondhu utilizes this community structure in order to make layout decisions. This improves the query response time of graph databases. Our systems are evaluated on real clusters using real-world graphs.","abstract_html":"Large graphs abound around us - online social networks, Web graphs, the Internet, citation networks, protein interaction networks, telephone call graphs, peer-to-peer overlay networks, electric power grid networks, etc. Many real- life graphs are power-law graphs. A fundamental challenge in today’s Big Data world is storage and processing of these large-scale power-law graphs. In this thesis, we show that graph processing can be made faster and graph storage can be made more efficient by using techniques that leverage the structure of the underlying power-law graphs. To this end, we present two systems. First, we present LFGraph, which is a fast, distributed, in- memory graph analytics platform. LFGraph leverages the structure and characteristics of power-law graphs in order to reduce communication overhead, and to balance communication and computation load. This makes analytics faster on power-law graphs. Next, we present Bondhu, which is a disk layout manager for graph databases. Bondhu exploits the fact that most real-life power-law graphs are also small-world and these exhibit strong com- munity structure. Bondhu utilizes this community structure in order to make layout decisions. This improves the query response time of graph databases. Our systems are evaluated on real clusters using real-world graphs.","abstract_has_math":false,"creators":["Hoque, Imranul"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Gupta, Indranil","Zhai, ChengXiang","Snir, Marc","Steinder, Malgorzata"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-01-16T17:57:32Z","date_published":"2014-01-16T17:57:32Z","updated_at":"2026-07-22T22:25:36Z","subjects":["Graph","Storage","Analytics","Distributed System","Power-Law"],"languages":["en"],"rights":["Copyright 2013 Imranul Hoque"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/46650","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Gupta, Indranil","Zhai, ChengXiang","Snir, Marc","Steinder, Malgorzata"]},{"key":"dc:creator","label":"Author","values":["Hoque, Imranul"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-01-16T17:57:32Z","2013-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Graph","Storage","Analytics","Distributed System","Power-Law"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Imranul Hoque"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/46650"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Large graphs abound around us - online social networks, Web graphs, the Internet, citation networks, protein interaction networks, telephone call graphs, peer-to-peer overlay networks, electric power grid networks, etc. Many real- life graphs are power-law graphs. A fundamental challenge in today’s Big Data world is storage and processing of these large-scale power-law graphs. In this thesis, we show that graph processing can be made faster and graph storage can be made more efficient by using techniques that leverage the structure of the underlying power-law graphs. To this end, we present two systems. First, we present LFGraph, which is a fast, distributed, in- memory graph analytics platform. LFGraph leverages the structure and characteristics of power-law graphs in order to reduce communication overhead, and to balance communication and computation load. This makes analytics faster on power-law graphs. Next, we present Bondhu, which is a disk layout manager for graph databases. Bondhu exploits the fact that most real-life power-law graphs are also small-world and these exhibit strong com- munity structure. Bondhu utilizes this community structure in order to make layout decisions. This improves the query response time of graph databases. Our systems are evaluated on real clusters using real-world graphs.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-09-04T22:01:07Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Hoque_Imranul.pdf: 2143095 bytes, checksum: 6c38e7d1abe53bd83980adfaeb87a2a1 (MD5)","Made available in DSpace on 2014-01-16T17:57:32Z (GMT). No. of bitstreams: 2 Imranul_Hoque.pdf: 2143095 bytes, checksum: 6c38e7d1abe53bd83980adfaeb87a2a1 (MD5) license.txt: 4062 bytes, checksum: 2979a4d8079fd9e57a8d9e67067f048c (MD5)"]},{"key":"dc:title","label":"Title","values":["Storage and processing systems for power-law graphs"]}]}],"canonical_facts":{"dc:contributor":["Gupta, Indranil","Zhai, ChengXiang","Snir, Marc","Steinder, Malgorzata"],"dc:creator":["Hoque, Imranul"],"dc:date":["2014-01-16T17:57:32Z","2013-12"],"dc:description":["Large graphs abound around us - online social networks, Web graphs, the Internet, citation networks, protein interaction networks, telephone call graphs, peer-to-peer overlay networks, electric power grid networks, etc. Many real- life graphs are power-law graphs. A fundamental challenge in today’s Big Data world is storage and processing of these large-scale power-law graphs. In this thesis, we show that graph processing can be made faster and graph storage can be made more efficient by using techniques that leverage the structure of the underlying power-law graphs. To this end, we present two systems. First, we present LFGraph, which is a fast, distributed, in- memory graph analytics platform. LFGraph leverages the structure and characteristics of power-law graphs in order to reduce communication overhead, and to balance communication and computation load. This makes analytics faster on power-law graphs. Next, we present Bondhu, which is a disk layout manager for graph databases. Bondhu exploits the fact that most real-life power-law graphs are also small-world and these exhibit strong com- munity structure. Bondhu utilizes this community structure in order to make layout decisions. This improves the query response time of graph databases. Our systems are evaluated on real clusters using real-world graphs.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-09-04T22:01:07Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Hoque_Imranul.pdf: 2143095 bytes, checksum: 6c38e7d1abe53bd83980adfaeb87a2a1 (MD5)","Made available in DSpace on 2014-01-16T17:57:32Z (GMT). No. of bitstreams: 2 Imranul_Hoque.pdf: 2143095 bytes, checksum: 6c38e7d1abe53bd83980adfaeb87a2a1 (MD5) license.txt: 4062 bytes, checksum: 2979a4d8079fd9e57a8d9e67067f048c (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/46650"],"dc:language":["en"],"dc:rights":["Copyright 2013 Imranul Hoque"],"dc:subject":["Graph","Storage","Analytics","Distributed System","Power-Law"],"dc:title":["Storage and processing systems for power-law graphs"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:36Z"}