 |
В.А. Тищенко "Структура OPC-trie как новый тип индекса в СУБД НИКА" |
 |
|
Аннотация.
Построение индексов является стандартной процедурой в любой СУБД. Однако инвертированный индекс не обеспечивает оптимальный интерактивный доступ к ключевому массиву. Для оптимального доступа к ключам при организации интерактивного интерфейса предполагается использование сжатого префиксного дерева PATRICIA-trie в качестве индекса. Сама структура PATRICIA-trie не обеспечивает оптимального доступа к ключам и требует дополнительного сжатия префиксов для получения оптимального классификатора. Результатом, предлагаемым в данной статье, является использование оптимальной структуры OPC-trie в качестве индекса. OPC-trie создается посредством дополнительного сжатия по путям PATRICIA-trie и не требует динамического сжатия префиксов.
Ключевые слова:
PATRICIA-trie, OPC-trie, вариграммы, многоуровневый индекс по лексикографическому признаку.
Стр. 76-81.
DOI: 10.14357/20790279210408 Литература
1. Morrison, D. PATRICIA-practical algorithm to retrieve information coded in alphanumeric / D. Morrison // J. ACM 15,4. 0ct. 1968. P. 514-534. 2. Sussenguth E.H. Use tree structures for processing files / E.H. Sussenguth // CACM 6. 1963. P. 272-279. 3. Арлазаров В.Л. Устройство отыскания информации по ключевым словам / В.Л. Арлазаров, В.А. Тищенко // Патент на изобретение № 2679967 C1 Российская Федерация. 2019. Бюл. № 5. 4. Тищенко В.А. OPC-trie: спецификация оптимального классификатора для СУБД НИКА // Труды ИСА РАН. 2021. Т. 71. Вып. 1. С. 67-71. 5. Тищенко В.А. Выбор оптимального алфавитного классификатора при минимизации общего числа операций // Труды ИСА РАН. 2018. Т. 68. № 1. С.54-57. 6. Тищенко В.А. Идеальный случай классификатора по лексикографическому признаку при равномерном распределении ключей по префиксам / В.А. Тищенко // Материалы XXXIV Международной научно-практической конференции “Eurasiascience”, 31 декабря 2020 года. С.108-109. 7. Areias M. On the correctness and efficiency of a novel lock-free hash trie map design / Areias M., Rocha R.// JPDC,150, April 2021. P. 184-195. 8. Zhu A.Y.C. ROP Defense Using Trie Graph for System Security / Zhu A.Y.C., Yan W.Q., Sinha R. // IJDCF, 13,6. 2021. P. 1-12. 9. Moreno P. On the Implementation of Memory Reclamation Methods in a Lock-Free Hash Trie Design / Moreno P., Areias M., Rocha R.// JPDC,155, 2021, P.1-13. 10. Savnik I. Data structure set-trie for storing and querying sets: Theoretical and empirical analysis / Savnik I., Akulich M., Krnc M. // PLoS ONE 16(2). 2021.
|
