Labeling Dynamic XML Trees

Summary: Assign immutable insertion-time labels to nodes of dynamic XML trees so ancestry is decidable from label pairs; labels are provably shortest up to constant factors. Schemes that exploit DTD/statistical "clues" yield shorter, near-minimal labels. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1270
Venue: PODS
Year: 2002
Pagerank: 7.9151381e-05
Overall Rank: 2,967 | 79.65%
DOI: 10.1145/543613.543648

Incoming Non-self Citations Over Time

Authors

1. Edith Cohen (AT&T)
2. Haim Kaplan (Tel Aviv University)
3. Tova Milo (INRIA; Tel Aviv University)

BibTeX Citation

@inproceedings{cohen_pods02,
        address = {New York, NY, USA},
        series = {{PODS} '02},
        title = {{Labeling Dynamic XML Trees}},
        url = {https://dl.acm.org/doi/10.1145/543613.543648},
        doi = {10.1145/543613.543648},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cohen, Edith and Kaplan, Haim and Milo, Tova},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,204	A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding	2003	SIGMOD	0.00011664562
1,460	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010710674
1,849	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.6191884e-05
5,336	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.2612462e-05
5,458	Using Partial Evaluation in Distributed Query Evaluation	2006	VLDB	6.2115011e-05
5,750	DDE: From Dewey to a Fully Dynamic XML Labeling Scheme	2009	SIGMOD	6.100444e-05
7,089	Labeling Workflow Views with Fine-Grained Dependencies	2012	VLDB	5.7066232e-05
7,980	Incremental Maintenance of Path-Expression Views	2005	SIGMOD	5.5146804e-05
8,049	Labeling Recursive Workflow Executions On-the-Fly	2011	SIGMOD	5.500317e-05
8,870	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.3543292e-05
12,689	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,628	Reasoning about XML Update Constraints	2007	PODS
2	2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS
3	8,870	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD
4	13,683	Efficient Evaluation for a Temporal Logic on Changing XML Documents	2011	PODS
5	1,523	Efficient Structural Joins on Indexed XML Documents	2002	VLDB
6	5,209	Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances	2008	VLDB
7	2,699	Approximate XML Joins	2002	SIGMOD
8	5,332	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS
9	5,750	DDE: From Dewey to a Fully Dynamic XML Labeling Scheme	2009	SIGMOD
10	3,318	On the Complexity of Managing Probabilistic XML Data	2007	PODS