{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:24:59Z","timestamp":1742912699005,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030611323"},{"type":"electronic","value":"9783030611330"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-61133-0_4","type":"book-chapter","created":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T10:04:54Z","timestamp":1604570694000},"page":"49-62","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Scalable In-Memory Graph Pattern Matching on Symmetric Multiprocessor Systems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2616-8739","authenticated-orcid":false,"given":"Alexander","family":"Krause","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8671-5466","authenticated-orcid":false,"given":"Dirk","family":"Habich","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8107-2775","authenticated-orcid":false,"given":"Wolfgang","family":"Lehner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,6]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Angles, R.: A comparison of current graph database models. In: ICDE Workshop, pp. 171\u2013177 (2012)","DOI":"10.1109\/ICDEW.2012.31"},{"issue":"2","key":"4_CR2","first-page":"121","volume":"11","author":"R Appuswamy","year":"2017","unstructured":"Appuswamy, R., Anadiotis, A., Porobic, D., Iman, M., Ailamaki, A.: Analyzing the impact of system architecture on the scalability of OLTP engines for high-contention workloads. PVLDB 11(2), 121\u2013134 (2017)","journal-title":"PVLDB"},{"issue":"4","key":"4_CR3","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1109\/TKDE.2016.2633993","volume":"29","author":"G Bagan","year":"2017","unstructured":"Bagan, G., Bonifati, A., Ciucanu, R., Fletcher, G.H.L., Lemay, A., Advokaat, N.: gmark: schema-driven generation of graphs and queries. IEEE Trans. Knowl. Data Eng. 29(4), 856\u2013869 (2017)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"4_CR4","volume-title":"Pattern Recognition and Machine Learning","author":"CM Bishop","year":"2006","unstructured":"Bishop, C.M.: Pattern Recognition and Machine Learning. Springer, New York (2006)"},{"issue":"7","key":"4_CR5","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422\u2013426 (1970)","journal-title":"Commun. ACM"},{"issue":"4","key":"4_CR6","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/2094114.2094126","volume":"40","author":"F F\u00e4rber","year":"2011","unstructured":"F\u00e4rber, F., Cha, S.K., Primsch, J., Bornh\u00f6vd, C., Sigg, S., Lehner, W.: SAP HANA database: data management for modern business applications. SIGMOD Rec. 40(4), 45\u201351 (2011)","journal-title":"SIGMOD Rec."},{"key":"4_CR7","unstructured":"Hey, T., Tansley, S., Tolle, K.M. (eds.): The Fourth Paradigm: Data-Intensive Scientific Discovery. Microsoft Research (2009)"},{"key":"4_CR8","unstructured":"Hyafil, L., Rivest, R.L.: Graph partitioning and constructing optimal decision trees are polynomial complete problems. IRIA, Laboratoire de Recherche en Informatique et Automatique (1973)"},{"key":"4_CR9","unstructured":"Karypis, G., Kumar, V.: MeTis: unstructured graph partitioning and sparse matrix ordering system, Version 5.1 (2013). http:\/\/www.cs.umn.edu\/~metis"},{"key":"4_CR10","unstructured":"Kiefer, T., Schlegel, B., Lehner, W.: Experimental evaluation of NUMA effects on database management systems. In: BTW, pp. 185\u2013204 (2013)"},{"key":"4_CR11","unstructured":"Kissinger, T., Kiefer, T., Schlegel, B., Habich, D., Molka, D., Lehner, W.: ERIS: A numa-aware in-memory storage engine for analytical workload. In: ADMS@VLDB, pp. 74\u201385 (2014)"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Krause, A., Ebner, F., Habich, D., Lehner, W.: Trading memory versus workload overhead in graph pattern matching on multiprocessor systems. In: DATA, pp. 400\u2013407 (2019)","DOI":"10.5220\/0008116904000407"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Krause, A., Kissinger, T., Habich, D., Lehner, W.: Nemesys - A showcase of data oriented near memory graph processing. In: Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30\u2013July 5, pp. 1945\u20131948 (2019)","DOI":"10.1145\/3299869.3320226"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-319-64203-1_11","volume-title":"Euro-Par 2017: Parallel Processing","author":"A Krause","year":"2017","unstructured":"Krause, A., Kissinger, T., Habich, D., Voigt, H., Lehner, W.: Partitioning strategy selection for in-memory graph pattern matching on multiprocessor systems. In: Rivera, F.F., Pena, T.F., Cabaleiro, J.C. (eds.) Euro-Par 2017. LNCS, vol. 10417, pp. 149\u2013163. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-64203-1_11"},{"key":"4_CR15","series-title":"Communications in Computer and Information Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-319-67162-8_6","volume-title":"New Trends in Databases and Information Systems","author":"A Krause","year":"2017","unstructured":"Krause, A., Ungeth\u00fcm, A., Kissinger, T., Habich, D., Lehner, W.: Asynchronous graph pattern matching on multiprocessor systems. In: Kirikova, M., N\u00f8rv\u00e5g, K., Papadopoulos, G.A., Gamper, J., Wrembel, R., Darmont, J., Rizzi, S. (eds.) ADBIS 2017. CCIS, vol. 767, pp. 45\u201353. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-67162-8_6"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Leis, V., Boncz, P.A., Kemper, A., Neumann, T.: Morsel-driven parallelism: a numa-aware query evaluation framework for the many-core age. In: SIGMOD, pp. 743\u2013754 (2014)","DOI":"10.1145\/2588555.2610507"},{"issue":"3","key":"4_CR17","first-page":"281","volume":"8","author":"Y Lu","year":"2014","unstructured":"Lu, Y., Cheng, J., Yan, D., Wu, H.: Large-scale distributed graph computing systems: an experimental evaluation. PVLDB 8(3), 281\u2013292 (2014)","journal-title":"PVLDB"},{"issue":"2","key":"4_CR18","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/2818185","volume":"48","author":"RR McCune","year":"2015","unstructured":"McCune, R.R., Weninger, T., Madey, G.: Thinking like a vertex: a survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Comput. Surv. 48(2), 25:1\u201325:39 (2015)","journal-title":"ACM Comput. Surv."},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Nguyen, D., Lenharth, A., Pingali, K.: A lightweight infrastructure for graph analytics. In: SOSP, pp. 456\u2013471 (2013)","DOI":"10.1145\/2517349.2522739"},{"issue":"20","key":"4_CR20","doi-asserted-by":"publisher","first-page":"4021","DOI":"10.1093\/nar\/28.20.4021","volume":"28","author":"H Ogata","year":"2000","unstructured":"Ogata, H., Fujibuchi, W., Goto, S., Kanehisa, M.: A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters. Nucleic Acids Res. 28(20), 4021\u20134028 (2000)","journal-title":"Nucleic Acids Res."},{"issue":"6","key":"4_CR21","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1177\/016555150202800601","volume":"28","author":"E Otte","year":"2002","unstructured":"Otte, E., Rousseau, R.: Social network analysis: a powerful strategy, also for the information sciences. J. Inf. Sci. 28(6), 441\u2013453 (2002)","journal-title":"J. Inf. Sci."},{"issue":"1","key":"4_CR22","first-page":"928","volume":"3","author":"I Pandis","year":"2010","unstructured":"Pandis, I., Johnson, R., Hardavellas, N., Ailamaki, A.: Data-oriented transaction execution. PVLDB 3(1), 928\u2013939 (2010)","journal-title":"PVLDB"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Pandit, S., Chau, D.H., Wang, S., Faloutsos, C.: NetProbe: a fast and scalable system for fraud detection in online auction networks. In: WWW, pp. 201\u2013210 (2007)","DOI":"10.1145\/1242572.1242600"},{"issue":"3","key":"4_CR24","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/1015706.1015720","volume":"23","author":"C Rother","year":"2004","unstructured":"Rother, C., Kolmogorov, V., Blake, A.: \u201cgrabcut\u201d: interactive foreground extraction using iterated graph cuts. ACM Trans. Graph. 23(3), 309\u2013314 (2004)","journal-title":"ACM Trans. Graph."},{"issue":"4","key":"4_CR25","first-page":"420","volume":"11","author":"S Sahu","year":"2017","unstructured":"Sahu, S., Mhedhbi, A., Salihoglu, S., Lin, J., \u00d6zsu, M.T.: The ubiquity of large graphs and surprising challenges of graph processing. PVLDB 11(4), 420\u2013431 (2017)","journal-title":"PVLDB"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Shun, J., Blelloch, G.E.: Ligra: a lightweight graph processing framework for shared memory. In: PPoPP, pp. 135\u2013146 (2013)","DOI":"10.1145\/2517327.2442530"},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"Tas, M.K., Kaya, K., Saule, E.: Greed is good: optimistic algorithms for bipartite-graph partial coloring on multicore architectures. CoRR abs\/1701.02628 (2017)","DOI":"10.1109\/ICPP.2017.59"},{"issue":"1","key":"4_CR28","first-page":"1008","volume":"1","author":"C Weiss","year":"2008","unstructured":"Weiss, C., Karras, P., Bernstein, A.: Hexastore: sextuple indexing for semantic web data management. PVLDB 1(1), 1008\u20131019 (2008)","journal-title":"PVLDB"},{"issue":"1","key":"4_CR29","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/2206869.2206879","volume":"41","author":"PT Wood","year":"2012","unstructured":"Wood, P.T.: Query languages for graph databases. SIGMOD Rec. 41(1), 50\u201360 (2012)","journal-title":"SIGMOD Rec."},{"key":"4_CR30","doi-asserted-by":"crossref","unstructured":"Yan, D., Cheng, J., Lu, Y., Ng, W.: Effective techniques for message reduction and load balancing in distributed graph computation. In: WWW, pp. 1307\u20131317 (2015)","DOI":"10.1145\/2736277.2741096"},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"Zhang, K., Chen, R., Chen, H.: NUMA-aware graph-structured analytics. In: PPoPP, pp. 183\u2013193 (2015)","DOI":"10.1145\/2858788.2688507"}],"container-title":["Communications in Computer and Information Science","Software Foundations for Data Interoperability and Large Scale Graph Data Analytics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-61133-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,24]],"date-time":"2021-04-24T18:13:35Z","timestamp":1619288015000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-61133-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030611323","9783030611330"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-61133-0_4","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"6 November 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LSGDA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Large Scale Graph Data Analytics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tokyo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"lsgda2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/lsgda.github.io\/2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"CMT","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"18","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2,8","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the COVID-19 pandemic the conference was held online.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}