ORDPATHs: Insert-Friendly XML Node Labels

Summary: ORDPATHS, a schema-free hierarchical labeling for XML trees, encodes document order and ancestry in a compact binary form. Supports insertion of new nodes between siblings without relabeling existing nodes; integrated in SQL Server. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h9f8ad104c0ffc846
Venue: SIGMOD
Year: 2004
Pagerank: 0.00014372588
Overall Rank: 734 | 95.07%
DOI: 10.1145/1007568.1007686

Incoming Non-self Citations Over Time

Authors

1. Patrick O'Neil (University of Massachusetts Boston)
2. Elizabeth O'Neil (University of Massachusetts Boston)
3. Shankar Pal (Microsoft)
4. Istvan Cseri (Microsoft)
5. Gideon Schaller (Microsoft)
6. Nigel Westbury (Microsoft)

BibTeX Citation

@inproceedings{oneil_sigmod04,
        title = {{ORDPATHs: Insert-Friendly XML Node Labels}},
        author = {O'Neil, Patrick and O'Neil, Elizabeth and Pal, Shankar and Cseri, Istvan and Schaller, Gideon and Westbury, Nigel},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007686},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007686},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.0004314366
1,497	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010477876
2,082	Indexing XML Data Stored in a Relational Database	2004	VLDB	9.0718964e-05
3,477	XML and Relational Database Management Systems: Inside Microsoft SQL Server 2005	2005	SIGMOD	7.267158e-05
4,189	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.7427859e-05
4,278	XQuery Implementation in a Relational Database System	2005	VLDB	6.6884521e-05
4,386	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.6230198e-05
4,964	Avalanche-Safe LINQ Compilation	2010	VLDB	6.335593e-05
5,339	Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances	2008	VLDB	6.1721633e-05
5,874	DDE: From Dewey to a Fully Dynamic XML Labeling Scheme	2009	SIGMOD	5.9609167e-05
6,048	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.9024167e-05
6,802	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.6773357e-05
7,240	Labeling Workflow Views with Fine-Grained Dependencies	2012	VLDB	5.5759411e-05
7,421	Structured Materialized Views for XML Queries	2007	VLDB	5.5301467e-05
7,630	Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect	2007	SIGMOD	5.4795145e-05
7,759	XQuery Reloaded	2009	VLDB	5.4567128e-05
7,896	Contest of XML Lock Protocols	2006	VLDB	5.4301275e-05
8,027	Cost-Sensitive Reordering of Navigational Primitives	2005	SIGMOD	5.4029105e-05
8,152	Incremental Maintenance of Path-Expression Views	2005	SIGMOD	5.3884533e-05
8,153	DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data	2013	SIGMOD	5.3883285e-05
8,201	Labeling Recursive Workflow Executions On-the-Fly	2011	SIGMOD	5.3778252e-05
8,295	Relational Support for Flexible Schema Scenarios	2008	VLDB	5.3589408e-05
8,507	Efficient Keyword Search over Virtual XML Views	2007	VLDB	5.3271356e-05
8,753	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	5.2854393e-05
9,037	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.2317228e-05
9,757	Indexing Highly Dynamic Hierarchical Data	2015	VLDB	5.1325223e-05
10,233	TreeCat: Standalone Catalog Engine for Large Data Systems	2025	VLDB	5.0547568e-05
11,771	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	4.9769913e-05
12,102	Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data	2020	VLDB	4.9769913e-05
12,795	Cost Based Plan Selection for XPath	2009	SIGMOD	4.9769913e-05
12,985	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
86	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00035793969
166	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027241844
374	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00019698564
918	Accelerating XPath Location Steps	2002	SIGMOD	0.00013078274

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	918	Accelerating XPath Location Steps	2002	SIGMOD
2	7,314	Query Translation from XPath to SQL in the Presence of Recursive DTDs	2005	VLDB
3	5,339	Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances	2008	VLDB
4	8,050	Extended Path Expressions for XML	2001	PODS
5	2,082	Indexing XML Data Stored in a Relational Database	2004	VLDB
6	4,278	XQuery Implementation in a Relational Database System	2005	VLDB
7	12,851	Relational-Style XML Query	2008	SIGMOD
8	3,028	Labeling Dynamic XML Trees	2002	PODS
9	4,808	XML Schemas in Oracle XML DB	2003	VLDB
10	374	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD