Статья 'Обзор методов построения контейнеров данных «ключ-значение» для использования в самоадаптирующихся контейнерах данных' - журнал 'Кибернетика и программирование' - NotaBene.ru
по
Journal Menu
> Issues > Rubrics > About journal > Authors > About the Journal > Requirements for publication > Council of Editors > Peer-review process > Policy of publication. Aims & Scope. > Article retraction > Ethics > Online First Pre-Publication > Copyright & Licensing Policy > Digital archiving policy > Open Access Policy > Open access publishing costs > Article Identification Policy > Plagiarism check policy
Journals in science databases
About the Journal

Публикация за 72 часа - теперь это реальность!
При необходимости издательство предоставляет авторам услугу сверхсрочной полноценной публикации. Уже через 72 часа статья появляется в числе опубликованных на сайте издательства с DOI и номерами страниц.
По первому требованию предоставляем все подтверждающие публикацию документы!
MAIN PAGE > Back to contents
Cybernetics and programming
Reference:

Review of Constructing Key-Value Data Containers to be Used in Self-Adapting Data Containers

Potapov Danila Romanovich

post-graduate student of the Department of Software and Information Systems Administration at Voronezh State University

394018, Russia, Voronezh, str. Universitetskaya Square, 1, room No. 222

potapovd36@gmail.com
Artemov Mikhail Anatol'evich

Doctor of Physics and Mathematics

head of the Department of Software and Information Systems Administration at Voronezh State University

394018, Russia, Voronezh, str. Universitetskaya Square, 1, room No. 222

artemov_m_a@mail.ru
Baranovskii Evgenii Sergeevich

PhD in Physics and Mathematics

associate professor of the Department of Software and Information Systems Administration at Voronezh State University

394018, Russia, Voronezh, str. Universitetskaya Square, 1, room No. 222

esbaranovskii@gmail.com
Seleznev Konstantin Egorovich

PhD in Technical Science

associate professor of the Department of Software and Information Systems Administration at Voronezh State University

394018, Russia, Voronezh, str. Universitetskaya Square, 1, room No. 222

skostik@relex.ru

DOI:

10.25136/2306-4196.2017.5.23557

Review date:

10-07-2017


Publish date:

30-10-2017


Abstract.

The article is devoted to existing methods of constructing associative data containers that can be used in self-adapting data containers. Construction of associative containers is a topical issue due to the growing popularity and frequent use of such containers in the spheres of NoSQL and BigData. The present article provides a review and analysis of sorted-out and hashed containers such as various kinds of trees, SSTable, hash-tables, etc. In addition, the authors of the article also analyze the scope of application of these structures. The article is of reviewing nature and aims at analysis and comparison of existing methods of key-value data containers construction. Despite the fact that this topic is widely presented in the academic literature, at the present time there are no works that would be fully devoted to the systematic review and analysis of key-value data containers construction. As a result of the research, the authors have defined the main spheres of application of data containers when using self-adapting associative data containers. 

Keywords: LSM tree, SSTable, balanced trees, B-trees, associative containers, optimal container, store the data, fractal tree, heap, hashing
This article written in Russian. You can find full text of article in Russian here .

