Key words
hierarchical bitmap-indices, OR and XOR operation, random event flow, distribution density function, simulation, confidence interval.
articles
The author:
Trub I. Published in
№ 4(76)
31 august 2018 year
Rubric: Theory and practice
Rubric: Theory and practice
Simulation of hierarchical bitmap-indices
The article describes simulation model of search queries to database with logical operations on hierarchical
bitmap indices. Proposed approach considers bitmaps on time property and combines multileveling
of bitmaps with their binning on sequence of different time units. The input data are distribution
of creation new records flow and distribution of query time interval, the varying condition is
bitmap hierarchy, the model output is average number of OR/XOR logical operations to satisfy query.
The target is to choose bitmap indices hierarchy, that minimizes this number. Simulation technique for
such kind of model is very special, that is why model is manually implemented on C language in order
to carefully cover all its features. Much attention is payed to output analysis as stopping rule when
required confidence interval for target parameter is obtained. Mathematical background of model includes
random number generators and some numerical methods, such as least square method, integration
and spectral analysis. Model verification is provided by several ways, in particular, by comparison
with existing analytical model results when input distribution is exponential. Several experiments
confirm existence of optimal hierarchy and were carried out for different kinds of distributions including
heavy-tailed. Graphical illustrations of simulation results are presented.
