{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T14:01:15Z","timestamp":1791122475678,"version":"4.1.0"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>We consider the following problem. Given a rooted tree T, label the nodes of T in the most compact way such that, given the labels of two nodes u and v, one can determine in constant time, by looking only at the labels, whether u is ancestor of v. The best known labeling scheme is rather straightforward and uses labels of length at most $2\\log_2 n$ bits each, where n is the number of nodes in the tree. Our main result in this paper is a labeling scheme with maximum label length $\\log_2 n + \\Oh(\\sqrt{\\log n})$. Our motivation for studying this problem is enhancing the performance of web search engines. In the context of this application each indexed document is a tree, and the labels of all trees are maintained in main memory. Therefore even small improvements in the maximum label length are important.<\/jats:p>","DOI":"10.1137\/s0097539703437211","type":"journal-article","created":{"date-parts":[[2008,2,12]],"date-time":"2008-02-12T16:51:45Z","timestamp":1202835105000},"page":"1295-1309","source":"Crossref","is-referenced-by-count":44,"title":["Compact Labeling Scheme for Ancestor Queries"],"prefix":"10.1137","volume":"35","author":[{"given":"Serge","family":"Abiteboul","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen","family":"Alstrup","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tova","family":"Milo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Theis","family":"Rauhe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"S. Abiteboul, P. Buneman, and D. Suciu,\n                      Data on the Web: From Relations to Semistructured Data and XML\n                      , Morgan\u2010Kaufmann, San Francisco, 1999."},{"key":"R2","unstructured":"Serge Abiteboul, Haim Kaplan, Tova Milo, Compact labeling schemes for ancestor queries (extended abstract), SIAM, Philadelphia, PA, 2001, 547\u2013556MR1958448"},{"key":"R3","unstructured":"Stephen Alstrup, Philip Bille, Theis Rauhe, Labeling schemes for small distances in trees, ACM, New York, 2003, 689\u2013698MR1974981"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1155-5"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup, Minimizing diameters of dynamic trees, Lecture Notes in Comput. Sci., Vol. 1256, Springer, Berlin, 1997, 270\u201328098m:68197","DOI":"10.1007\/3-540-63165-8_184"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Stephen Alstrup, Jacob Holm, Mikkel Thorup, Maintaining center and median in dynamic trees, Lecture Notes in Comput. Sci., Vol. 1851, Springer, Berlin, 2000, 46\u201356MR1792584","DOI":"10.1007\/3-540-44985-X_6"},{"key":"R7","unstructured":"S. Alstrup and T. Rauhe,\n                      Improved labeling scheme for ancestor queries\n                      , in Proceedings of the Thirteen Annual ACM\u2010SIAM Symposium on Discrete Algorithms (SODA), San Francisco, CA, 2002, SIAM, Philadelphia, 2002, pp. 947\u2013953."},{"key":"R8","unstructured":"Altavista\n                      , online search engine at http:\/\/www.altavista.com."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1966.1053860"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(67)90082-0"},{"key":"R11","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest,\n                      Introduction to Algorithms\n                      , MIT Press\/ McGraw\u2013Hill, New York, 1991."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00020-1"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792226825"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0073-5"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1959.tb01583.x"},{"key":"R17","unstructured":"Google\n                      , online search engine at http:\/\/www.google.com\/."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0405049"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Haim Kaplan, Tova Milo, Short and simple labels for small distances and other functions, Lecture Notes in Comput. Sci., Vol. 2125, Springer, Berlin, 2001, 246\u20132572003i:68112","DOI":"10.1007\/3-540-44634-6_23"},{"key":"R20","unstructured":"H. Kaplan, T. Milo, and R. Shabo,\n                      A comparison of labeling schemes for ancestor queries\n                      , in Proceedings of the Thirteen Annual ACM\u2010SIAM Symposium on Discrete Algorithms (SODA), San Francisco, CA, 2002, SIAM, Philadelphia, 2002, pp. 954\u2013963."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433912"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.03.005"},{"key":"R23","unstructured":"Q. Li and B. Moon,\n                      Indexing and querying xml data for regular path expression\n                      , in Proceedings of the 27th International Conference on Very Large Data Bases (VLDB), Rome, 2001, Morgan Kaufmann, San Francisco, 2001, pp. 361\u2013370."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/0206017"},{"key":"R25","unstructured":"Oasis,\n                      Organization for the Advancement of Structures Information Standards\n                      , available online at http:\/\/www.oasis\u2010open.org\/."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/28.1.5"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Mikkel Thorup, Uri Zwick, Approximate distance oracles, ACM, New York, 2001, 183\u2013192MR2120314","DOI":"10.1145\/380752.380798"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289142"},{"key":"R31","unstructured":"W3. Extensible Markup Languange (XML)\n                      1.0, documentation online at http:\/\/www.w3.org\/XML."},{"key":"R32","unstructured":"W3C. Extensible Stylesheet Language (XSL)\n                      , documentation online at http:\/\/www.w3.org\/Style\/XSL\/."},{"key":"R33","unstructured":"HyperText Markup Language (HTML)\n                      , documentation online at http:\/\/www.w3.org\/MarkUp."},{"key":"R34","unstructured":"Xyleme\n                      .\n                      A dynamic data warehouse for the XML data of the web\n                      , documentation online at http:\/\/www.xyleme.com."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539703437211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:24:05Z","timestamp":1787336645000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539703437211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/S0097539703437211"],"URL":"https:\/\/doi.org\/10.1137\/s0097539703437211","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}