{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,8]],"date-time":"2023-09-08T00:04:57Z","timestamp":1694131497638},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>With the rapid growth of large graphs, we cannot assume that graphs can still be fully loaded into memory, thus the disk-based graph operation is inevitable. In this paper, we take the shortest path discovery as an example to investigate the technique issues when leveraging existing infrastructure of relational database (RDB) in the graph data management.<\/jats:p>\n          <jats:p>\n            Based on the observation that a variety of graph search queries can be implemented by iterative operations including selecting frontier nodes from visited nodes, making expansion from the selected frontier nodes, and merging the expanded nodes into the visited ones, we introduce a relational\n            <jats:italic>FEM<\/jats:italic>\n            framework with three corresponding operators to implement graph search tasks in the RDB context. We show new features such as\n            <jats:italic>window function<\/jats:italic>\n            and\n            <jats:italic>merge statement<\/jats:italic>\n            introduced by recent SQL standards can not only simplify the expression but also improve the performance of the\n            <jats:italic>FEM<\/jats:italic>\n            framework. In addition, we propose two optimization strategies specific to shortest path discovery inside the\n            <jats:italic>FEM<\/jats:italic>\n            framework. First, we take a bi-directional set Dijkstra's algorithm in the path finding. The bi-directional strategy can reduce the search space, and set Dijkstra's algorithm finds the shortest path in a set-at-a-time fashion. Second, we introduce an index named SegTable to preserve the local shortest segments, and exploit SegTable to further improve the performance. The final extensive experimental results illustrate our relational approach with the optimization strategies achieves high scalability and performance.\n          <\/jats:p>","DOI":"10.14778\/2095686.2095694","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"358-369","source":"Crossref","is-referenced-by-count":23,"title":["Relational approach for shortest path discovery over large graphs"],"prefix":"10.14778","volume":"5","author":[{"given":"Jun","family":"Gao","sequence":"first","affiliation":[{"name":"Peking University"}]},{"given":"Ruoming","family":"Jin","sequence":"additional","affiliation":[{"name":"Kent State University"}]},{"given":"Jiashuai","family":"Zhou","sequence":"additional","affiliation":[{"name":"Peking University"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong"}]},{"given":"Xiao","family":"Jiang","sequence":"additional","affiliation":[{"name":"Peking University"}]},{"given":"Tengjiao","family":"Wang","sequence":"additional","affiliation":[{"name":"Peking University"}]}],"member":"320","published-online":{"date-parts":[[2011,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache Hadoop. http:\/\/hadoop.apache.org. Apache Hadoop . http:\/\/hadoop.apache.org."},{"key":"e_1_2_1_2_1","first-page":"156","volume-title":"SODA","author":"Goldberg A.","year":"2005","unstructured":"A. Goldberg and C. Harrelson . Computing the shortest path: search meets graph theory . In SODA , pages 156 -- 165 , 2005 . A. Goldberg and C. Harrelson. Computing the shortest path: search meets graph theory. In SODA, pages 156--165, 2005."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989425"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11731139_75"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687725"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807178"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014088"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00217-2"},{"key":"e_1_2_1_9_1","volume-title":"The traveling salesman problem: A case study in local optimization. Local search in combinatorial optimization, 215--310","author":"Johnson D.","year":"1997","unstructured":"D. Johnson and L. McGeoch . The traveling salesman problem: A case study in local optimization. Local search in combinatorial optimization, 215--310 , 1997 . D. Johnson and L. McGeoch. The traveling salesman problem: A case study in local optimization. Local search in combinatorial optimization, 215--310, 1997."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1763424.1763428"},{"key":"e_1_2_1_11_1","first-page":"937","volume-title":"SODA","author":"Cohen E.","year":"2002","unstructured":"E. Cohen , E. Halperin , H. Kaplan , and U. Zwick . Reachability and distance queries via 2-hop labels . In SODA , pages 937 -- 946 , 2002 . E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. In SODA, pages 937--946, 2002."},{"key":"e_1_2_1_12_1","first-page":"269","volume-title":"Numerische Mathematik","author":"Dijkstra E.","year":"1959","unstructured":"E. Dijkstra . A note on two problems in connexion with graphs . Numerische Mathematik , pages 269 -- 271 , 1959 . E. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, pages 269--271, 1959."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007623"},{"key":"e_1_2_1_14_1","volume-title":"Database Systems: The Complete Book","author":"Garcia-Molina H.","year":"2008","unstructured":"H. Garcia-Molina , J. Ullman , and J. Widom . Database Systems: The Complete Book . Prentice Hall Press , 2008 . H. Garcia-Molina, J. Ullman, and J. Widom. Database Systems: The Complete Book. Prentice Hall Press, 2008."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807217"},{"key":"e_1_2_1_16_1","first-page":"137","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . Mapreduce: Simplified data processing on large clusters . In OSDI , pages 137 -- 150 , 2004 . J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. In OSDI, pages 137--150, 2004."},{"key":"e_1_2_1_17_1","first-page":"302","volume-title":"VLDB","author":"Shanmugasundaram J.","year":"1999","unstructured":"J. Shanmugasundaram , K. Tufte , C. Zhang , G. He , D. DeWitt , and J. Naughton . Relational databases for querying xml documents: Limitations and opportunities . In VLDB , pages 302 -- 314 , 1999 . J. Shanmugasundaram, K. Tufte, C. Zhang, G. He, D. DeWitt, and J. Naughton. Relational databases for querying xml documents: Limitations and opportunities. In VLDB, pages 302--314, 1999."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287441"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646063"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.172"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13672-6_16"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247573"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2095686.2095694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:46:20Z","timestamp":1672220780000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2095686.2095694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.14778\/2095686.2095694"],"URL":"https:\/\/doi.org\/10.14778\/2095686.2095694","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}