, 2005b).
There are a number of strategies to minimize the time required for the candidate
check (Koudas, 2000; Rotem et al., 2005a, 2005b; Stockinger et al., 2004). Koudas
(2000) considered the problem of finding the optimal binning for a given set of
equality queries. Rotem et al. (2005a, 2005b) considered the problem of finding the
optimal binning for range queries. Their approaches are based on dynamic programming.
Since the time required by the dynamic programming grows quadratic with
the problem size, these approaches are only efficient for attributes with relatively
small attribute cardinalities (Koudas, 2000) or with relatively small sets of known
queries (Stockinger et al., 2004). Stockinger et al. (2004) considered the problem
of optimizing the order of evaluating multidimensional range queries. The key idea
is to use more operations on bitmaps to reduce the number of candidates checked.
This approach usually reduces the total query response time. Further improvements
to this approach are to consider the attribute distribution and other factors that influence
the actual time required for the candidate check.
Figure 4. Range query ???37 <= A < 63??? on a bitmap index with binning
66 Stockinger & Wu
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission of
Idea Group Inc.
Pages:
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328