{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T05:09:35Z","timestamp":1725253775077},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,2]]},"abstract":"Much work has been devoted to supporting RDF data. But state-of-the-art systems and methods still cannot handle web scale RDF data effectively. Furthermore, many useful and general purpose graph-based operations (e.g., random walk, reachability, community discovery) on RDF data are not supported, as most existing systems store and index data in particular ways (e.g., as relational tables or as a bitmap matrix) to maximize one particular operation on RDF data: SPARQL query processing. In this paper, we introduce Trinity. RDF, a distributed, memory-based graph engine for web scale RDF data. Instead of managing the RDF data in triple stores or as bitmap matrices, we store RDF data in its native graph form. It achieves much better (sometimes orders of magnitude better) performance for SPARQL queries than the state-of-the-art approaches. Furthermore, since the data is stored in its native graph form, the system can support other operations (e.g., random walks, reachability) on RDF graphs as well. We conduct comprehensive experimental studies on real life, web scale RDF data to demonstrate the effectiveness of our approach.<\/jats:p>","DOI":"10.14778\/2535570.2488333","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"265-276","source":"Crossref","is-referenced-by-count":199,"title":["A distributed graph engine for web scale RDF data"],"prefix":"10.14778","volume":"6","author":[{"given":"Kai","family":"Zeng","sequence":"first","affiliation":[{"name":"UCLA"}]},{"given":"Jiacheng","family":"Yang","sequence":"additional","affiliation":[{"name":"Columbia University"}]},{"given":"Haixun","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia"}]},{"given":"Bin","family":"Shao","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia"}]},{"given":"Zhongyuan","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia and Renmin University of China"}]}],"member":"320","published-online":{"date-parts":[[2013,2]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Billion Triple Challenge. http:\/\/challenge.semanticweb.org\/. Billion Triple Challenge. http:\/\/challenge.semanticweb.org\/."},{"key":"e_1_2_1_2_1","unstructured":"DBpedia SPARQL Benchmark (DBPSB). http:\/\/aksw.org\/Projects\/DBPSB. DBpedia SPARQL Benchmark (DBPSB). http:\/\/aksw.org\/Projects\/DBPSB."},{"key":"e_1_2_1_3_1","unstructured":"Jena. http:\/\/jena.sourceforge.net. Jena. http:\/\/jena.sourceforge.net."},{"key":"e_1_2_1_4_1","unstructured":"Trinity. http:\/\/research.microsoft.com\/en-us\/projects\/trinity\/. Trinity. http:\/\/research.microsoft.com\/en-us\/projects\/trinity\/."},{"issue":"2","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s00778-008-0125-y","article-title":"SW-Store: a vertically partitioned DBMS for Semantic Web data management","volume":"18","author":"Abadi D. J.","year":"2009","unstructured":"D. J. Abadi , A. Marcus , S. Madden , and K. Hollenbach . SW-Store: a vertically partitioned DBMS for Semantic Web data management . VLDB J. , 18 ( 2 ): 385 - 406 , 2009 . D. J. Abadi, A. Marcus, S. Madden, and K. Hollenbach. SW-Store: a vertically partitioned DBMS for Semantic Web data management. VLDB J., 18(2):385-406, 2009.","journal-title":"VLDB J."},{"key":"e_1_2_1_6_1","volume-title":"SemWeb","author":"Alexaki S.","year":"2001","unstructured":"S. Alexaki , V. Christophides , G. Karvounarakis , D. Plexousakis , and K. Tolle . The ICS-FORTH RDFSuite: Managing Voluminous RDF Description Bases . In SemWeb , 2001 . S. Alexaki, V. Christophides, G. Karvounarakis, D. Plexousakis, and K. Tolle. The ICS-FORTH RDFSuite: Managing Voluminous RDF Description Bases. In SemWeb, 2001."},{"key":"e_1_2_1_7_1","first-page":"346","volume-title":"ESWC","author":"Angles R.","year":"2005","unstructured":"R. Angles and C. Guti\u00e9rrez . Querying rdf data from a graph database perspective . In ESWC , pages 346 - 360 , 2005 . R. Angles and C. Guti\u00e9rrez. Querying rdf data from a graph database perspective. In ESWC, pages 346-360, 2005."},{"key":"e_1_2_1_8_1","first-page":"41","volume-title":"WWW","author":"Atre M.","year":"2010","unstructured":"M. Atre , V. Chaoji , M. J. Zaki , and J. A. Hendler . Matrix \"Bit\" loaded: a scalable lightweight join query processor for RDF data . In WWW , pages 41 - 50 , 2010 . M. Atre, V. Chaoji, M. J. Zaki, and J. A. Hendler. Matrix \"Bit\" loaded: a scalable lightweight join query processor for RDF data. In WWW, pages 41-50, 2010."},{"key":"e_1_2_1_9_1","first-page":"722","volume-title":"ISWC\/ASWC","author":"Auer S.","year":"2007","unstructured":"S. Auer , C. Bizer , G. Kobilarov , J. Lehmann , R. Cyganiak , and Z. G. Ives . DBpedia: A Nucleus for a Web of Open Data . In ISWC\/ASWC , pages 722 - 735 , 2007 . S. Auer, C. Bizer, G. Kobilarov, J. Lehmann, R. Cyganiak, and Z. G. Ives. DBpedia: A Nucleus for a Web of Open Data. In ISWC\/ASWC, pages 722-735, 2007."},{"issue":"1","key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/322234.322238","article-title":"Using Semi-Joins to Solve Relational Queries","volume":"28","author":"Bernstein P. A.","year":"1981","unstructured":"P. A. Bernstein and D.-M. W. Chiu . Using Semi-Joins to Solve Relational Queries . J. ACM , 28 ( 1 ): 25 - 40 , 1981 . P. A. Bernstein and D.-M. W. Chiu. Using Semi-Joins to Solve Relational Queries. J. ACM, 28(1):25-40, 1981.","journal-title":"J. ACM"},{"key":"e_1_2_1_11_1","first-page":"27","volume-title":"LA-WEB","author":"B\u00f6nstr\u00f6m V.","year":"2003","unstructured":"V. B\u00f6nstr\u00f6m , A. Hinze , and H. Schweppe . Storing rdf as a graph . In LA-WEB , pages 27 - 36 , 2003 . V. B\u00f6nstr\u00f6m, A. Hinze, and H. Schweppe. Storing rdf as a graph. In LA-WEB, pages 27-36, 2003."},{"key":"e_1_2_1_12_1","volume-title":"ISWC","author":"Broekstra J.","year":"2002","unstructured":"J. Broekstra , A. Kampman , and F. van Harmelen . Sesame : A Generic Architecture for Storing and Querying RDF and RDF Schema . In ISWC , 2002 . J. Broekstra, A. Kampman, and F. van Harmelen. Sesame: A Generic Architecture for Storing and Querying RDF and RDF Schema. In ISWC, 2002."},{"key":"e_1_2_1_13_1","first-page":"913","volume-title":"ICDE","author":"Cheng J.","year":"2008","unstructured":"J. Cheng , J. X. Yu , B. Ding , P. S. Yu , and H. Wang . Fast graph pattern matching . In ICDE , pages 913 - 922 , 2008 . J. Cheng, J. X. Yu, B. Ding, P. S. Yu, and H. Wang. Fast graph pattern matching. In ICDE, pages 913-922, 2008."},{"key":"e_1_2_1_14_1","volume-title":"VLDB","author":"Chong E. I.","year":"2005","unstructured":"E. I. Chong , S. Das , G. Eadon , and J. Srinivasan . An Efficient SQL-based RDF Querying Scheme . In VLDB , 2005 . E. I. Chong, S. Das, G. Eadon, and J. Srinivasan. An Efficient SQL-based RDF Querying Scheme. In VLDB, 2005."},{"key":"e_1_2_1_15_1","first-page":"501","volume-title":"Semantic Web Information Management","author":"Erling O.","year":"2009","unstructured":"O. Erling and I. Mikhailov . Virtuoso: RDF Support in a Native RDBMS . In Semantic Web Information Management , pages 501 - 519 . 2009 . O. Erling and I. Mikhailov. Virtuoso: RDF Support in a Native RDBMS. In Semantic Web Information Management, pages 501-519. 2009."},{"issue":"2","key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/j.websem.2005.06.005","article-title":"LUBM: A benchmark for OWL knowledge base systems","volume":"3","author":"Guo Y.","year":"2005","unstructured":"Y. Guo , Z. Pan , and J. Heflin . LUBM: A benchmark for OWL knowledge base systems . Journal of Web Semantics , 3 ( 2-3 ): 158 - 182 , 2005 . Y. Guo, Z. Pan, and J. Heflin. LUBM: A benchmark for OWL knowledge base systems. Journal of Web Semantics, 3(2-3):158-182, 2005.","journal-title":"Journal of Web Semantics"},{"key":"e_1_2_1_17_1","first-page":"211","volume-title":"ISWC\/ASWC","author":"Harth A.","year":"2007","unstructured":"A. Harth , J. Umbrich , A. Hogan , and S. Decker . Yars2: A federated repository for querying graph structured data from the web . In ISWC\/ASWC , pages 211 - 224 , 2007 . A. Harth, J. Umbrich, A. Hogan, and S. Decker. Yars2: A federated repository for querying graph structured data from the web. In ISWC\/ASWC, pages 211-224, 2007."},{"key":"e_1_2_1_18_1","volume-title":"ISWC","author":"Hayes J.","year":"2004","unstructured":"J. Hayes and C. Gutierrez . Bipartite graphs as intermediate model for rdf . In ISWC , 2004 . J. Hayes and C. Gutierrez. Bipartite graphs as intermediate model for rdf. In ISWC, 2004."},{"key":"e_1_2_1_19_1","volume-title":"SIGMOD","author":"He H.","year":"2008","unstructured":"H. He and A. K. Singh . Graphs-at-a-time: query language and access methods for graph databases . In SIGMOD , 2008 . H. He and A. K. Singh. Graphs-at-a-time: query language and access methods for graph databases. In SIGMOD, 2008."},{"key":"e_1_2_1_20_1","volume-title":"Scalable SPARQL Querying of Large RDF Graphs. PVLDB, 4(11)","author":"Huang J.","year":"2011","unstructured":"J. Huang , D. J. Abadi , and K. Ren . Scalable SPARQL Querying of Large RDF Graphs. PVLDB, 4(11) , 2011 . J. Huang, D. J. Abadi, and K. Ren. Scalable SPARQL Querying of Large RDF Graphs. PVLDB, 4(11), 2011."},{"issue":"9","key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"1312","DOI":"10.1109\/TKDE.2011.103","volume":"23","author":"Husain M. F.","year":"2011","unstructured":"M. F. Husain , J. P. McGlothlin , M. M. Masud , L. R. Khan , and B. M. Thuraisingham . Heuristics-Based Query Processing for Large RDF Graphs Using Cloud Computing. IEEE Trans. Knowl. Data Eng. , 23 ( 9 ): 1312 - 1327 , 2011 . M. F. Husain, J. P. McGlothlin, M. M. Masud, L. R. Khan, and B. M. Thuraisingham. Heuristics-Based Query Processing for Large RDF Graphs Using Cloud Computing. IEEE Trans. Knowl. Data Eng., 23(9):1312-1327, 2011.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_22_1","first-page":"172","volume-title":"Manipulation and Inference on Databases. In WAIM","author":"Lu J.","year":"2005","unstructured":"J. Lu , Y. Yu , K. Tu , C. Lin , and L. Zhang . An Approach to RDF(S) Query , Manipulation and Inference on Databases. In WAIM , pages 172 - 183 , 2005 . J. Lu, Y. Yu, K. Tu, C. Lin, and L. Zhang. An Approach to RDF(S) Query, Manipulation and Inference on Databases. In WAIM, pages 172-183, 2005."},{"issue":"1","key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1142\/S0129626407002843","volume":"17","author":"Lumsdaine A.","year":"2007","unstructured":"A. Lumsdaine , D. Gregor , B. Hendrickson , and J. W. Berry . Challenges in Parallel Graph Processing. Parallel Processing Letters , 17 ( 1 ): 5 - 20 , 2007 . A. Lumsdaine, D. Gregor, B. Hendrickson, and J. W. Berry. Challenges in Parallel Graph Processing. Parallel Processing Letters, 17(1):5-20, 2007.","journal-title":"Challenges in Parallel Graph Processing. Parallel Processing Letters"},{"key":"e_1_2_1_24_1","volume-title":"SIGMOD","author":"Malewicz G.","year":"2010","unstructured":"G. Malewicz , M. H. Austern , A. J. C. Bik , J. C. Dehnert , I. Horn , N. Leiser , and G. Czajkowski . Pregel: a system for large-scale graph processing . In SIGMOD , 2010 . G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD, 2010."},{"key":"e_1_2_1_25_1","volume-title":"RDF-3X: a RISC-style engine for RDF. PVLDB, 1(1)","author":"Neumann T.","year":"2008","unstructured":"T. Neumann and G. Weikum . RDF-3X: a RISC-style engine for RDF. PVLDB, 1(1) , 2008 . T. Neumann and G. Weikum. RDF-3X: a RISC-style engine for RDF. PVLDB, 1(1), 2008."},{"key":"e_1_2_1_26_1","volume-title":"SIGMOD","author":"Neumann T.","year":"2009","unstructured":"T. Neumann and G. Weikum . Scalable Join Processing on Very Large RDF Graphs . In SIGMOD , 2009 . T. Neumann and G. Weikum. Scalable Join Processing on Very Large RDF Graphs. In SIGMOD, 2009."},{"issue":"1","key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00778-009-0165-y","article-title":"The RDF-3X engine for scalable management of RDF data","volume":"19","author":"Neumann T.","year":"2010","unstructured":"T. Neumann and G. Weikum . The RDF-3X engine for scalable management of RDF data . VLDB J. , 19 ( 1 ): 91 - 113 , 2010 . T. Neumann and G. Weikum. The RDF-3X engine for scalable management of RDF data. VLDB J., 19(1):91-113, 2010.","journal-title":"VLDB J."},{"key":"e_1_2_1_28_1","volume-title":"Finding and evaluating community structure in networks. Physical review E, 69(2):026113","author":"Newman M.","year":"2004","unstructured":"M. Newman and M. Girvan . Finding and evaluating community structure in networks. Physical review E, 69(2):026113 , 2004 . M. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical review E, 69(2):026113, 2004."},{"key":"e_1_2_1_29_1","volume-title":"PSI EtA","author":"Rohloff K.","year":"2010","unstructured":"K. Rohloff and R. E. Schantz . High-performance, massively scalable distributed systems using the MapReduce software framework: the SHARD triple-store . In PSI EtA , 2010 . K. Rohloff and R. E. Schantz. High-performance, massively scalable distributed systems using the MapReduce software framework: the SHARD triple-store. In PSI EtA, 2010."},{"key":"e_1_2_1_31_1","volume-title":"SIGMOD","author":"Shao B.","year":"2012","unstructured":"B. Shao , H. Wang , and Y. Xiao . Managing and mining large graphs: Systems and implementations . In SIGMOD , 2012 . B. Shao, H. Wang, and Y. Xiao. Managing and mining large graphs: Systems and implementations. In SIGMOD, 2012."},{"key":"e_1_2_1_32_1","volume-title":"WWW","author":"Stocker M.","year":"2008","unstructured":"M. Stocker , A. Seaborne , A. Bernstein , C. Kiefer , and D. Reynolds . SPARQL basic graph pattern optimization using selectivity estimation . In WWW , 2008 . M. Stocker, A. Seaborne, A. Bernstein, C. Kiefer, and D. Reynolds. SPARQL basic graph pattern optimization using selectivity estimation. In WWW, 2008."},{"issue":"9","key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"788","DOI":"10.14778\/2311906.2311907","article-title":"Efficient subgraph matching on billion node graphs","volume":"5","author":"Sun Z.","year":"2012","unstructured":"Z. Sun , H. Wang , H. Wang , B. Shao , and J. Li . Efficient subgraph matching on billion node graphs . Proceedings of the VLDB Endowment , 5 ( 9 ): 788 - 799 , 2012 . Z. Sun, H. Wang, H. Wang, B. Shao, and J. Li. Efficient subgraph matching on billion node graphs. Proceedings of the VLDB Endowment, 5(9):788-799, 2012.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_34_1","volume-title":"ICDE, page 75","author":"Wang H.","year":"2006","unstructured":"H. Wang , H. He , J. Yang , P. S. Yu , and J. X. Yu . Dual Labeling: Answering Graph Reachability Queries in Constant Time . In ICDE, page 75 , 2006 . H. Wang, H. He, J. Yang, P. S. Yu, and J. X. Yu. Dual Labeling: Answering Graph Reachability Queries in Constant Time. In ICDE, page 75, 2006."},{"issue":"1","key":"e_1_2_1_35_1","first-page":"1008","article-title":"Hexastore: sextuple indexing for semantic web data management","volume":"1","author":"Weiss C.","year":"2008","unstructured":"C. Weiss , P. Karras , and A. Bernstein . Hexastore: sextuple indexing for semantic web data management . PVLDB , 1 ( 1 ): 1008 - 1019 , 2008 . C. Weiss, P. Karras, and A. Bernstein. Hexastore: sextuple indexing for semantic web data management. PVLDB, 1(1):1008-1019, 2008.","journal-title":"PVLDB"},{"key":"e_1_2_1_36_1","first-page":"131","volume-title":"SWDB","author":"Wilkinson K.","year":"2003","unstructured":"K. Wilkinson , C. Sayers , H. A. Kuno , and D. Reynolds . Efficient RDF Storage and Retrieval in Jena2 . In SWDB , pages 131 - 150 , 2003 . K. Wilkinson, C. Sayers, H. A. Kuno, and D. Reynolds. Efficient RDF Storage and Retrieval in Jena2. In SWDB, pages 131-150, 2003."},{"key":"e_1_2_1_37_1","volume-title":"SIGMOD","author":"Wu W.","year":"2012","unstructured":"W. Wu , H. Li , H. Wang , and K. Zhu . Probase: A probabilistic taxonomy for text understanding . In SIGMOD , 2012 . W. Wu, H. Li, H. Wang, and K. Zhu. Probase: A probabilistic taxonomy for text understanding. In SIGMOD, 2012."},{"key":"e_1_2_1_38_1","first-page":"517","volume-title":"SIGMOD Conference","author":"Yang S.","year":"2012","unstructured":"S. Yang , X. Yan , B. Zong , and A. Khan . Towards effective partition management for large graphs . In SIGMOD Conference , pages 517 - 528 , 2012 . S. Yang, X. Yan, B. Zong, and A. Khan. Towards effective partition management for large graphs. In SIGMOD Conference, pages 517-528, 2012."},{"issue":"11","key":"e_1_2_1_39_1","first-page":"807","article-title":"Mining top-k large structural patterns in a massive network","volume":"4","author":"Zhu F.","year":"2011","unstructured":"F. Zhu , Q. Qu , D. Lo , X. Yan , J. Han , and P. S. Yu . Mining top-k large structural patterns in a massive network . PVLDB , 4 ( 11 ): 807 - 818 , 2011 . F. Zhu, Q. Qu, D. Lo, X. Yan, J. Han, and P. S. Yu. Mining top-k large structural patterns in a massive network. PVLDB, 4(11):807-818, 2011.","journal-title":"PVLDB"},{"issue":"1","key":"e_1_2_1_40_1","first-page":"886","article-title":"Pattern match query in a large graph database","volume":"2","author":"Zou L.","year":"2009","unstructured":"L. Zou , L. Chen , and M. T. \u00d6zsu . Distancejoin : Pattern match query in a large graph database . PVLDB , 2 ( 1 ): 886 - 897 , 2009 . L. Zou, L. Chen, and M. T. \u00d6zsu. Distancejoin: Pattern match query in a large graph database. PVLDB, 2(1):886-897, 2009.","journal-title":"PVLDB"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2535570.2488333","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:03:15Z","timestamp":1672225395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2535570.2488333"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["10.14778\/2535570.2488333"],"URL":"https:\/\/doi.org\/10.14778\/2535570.2488333","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,2]]}}}