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: 9694
Venue: VLDB
Year: 2006
Pagerank: 5.093636e-05
Overall Rank: 12,716 | 12.76%
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
79	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00036555628
1,744	System RX: One Part Relational, One Part XML	2005	SIGMOD	9.868841e-05
1,992	On the Performance of Object Clustering Techniques	1992	SIGMOD	9.3427219e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,756	Query-based Partitioning of Documents and Indexes for Information Lifecycle Management	2008	SIGMOD
2	6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
3	5,848	Efficient Mining of XML Query Patterns for Caching	2003	VLDB
4	6,547	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD
5	2,967	Labeling Dynamic XML Trees	2002	PODS
6	2,680	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD
7	9,730	Fast Optimal Twig Joins	2010	VLDB
8	12,383	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB
9	1,523	Efficient Structural Joins on Indexed XML Documents	2002	VLDB
10	9,234	On Optimal Node Splitting for R-trees	1998	VLDB