{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T04:33:10Z","timestamp":1791433990741,"version":"4.3.3"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,3,31]],"date-time":"2021-03-31T00:00:00Z","timestamp":1617148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR","award":["EQUUS ANR-19-CE48-0019"],"award-info":[{"award-number":["EQUUS ANR-19-CE48-0019"]}]},{"name":"DFG","award":["431183758"],"award-info":[{"award-number":["431183758"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>\n            We consider the information extraction framework known as\n            <jats:italic>document spanners<\/jats:italic>\n            and study the problem of efficiently computing the results of the extraction from an input document, where the extraction task is described as a sequential\n            <jats:italic>variable-set automaton<\/jats:italic>\n            (VA). We pose this problem in the setting of enumeration algorithms, where we can first run a preprocessing phase and must then produce the results with a small delay between any two consecutive results. Our goal is to have an algorithm that is tractable in combined complexity, i.e., in the sizes of the input document and the VA, while ensuring the best possible data complexity bounds in the input document size, i.e., constant delay in the document size. Several recent works at PODS\u201918 proposed such algorithms but with linear delay in the document size or with an exponential dependency in size of the (generally nondeterministic) input VA. In particular, Florenzano et\u00a0al. suggest that our desired runtime guarantees cannot be met for general sequential VAs. We refute this and show that, given a nondeterministic sequential VA and an input document, we can enumerate the mappings of the VA on the document with the following bounds: the preprocessing is linear in the document size and polynomial in the size of the VA, and the delay is independent of the document and polynomial in the size of the VA. The resulting algorithm thus achieves tractability in combined complexity and the best possible data complexity bounds. Moreover, it is rather easy to describe, particularly for the restricted case of so-called extended VAs. Finally, we evaluate our algorithm empirically using a prototype implementation.\n          <\/jats:p>","DOI":"10.1145\/3436487","type":"journal-article","created":{"date-parts":[[2021,4,14]],"date-time":"2021-04-14T19:51:28Z","timestamp":1618429888000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Constant-Delay Enumeration for Nondeterministic Document Spanners"],"prefix":"10.1145","volume":"46","author":[{"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[{"name":"LTCI and T\u00e9l\u00e9com Paris and Institut polytechnique de Paris"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Bourhis","sequence":"additional","affiliation":[{"name":"CRIStAL and CNRS UMR 9189 and Inria Lille"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Mengel","sequence":"additional","affiliation":[{"name":"CRIL, CNRS &amp; Univ Artois"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthias","family":"Niewerth","sequence":"additional","affiliation":[{"name":"University of Bayreuth"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,4,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1974","unstructured":"Alfred V. Aho , John E. Hopcroft , and Jeffrey D . Ullman . 1974 . The Design and Analysis of Computer Algorithms. Addison-Wesley . Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of ICALP","author":"Amarilli Antoine","year":"2017","unstructured":"Antoine Amarilli , Pierre Bourhis , Louis Jachiet , and Stefan Mengel . 2017 . A circuit-based approach to efficient enumeration . In Proceedings of ICALP 2017. https:\/\/arxiv.org\/abs\/1702.05589. Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel. 2017. A circuit-based approach to efficient enumeration. In Proceedings of ICALP 2017. https:\/\/arxiv.org\/abs\/1702.05589."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of ICDT","author":"Amarilli Antoine","year":"2018","unstructured":"Antoine Amarilli , Pierre Bourhis , and Stefan Mengel . 2018 . Enumeration on trees under relabelings . In Proceedings of ICDT 2018. https:\/\/arxiv.org\/abs\/1709.06185. Antoine Amarilli, Pierre Bourhis, and Stefan Mengel. 2018. Enumeration on trees under relabelings. In Proceedings of ICDT 2018. https:\/\/arxiv.org\/abs\/1709.06185."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of ICDT","author":"Amarilli Antoine","year":"2019","unstructured":"Antoine Amarilli , Pierre Bourhis , Stefan Mengel , and Matthias Niewerth . 2019 . Constant-delay enumeration for nondeterministic document spanners . In Proceedings of ICDT 2019. https:\/\/drops.dagstuhl.de\/opus\/frontdoor.php?source_opus&equals;10324. Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. 2019. Constant-delay enumeration for nondeterministic document spanners. In Proceedings of ICDT 2019. https:\/\/drops.dagstuhl.de\/opus\/frontdoor.php?source_opus&equals;10324."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319702"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_11"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of ICDT","author":"Berkholz Christoph","year":"2017","unstructured":"Christoph Berkholz , Jens Keppeler , and Nicole Schweikardt . 2017 . Answering FO+MOD queries under updates on bounded degree databases . In Proceedings of ICDT 2017. https:\/\/arxiv.org\/abs\/1702.08764. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2017. Answering FO+MOD queries under updates on bounded degree databases. In Proceedings of ICDT 2017. https:\/\/arxiv.org\/abs\/1702.08764."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of ICDT","author":"Berkholz Christoph","year":"2018","unstructured":"Christoph Berkholz , Jens Keppeler , and Nicole Schweikardt . 2018 . Answering UCQs under updates and in the presence of integrity constraints . In Proceedings of ICDT 2017. https:\/\/arxiv.org\/abs\/1709.10039. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2018. Answering UCQs under updates and in the presence of integrity constraints. In Proceedings of ICDT 2017. https:\/\/arxiv.org\/abs\/1709.10039."},{"key":"e_1_2_1_10_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press , Cambridge, MA . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press, Cambridge, MA.","edition":"3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196987"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of ICDT 2017","author":"Freydenberger Dominik D.","year":"2017","unstructured":"Dominik D. Freydenberger . 2017 . A logic for document spanners . In Proceedings of ICDT 2017 . http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/7049\/. Dominik D. Freydenberger. 2017. A logic for document spanners. In Proceedings of ICDT 2017. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/7049\/."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9874-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9770-0"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196967"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.116"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02127798"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603137"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of STACS 2016","author":"Mary Arnaud","year":"2016","unstructured":"Arnaud Mary and Yann Strozecki . 2016 . Efficient enumeration of solutions produced by closure operations . In Proceedings of STACS 2016 . http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2016\/5753\/. Arnaud Mary and Yann Strozecki. 2016. Efficient enumeration of solutions produced by closure operations. In Proceedings of STACS 2016. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2016\/5753\/."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196968"},{"key":"e_1_2_1_23_1","unstructured":"Andrea Morciano. 2017. Engineering a Runtime System for AQL. Master\u2019s Thesis. Politecnico di Milano. https:\/\/www.politesi.polimi.it\/bitstream\/10589\/135034\/1\/2017_07_Morciano.pdf.  Andrea Morciano. 2017. Engineering a Runtime System for AQL. Master\u2019s Thesis. Politecnico di Milano. https:\/\/www.politesi.polimi.it\/bitstream\/10589\/135034\/1\/2017_07_Morciano.pdf."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209144"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196961"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.3.237"},{"key":"e_1_2_1_27_1","unstructured":"IBM Research. 2018. SystemT. Retrieved February 7 2021 from https:\/\/researcher.watson.ibm.com\/researcher\/view_group.php?id&equals;1264.  IBM Research. 2018. SystemT. Retrieved February 7 2021 from https:\/\/researcher.watson.ibm.com\/researcher\/view_group.php?id&equals;1264."},{"key":"e_1_2_1_28_1","volume-title":"AAAI Spring Symposium: Computational Approaches to Analyzing Weblogs","volume":"6","author":"Schler Jonathan","unstructured":"Jonathan Schler , Moshe Koppel , Shlomo Argamon , and James W. Pennebaker . 2006. Effects of age and gender on blogging . In AAAI Spring Symposium: Computational Approaches to Analyzing Weblogs , Vol. 6 . 199--205. http:\/\/u.cs.biu.ac.il\/&sim;koppel\/BlogCorpus.htm. Jonathan Schler, Moshe Koppel, Shlomo Argamon, and James W. Pennebaker. 2006. Effects of age and gender on blogging. In AAAI Spring Symposium: Computational Approaches to Analyzing Weblogs, Vol. 6. 199--205. http:\/\/u.cs.biu.ac.il\/&sim;koppel\/BlogCorpus.htm."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of STACS","author":"Segoufin Luc","year":"2014","unstructured":"Luc Segoufin . 2014 . A glimpse on constant delay enumeration (Invited talk) . In Proceedings of STACS 2014. https:\/\/hal.inria.fr\/hal-01070893\/document. Luc Segoufin. 2014. A glimpse on constant delay enumeration (Invited talk). In Proceedings of STACS 2014. https:\/\/hal.inria.fr\/hal-01070893\/document."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206036"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_32_1","unstructured":"Kunihiro Wasa. 2016. Enumeration of enumeration algorithms. arXiv:1605.05012. https:\/\/arxiv.org\/abs\/1605.05102.  Kunihiro Wasa. 2016. Enumeration of enumeration algorithms. arXiv:1605.05012. https:\/\/arxiv.org\/abs\/1605.05102."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3436487","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3436487","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:45:16Z","timestamp":1750268716000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3436487"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,31]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3436487"],"URL":"https:\/\/doi.org\/10.1145\/3436487","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,31]]},"assertion":[{"value":"2020-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}