Apart from data and system specific parameters, we define a parameter called
scaling factor (sf), to facilitate the comparison between PMap and REBSI. We
consider REBSIs that are time-optimal under a given space constraint (Chan
& Ioannidis, 1998). REBSIs occupy a large amount of disk space because a
separate REBSI has to be created for each attribute to be indexed, so more
space is allotted to it than space occupied by the corresponding PMap. The
space constraint for REBSI is equal to the space occupied by the corresponding
PMap multiplied by a scaling factor. For example, a scaling factor of 2
means that the bitmap index occupies twice the space used by the PMap. The
minimum scaling factor is the smallest value for which a REBSI corresponding
to the PMap can be constructed. We vary scaling factors to compare PMap
performance with faster REBSIs; greater storage allocation reduces the number
of bitmaps that need to be scanned to answer a query. Apart from the minimum
scaling factor (sf_min) needed to create a REBSI, we consider one or two other
suitable sf values to create REBSI with increased space consumption but faster
performance. In other words, to create a REBSI with the same attributes as
the PMap requires four times the space (sf = 4) of the PMap. Since that is the
baseline performance for REBSI, we also create a REBSI that is 10 times the
2 Davis & Gupta
Copyright ?© 2007, Idea Group Inc.
Pages:
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373