In
order to create a REBSI with the same attributes as the PMap, four times the space
is required (min_sf = 4). Table 10 shows the average number of bitmap scans for
each attribute for both database sizes, with the min_sf and 8K blocksize. The size
of each bitmap in blocks (z) is also given for both cases.
Observations
Figure 2 shows a performance comparison graph for the two techniques and the
VHCAQS for the database size of 1,000,000 tuples and 8K blocksize. The x-axis
shows the queries and the y-axis shows the index pages retrieved for each query.
The queries are ordered in decreasing order of the difference between the average
number of index pages retrieved by the PMap (PAvg) and the number of pages
retrieved by the REBSI with the smallest scaling factor (min_sf), i.e., occupying
the minimal required space. To simplify the figure, performance results for HC11
and HC12 are not shown. In both cases, the number of index blocks exceeds 3,000
for the smaller REBSI (sf = 4) and 1,000 for the larger REBSI (sf = 10); the PMap
average number of blocks is 36 and 113, respectively.
Table 9a. pmasks for queries in the VHCAQS
ID K100k K10k K1k K2 KSEQ
HC1 0 0 0 0 1 1 0 0 0 0 0
HC2 0 0 1 1 0 0 0 0 0 0 0
HC3 1 1 0 0 0 0 0 0 0 0 0
HC7 0 0 0 0 0 0 0 1 1 1 1
HC4 0 0 0 0 1 1 1 0 0 0 0
HC5 0 0 1 1 0 0 1 0 0 0 0
HC6 1 1 0 0 0 0 1 0 0 0 0
HC8 0 0 0 0 0 0 1 1 1 1 1
HC9 0 0 1 1 0 0 0 0 0 0 0
HC10 1 1 0 0 0 0 0 1 1 1 1
HC11 0 0 1 1 0 0 0 1 1 1 1
HC12 1 1 0 0 0 0 0 1 1 1 1
6 Davis & Gupta
Copyright ?© 2007, Idea Group Inc.
Pages:
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379