Hierarchical Bin Buffering: Online Local Moments for Dynamic External Memory Arrays Export

@article{citeulike:4184915, abstract = {Local moments are used for local regression, to compute statistical measures such as sums, averages, and standard deviations, and to approximate probability distributions. We consider the case where the data source is a very large I/O array of size n and we want to compute the first N local moments, for some constant N. Without precomputation, this requires O(n) time. We develop a sequence of algorithms of increasing sophistication that use precomputation and additional buffer space to speed up queries. The simpler algorithms partition the I/O array into consecutive ranges called bins, and they are applicable not only to local-moment queries, but also to algebraic queries (MAX, AVERAGE, SUM, etc.). With N buffers of size sqrt{n}, time complexity drops to O(sqrt n). A more sophisticated approach uses hierarchical buffering and has a logarithmic time complexity (O(b log\_b n)), when using N hierarchical buffers of size n/b. Using Overlapped Bin Buffering, we show that only a single buffer is needed, as with wavelet-based algorithms, but using much less storage. Applications exist in multidimensional and statistical databases over massive data sets, interactive image processing, and visualization.}, archivePrefix = {arXiv}, author = {Lemire, Daniel and Kaser, Owen}, citeulike-article-id = {4184915}, citeulike-linkout-0 = {http://arxiv.org/abs/cs/0610128}, citeulike-linkout-1 = {http://arxiv.org/pdf/cs/0610128}, day = {24}, eprint = {cs/0610128}, keywords = {algorithms}, month = {Aug}, posted-at = {2009-03-17 01:20:10}, priority = {0}, title = {Hierarchical Bin Buffering: Online Local Moments for Dynamic External Memory Arrays}, url = {http://arxiv.org/abs/cs/0610128}, year = {2007} }

TY - JOUR ID - citeulike:4184915 L3 - citeulike-article-id:4184915 N2 - Local moments are used for local regression, to compute statistical measures such as sums, averages, and standard deviations, and to approximate probability distributions. We consider the case where the data source is a very large I/O array of size n and we want to compute the first N local moments, for some constant N. Without precomputation, this requires O(n) time. We develop a sequence of algorithms of increasing sophistication that use precomputation and additional buffer space to speed up queries. The simpler algorithms partition the I/O array into consecutive ranges called bins, and they are applicable not only to local-moment queries, but also to algebraic queries (MAX, AVERAGE, SUM, etc.). With N buffers of size sqrt{n}, time complexity drops to O(sqrt n). A more sophisticated approach uses hierarchical buffering and has a logarithmic time complexity (O(b log_b n)), when using N hierarchical buffers of size n/b. Using Overlapped Bin Buffering, we show that only a single buffer is needed, as with wavelet-based algorithms, but using much less storage. Applications exist in multidimensional and statistical databases over massive data sets, interactive image processing, and visualization. TI - Hierarchical Bin Buffering: Online Local Moments for Dynamic External Memory Arrays KW - algorithms AU - Lemire, Daniel AU - Kaser, Owen PY - 2007/Aug/24/ UR - http://arxiv.org/abs/cs/0610128 ER -