{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T08:32:36Z","timestamp":1785227556023,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,20]],"date-time":"2021-06-20T00:00:00Z","timestamp":1624147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["416776735, 431183758"],"award-info":[{"award-number":["416776735, 431183758"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,20]]},"DOI":"10.1145\/3452021.3458325","type":"proceedings-article","created":{"date-parts":[[2021,10,29]],"date-time":"2021-10-29T14:03:04Z","timestamp":1635516184000},"page":"153-165","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Spanner Evaluation over SLP-Compressed Documents"],"prefix":"10.1145","author":[{"given":"Markus L.","family":"Schmid","sequence":"first","affiliation":[{"name":"Humboldt Universitaet zu Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicole","family":"Schweikardt","sequence":"additional","affiliation":[{"name":"Humboldt Universitaet zu Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Proc. FOCS'17","author":"Abboud A.","year":"1803","unstructured":"A. Abboud , A. Backurs , K. Bringmann , and M. K\u00fcnnemann . 2017. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve . In Proc. FOCS'17 . 192--203. Extended version available at http:\/\/arxiv.org\/abs\/ 1803 .00796. A. Abboud, A. Backurs, K. Bringmann, and M. K\u00fcnnemann. 2017. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. In Proc. FOCS'17. 192--203. Extended version available at http:\/\/arxiv.org\/abs\/1803.00796."},{"key":"e_1_3_2_2_2_1","volume-title":"Proc. ICDT'19 .","author":"Amarilli A.","unstructured":"A. Amarilli , P. Bourhis , S. Mengel , and M. Niewerth . 2019. Constant-Delay Enumeration for Nondeterministic Document Spanners . In Proc. ICDT'19 . A. Amarilli, P. Bourhis, S. Mengel, and M. Niewerth. 2019. Constant-Delay Enumeration for Nondeterministic Document Spanners. In Proc. ICDT'19 ."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422648.3422655"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020-10013-w"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_3_2_2_6_1","unstructured":"Patrick Hagge Cording. 2015.\n  Algorithms and data structures for grammar-compressed strings\n   . Ph.D. Dissertation.  Patrick Hagge Cording. 2015. Algorithms and data structures for grammar-compressed strings . Ph.D. Dissertation."},{"key":"e_1_3_2_2_7_1","volume-title":"Proc. PODS'19","author":"Doleschal J.","unstructured":"J. Doleschal , B. Kimelfeld , W. Martens , Y. Nahshon , and F. Neven . 2019. Split-Correctness in Information Extraction . In Proc. PODS'19 . 149--163. J. Doleschal, B. Kimelfeld, W. Martens, Y. Nahshon, and F. Neven. 2019. Split-Correctness in Information Extraction. In Proc. PODS'19. 149--163."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_3_2_2_9_1","volume-title":"Proc. PODS'18 .","author":"Florenzano F.","unstructured":"F. Florenzano , C. Riveros , M. Ugarte , S. Vansummeren , and D. Vrgoc . 2018. Constant Delay Algorithms for Regular Document Spanners . In Proc. PODS'18 . F. Florenzano, C. Riveros, M. Ugarte, S. Vansummeren, and D. Vrgoc. 2018. Constant Delay Algorithms for Regular Document Spanners. In Proc. PODS'18 ."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9874-1"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9770-0"},{"key":"e_1_3_2_2_12_1","volume-title":"Proc. PODS'18","author":"Freydenberger D.","unstructured":"D. Freydenberger , B. Kimelfeld , and L. Peterfreund . 2018. Joining Extractions of Regular Expressions . In Proc. PODS'18 . 137--149. D. Freydenberger, B. Kimelfeld, and L. Peterfreund. 2018. Joining Extractions of Regular Expressions. In Proc. PODS'18. 137--149."},{"key":"e_1_3_2_2_13_1","volume-title":"Proc. FOCS'19","author":"Ganardi M.","unstructured":"M. Ganardi , A. Jez , and M. Lohrey . 2019. Balancing Straight-Line Programs . In Proc. FOCS'19 . 1169--1183. M. Ganardi, A. Jez, and M. Lohrey. 2019. Balancing Straight-Line Programs. In Proc. FOCS'19. 1169--1183."},{"key":"e_1_3_2_2_14_1","unstructured":"K. Goto S. Maruyama S. Inenaga H. Bannai H. Sakamoto and M. Takeda. 2011. Restructuring Compressed Texts without Explicit Decompression. CoRR Vol. abs\/1107.2729 (2011). http:\/\/arxiv.org\/abs\/1107.2729  K. Goto S. Maruyama S. Inenaga H. Bannai H. Sakamoto and M. Takeda. 2011. Restructuring Compressed Texts without Explicit Decompression. CoRR Vol. abs\/1107.2729 (2011). http:\/\/arxiv.org\/abs\/1107.2729"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.841160"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2012-0016"},{"key":"e_1_3_2_2_18_1","volume-title":"The Compressed Word Problem for Groups Springer Briefs in Mathematics ed","author":"Lohrey M.","unstructured":"M. Lohrey . 2014. The Compressed Word Problem for Groups Springer Briefs in Mathematics ed . Springer . M. Lohrey. 2014. The Compressed Word Problem for Groups Springer Briefs in Mathematics ed. Springer."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.002"},{"key":"e_1_3_2_2_20_1","volume-title":"Proc. PODS'18 .","author":"Maturana F.","unstructured":"F. Maturana , C. Riveros , and D. Vrgoc . 2018. Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity . In Proc. PODS'18 . F. Maturana, C. Riveros, and D. Vrgoc. 2018. Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity. In Proc. PODS'18 ."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622776.1622780"},{"key":"e_1_3_2_2_24_1","volume-title":"Proc. ICDT'21 . Extended version","author":"Peterfreund L.","year":"2021","unstructured":"L. Peterfreund . 2021 . Grammars for Document Spanners . In Proc. ICDT'21 . Extended version available at https:\/\/arxiv.org\/abs\/2003.06880. L. Peterfreund. 2021. Grammars for Document Spanners. In Proc. ICDT'21 . Extended version available at https:\/\/arxiv.org\/abs\/2003.06880."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"crossref","unstructured":"W. Plandowski and W. Rytter. 1999. Complexity of Language Recognition Problems for Compressed Words. In Jewels are Forever Contributions on Theoretical Computer Science in Honor of Arto Salomaa . 262--272.  W. Plandowski and W. Rytter. 1999. Complexity of Language Recognition Problems for Compressed Words. In Jewels are Forever Contributions on Theoretical Computer Science in Honor of Arto Salomaa . 262--272.","DOI":"10.1007\/978-3-642-60207-8_23"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00777-6"},{"key":"e_1_3_2_2_27_1","volume-title":"Proc. ICDT'21 . Extended version","author":"Schmid M.L.","unstructured":"M.L. Schmid and N. Schweikardt . 2021. A Purely Regular Approach to Non-Regular Core Spanners . In Proc. ICDT'21 . Extended version available at https:\/\/arxiv.org\/abs\/2010.13442. M.L. Schmid and N. Schweikardt. 2021. A Purely Regular Approach to Non-Regular Core Spanners. In Proc. ICDT'21 . Extended version available at https:\/\/arxiv.org\/abs\/2010.13442."},{"key":"e_1_3_2_2_28_1","unstructured":"M.L. Schmid and N. Schweikardt. 2021. Spanner evaluation over SLP-Compressed documents. CoRR Vol. abs\/2101.10890 (2021). https:\/\/arxiv.org\/abs\/2101.10890  M.L. Schmid and N. Schweikardt. 2021. Spanner evaluation over SLP-Compressed documents. CoRR Vol. abs\/2101.10890 (2021). https:\/\/arxiv.org\/abs\/2101.10890"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322346"}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","location":"Virtual Event China","acronym":"SIGMOD\/PODS '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452021.3458325","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3452021.3458325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:00Z","timestamp":1750197780000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452021.3458325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,20]]},"references-count":26,"alternative-id":["10.1145\/3452021.3458325","10.1145\/3452021"],"URL":"https:\/\/doi.org\/10.1145\/3452021.3458325","relation":{},"subject":[],"published":{"date-parts":[[2021,6,20]]},"assertion":[{"value":"2021-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}