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.00014379182
Overall Rank: 733 | 95.08%
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.00043160717
1,496	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010482718
2,080	Indexing XML Data Stored in a Relational Database	2004	VLDB	9.0761918e-05
3,477	XML and Relational Database Management Systems: Inside Microsoft SQL Server 2005	2005	SIGMOD	7.2705957e-05
4,189	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.7459542e-05
4,277	XQuery Implementation in a Relational Database System	2005	VLDB	6.6914942e-05
4,383	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.6261511e-05
4,962	Avalanche-Safe LINQ Compilation	2010	VLDB	6.3385889e-05
5,334	Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances	2008	VLDB	6.1750849e-05
5,874	DDE: From Dewey to a Fully Dynamic XML Labeling Scheme	2009	SIGMOD	5.9637398e-05
6,046	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.9052121e-05
6,800	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.6792071e-05
7,237	Labeling Workflow Views with Fine-Grained Dependencies	2012	VLDB	5.5785819e-05
7,418	Structured Materialized Views for XML Queries	2007	VLDB	5.5327659e-05
7,624	Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect	2007	SIGMOD	5.4821096e-05
7,753	XQuery Reloaded	2009	VLDB	5.4592972e-05
7,892	Contest of XML Lock Protocols	2006	VLDB	5.4326858e-05
8,022	Cost-Sensitive Reordering of Navigational Primitives	2005	SIGMOD	5.4054691e-05
8,146	Incremental Maintenance of Path-Expression Views	2005	SIGMOD	5.3910052e-05
8,147	DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data	2013	SIGMOD	5.3908805e-05
8,193	Labeling Recursive Workflow Executions On-the-Fly	2011	SIGMOD	5.3803708e-05
8,289	Relational Support for Flexible Schema Scenarios	2008	VLDB	5.3614788e-05
8,501	Efficient Keyword Search over Virtual XML Views	2007	VLDB	5.3296585e-05
8,745	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	5.2879425e-05
9,029	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.2342004e-05
9,752	Indexing Highly Dynamic Hierarchical Data	2015	VLDB	5.1349531e-05
10,227	TreeCat: Standalone Catalog Engine for Large Data Systems	2025	VLDB	5.0571508e-05
11,765	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	4.9793485e-05
12,096	Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data	2020	VLDB	4.9793485e-05
12,789	Cost Based Plan Selection for XPath	2009	SIGMOD	4.9793485e-05
12,979	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	4.9793485e-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.00035810622
166	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027254612
374	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00019707844
918	Accelerating XPath Location Steps	2002	SIGMOD	0.00013084437

Semantically Similar Papers

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