A Linear Time Algorithm for Optimal Tree Sibling Partitioning and Approximation Algorithms in Natix

Summary: Presents a linear-time optimal algorithm for capacity-constrained ordered-tree partitioning that lets adjacent sibling subtrees share storage units, beyond conventional subtree partitions. Streaming heuristics retain near-optimality; sibling partitioning cuts partitions by >90% and doubles query performance. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h93711bb9545ee2ee
Venue: VLDB
Year: 2006
Pagerank: 4.9793485e-05
Overall Rank: 13,006 | 12.56%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Carl-Christian Kanne (University of Mannheim)
2. Guido Moerkotte (University of Mannheim)

BibTeX Citation

@article{kanne_vldb06,
        title = {{A Linear Time Algorithm for Optimal Tree Sibling Partitioning and Approximation Algorithms in Natix}},
        author = {Kanne, Carl-Christian and Moerkotte, Guido},
        journal = {PVLDB},
        series = {{VLDB} '06},
        volume = {32},
        pages = {91--102},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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
1,784	System RX: One Part Relational, One Part XML	2005	SIGMOD	9.6511778e-05
2,028	On the Performance of Object Clustering Techniques	1992	SIGMOD	9.1612098e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	14,067	Query-based Partitioning of Documents and Indexes for Information Lifecycle Management	2008	SIGMOD
2	6,137	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
3	5,971	Efficient Mining of XML Query Patterns for Caching	2003	VLDB
4	6,557	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD
5	3,027	Labeling Dynamic XML Trees	2002	PODS
6	2,733	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD
7	9,901	Fast Optimal Twig Joins	2010	VLDB
8	12,674	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB
9	1,554	Efficient Structural Joins on Indexed XML Documents	2002	VLDB
10	9,406	On Optimal Node Splitting for R-trees	1998	VLDB