Cost-Sensitive Reordering of Navigational Primitives

Summary: Cost-sensitive reordering of navigational primitives for path queries using partial path instances; a physical algebra isolates I/O in a single operator with sequential or asynchronous I/O. No special storage formats; relies on simple tree navigations and standard optimizations; XMark experiments show up to 4× speedup from reordering. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3682
Venue: SIGMOD
Year: 2005
Pagerank: 4.631832e-05
Overall Rank: 7,852 | 45.43%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,324	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	5.5668659e-05
12,196	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
99	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00050043993
153	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00040759404
206	Storing Semistructured Data with STORED	1999	SIGMOD	0.00034583517
239	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031581944
712	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00017714027
843	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00015975516
1,028	Accelerating XPath Location Steps	2002	SIGMOD	0.00014578947
1,492	Advanced Query Processing in Object Bases Using Access Support Relations	1990	VLDB	0.00011683783
2,223	Efficient Assembly of Complex Objects	1991	SIGMOD	9.2579138e-05
2,567	Dual-Buffering Strategies in Object Bases	1994	VLDB	8.5240847e-05
2,862	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	7.9982917e-05
3,927	Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases	1994	VLDB	6.6207132e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,045	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00014451072
5,194	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.6318244e-05
414	A Fast Index for Semistructured Data	2001	VLDB	0.00023801668
11,256	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	4.1905499e-05
2,018	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7852268e-05
276	Regular Path Queries with Constraints	1997	PODS	0.00029365217
4,420	Reordering Query Execution in Tertiary Memory Databases	1996	VLDB	6.1942119e-05
2,506	Evaluating Queries with Generalized Path Expressions	1996	SIGMOD	8.6273062e-05
7,299	Benefits of Path Summaries in an XML Query Optimizer Supporting Multiple Access Methods	2005	VLDB	4.7641328e-05
3,904	Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases	1996	VLDB	6.6437893e-05