Efficient Computation of Stream Cubes Using AVL Trees


The KIPS Transactions:PartD, Vol. 14, No. 6, pp. 597-604, Oct. 2007
10.3745/KIPSTD.2007.14.6.597,   PDF Download:

Abstract

Stream data is a continuous flow of information that mostly arrives as the form of an infinite rapid stream. Recently researchers show a great deal of interests in analyzing such data to obtain value added information. Here, we propose an efficient cube computation algorithm for multidimensional analysis of stream data. The fact that stream data arrives in an unsorted fashion and aggregation results can only be obtained after the last data item has been read, cube computation requires a tremendous amount of memory. In order to resolve such difficulties, we compute user selected aggregation tables only, and use a combination of an array and AVL trees as a temporary storage for aggregation tables. The proposed cube computation algorithm works even when main memory is not large enough to store all the aggregation tables during the computation. We showed that the proposed algorithm is practically fast enough by theoretical analysis and performance evaluation.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
J. H. Kim and M. Kim, "Efficient Computation of Stream Cubes Using AVL Trees," The KIPS Transactions:PartD, vol. 14, no. 6, pp. 597-604, 2007. DOI: 10.3745/KIPSTD.2007.14.6.597.

[ACM Style]
Ji Hyun Kim and Myung Kim. 2007. Efficient Computation of Stream Cubes Using AVL Trees. The KIPS Transactions:PartD, 14, 6, (2007), 597-604. DOI: 10.3745/KIPSTD.2007.14.6.597.