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.00014329959
Overall Rank: 735 | 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.00043085722
1,497	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010447125
2,093	Indexing XML Data Stored in a Relational Database	2004	VLDB	9.0419151e-05
3,485	XML and Relational Database Management Systems: Inside Microsoft SQL Server 2005	2005	SIGMOD	7.243179e-05
4,208	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.7214366e-05
4,289	XQuery Implementation in a Relational Database System	2005	VLDB	6.6676702e-05
4,410	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.6011343e-05
4,985	Avalanche-Safe LINQ Compilation	2010	VLDB	6.3150185e-05
5,354	Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances	2008	VLDB	6.1517601e-05
5,887	DDE: From Dewey to a Fully Dynamic XML Labeling Scheme	2009	SIGMOD	5.9412062e-05
6,062	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.8829004e-05
6,816	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.6593309e-05
7,259	Labeling Workflow Views with Fine-Grained Dependencies	2012	VLDB	5.5575036e-05
7,441	Structured Materialized Views for XML Queries	2007	VLDB	5.5118606e-05
7,645	Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect	2007	SIGMOD	5.4613959e-05
7,776	XQuery Reloaded	2009	VLDB	5.4386695e-05
7,912	Contest of XML Lock Protocols	2006	VLDB	5.4124721e-05
8,045	Cost-Sensitive Reordering of Navigational Primitives	2005	SIGMOD	5.3850485e-05
8,169	Incremental Maintenance of Path-Expression Views	2005	SIGMOD	5.3706616e-05
8,170	DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data	2013	SIGMOD	5.3705113e-05
8,216	Labeling Recursive Workflow Executions On-the-Fly	2011	SIGMOD	5.3600428e-05
8,310	Relational Support for Flexible Schema Scenarios	2008	VLDB	5.3412209e-05
8,523	Efficient Keyword Search over Virtual XML Views	2007	VLDB	5.3095398e-05
8,774	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	5.2679623e-05
9,058	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.214424e-05
9,789	Indexing Highly Dynamic Hierarchical Data	2015	VLDB	5.115551e-05
10,263	TreeCat: Standalone Catalog Engine for Large Data Systems	2025	VLDB	5.0380426e-05
11,815	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	4.9605343e-05
12,146	Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data	2020	VLDB	4.9605343e-05
12,838	Cost Based Plan Selection for XPath	2009	SIGMOD	4.9605343e-05
13,027	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	4.9605343e-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.0003567995
167	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027156235
377	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00019634591
922	Accelerating XPath Location Steps	2002	SIGMOD	0.0001303574

Semantically Similar Papers

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