Hierarchical Bin Buffering: Online Local Moments for Dynamic External Memory Arrays
For a massive I/O array of size n, we want to compute the first N local moments, for some constant N. Our simpler algorithms partition the array into consecutive ranges called bins, and apply not only to local-moment queries, but also to algebraic queries. With N buffers of size v n, time complexity drops to O(root n). A more sophisticated approach uses hierarchical buffering and has a logarithmic time complexity (O(blog(b) n)), when using N hierarchical buffers of size n/b. Using overlapped bin buffering, we show that only one buffer is needed, as with wavelet-based algorithms, but using much less storage.
hierarchical buffers very large arrays statistical queries polynomial fitting