In Figure 7 we depict such an allocation of chunks into buckets. In this figure we
depict an arbitrary chunk-tree, where subtrees appear as triangles and specific nodes
(i.e., chunks) as squares. The number within a triangle denotes the size of the corresponding
subtree. The number within a square denotes the size of all subtrees
under this node, plus the size of the node itself. In the figure, we have assumed a
bucket size of 30 storage units. The lowest depth subtree that has been stored in a
bucket corresponds to depth D = 1 (see bucket B1). This bucket has the maximum
hierarchical clustering degree among all buckets of the specific chunk-to-bucket
allocation. Essentially this means that HPP queries that need to access B1 will have
reduced I/O cost, since this bucket has stored a larger subspace.
Figure 7. The chunk-to-bucket allocation for a chunk-tree where the size of a bucket
is SB = 30 units of storage
6
40
0
20
D = 0
D MAX =
D =
SB = 30
B
B
B
Advanced Ad Hoc Star Query Processing 149
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission
of Idea Group Inc. is prohibited.
Note that the upper nodes (including the root node) that ???fail??? to be allocated to
some bucket comprise the root-directory of the CUBE File. The root-directory is
usually cached in main memory or it is further allocated into buckets as if it is a
chunk-tree on its own.
Pages:
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297