{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T01:08:57Z","timestamp":1790384937960,"version":"4.1.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            In the real world a graph is often fragmented and distributed across different sites. This highlights the need for evaluating queries on distributed graphs. This paper proposes distributed evaluation algorithms for three classes of queries:\n            <jats:italic>reachability<\/jats:italic>\n            for determining whether one node can reach another,\n            <jats:italic>bounded reachability<\/jats:italic>\n            for deciding whether there exists a path of a bounded length between a pair of nodes, and\n            <jats:italic>regular reachability<\/jats:italic>\n            for checking whether there exists a path connecting two nodes such that the node labels on the path form a string in a given regular expression. We develop these algorithms based on\n            <jats:italic>partial evaluation<\/jats:italic>\n            , to explore parallel computation. When evaluating a query\n            <jats:italic>Q<\/jats:italic>\n            on a distributed graph\n            <jats:italic>G<\/jats:italic>\n            , we show that these algorithms possess the following\n            <jats:italic>performance guarantees, no matter how G<\/jats:italic>\n            is fragmented and distributed: (1) each site is visited\n            <jats:italic>only once<\/jats:italic>\n            ; (2) the total network traffic is determined by the size of\n            <jats:italic>Q<\/jats:italic>\n            and the fragmentation of\n            <jats:italic>G, independent of<\/jats:italic>\n            the size of\n            <jats:italic>G<\/jats:italic>\n            ; and (3) the response time is decided by the largest fragment of\n            <jats:italic>G rather than<\/jats:italic>\n            the entire\n            <jats:italic>G<\/jats:italic>\n            . In addition, we show that these algorithms can be readily implemented in the MapReduce framework. Using synthetic and real-life data, we experimentally verify that these algorithms are scalable on large graphs, regardless of how the graphs are distributed.\n          <\/jats:p>","DOI":"10.14778\/2350229.2350248","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1304-1316","source":"Crossref","is-referenced-by-count":37,"title":["Performance guarantees for distributed reachability queries"],"prefix":"10.14778","volume":"5","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"University of Edinburgh and Harbin Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yinghui","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Edinburgh and UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739056"},{"key":"e_1_2_1_2_1","volume-title":"ADBIS Research Communic","author":"Anh V. L.","year":"2007"},{"key":"e_1_2_1_3_1","first-page":"211","volume-title":"VLDB","author":"Buneman P.","year":"2006"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247537"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454167"},{"key":"e_1_2_1_10_1","first-page":"3","article-title":"Algorithms for graph partitioning: A survey","author":"Fj\u00e4llstr\u00f6m P.-O.","year":"1998","journal-title":"Link\u00f6ping Electronic Articles in Computer and Information Science"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87993-0_17"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1496091.1496103"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094844"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11560647_35"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1748"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10665-1_72"},{"key":"e_1_2_1_17_1","volume-title":"A distributed method for trust-aware recommendation in social networks. CoRR, abs\/1011.2245","author":"Jamali M.","year":"2010"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/243439.243447"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/371578.371598"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_22_1","first-page":"185","volume-title":"VLDB","author":"Mendelzon A. O.","year":"1989"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454216"},{"key":"e_1_2_1_24_1","volume-title":"Principles of Distributed Database Systems","author":"Ozsu M. T.","year":"1999"},{"key":"e_1_2_1_25_1","volume-title":"Divide and conquer: Partitioning online social networks. CoRR, abs\/0905.4918","author":"Pujol J. M.","year":"2009"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1789394.1789443"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of Linked Data on the Web Workshop, WWW","author":"Rowe M.","year":"2009"},{"key":"e_1_2_1_28_1","unstructured":"M. Sevalnev. From prefix computation on pram for finding euler tours to usage of hadoop-framework for distributed breadth first search. http:\/\/www.cs.hut.fi\/.  M. Sevalnev. From prefix computation on pram for finding euler tours to usage of hadoop-framework for distributed breadth first search. http:\/\/www.cs.hut.fi\/."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.061"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/507234.507235"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_6"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/647911.740642"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:27:34Z","timestamp":1672226854000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":32,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350248"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350248","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}