Patent ID: 7177854

Claim:
Method for processing a data cube for range-sum queries which includes a prefixed-sum cube to store the cumulative sum of data and a dynamic update cube using an multidimensional index structure called Δ-tree to store the updated values of the data cube comprising: storing only the changed information of the cell in the data cube into the Δ-tree, which constructed by the same process as a R*-tree, in which initially, the Δ-tree has only a directory node called root node, and whenever the data cube cell is updated, the difference Δ between new and old values of the data cube cell and its spatial position information are stored in the Δ-tree, instead of updating directly to the prefixed-sum cube, wherein the directory node contains (L 1, L 2 , . . . , L n ) , where L i is the tuple about i-th child node C i and has the form as (ΣΔ, M, cp i , MBR i ); ΣΔis the sum of all ΣΔvalues(Δvalues) of C i when C i is a directory node (data node); cp i is the address of C i and MBR i is the MBR enclosing all entries in C i ; M has the form of (μ 1 ,μ 2 . . . ,μ d ), where d is the dimension and μ j , is the mean position of the j-th dimension of MBR i which is defined as μ j = ∑ m = 1 n j ⁢ m ⁢ ⁢ F j ⁢ ( m ) ∑ m = 1 n j ⁢ F j ⁢ ( m ) , with F j ⁡ ( m ) = ∑ k h = 1 , n h k j = m h ≠ j ⁢ f ⁡ ( k 1 , … ⁢ , k j , … ⁢ , k d ) where f(k 1 ,k 2 , . . . k d ) is the value of an update position (k 1 , k 2 , . . . , k d ) in MBR i with 1 ≦k j ≦n j , and n j is the number of partitions of the j-th dimension of MBR i , and the data node is at level 0 and it contains (D 1 , D 2 , . . . , D n ), where D i is the tuple about i-th data entry and has the form (P i , Δ i ), with P i being the position index and Δ i being the difference between the changed cell; and managing the Δ-tree to improve the update speed of the data cube.