This suggests that the indexing
methods for OLAP must put more emphasis on searching than on updating. Among
the indexing methods known in the literature, the bitmap index has the best balance
between searching and updating for OLAP operations.
Frequently, in OLAP operations each query involves a number of attributes. Furthermore,
each new query often involves a different set of attributes than the previous
one. Using a typical multidimensional indexing method, a separate index is required
for nearly every combination of attributes (Gaede & Guenther, 1998). It is easy to
see that the number of indices grows exponentially with the number of attributes
in a dataset. In the literature this is sometimes called the curse of dimensionality
(Berchtold et al., 1998; Keim & Hinneburg, 1999). For datasets with a moderate
number of dimensions, a common way to cure this problem is to use one of the
multidimensional indexing methods, such as R-Trees or kd-trees. These approaches
have two notable shortcomings. Firstly, they are effective only for datasets with a
modest number of dimensions, say, < 15. Secondly, they are only efficient for queries
involving all indexed attributes. However, in many applications only some of the
attributes are used in the queries. In these cases, the conventional indexing methods
are often not efficient. For ad hoc range queries, most of the known indexing
methods do not perform better than the projection index (O??™Neil & Quass, 1997),
which can be viewed as one way to organize the base.
Pages:
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316