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: 3651
Venue: SIGMOD
Year: 2004
Pagerank: 0.00014637695
Overall Rank: 719 | 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
51	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.0004291425
1,460	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010710674
2,031	Indexing XML Data Stored in a Relational Database	2004	VLDB	9.2839251e-05
3,408	XML and Relational Database Management Systems: Inside Microsoft SQL Server 2005	2005	SIGMOD	7.4370792e-05
4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.8973582e-05
4,265	XQuery Implementation in a Relational Database System	2005	VLDB	6.7936855e-05
4,294	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.7780241e-05
4,847	Avalanche-Safe LINQ Compilation	2010	VLDB	6.4805473e-05
5,209	Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances	2008	VLDB	6.3163287e-05
5,750	DDE: From Dewey to a Fully Dynamic XML Labeling Scheme	2009	SIGMOD	6.100444e-05
5,931	Your notebook is not crumby enough, REPLace it	2020	CIDR	6.0369708e-05
6,688	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.8015211e-05
7,089	Labeling Workflow Views with Fine-Grained Dependencies	2012	VLDB	5.7066232e-05
7,267	Structured Materialized Views for XML Queries	2007	VLDB	5.6597556e-05
7,486	Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect	2007	SIGMOD	5.6073128e-05
7,607	XQuery Reloaded	2009	VLDB	5.5845947e-05
7,737	Contest of XML Lock Protocols	2006	VLDB	5.5558475e-05
7,864	Cost-Sensitive Reordering of Navigational Primitives	2005	SIGMOD	5.5294867e-05
7,980	Incremental Maintenance of Path-Expression Views	2005	SIGMOD	5.5146804e-05
7,981	DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data	2013	SIGMOD	5.5146136e-05
8,049	Labeling Recursive Workflow Executions On-the-Fly	2011	SIGMOD	5.500317e-05
8,109	Relational Support for Flexible Schema Scenarios	2008	VLDB	5.4843869e-05
8,333	Efficient Keyword Search over Virtual XML Views	2007	VLDB	5.4519621e-05
8,577	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	5.409313e-05
8,870	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.3543292e-05
9,576	Indexing Highly Dynamic Hierarchical Data	2015	VLDB	5.2528121e-05
10,976	TreeCat: Standalone Catalog Engine for Large Data Systems	2025	VLDB	5.093636e-05
11,453	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	5.093636e-05
11,794	Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data	2020	VLDB	5.093636e-05
12,499	Cost Based Plan Selection for XPath	2009	SIGMOD	5.093636e-05
12,689	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	5.093636e-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
79	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00036555628
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
362	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00020125068
893	Accelerating XPath Location Steps	2002	SIGMOD	0.00013374715

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,486	Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect	2007	SIGMOD
2	7,172	Query Translation from XPath to SQL in the Presence of Recursive DTDs	2005	VLDB
3	5,209	Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances	2008	VLDB
4	7,876	Extended Path Expressions for XML	2001	PODS
5	2,031	Indexing XML Data Stored in a Relational Database	2004	VLDB
6	4,265	XQuery Implementation in a Relational Database System	2005	VLDB
7	12,555	Relational-Style XML Query	2008	SIGMOD
8	2,967	Labeling Dynamic XML Trees	2002	PODS
9	4,710	XML Schemas in Oracle XML DB	2003	VLDB
10	362	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD