Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
size of our PMap to investigate how the PMap competes with a more efficient
REBSI.
2. Measuring.PMap.performance:.The pstrings of a PMap are stored in a B+
tree for efficient searching. A query with multiple predicates can be rewritten
in disjunctive normal form and processed as separate queries whose results are
OR??™d together to obtain the query answer (we call this strategy A) or processed
as a single query (strategy B). In either case, multiple pfilters are generated;
we call the one with the lowest value pfilter low (pfilterl) and the one with the
highest value pfilter high (pfilterh). Only the pstrings with values between pfilterl
and pfilterh need to be searched in the B+ tree. For our performance study, the
more efficient strategy is chosen in each individual case. A minimum number
of record pointers to answer a query is computed based on the utilization of
a pstring; for example, a range property may only utilize 20 different values
even though 32 have to be allocated to store it (5 bits). A maximum number
of record pointers is computed based on the number of leaf level blocks that
appear between the lower and upper pfilters. The minimum represents best
case performance and the maximum is worst case performance.
Pages:
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374