NDLI: An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets

Content Provider	ACM Digital Library
Author	Fraigniaud, Pierre Korman, Amos
Copyright Year	2016
Abstract	In this article, we solve the $\textit{ancestry}-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 $\textit{n}-node$ trees with label size log $_{2}n$ + $\textit{O}(log$ log $\textit{n})$ bits, thus matching the log $_{2}n$ + Ω(log log $\textit{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 $\textit{n}-node$ trees with a depth of at most $\textit{d},$ the simplified ancestry scheme enjoys label size of log $_{2}n$ + $2log_{2}d$ + $\textit{O}(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 $\textit{adjacency}-labeling$ scheme that labels $\textit{n}-node$ trees of depth $\textit{d}$ with labels of size log $_{2}n$ + 3log $_{2}d$ + $\textit{O}(1)$ bits. All our schemes assign the labels in linear time, and guarantee that any query can be answered in constant time. Finally, our ancestry scheme finds applications to the construction of small $\textit{universal}$ partially ordered sets (posets). Specifically, for any fixed integer $\textit{k},$ it enables the construction of a universal poset of size $Õ(n^{k})$ for the family of $\textit{n}-element$ posets with a tree dimension of at most $\textit{k}.$ Up to lower-order terms, this bound is tight thanks to a lower bound of $\textit{n}\textit{k}$ ™ $\textit{o}(1)$ by to Alon and Scheinerman [1988].
Starting Page	1
Ending Page	31
Page Count	31
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2794076
Journal	Journal of the ACM (JACM)
Volume Number	63
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-02-12
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Database XML search engine Graph decomposition Labeling scheme Poset Tree
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Compact Ancestry Labeling Schemes for XML Trees (2010)

Compact ancestry labeling schemes for xml trees (2010)

An optimal ancestry scheme and small universal posets

BusSEngine: a business search engine

An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets

Compressing and indexing labeled trees, with applications

Optimal Search on Some Game Trees

Compact ancestry labeling schemes for trees of small depth (2009).

An optimal minimum spanning tree algorithm

An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets

Similar Documents

Compact Ancestry Labeling Schemes for XML Trees (2010)

Compact ancestry labeling schemes for xml trees (2010)

An optimal ancestry scheme and small universal posets

BusSEngine: a business search engine

An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets

Compressing and indexing labeled trees, with applications

Optimal Search on Some Game Trees

Compact ancestry labeling schemes for trees of small depth (2009).

An optimal minimum spanning tree algorithm

An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets