In [SPAA2007], define a streaming B-tree (or index) as one that supports updates in amortized @math IOs, and present a structure achieving amortized @math IOs and queries in @math IOs. We extend their result to the partially-persistent case. For a version @math , let @math be the number of keys accessible at @math and @math be the total number of updates. We give a data structure using space @math , supporting updates to a leaf version @math with @math amortized IOs and answering range queries returning @math elements with @math IOs on average (where the average is over all queries covering disjoint key ranges at a given version). This is the first persistent streaming' index we are aware of, i.e. that supports updates in @math IOs and supports efficient range queries.
@cite_0 prove that any partially-persistent CO index that answers queries in @math IOs must use superlinear space. Our query bound comes close to this, except that the first term in our bound is @math , and the bound is an average-case bound, not worst-case. It remains open to improve our query bound to a worst-case one.
@cite_0
2059543065
We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space required by any cache-oblivious data structure for these problems that achieves an optimal query bound of O(logBN + K B) block transfers in the worst case, where K is the size of the query output. The problems we study are three-sided range reporting, 3-d dominance reporting, and 3-d halfspace range reporting. We prove that, in order to achieve the above query bound or even a bound of O((logB N)c (1 + K B)), for any constant c > 0, the structure has to use Ohmega(N (log log N)e) space, where e > 0 is a constant that depends on c and on the constant hidden in the big-Oh notation of the query bound. Our result has a number of interesting consequences. The first one is a new type of separation between the I O model and the cache-oblivious model, as I O-efficient data structures with the optimal query bound and using linear or O(N logAST N) space are known for the above problems. The second consequence is the non-existence of a linear-space cache-oblivious persistent B-tree with worst-case optimal 1-d range reporting queries.