Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
base data. Typically, the records from these high-energy physics experiments are
not correlated with each other. Thus, it is generally hard for the run-length encoding
to be effective. This is why the index sizes for range encoding are relatively large
compared with the previous datasets. However, equality encoding compresses very
well for this physics dataset.
Overall, we see that the actual bitmap index sizes are considerably smaller than the
base data sizes and less than the sizes of typical commercial implementations of
B-trees (that are often three to four times the size of the base data).
Time. Complexity:.Query. Response.Time
In this section we are focusing on the two basic encoding methods, namely equality
encoding and range encoding. We have chosen these two encoding methods for the
following reason. Equality encoding showed to be the most space efficient method.
Range encoding, on the other hand, is the most time efficient method for one-sided
range queries (Chan & Ioannidis, 1998) that we use in our experiments.
Analyses have shown that the worst case query response time to answer a onedimensional
range query using a WAH compressed basic bitmap index (equalityencoded
without binning) is a linear function of the number hits (Wu et al.
Pages:
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340