ЭФФЕКТИВНЫЙ АЛГОРИТМ ОПТИМИЗАЦИИ РАЗМЕРА БИТОВОГО ИНДЕКСА С ПОМОЩЬЮ ИМИТАЦИОННОЙ МОДЕЛИ
| Rok vydání: | 2019 |
|---|---|
| Předmět: | |
| DOI: | 10.24411/1993-8314-2019-10025 |
| Popis: | Рассмотрено применение ранее построенной имитационной модели иерархических битовых индексов к поиску оптимального размера индекса второго уровня. Предложен алгоритм, позволяющий получить хорошее приближение к точке минимума за один прогон модели, без ее многократного выполнения в различных точках поверхности отклика. Основной идеей алгоритма является моделирование специальным образом построенной функции от входных данных, свойства которой подробно исследованы в работе. The article continues learning of database hierarchical bitmap indices simulation model, that was earlier built by author. Target of research is to find optimal time unit size of the second level index for arbitrary distributions of new database records flow, query time length interval and granularity of query interval edges. The optimized value is average number of OR/XOR bitstring operations to satisfy range query. The usual way is to run model many times with different values of second level index size in accordance with chosen optimization method. Article proposes heuristic algorithm which allows to get very good initial approximation to optimal value with only one model run and in practice it quite can be assigned as the final solution. This result is obtained by some facts from renewal theory but mainly by consideration of special integral function from random model input data and replacement model output by values of this function. Mathematical properties of this function, that help to do such trick, are formulated and proved by means of simple number theory suggestions. It is noted, that this approach is similar to one, in which well known slice indexes are introduced . Proposed algorithm is confirmed by some numerical results for some kinds of input data distributions. Graphical illustrations of results are also presented. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|