Vestnik КRAUNC. Fiz.-Mat. nauki. 2023. vol. 43. no. 2. P. 44-54. ISSN 2079-6641

INFORMATION AND COMPUTATION TECHNOLOGIES
https://doi.org/10.26117/2079-6641-2023-43-2-44-54
Research Article
Full text in Russian
MSC 68T99

Contents of this issue

Read Russian Version

Binary Coding of Hierarchical Structures

V. S. Kirillov^\ast

Kabardino-Balkarian Scientific Center of the Russian Academy of Sciences 360010, Nalchik, 2 Balkarov street, Russia

Abstract. This article presents an algorithm that provides enhanced capabilities for representing keys in hierarchical structures. By using a binary representation of the materialized path, it allows efficient sorting of nodes through bitwise comparison and rapid computation of upper and lower bounds for all keys within the subtree. This methodology finds widespread application in database design and information filtering tasks. The study compares this algorithm with various approaches used in well-known database servers. The research findings confirm the effectiveness of the proposed method and its advantages over alternative approaches. It enables faster execution of sorting operations and computation of key bounds, which are critical for the efficient functioning of databases and processing large volumes of information. Therefore, the presented algorithm holds significant practical relevance and can serve as a valuable tool in the development and optimization of databases, as well as in other tasks related to information processing and filtering.

Key words: trees data, hierarchies, relational database & models

Received: 03.04.2023; Revised: 12.04.2023; Accepted: 16.04.2023; First online: 30.06.2023

For citation. Kirillov V.S. Binary coding of hierarchical structures. Vestnik KRAUNC. Fiz.-mat. nauki. 2023, 43: 2, 44-54. EDN: XUMKPG. https://doi.org/10.26117/2079-6641-2023-43-2-44-54.

Funding. The work was carried out without the support of funds.

Competing interests. There are no conflicts of interest regarding authorship and publication.

Contribution and Responsibility. The author participated in the writing of the article and is fully responsible for submitting the final version of the article to the press.

^\astCorrespondence: E-mail: vkirillov74@gmail.com

The content is published under the terms of the Creative Commons Attribution 4.0 International License

© Kirillov V.S., 2023

© Institute of Cosmophysical Research and Radio Wave Propagation, 2023 (original layout, design, compilation)

References

  1. O’Neil P. et al. ORDPATHs: Insert-friendly XML node labels. Proceedings of the 2004 ACM SIGMOD international conference on Management of data, 2004, 903-908. http://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/2014/2007/Papers/ordpath.pdf
  2. PostgreSQL index – ltree https://www.postgresql.org/docs/current/ltree.html
  3. Guttman A. R-trees: A dynamic index structure for spatial searching http://www.sai. msu.su/~megera/postgres/gist/papers/gutman-rtree.pdf
  4. Zabavskyy A. Closure Table Pattern to Model Hierarchies in NoSQL https://towardsdatascience.com/closure-table-pattern-to-model-hierarchies-in-nosqlc1be6a87e05b
  5. Oracle-Hierarchical Queries https://docs.oracle.com/database/121/SQLRF/queries003.htm#SQLRF52332
  6. Abdelali E., Mazouz S. et al. Different Approaches to Modeling the Trees Data in Relational Database. International Journal of Computer Applications. 2012, 53, 18.
  7. Tropashko V. Nested Intervals Tree Encoding with Continued Fraction.
  8. Tropashko V. Encoding in SQL, SIGMOD. Nested Intervals Tree. 2005.
  9. Tropashko V. Trees in SQL: Nested Sets and Materialized Path. 2003.
  10. Tropashko V. Nested Intervals with Farey Fractions. 2004.
  11. Celko J. Trees & Hierarchy in SQL for Smarties. Morgan Kaufmann Publishers, San Francisco, 2004, CA 94111.
  12. Celko J. SQL for Smarties: Advanced SQL Programming. Morgan Kaufmann Publishers, San Francisco, 1999, CA, p. 576.
  13. Celko J. Thinking in Auxiliary Sets, Temporal and Virtual Tables in SQL. Morgan Kaufmann Publishers, Burlington, 2008. MA 01803-4255.
  14. Celko J. SQL for Smarties: Advanced SQL Programming third edition. Morgan Kaufmann Publishers, San Francisco, continuation 400, 2005, CA 94111.
  15. Celko J. SQL for Smarties: Advanced SQL Programming fourth edition. Morgan Kaufmann Publishers, Burlington, 2011, MA 01803.
  16. Leiserson Ch.E., Prokop H., Randall K.H. Using de Bruijn Sequences to Index a 1 in a Computer Word http://supertech.csail.mit.edu/papers/debruijn.pdf
  17. Count the consecutive zero bits (trailing) on the right with modulus division and lookup https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightModLookup
  18. Reverse bits in word by lookup table https://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
  19. Kernighan B.W., Ritchie D. M. C Programming Language 2nd Ed.
  20. Beeler M., Gosper R.W., Schroeppel R. H. MIT Artificial intelligence memo, 239, 1972
  21. Interleave bits by table lookup https://graphics.stanford.edu/~seander/bithacks.
    html#InterleaveTableLookup

Information about author

Kirillov Vladimir Svjatoslavovich – Ph. D. (Phys. & Math.), Researcher, Kabardino-Balkarian Scientific Center of the Russian Academy of Sciences, Russia, ORCID 0009-0007-3996-1844.

Read articleDownload article