In other words, for each
of the two pstring sizes (ws) for a query set, we vary the number of tuples (t)
and block size (Sb) and calculate the space occupied by the corresponding
PMap and the minimum and maximum number of index pages retrieved to
answer the queries in this set. For each database size and block size combination
corresponding to a PMap, we find 3 different REBSIs by varying the
scaling factor and using algorithms FindSmallestN and RefineIndex (Chan &
Ioannidis, 1998). In the REBSI for a query set, a separate REBSI is created for
every attribute that is present in the query set to be able to answer each query
completely. Then we determine the index pages retrieved using each of these
bitmaps for the particular query set using the Time formula (Chan & Ioannidis,
1998). Thus, the inputs to the REBSI storage and performance measurement
simulator are tuple size, block size and the scaling factor with respect to the corresponding
PMap. The results of these experiments for the PMap and REBSI
techniques with one query set (very high cardinality attributes) are presented
and analyzed here to illustrate the methodology and develop intuition for the
general observations we offer. Cost models and results for different query sets
are detailed elsewhere (Gupta et al., 2002).
Very High Cardinality Attribute Query Set
The very high cardinality attribute query set (VHCAQS) consists of high cardinality
attribute queries (Gupta et al.
Pages:
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376