{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T07:21:00Z","timestamp":1772608860036,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,2,12]],"date-time":"2016-02-12T00:00:00Z","timestamp":1455235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"INRIA project GANG"},{"name":"ANR project DISPLEXITY"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,3,30]]},"abstract":"<jats:p>\n            In this article, we solve the\n            <jats:italic>ancestry<\/jats:italic>\n            -labeling scheme problem, which aims at assigning the shortest possible labels (bit strings) to nodes of rooted trees, so ancestry queries between any two nodes can be answered by inspecting their assigned labels only. This problem was introduced more than 20 years ago by Kannan et al. [1988] and is among the most well-studied problems in the field of informative labeling schemes. We construct an ancestry-labeling scheme for\n            <jats:italic>n<\/jats:italic>\n            -node trees with label size log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (log log\n            <jats:italic>n<\/jats:italic>\n            ) bits, thus matching the log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            + \u03a9(log log\n            <jats:italic>n<\/jats:italic>\n            ) bits lower bound given by Alstrup et al. [2003]. Our scheme is based on a simplified ancestry scheme that operates extremely well on a restricted set of trees. In particular, for the set of\n            <jats:italic>n<\/jats:italic>\n            -node trees with a depth of at most\n            <jats:italic>d<\/jats:italic>\n            , the simplified ancestry scheme enjoys label size of log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            + 2log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>d<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (1) bits. Since the depth of most XML trees is at most some small constant, such an ancestry scheme may be of practical use. In addition, we also obtain an\n            <jats:italic>adjacency<\/jats:italic>\n            -labeling scheme that labels\n            <jats:italic>n<\/jats:italic>\n            -node trees of depth\n            <jats:italic>d<\/jats:italic>\n            with labels of size log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            + 3log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>d<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (1) bits. All our schemes assign the labels in linear time, and guarantee that any query can be answered in constant time.\n          <\/jats:p>\n          <jats:p>\n            Finally, our ancestry scheme finds applications to the construction of small\n            <jats:italic>universal<\/jats:italic>\n            partially ordered sets (posets). Specifically, for any fixed integer\n            <jats:italic>k<\/jats:italic>\n            , it enables the construction of a universal poset of size\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>\n              n\n              <jats:sup>k<\/jats:sup>\n            <\/jats:italic>\n            ) for the family of\n            <jats:italic>n<\/jats:italic>\n            -element posets with a tree dimension of at most\n            <jats:italic>k<\/jats:italic>\n            . Up to lower-order terms, this bound is tight thanks to a lower bound of\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n              \u2212\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            by to Alon and Scheinerman [1988].\n          <\/jats:p>","DOI":"10.1145\/2794076","type":"journal-article","created":{"date-parts":[[2016,2,22]],"date-time":"2016-02-22T13:07:16Z","timestamp":1456146436000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets"],"prefix":"10.1145","volume":"63","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[{"name":"CNRS and University Paris Diderot, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amos","family":"Korman","sequence":"additional","affiliation":[{"name":"CNRS and University Paris Diderot, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,2,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703437211"},{"key":"e_1_2_1_2_1","volume-title":"Web: From Relations to Semistructured Data and XML. Morgan Kaufmann","author":"Abiteboul S.","year":"1999","unstructured":"S. Abiteboul , P. Buneman , and D. Suciu . 1999 . Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann , Burlington, MA . S. Abiteboul, P. Buneman, and D. Suciu. 1999. Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, Burlington, MA."},{"key":"e_1_2_1_3_1","volume-title":"Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA).","author":"Abiteboul S.","unstructured":"S. Abiteboul , H. Kaplan , and T. Milo . 2001. Compact labeling schemes for ancestor queries . In Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA). S. Abiteboul, H. Kaplan, and T. Milo. 2001. Compact labeling schemes for ancestor queries. In Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"D. Adjiashvili and N. Rotbart. 2014. Labeling schemes for bounded degree graphs. In ICALP. 375--386.  D. Adjiashvili and N. Rotbart. 2014. Labeling schemes for bounded degree graphs. In ICALP. 375--386.","DOI":"10.1007\/978-3-662-43951-7_32"},{"key":"e_1_2_1_5_1","volume-title":"Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (SODA).","author":"Alstrup S.","unstructured":"S. Alstrup , P. Bille , and T. Rauhe . 2003. Labeling schemes for small distances in trees . In Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (SODA). S. Alstrup, P. Bille, and T. Rauhe. 2003. Labeling schemes for small distances in trees. In Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (SODA)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1155-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.84"},{"key":"e_1_2_1_8_1","volume-title":"Proc. 25th ACM-SIAM Symposium on Discrete Algorithms (SODA). 972--982","author":"Alstrup S.","unstructured":"S. Alstrup , E. B. Halvorsen , and K. G. Larsen . 2014. Near-optimal labeling schemes for nearest common ancestors . In Proc. 25th ACM-SIAM Symposium on Discrete Algorithms (SODA). 972--982 . S. Alstrup, E. B. Halvorsen, and K. G. Larsen. 2014. Near-optimal labeling schemes for nearest common ancestors. In Proc. 25th ACM-SIAM Symposium on Discrete Algorithms (SODA). 972--982."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746545"},{"key":"e_1_2_1_10_1","volume-title":"Proc. 43rd IEEE Symp. on Foundations of Computer Science (FOCS).","author":"Alstrup S.","unstructured":"S. Alstrup and T. Rauhe . 2002. Small induced-universal graphs and compact implicit graph representations . In Proc. 43rd IEEE Symp. on Foundations of Computer Science (FOCS). S. Alstrup and T. Rauhe. 2002. Small induced-universal graphs and compact implicit graph representations. In Proc. 43rd IEEE Symp. on Foundations of Computer Science (FOCS)."},{"key":"e_1_2_1_11_1","volume-title":"Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). 947--953","author":"Alstrup S.","unstructured":"S. Alstrup and T. Rauhe . 2002. Improved labeling scheme for ancestor queries . In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). 947--953 . S. Alstrup and T. Rauhe. 2002. Improved labeling scheme for ancestor queries. In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). 947--953."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00143892"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01111300"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543648"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_45"},{"key":"e_1_2_1_16_1","unstructured":"L. Denoyer. 2009. Personal Communication.  L. Denoyer. 2009. Personal Communication."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147197.1147210"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00020-1"},{"key":"e_1_2_1_19_1","volume-title":"Theory of Relations North-Holland","author":"Fraisse R.","unstructured":"R. Fraisse . 1953. Theory of Relations North-Holland , Amsterdam . R. Fraisse. 1953. Theory of Relations North-Holland, Amsterdam."},{"key":"e_1_2_1_20_1","volume-title":"Proc. 28th Int. Colloq. on Automata, Languages, and Programing (ICALP), LNCS 2076. Springer","author":"Fraigniaud P.","unstructured":"P. Fraigniaud and C. Gavoille . 2001. Routing in trees . In Proc. 28th Int. Colloq. on Automata, Languages, and Programing (ICALP), LNCS 2076. Springer , Berlin, 757--772. P. Fraigniaud and C. Gavoille. 2001. Routing in trees. In Proc. 28th Int. Colloq. on Automata, Languages, and Programing (ICALP), LNCS 2076. Springer, Berlin, 757--772."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584031"},{"key":"e_1_2_1_22_1","volume-title":"Proc. 21st ACM-SIAM Symp. on Discrete Algorithms (SODA), 458--466","author":"Fraigniaud P.","unstructured":"P. Fraigniaud and A. Korman . 2010a. Compact ancestry labeling schemes for XML trees . In Proc. 21st ACM-SIAM Symp. on Discrete Algorithms (SODA), 458--466 . P. Fraigniaud and A. Korman. 2010a. Compact ancestry labeling schemes for XML trees. In Proc. 21st ACM-SIAM Symp. on Discrete Algorithms (SODA), 458--466."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806773"},{"key":"e_1_2_1_24_1","volume-title":"15th Annual European Symposium on Algorithms (ESA), 582--593","author":"Gavoille C.","unstructured":"C. Gavoille and A. Labourel . 2007. Shorter implicit representation for planar graphs and bounded treewidth graphs . In 15th Annual European Symposium on Algorithms (ESA), 582--593 . C. Gavoille and A. Labourel. 2007. Shorter implicit representation for planar graphs and bounded treewidth graphs. In 15th Annual European Symposium on Algorithms (ESA), 582--593."},{"key":"e_1_2_1_25_1","volume-title":"Proc. European Conf. on Combinatorics, Graph Theory and Applications.","author":"Gavoille C.","unstructured":"C. Gavoille and C. Paul . 2001. Split decomposition and distance labelling: An optimal scheme for distance hereditary graphs . In Proc. European Conf. on Combinatorics, Graph Theory and Applications. C. Gavoille and C. Paul. 2001. Split decomposition and distance labelling: An optimal scheme for distance hereditary graphs. In Proc. European Conf. on Combinatorics, Graph Theory and Applications."},{"key":"e_1_2_1_26_1","volume-title":"Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA), 210--219","author":"Gavoille C.","unstructured":"C. Gavoille , D. Peleg , S. P\u00e9rennes , and R. Raz . 2001. Distance labeling in graphs . In Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA), 210--219 . C. Gavoille, D. Peleg, S. P\u00e9rennes, and R. Raz. 2001. Distance labeling in graphs. In Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA), 210--219."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_32"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.01.008"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10468"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0096607-8"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433912"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721855"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0025-1"},{"key":"e_1_2_1_34_1","volume-title":"Workshop on Algorithms and Data Structures.","author":"Kaplan H.","unstructured":"H. Kaplan and T. Milo . 2001. Short and simple labels for small distances and other functions . In Workshop on Algorithms and Data Structures. H. Kaplan and T. Milo. 2001. Short and simple labels for small distances and other functions. In Workshop on Algorithms and Data Structures."},{"key":"e_1_2_1_35_1","volume-title":"Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA).","author":"Kaplan H.","unstructured":"H. Kaplan , T. Milo , and R. Shabo . 2002. A comparison of labeling schemes for ancestor queries . In Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA). H. Kaplan, T. Milo, and R. Shabo. 2002. A comparison of labeling schemes for ancestor queries. In Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405049"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118226.3118474"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-005-1544-y"},{"key":"e_1_2_1_39_1","volume-title":"Proc. 13th Int. Conf. on Management of Data","author":"Mlynkova I.","year":"2006","unstructured":"I. Mlynkova , K. Toman , and J. Pokorny . 2006. Statistical analysis of real XML data collections . In Proc. 13th Int. Conf. on Management of Data ( 2006 ), 20--31. I. Mlynkova, K. Toman, and J. Pokorny. 2006. Statistical analysis of real XML data collections. In Proc. 13th Int. Conf. on Management of Data (2006), 20--31."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.03.015"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_2_1_44_1","volume-title":"Newblock Combinatorics and Partially Ordered Sets: Dimension Theory","author":"Trotter W. T.","unstructured":"W. T. Trotter . 1992. Newblock Combinatorics and Partially Ordered Sets: Dimension Theory . The Johns Hopkins University Press, Baltimore , MD. W. T. Trotter. 1992. Newblock Combinatorics and Partially Ordered Sets: Dimension Theory. The Johns Hopkins University Press, Baltimore, MD."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(77)90048-X"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1962-0172273-0"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2794076","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2794076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:26Z","timestamp":1750273466000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2794076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,12]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,3,30]]}},"alternative-id":["10.1145\/2794076"],"URL":"https:\/\/doi.org\/10.1145\/2794076","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,12]]},"assertion":[{"value":"2011-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}