{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:56:17Z","timestamp":1757454977259,"version":"3.44.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2023\/51\/B\/ST6\/01505"],"award-info":[{"award-number":["2023\/51\/B\/ST6\/01505"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["466789228, 522576760"],"award-info":[{"award-number":["466789228, 522576760"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>Information extraction from textual data, where the query is represented by a finite transducer and the task is to enumerate all results without repetition, and its extension to the weighted case, where each output element has a weight and the output elements are to be enumerated sorted by their weights, are important and well studied problems in database theory. On the one hand, the first framework already covers the well-known case of regular document spanners, while the latter setting covers several practically relevant tasks that cannot be described in the unweighted setting.<\/jats:p>\n          <jats:p>It is known that in the unweighted case this problem can be solved with linear time preprocessing O(|D|) and output-linear delay O(|s|) in data complexity, where D is the input data and s is the current output element. For the weighted case, Bourhis, Grez, Jachiet, and Riveros [ICDT 2021] recently designed an algorithm with linear time preprocessing, but the delay of O(|s| \u00b7 log|D|) depends on the size of the data.<\/jats:p>\n          <jats:p>\n            We first show how to leverage the existing results on enumerating shortest paths to obtain a simple alternative algorithm with linear preprocessing and a delay of O(|s\n            <jats:sub>i<\/jats:sub>\n            | + min\\ log i, log|D| ) for the i\n            <jats:sup>th<\/jats:sup>\n            output element s\n            <jats:sub>i<\/jats:sub>\n            (in data complexity); thus, substantially improving the previous algorithm. Next, we develop a technically involved rounding technique that allows us to devise an algorithm with linear time preprocessing and output-linear delay O(|s|) with high probability. To this end, we combine tools from algebra, high-dimensional geometry, and linear programming.\n          <\/jats:p>","DOI":"10.1145\/3695840","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-19","source":"Crossref","is-referenced-by-count":1,"title":["Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6993-5440","authenticated-orcid":false,"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6094-3324","authenticated-orcid":false,"given":"Florin","family":"Manea","sequence":"additional","affiliation":[{"name":"Computer Science Department and CIDAS, Universit\u00e4t G\u00f6ttingen, G\u00f6ttingen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5137-1504","authenticated-orcid":false,"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2024.25"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422648.3422655"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3436487"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.1998.1580"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236460"},{"key":"e_1_2_1_6_1","volume-title":"MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay. In Computer Science Logic CSL 2006, 15th Annual Conference of the EACSL, Proceedings. 167--181","author":"Bagan Guillaume","year":"2006","unstructured":"Guillaume Bagan. 2006. MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay. In Computer Science Logic CSL 2006, 15th Annual Conference of the EACSL, Proceedings. 167--181."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2021.20"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-19(3:12)2023"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2020.8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"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\/3351451"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1030"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100217"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2022.10"},{"volume-title":"Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics","author":"Gr\u00f6tschel Martin","key":"e_1_2_1_16_1","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 1988. Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, Vol. 2. Springer."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181890"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3285953"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041--5553(80)90061-0"},{"volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","key":"e_1_2_1_20_1","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley."},{"key":"e_1_2_1_21_1","volume-title":"Linear Algebra","author":"Lang Serge","year":"1949","unstructured":"Serge Lang. 1987. Linear Algebra, 3rd Edition. Springer. https:\/\/link.springer.com\/book\/10.1007\/978--1--4757--1949--9","edition":"3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196968"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.7"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-031--52113--3_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3526069"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2205.05649"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695840","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695840","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:29:32Z","timestamp":1755916172000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695840"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695840"],"URL":"https:\/\/doi.org\/10.1145\/3695840","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}