{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T08:21:43Z","timestamp":1792743703926,"version":"4.5.0"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030307929","type":"print"},{"value":"9783030307936","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-30793-6_15","type":"book-chapter","created":{"date-parts":[[2019,10,16]],"date-time":"2019-10-16T19:05:00Z","timestamp":1571252700000},"page":"258-275","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":44,"title":["A Worst-Case Optimal Join Algorithm for SPARQL"],"prefix":"10.1007","author":[{"given":"Aidan","family":"Hogan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carlos","family":"Rojas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adri\u00e1n","family":"Soto","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,10,17]]},"reference":[{"key":"15_CR1","unstructured":"Apache Jena. https:\/\/jena.apache.org\/. Accessed 30 Dec 2018"},{"key":"15_CR2","unstructured":"Github project. https:\/\/gqgh5wfgzt.github.io\/benchmark-leapfrog\/"},{"key":"15_CR3","unstructured":"SPARQL 1.1 Query Language. https:\/\/www.w3.org\/TR\/sparql11-query\/. Accessed 30 Dec 2018"},{"issue":"4","key":"15_CR4","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/3129246","volume":"42","author":"CR Aberger","year":"2017","unstructured":"Aberger, C.R., Lamb, A., Tu, S., N\u00f6tzli, A., Olukotun, K., R\u00e9, C.: EmptyHeaded: a relational engine for graph processing. ACM Trans. Database Syst. (TODS) 42(4), 20 (2017)","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Abo Khamis, M., Ngo, H.Q., Rudra, A.: FAQ: questions asked frequently. In: Principles of Database Systems (PODS), pp. 13\u201328. ACM (2016)","DOI":"10.1145\/2902251.2902280"},{"key":"15_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-319-11964-9_13","volume-title":"The Semantic Web \u2013 ISWC 2014","author":"G Alu\u00e7","year":"2014","unstructured":"Alu\u00e7, G., Hartig, O., \u00d6zsu, M.T., Daudjee, K.: Diversified stress testing of RDF data management systems. In: Mika, P., et al. (eds.) ISWC 2014. LNCS, vol. 8796, pp. 197\u2013212. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11964-9_13"},{"key":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-319-46523-4_2","volume-title":"The Semantic Web \u2013 ISWC 2016","author":"R Angles","year":"2016","unstructured":"Angles, R., Gutierrez, C.: The multiset semantics of SPARQL patterns. In: Groth, P., et al. (eds.) ISWC 2016. LNCS, vol. 9981, pp. 20\u201336. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-46523-4_2"},{"key":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/978-3-642-41338-4_18","volume-title":"The Semantic Web \u2013 ISWC 2013","author":"C Buil-Aranda","year":"2013","unstructured":"Buil-Aranda, C., Hogan, A., Umbrich, J., Vandenbussche, P.-Y.: SPARQL web-querying infrastructure: ready for action? ISWC 2013. LNCS, vol. 8219, pp. 277\u2013293. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-41338-4_18"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Aref, M.: Design and implementation of the LogicBlox system. In: SIGMOD International Conference on Management of Data, pp. 1371\u20131382. ACM (2015)","DOI":"10.1145\/2723372.2742796"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Atre, M., Chaoji, V., Zaki, M.J., Hendler, J.A.: Matrix \u201cBit\u201d loaded: a scalable lightweight join query processor for RDF data. In: World Wide Web (WWW), pp. 41\u201350 (2010)","DOI":"10.1145\/1772690.1772696"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Atserias, A., Grohe, M., Marx, D.: Size bounds and query plans for relational joins. In: Foundations of Computer Science (FOCS), pp. 739\u2013748. IEEE (2008)","DOI":"10.1109\/FOCS.2008.43"},{"key":"15_CR12","unstructured":"Barbay, J., Kenyon, C.: Adaptive intersection and t-threshold problems. In: Symposium on Discrete Algorithms (SODA), pp. 390\u2013399. Society for Industrial and Applied Mathematics (2002)"},{"issue":"2","key":"15_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4018\/jswis.2009040101","volume":"5","author":"C Bizer","year":"2009","unstructured":"Bizer, C., Schultz, A.: The Berlin SPARQL benchmark. Int. J. Semant. Web Inf. Syst. (IJSWIS) 5(2), 1\u201324 (2009)","journal-title":"Int. J. Semant. Web Inf. Syst. (IJSWIS)"},{"issue":"2","key":"15_CR14","first-page":"149","volume":"11","author":"A Bonifati","year":"2017","unstructured":"Bonifati, A., Martens, W., Timm, T.: An analytical study of large SPARQL query logs. PVLDB 11(2), 149\u2013161 (2017)","journal-title":"PVLDB"},{"key":"15_CR15","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Adaptive set intersections, unions, and differences. In: Symposium on Discrete Algorithms (SODA). Citeseer (2000)"},{"key":"15_CR16","series-title":"Studies in Computational Intelligence","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/978-3-642-02184-8_2","volume-title":"Networked Knowledge - Networked Media","author":"O Erling","year":"2009","unstructured":"Erling, O., Mikhailov, I.: RDF support in the virtuoso DBMS. In: Pellegrini, T., Auer, S., Tochtermann, K., Schaffert, S. (eds.) Networked Knowledge - Networked Media. Studies in Computational Intelligence, vol. 221, pp. 7\u201324. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02184-8_2"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Galkin, M., Endris, K.M., Acosta, M., Collarana, D., Vidal, M., Auer, S.: SMJoin: a multi-way join operator for SPARQL queries. In: International Conference on Semantic Systems (SEMANTICS), pp. 104\u2013111 (2017)","DOI":"10.1145\/3132218.3132220"},{"key":"15_CR18","unstructured":"Harth, A., Decker, S.: Optimized index structures for querying RDF from the Web. In: Latin American Web Congress (LA-Web 2005), pp. 71\u201380 (2005)"},{"key":"15_CR19","doi-asserted-by":"publisher","unstructured":"Kalinsky, O., Etsion, Y., Kimelfeld B.: Flexible caching in Trie joins. In: International Conference on Extending Database Technology (EDBT), pp. 282\u2013293. Springer (2017). https:\/\/doi.org\/10.5441\/002\/edbt.2017.26","DOI":"10.5441\/002\/edbt.2017.26"},{"key":"15_CR20","unstructured":"Kalinsky, O., Mishali, O., Hogan, A., Etsion, Y., Kimelfeld, B.: Efficiently charting RDF. CoRR, abs\/1811.10955 (2018)"},{"issue":"4","key":"15_CR21","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/2967101","volume":"41","author":"MA Khamis","year":"2016","unstructured":"Khamis, M.A., Ngo, H.Q., R\u00e9, C., Rudra, A.: Joins via geometric resolutions: worst case and beyond. ACM Trans. Database Syst. (TODS) 41(4), 22 (2016)","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"15_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-030-00668-6_23","volume-title":"The Semantic Web \u2013 ISWC 2018","author":"S Malyshev","year":"2018","unstructured":"Malyshev, S., Kr\u00f6tzsch, M., Gonz\u00e1lez, L., Gonsior, J., Bielefeldt, A.: Getting the most out of Wikidata: semantic technology usage in Wikipedia\u2019s knowledge graph. In: Vrande\u010di\u0107, D., et al. (eds.) ISWC 2018. LNCS, vol. 11137, pp. 376\u2013394. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-00668-6_23"},{"issue":"1","key":"15_CR23","first-page":"647","volume":"1","author":"T Neumann","year":"2008","unstructured":"Neumann, T., Weikum, G.: RDF-3X: a RISC-style engine for RDF. PVLDB 1(1), 647\u2013659 (2008)","journal-title":"PVLDB"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Ngo, H.Q.: Worst-case optimal join algorithms: techniques, results, and open problems. In: Principles of Database Systems (PODS), pp. 111\u2013124. ACM (2018)","DOI":"10.1145\/3196959.3196990"},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"Ngo, H.Q., Nguyen, D.T., Re, C., Rudra, A.: Beyond worst-case analysis for joins with minesweeper. In: Principles of Database Systems (PODS), pp. 234\u2013245. ACM (2014)","DOI":"10.1145\/2594538.2594547"},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"Ngo, H.Q., Porat, E., R\u00e9, C., Rudra, A.: Worst-case optimal join algorithms. In: Principles of Database Systems (PODS), pp. 37\u201348. ACM (2012)","DOI":"10.1145\/2213556.2213565"},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"Ngo, H.Q., R\u00e9, C., Rudra, A.: Skew strikes back: new developments in the theory of join algorithms. arXiv preprint arXiv:1310.3314 (2013)","DOI":"10.1145\/2590989.2590991"},{"key":"15_CR28","doi-asserted-by":"crossref","unstructured":"Nguyen, D., et al.: Join processing for graph patterns: an old dog with new tricks. In: GRADES, p. 2. ACM (2015)","DOI":"10.1145\/2764947.2764948"},{"key":"15_CR29","volume-title":"Database Management Systems","author":"R Ramakrishnan","year":"2000","unstructured":"Ramakrishnan, R., Gehrke, J.: Database Management Systems. McGraw Hill, New York (2000)"},{"key":"15_CR30","first-page":"193","volume-title":"Emerging Directions in Database Systems and Applications","author":"Bryan Thompson","year":"2014","unstructured":"Thompson, B.B., Personick, M., Cutcher, M.: The Bigdata\u00aeRDF graph database. In: Linked Data Management, pp. 193\u2013237 (2014)"},{"key":"15_CR31","unstructured":"Veldhuizen, T.L.: Leapfrog Triejoin: a simple, worst-case optimal join algorithm. In: ICDT, pp. 96\u2013106 (2014)"},{"key":"15_CR32","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/2629489","volume":"57","author":"D Vrande\u010di\u0107","year":"2014","unstructured":"Vrande\u010di\u0107, D., Kr\u00f6tzsch, M.: Wikidata: a free collaborative knowledgebase. Commun. ACM 57, 78\u201385 (2014)","journal-title":"Commun. ACM"},{"issue":"1","key":"15_CR33","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"}],"container-title":["Lecture Notes in Computer Science","The Semantic Web \u2013 ISWC 2019"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-30793-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T19:11:17Z","timestamp":1729105877000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-30793-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030307929","9783030307936"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-30793-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"17 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ISWC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Semantic Web Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Auckland","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"New Zealand","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 October 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 October 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"semweb2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iswc2019.semanticweb.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single- and Double blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"283","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":"74","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":"0","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":"26% - 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-4","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":"1-3","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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}