Digital Symposium Collection 2000

Hash in Place with Memory Shifting: Datacube Computation Revisited J.X. Yu and H. Lu   View Paper (PDF)   Return to Poster Session 2: Interoperable Databases Abstract A datacube on n attributes requires the computation of an aggregation function over all groups generated by 2**n interrelated GROUP-BYs. Even n is not very large, the computation could be very expensive if the database involved is large. Although a number of algorithms with various optimization techniques have been proposed, accurate estimation of memory requirement and efficient use of the available memory remain difficult issues. In this paper, we present a new approach for datacube computation. The approach uses the available memory to maintain a minimum number of hash tables for computing related cuboids and manages memory dynamically by shifting memory pages among hash tables. Therefore, no memory requirement estimation is necessary and all memory available can be fully utilized. Copyright(C) 2000 ACM