Eng During last 365 days Approved articles: 2088,   Articles in work: 317 Declined articles: 839 
Articles and journals | Tariffs | Payments | Your profile

Back to contents

The model of hierarchical indexes of databases with decision making and its comparison with the minimax model
Trub Il'ya

PhD in Technical Science

Senior Software Engineer, Samsung Research Center Ltd.

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



Trub Nataliya

Senior Lecturer, Department of Mathematics, Moscow State University for the Humanities and Economics

107150, Russia, g. Moscow, ul. Losinoostrovskaya, 49



The subject of the study is the concept of hierarchical bitmap-indexes proposed by the authors. 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 to construct a probabilistic model that makes it possible to evaluate the effectiveness of decision making: what bitwise operation to apply at the next level of the hierarchy when constructing the resulting sample is a disjunction or an exclusive OR. The author focuses on justifying the validity of the model and comparing the results with the previously constructed minimax model, in which the decision was made according to a pre-established rule and did not depend on the current state of the system. The methodology of the study is probability theory, methods multicriteria optimization and computational experiment, as well as related methods of intuitive evaluation of the likelihood of the results. Main conclusions of the study: an analytical model of the dynamic selection of an index operation has been constructed and verified; It is shown that the proposed discipline of choice gives higher productivity in comparison with the minimax model and software is developed to obtain a numerical estimate of this difference; a model for estimating the costs of dynamic decision making and a weight function that allows one to evaluate the efficiency of the model with decision making and to choose one of the two models is proposed for this or that choice of weights.

Keywords: multi-criterial optimization, binning, minimax rule, exclusive OR, disjunction, exponential distribution, total probability, random flow of events, hierarchical bitmap-indexes, weighted function



Article was received:


Review date:


Publish date:


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

Venttsel' E.S. Teoriya veroyatnostei.-M.: Nauka, 1969.-576 s.
Kleinrok L. Teoriya massovogo obsluzhivaniya.-M.: Mashinostroenie, 1979.-432 s.
Larichev O. Teoriya i metody prinyatiya reshenii.-M.: Logos,2002.-392 s.
Podinovskii V.V. Vvedenie v teoriyu vazhnosti kriteriev v mnogokriterial'nykh zadachakh prinyatiya reshenii.-M.: Fizmatlit, 2007.-63 s.
Podinovskii V.V., Potapov M.A. Metod vzveshennoi summy kriteriev v analize mnogokriterial'nykh reshenii: PRO et CONTRA.-Biznes-Informatika, 3(25), 2013.-s.41-48.
Sokolov A.V., Tokarev V.V. Metody optimal'nykh reshenii. T.1.-M.: Fizmatlit, 2011.-564 s.
Trub I.I. Analiticheskaya veroyatnostnaya model' bitmap-indeksov. //Programmnye sistemy i vychislitel'nye metody.-2016.-4.-s.315-323. DOI: 10.7256/2305-6061.2016.4.21091
Trub I.I. Veroyatnostnaya model' ierarkhicheskikh indeksov baz dannykh. //Programmnye sistemy i vychislitel'nye metody.-2017.- 4.-s.15-31. DOI: 10.7256/2454-0714.2017.4.24437 URL: http://nbpublish.com/library_read_article.php?id=24437
Fedorov V.V. Chislennye metody maksimina.-M.: Nauka, 1979.-280 s.
Chmiel J., Morzy T., Wrembel R. HOBI: Hierarchically Organized Bitmap Index for Indexing Dimensional Data. - In Proc. of the Eleventh International Conference on Data Warehousing and Knowledge Discovery (DaWaK), August, 2009, pp. 87-98. DOI: 10.1007/978-3-642-03730-6_8
Kim J.W. Binning Strategy for Hierarchical Bitmap Indices with Large Scale Domain Hierarchy. - International Journal of Applied Engineering Research, Volume 11, Number 18 (2016), pp.9289-9296.
Morzy M., Morzy T., Nanopoulos A., Manolopoulos Y. Hierarchical Bitmap Index: an Efficient and Scalable Indexing Technique for Set-Valued Attributes. - In Proc. "Advances in Databases and Information Systems, Seventh East European Conference, ADBIS 2003, Dresden, Germany, September 3-6, 2003", volume 2798 of Lecture Notes in Computer Science, pp. 236-252. - Springer, 2003.
Nagarkar P., Candan K. HCS: Hierarchical Cut Selection for Efficiently Processing Queries on Data Columns using Hierarchical Bitmap Indices. - In Proc. 17-th International Conference on Extending Database Technology (EDBT), March 24-28, 2014, Athens, Greece. pp. 271-282.
Nagarkar P., Candan K., Bhat A. Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads. - In Proc. of the VLDB Endowment, Volume 8, Number 12, 2015, pp.1382-1393.
Otoo E., Wu K. Accelerating Queries on Very Large Datasets. - In book "Sceintific Data Management. Challenges, Technology and Deployment" (edited by Arie Shoshani, Doron Rotem), pp.183-234. - Chapman & Hall/CRC, 2010, 558 p.
Pieprzyk J., Morzy M., Comarch S. Mining Generalized Association Rules Using Prutax and Hierarchical Bitmap Index. - URL: www.cs.put.poznan.pl/mmorzy/papers/admkd07.pdf
Wu K., Madduri K., Canon S. Multi-Level Bitmap Indexes for Flash Memory Storage. - In Proc. of the 14-th International Database Engineering & Applications Symposium (IDEAS), 2010, pp.114-116.DOI: 10.1145/1866480.1866497.
Wojciechowski A., Wrembel R. On Index Structures for Star Query Processing in Data Warehouses. - In book "Business Intelligence. Third European Summer School, eBISS 2013, Dagsuhl Castle, Germany, July 7-12, 2013. Tutorial Lectures" (edited by Esteban Zimanyi), pp. 182-217. - Springer, 2014, 245 p. DOI 10.1007/978-3-319-05461-2