Probabilistic model of hierarchical database indexes
// Software systems and computational methods. – 2017. – є 4.
– P. 15-31.
Read the article
Abstract: The subject of the study is the concept of hierarchical bitmap-indexes proposed by the author. It is that in order to improve the processing performance of queries on the time filter, the indices are supported not only for the values of the basic unit of time, but also for arbitrary larger multiple units. The object of the study is the construction of an analytic probability model of such indices for the particular case of the exponential distribution of a random stream of recording records in a database. The author focuses on such an aspect as the calculation of the discrete distribution of the number of indices involved in the processing of the query. The methodology of the study is probability theory, combinatorial methods, measure theory, computational experiment. In addition, it is shown that the latest concepts of the theory of cellular automata, such as the Zaitsev's neighborhood, can be used to study the features of the proposed model. The main results of the work can be formulated as follows: introduced an original, intuitive concept of building indexes; new, meaningful optimization problems for selecting a hierarchical index system are formulated; a mathematical model is constructed and verified, allowing to estimate the efficiency of using the chosen hierarchy of indices. It is shown that in the limiting case the model naturally tends to a set of fractal nature, in particular, one of the varieties of Cantor dust, for which the formula for calculating its Hausdorff-Besicovitch dimension is derived through the application parameters of the initial problem.
Keywords: Cantor dust, fractal set, total probability, exponential distribution, random flow of events, hierarchical bitmap-indexes, Hausdorff-Besikovitch dimensionality, disjunction, exclusive OR, Zaitsev's neighborhood
McNutt B. The Fractal Structure of Data Reference: Application to the Memory Hierarchy. - Kluwer Academic, Boston, 2000. - 132 p.
Bulut A., Singh A.K. Indexing and Querying Data Streams.-In book DataStreams: Models and Algorithms (edited by Charu C. Aggarwal).-Springer, 2007, 373 p.-pp.237-259.
Trub I.I. O raspredelenii kolichestva bitmap-indeksov dlya proizvol'nogo potoka zaneseniya zapisey v bazu dannykh //Programmnye sistemy i vychislitel'nye metody.-2017.-є 1.-s.11-21. DOI: 10.7256/2454-0714.2017.1.21790
Trub I.I. Analiticheskoe veroyatnostnoe modelirovanie bitmap-indeksov //Programmnye sistemy i vychislitel'nye metody.-2016-є 4.-s.315-323. DOI: 10.7256/2305-6061.2016.4.2109
Mandel'brot B. Fraktal'naya geometriya prirody.-Moskva, Institut komp'yuternykh issledovaniy, 2002.-656 s.
Gradshteyn I.S., Ryzhik I.M. Tablitsy integralov, summ, ryadov i proizvedeniy.-SPb, BKhV, 2011, 7-e izd.-1232 s.
Demenyuk S.L. Fraktal: mezhdu mifom i remeslom.-Akademiya issledovaniya kul'tury RINVOL, SPb, 2011.-296 s.