References
1.
Myusser D., Derdzh Zh., Seini A. C++ i STL. Spravochnoe rukovodstvo. 2-e izd. M.: Vil'yams, 2010. 430 s.
2.
Sadaladzh P. Dzh., Fauler M. NoSQL: Novaya metodologiya razrabotki nerelyatsionnykh baz dannykh. M.: Vil'yams, 2013. 172 s.
3.
SSTable & LSM-Tree [Elektronnyi recurs]. Rezhim dostupa: http://www.mezhov.com/2013/09/sstable-lsm-tree.html. – Zaglavie s ekrana (data obrashcheniya: 23.06.2017).
4.
Carpenter J., Hewitt E. Cassandra: The Definitive Guide, 2nd Edition. NY: O'Reilly Media, 2016. 360p.
5.
Islamov A. Sh., Artemov M. A., Baranovskii E. S., Kirgintsev M. V. Obrabotka bol'shikh ob''emov dannykh na osnove MapReduce // Informatika: problemy, metodologiya, tekhnologii. Materialy XV mezhdunarodnoi nauchno-metodicheskoi konferentsii. Voronezh: VGU, 2015. C. 78–80.
6.
SSTable and Log Structured Storage: LevelDB [Elektronnyi recurs]. Rezhim dostupa: https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb. Zaglavie s ekrana (data obrashcheniya: 23.06.2017).
7.
Zobov V. V., Seleznev K. E. Instrument dlya modelirovaniya nagruzki na konteinery dannykh // Materialy chetyrnadtsatoi nauchno-metodicheskoi konferentsii «Informatika: problemy, metodologiya, tekhnologii», 10-11 fevralya 2011 g. Voronezh: VGU, 2014. T. 3. S. 154–161.
8.
Akho A. V., Khopkroft D. E., Ul'man D. D. Struktury dannykh i algoritmy. M.: Vil'yams, 2003. 382 s.
9.
Kormen T. Kh. [i dr.] Algoritmy: postroenie i analiz. 2-e izd. M.: Izdatel'skii dom «Vil'yams», 2005. 1296 s.
10.
Topp U., Ford U. Struktury dannykh v C++. M.: Binom, 2000. 815 s.
11.
Virt H. Algoritmy + struktury dannykh = programmy. M.: Mir, 1985. 406 s.
12.
Struktury dannykh: binarnye derev'ya. Chast' 2: obzor sbalansirovannykh derev'ev [Elektronnyi recurs]. Rezhim dostupa: https://habrahabr.ru/post/66926/. Zaglavie s ekrana (data obrashcheniya: 23.06.2017).
13.
Knut D. E. Iskusstvo programmirovaniya dlya EVM. T. 1 : Osnovnye algoritmy. M.: Mir, 1976. 736 s.
14.
Sedzhvik R. Fundamental'nye algoritmy na Java. Ch. 1 – 4: Analiz. Struktury dannykh. Sortirovka. Poisk. Kiev: DiaSoft, 2002. 688 s.
15.
Aragon C. R., Seidel R. Randomized Search Trees // Proc. 30th Symp. Foundations of Computer Science. Washington, D.C.: IEEE Computer Society Press, 1989. P. 540–545.
16.
Sleator D. D., Tarjan R. E. Self-Adjusting Binary Search Trees // Journal of the ACM. 1985. № 32. P. 652–686.
17.
Andersson A. Improving partial rebuilding by using simple balance criteria // Proc. Workshop on Algorithms and Data Structures. Berlin: Springer-Verlag, 1989. P. 393–402.
18.
Levitin A. V. Algoritmy. Vvedenie v razrabotku i analiz. M.: Vil'yams, 2006. 576 s.
19.
Zubov V. S., Shevchenko I. V. Struktury i metody obrabotki dannykh. Praktikum v srede Delphi. M.: Filin'', 2004. 304 c.
20.
Berliner H. The B* Tree Search Algorithm. A Best-First Proof Procedure // Artificial Intelligence. 1979. № 12. P. 23–40.
21.
Arge L. The buffer tree: a new technique for optimal I/O-algorithms // In Proc. Workshop on Algorithms and Data Structures. Berlin: Springer-Verlag, 1995. P. 334–345.
22.
Bender M., Farach-Colton M., Jannen W, Johnson R., Kuszmaul B. C., Porter D. E., Yuan J., Zhan Y. An Introduction to Bε-Trees and Write-Optimization // In: login; magazine. 2015. Vol. 40. No 5. P. 22–28.
23.
Buchsbaum A. L., Goldwasser M., Venkatasubramanian S., Westbrook J. R. On external memory graph traversal // In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’00). Philadelphia: Society for Industrial and Applied Mathematics, 2000. P. 859–860.
24.
O’Neil P. E., Cheng E., Gawlick D., O’Neil E. J. The log-structured merge-tree (LSM-tree) // Acta Informatica. 1996. Vol. 33, No. 4. P. 351–385.
25.
Sears R., Ramakrishnan R. bLSM: a general purpose log structured merge tree // In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. NY: ASM, 2012. P. 217–228.
26.
Tan W., Tata S., Tang Y., Fong L. Diff-Index: Differentiated Index in Distributed Log-Structured Data Stores // In Proceedings of the 17th International Conference on Extending Database Technology, EDBT. Konstanz, Germany: OpenProceedings.org, 2014. P. 700–711.
27.
LevelDB [Elektronnyi recurs]. Rezhim dostupa: http://leveldb.org. – Zaglavie s ekrana (data obrashcheniya: 23.06.2017).
28.
Bender M. A., Farach-Colton M., Fineman J., Fogel Y., Kuszmaul B., Nelson J. Cache-Oblivious streaming B-trees // Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures. CA: ACM Press, 2007. P. 81–92.
29.
Alekseev V. E., Talanov V. A. Grafy i algoritmy. Struktury dannykh. Modeli vychislenii. M.: Internet Un-t Inform. Tekhnologii: BINOM, 2006. 320 s.
30.
T. Kh. Kormen [i dr.]. Algoritmy: postroenie i analiz = Introduction to Algorithms. M.: Vil'yams, 2005. 1296 s.
31.
Fredman M. L., Tarjan R. E. Fibonacci heaps and their uses in improved network optimization algorithms // Journal of the Association for Computing Machinery. 1987. Vol. 34, No. 3. P. 596–615.
32.
Kaplan H., Tarjan R. E. Thin heaps, thick heaps // ACM Transactions on Algorithms (TALG). 2008. Vol. 4, Article No. 3. P. 1–14.
33.
Crane C. A. Linear lists and priority queues as balanced binary trees. Stanford: Stanford University, 1972.
34.
Takaoka T. Theory of 2-3 Heaps // Discrete Applied Math. 2003. Vol. 126. P. 115–128.
35.
Brodal G. S., Okasaki C. Optimal purely functional priority queues // Journal of Functional Programming. 1996. Vol. 6. P. 839–857.
36.
Potapov D. R., Artemov M. A., Baranovskii E. S. Obzor uslovii adaptatsii samoadaptiruyushchikhsya assotsiativnykh konteinerov dannykh // Vestnik Voronezhskogo gosudarstvennogo universiteta. Seriya: Sistemnyi analiz i informatsionnye tekhnologii. 2017. № 1. S. 112–119.
37.
Gulakov V. K., Trubakov A.O. Mnogomernye struktury dannykh. Bryansk: BGTU, 2010. 387 s.
38.
Knut D. Iskusstvo programmirovaniya. T. 3. Sortirovka i poisk / D. Knut. 2-e izdanie. M.: «Vil'yams», 2007. S. 824.
39.
Pagh R., Flemming F. R. Cuckoo Hashing // Journal of Algorithms. 2004. Vol. 51. P. 122–144.
40.
Fredman M. L., Komlos J., Szemeredi E. Storing a Sparse Table with O(1) Worst Case Access Time // Journal of the ACM. 1984. Vol. 31. No. 3. P. 538–544.
41.
Herlihy M., Shavit N., Tzafrir M. Hopscotch Hashing // Proceedings of the 22nd international symposium on Distributed Computing. Arcachon, France: Springer-Verlag, 2008. P. 350–364.
42.
Fil'tr Bluma [Elektronnyi recurs]. Rezhim dostupa: https://ru.wikipedia.org/wiki/Fil'tr_Bluma. Zaglavie s ekrana (data obrashcheniya: 23.06.2017).
43.
Hash array mapped trie [Elektronnyi recurs]. Rezhim dostupa: https://habrahabr.ru/post/266861/. Zaglavie s ekrana (data obrashcheniya: 23.06.2017)
Link to this article

You can simply select and copy link from below text field.


Other our sites:
Official Website of NOTA BENE / Aurora Group s.r.o.
"History Illustrated" Website