{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:50:28Z","timestamp":1759683028570,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>\n            We consider a fragment of XPath 1.0, where attribute and text values may be compared. We show that for any unary query \u03c6 in this fragment, the set of nodes that satisfy the query in a document\n            <jats:italic>t<\/jats:italic>\n            can be calculated in time\n            <jats:italic>O<\/jats:italic>\n            (|\u03c6|\n            <jats:sup>3<\/jats:sup>\n            |\n            <jats:italic>t<\/jats:italic>\n            |). We show that for a query in a bigger fragment with Kleene star allowed, the same can be done in time\n            <jats:italic>O<\/jats:italic>\n            (2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n            <\/jats:sup>\n            (|\u03c6|)|t|) or in time\n            <jats:italic>O<\/jats:italic>\n            (|\u03c6|\n            <jats:sup>3<\/jats:sup>\n            |t|log|t|). Finally, we present algorithms for binary queries of XPath, which do a precomputation on the document and then output the selected pairs with constant delay.\n          <\/jats:p>","DOI":"10.1145\/1989727.1989731","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["XPath evaluation in linear time"],"prefix":"10.1145","volume":"58","author":[{"given":"Miko\u0142aj","family":"Boja\u0144czyk","sequence":"first","affiliation":[{"name":"Warsaw University, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Parys","sequence":"additional","affiliation":[{"name":"Warsaw University, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,7,20]]},"reference":[{"volume-title":"Proceedings of the 4th Latin American Symposium on Theoretical Informatics","series-title":"Lecture Notes in Computer Science Series","author":"Bender M. A.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1456650.1456653"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02737-6_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376951"},{"key":"e_1_2_1_5_1","unstructured":"Clark J. and DeRose S. 1999. XML Path language (XPath) version 1.0 W3C recommendation. Tech. rep. W3C.  Clark J. and DeRose S. 1999. XML Path language (XPath) version 1.0 W3C recommendation. Tech. rep. W3C."},{"volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases. VLDB Endowment, 95--106","author":"Gottlob G.","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the 19th International Conference on Data Engineering. IEEE Computer Society, 379--390","author":"Gottlob G.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071614"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759210.1759301"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800152.804905"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601869"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559805"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989727.1989731","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1989727.1989731","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:05:54Z","timestamp":1750244754000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989727.1989731"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1989727.1989731"],"URL":"https:\/\/doi.org\/10.1145\/1989727.1989731","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2010-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}