Without
compression, one would clearly favor range encoding. However, with compression,
the relative strength is not as obvious. With a WAH compressed equality-encoded
index, it was shown that the cost of the index scan is proportional to the number of
hits, independent of the number of bitmaps involved (Wu et al., 2006). Because the
equality-encoded indices are much easier to compress, this could make the WAH
compressed equality-encoded index a preferred choice.
Finally, the binning strategy has an impact on the candidate check. The simplest
kind of binning, called equi-width binning, partitions the domain of the indexed
attribute into bins of equal size. As a result, each bin might have a different number
of entries. Equi-depth binning, on the other hand, distributes the number of entries
equally among the bins. This technique has a better worst-case behavior than equiwidth
binning but is more costly to build because one typically has to scan the data
first to generate the exact histogram before starting with the binning.
One approach to reduce the cost of building a set of equi-depth bins is to use a
sampled histogram instead of the exact histogram. Another approach is to first
build an equi-width binned index with more bins than desired, and then combine
the neighboring bins to form approximate equi-depth bins. However, the second
approach might not produce well-balanced bins.
Pages:
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335