A Linear Time Algorithm for Optimal Tree Sibling Partitioning and Approximation Algorithms in Natix
Summary: Presents a linear-time algorithm for optimal partitioning of an ordered, weighted tree into fixed-capacity partitions, enabling adjacent siblings to share a partition (sibling partitioning). Also provides memory-light near-optimal heuristics; experiments show >90% fewer partitions and >2× faster queries than parent–child-only partitioning. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 99 | XMark: A Benchmark for XML Data Management | 2002 | VLDB | 0.00050043993 |
| 1,894 | On the Performance of Object Clustering Techniques | 1992 | SIGMOD | 0.00010175304 |
| 2,066 | System RX: One Part Relational, One Part XML | 2005 | SIGMOD | 9.64571e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 13,569 | Query-based Partitioning of Documents and Indexes for Information Lifecycle Management | 2008 | SIGMOD | - |
| 6,240 | Scaling Similarity Joins over Tree-Structured Data | 2015 | VLDB | 5.1362097e-05 |
| 6,221 | Efficient Mining of XML Query Patterns for Caching | 2003 | VLDB | 5.1446262e-05 |
| 6,697 | Optimal Splitters for Temporal and Multi-version Databases | 2013 | SIGMOD | 4.9538866e-05 |
| 3,151 | Labeling Dynamic XML Trees | 2002 | PODS | 7.4735481e-05 |
| 2,957 | Efficient Algorithms for Minimizing Tree Pattern Queries | 2002 | SIGMOD | 7.8143379e-05 |
| 9,594 | Fast Optimal Twig Joins | 2010 | VLDB | 4.3155661e-05 |
| 12,196 | Generating Efficient Execution Plans for Vertically Partitioned XML Databases | 2011 | VLDB | 4.1905499e-05 |
| 1,732 | Efficient Structural Joins on Indexed XML Documents | 2002 | VLDB | 0.00010716665 |
| 9,021 | On Optimal Node Splitting for R-trees | 1998 | VLDB | 4.4049428e-05 |