Abstract | ||
---|---|---|
We propose an efficient window aggregation method over multi-dimensional array data based on incremental computation. We improve several aggregations with different data structures exploited to achieve efficient computation: list for sum and avg, heap for max and min, and balanced binary search tree for percentile. We present time complexity analysis for the methods, and then evaluate performance with experiments in SciDB array database system with both synthetic and JRA55 meteorological dataset. Our analysis shows that performance improvement is proportional to the window size in the last dimension in theory, and the result of experiment is consistent with the analysis. In certain cases, it shows an acceleration factor more than 13 by the proposed method with percentile, while a factor over 28 with maximum. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1109/BigData.2014.7004230 | BigData Conference |
Keywords | Field | DocType |
window aggregation method,database management systems,parallel processing,incremental window aggregates,multi-dimensional array,incremental computation,tree data structures,data structures,scidb array database system,computational complexity,jra55 meteorological dataset,array database,time complexity analysis,multidimensional array data,heap,balanced binary search tree,acceleration factor,list,window aggregates | Array DBMS,Data mining,Data structure,Sparse array,Computer science,Self-balancing binary search tree,Heap (data structure),Time complexity,Percentile,Computation | Conference |
ISSN | Citations | PageRank |
2639-1589 | 1 | 0.34 |
References | Authors | |
13 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Li Jiang | 1 | 1 | 1.02 |
Hideyuki Kawashima | 2 | 2 | 1.72 |
Osamu Tatebe | 3 | 309 | 42.94 |