Eng During last 365 days Approved articles: 1995,   Articles in work: 340 Declined articles: 789 
Articles and journals | Tariffs | Payments | Your profile

Back to contents

Probabilistic model of hierarchical database indexes
Trub Il'ya

PhD in Technical Science

Senior Software Engineer, Samsung Research Center Ltd.

127018, Russia, Moscow, ul. Dvintsev, 12, of. C





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



Article was received:


Review date:


Publish date:


This article written in Russian. You can find full text of article in Russian here .

Vilenkin N.Ya. Kombinatorika.-M.: Nauka, 1969.-328 s.
Gerega A.N. Konstruktivnye fraktaly v teorii mnozhestv.-Odessa, "Osvita Ukrainy", 2017.-85 s.
Gradshtein I.S., Ryzhik I.M. Tablitsy integralov, summ, ryadov i proizvedenii.-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.
Kronover R.M. Fraktaly i khaos v dinamicheskikh sistemakh.-Moskva: Postmarket, 2000.-352 s.
Mandel'brot B. Fraktal'naya geometriya prirody.-Moskva, Institut komp'yuternykh issledovanii, 2002.-656 s.
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
Trub I.I. O raspredelenii kolichestva bitmap-indeksov dlya proizvol'nogo potoka zaneseniya zapisei v bazu dannykh //Programmnye sistemy i vychislitel'nye metody.-2017.- 1.-s.11-21. DOI: 10.7256/2454-0714.2017.1.21790
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.
McNutt B. The Fractal Structure of Data Reference: Application to the Memory Hierarchy. - Kluwer Academic, Boston, 2000. - 132 p.
Thiebaut D. From the fractal dimension of the intermiss gaps to the cache-miss ratio. - IBM J. Res. Develop., vol.32, No. 6, November, 1988. - pp.796-803.
Zaitsev D. A generalized neighborhood for cellular automata.-Theoretical Computer Science, 666 (2017), pp. 21-35