Abstract. 

Index building is a standard procedure in any DBMS. However, an inverted index does not provide optimal interactive access to the key array. For optimal access to keys when organizing an interactive interface, the article [5] assumes the use of a compressed prefix tree PATRICIA-trie as an index. The PATRICIA-trie structure itself does not provide optimal access to keys and requires additional prefix compression to obtain an optimal classifier. The result suggested in this article is the use of an optimal OPC-trie structure as an index. OPCtrie is created by additional compression along PATRICIA-trie paths and does not require dynamic compression of prefixes.

Keywords: 

PATRICIA-trie, OPC-trie, varigrams, multilevel lexicographic index.

PP. 76-81.

DOI: 10.14357/20790279210408

 

References

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. Arlazarov V.L. Device for finding information by keywords / V.L. Arlazarov, V.A. Tishchenko // Patent for invention No. 2679967 C1 Russian Federation, 2019. Bul. No. 5

4. Tishchenko V.A. OPC-trie: specification of an optimal classifier for the NIKA DBMS // Proceedings of ISA RAS, 2021, 71, No. 1. P.67-71.

5. Tishchenko V.A. The choice of the optimal alphabetical classifier while minimizing the total number of operations // Proceedings of ISA RAS, 2018. V. 68. No. 1. P.54-57

6. Tishchenko, V.A. The ideal case of a lexicographic classifier with a uniform distribution of keys by prefixes / V.A. Tishchenko // Materials of the XXXIV International Scientific and Practical Conference “Eurasiascience”, December 31, 2020 pp.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.