ASA-graphs for efficient data representation and processing

Horzyk, Adrian ; Bulanda, Daniel ; Starzyk, Janusz A.

International Journal of Applied Mathematics and Computer Science, Tome 30 (2020) no. 4, pp. 717-731.

Résumé

Fast discovering of various relationships in data is an important feature of modern data mining, cognitive, knowledge-based, and explainable AI systems, including deep neural networks. The ability to represent a rich set of relationships between stored data and objects is essential for fast inferences, finding associations, representing knowledge, and extracting useful patterns or other pieces of information. This paper introduces self-balancing, aggregating, and sorting ASA-graphs for efficient data representation in various data structures, databases, and data mining systems. These graphs are smaller and use more efficient algorithms for searching, inserting, and removing data than the most commonly used self-balancing trees. ASA-graphs also automatically aggregate and count all duplicates of values and represent them by the same nodes, connecting them in order, and simultaneously providing very fast data access based on a binary search tree approach. The proposed ASA-graph structure combines the advantages of sorted lists, binary search trees, B-trees, and B+trees, eliminating their weaknesses. Our experiments proved that the ASA-graphs outperform many commonly used self-balancing trees.

Détail

Keywords: self balancing trees, self sorting trees, self aggregating data structures, associative structures, data access efficiency, representation of relationships

Bibliographie

[1] [1] Adel’son-Vel’skii, G.M. and Landis, E.M. (1962). An algorithm for organization of information, Doklady Akademii Nauk 146(2): 263–266.

[2] [2] Altman, N.S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression, The American Statistician 46(3): 175–185.

[3] [3] Baran, M. (2018). Closest paths in graph drawings under an elastic metric, International Journal of Applied Mathematics and Computer Science 28(2): 387–397, DOI: 10.2478/amcs-2018-0029.

[4] [4] Bayer, R. and McCreight, E. (1972). Organization and maintenance of large ordered indices, Acta Informatica 1(3): 173–1.

[5] [5] Chen, L. and Schott, R. (1996). Optimal operations on red-black trees, International Journal of Foundations of Computer Science 7(03): 227–239.

[6] [6] Comer, D. (1979). Ubiquitous B-tree, ACM Computing Surveys 11(2): 121–137.

[7] [7] Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2009). Introduction to Algorithms, MIT Press, Cambridge, MA.

[8] [8] Dan, L. (2007). Indexing and Querying Moving Objects Databases, PhD thesis, National University of Singapore, Singapore.

[9] [9] Demaine, E.D., Harmon, D., Iacono, J. and Pătraşcu, M. (2007). Dynamic optimality—almost, SIAM Journal on Computing 37(1): 240–251.

[10] [10] Fan, K., Wang, X., Suto, K., Li, H. and Yang, Y. (2018). Secure and efficient privacy-preserving ciphertext retrieval in connected vehicular cloud computing, IEEE Network 32(3): 52–57.

[11] [11] Fenk, R. (2002). The BUB-tree, Proceedings of the 28th VLDB International Conference on Very Large Data Bases (VLDB’02), Hongkong, China, https://www.cse.ust.hk/vldb2002/VLDB2002-proceedings/papers/S34P16.pdf.

[12] [12] Graefe, G. (2011). Modern B-tree techniques, Foundations and Trends R _ in Databases 3(4): 203–402.

[13] [13] Guibas, L.J. and Sedgewick, R. (1978). A dichromatic framework for balanced trees, 19th Annual Symposium on Foundations of Computer Science (SFCS 1978), Ann Arbor, MI, USA, pp. 8–21.

[14] [14] Guttman, A. (1984). R-trees: A dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, Boston, MA, USA, pp. 47–57.

[15] [15] Haeupler, B., Sen, S. and Tarjan, R.E. (2015). Rank-balanced trees, ACM Transactions on Algorithms 11(4): 1–26.

[16] [16] Hibbard, T.N. (1962). Some combinatorial properties of certain trees with applications to searching and sorting, Journal of the ACM 9(1): 13–28.

[17] [17] Horzyk, A. (2013). Artificial Associative Systems and Associative Artificial Intelligence, Academic Publishing House EXIT, Warsaw, (in Polish).

[18] [18] Horzyk, A. (2015). Innovative types and abilities of neural networks based on associative mechanisms and a new associative model of neurons, Proceedings of the International Conference on Artificial Intelligence and Soft Computing, Zakopane, Poland, pp. 26–38.

[19] [19] Horzyk, A. (2017). Deep associative semantic neural graphs for knowledge representation and fast data exploration, Proceedings of the 9th International Conference on Knowledge Engineering and Ontology Development, Santa Cruz/Funchal, Madeira, Portugal, pp. 67–79.

[20] [20] Horzyk, A. (2018). Associative graph data structures with an efficient access via AVB+trees, Proceedings of the 11th International Conference on Human System Interaction, Gdańsk, Poland, pp. 169–175.

[21] [21] Horzyk, A. and Starzyk, J.A. (2018). Multi-class and multi-label classification using associative pulsing neural networks, 2018 IEEE World Congress on Computational Intelligence (WCCI 2018)/2018 International Joint Conference on Neural Networks (IJCNN 2018), Rio de Janeiro, Brazil, pp. 427–434.

[22] [22] Horzyk, A. and Starzyk, J.A. (2019). Associative data model in search for nearest neighbors and similar patterns, Proceedings of the 2019 IEEE Symposium Series on Computational Intelligence, Xiamen, China, pp. 932–939.

[23] [23] Horzyk, A., Starzyk, J.A. and Graham, J. (2017). Integration of semantic and episodic memories, Transactions on Neural Networks and Learning Systems 28(12): 3084–3095.

[24] [24] Jensen, C.S., Lin, D. and Ooi, B.C. (2004). Query and update efficient B+-tree based indexing of moving objects, Proceedings of the 30th International Conference on Very Large Data Bases, Toronto, Canada, Vol. 30, pp. 768–779.

[25] [25] Kim, W.-H., Seo, J., Kim, J. and Nam, B. (2018). clfB-tree: Cacheline friendly persistent B-tree for NVRAM, ACM Transactions on Storage 14(1): 1–17.

[26] [26] Knuth, D.E. (1998). Sorting and Searching. The Art of Computer Programming, Addison-Wesley, Boston, MA.

[27] [27] Lewicki, A. and Pancerz, K. (2020). Ant-based clustering for flow graph mining, International Journal of Applied Mathematics and Computer Science 30(3): 561–572, DOI: 10.34768/amcs-2020-0041.

[28] [28] Mehta, D. and Sahni, S. (2004). Handbook of Datastructures and Applications, CRS Press Tylor Francis Group, Boca Raton, FL.

[29] [29] Meidan, Y., Bohadana, M., Mathov, Y., Mirsky, Y., Shabtai, A., Breitenbacher, D. and Elovici, Y. (2018). N-BAIOT—network-based detection of IOT botnet attacks using deep autoencoders, IEEE Pervasive Computing 17(3): 12–22.

[30] [30] Pfaff, B. (2004). Performance analysis of BSTs in system software, ACMSIGMETRICS Performance Evaluation Review 32(1): 410–411.

[31] [31] Sagiv, Y. (1986). Concurrent operations on B*-trees with overtaking, Journal of Computer and System Sciences 33(2): 275–296.

[32] [32] Sedgewick, R. and Wayne, K. (2011). Algorithms, Addison-Wesley, Upper Saddle River, NJ.

[33] [33] Sharma, V., Kumar, R. and Kumar, N. (2018). DPTR: Distributed priority tree-based routing protocol for FANETs, Computer Communications 122: 129–151.

[34] [34] Shen,M., Jiang, X. and Sun, T. (2018). Anomaly detection based on nearest neighbor search with locality-sensitive B-tree, Neurocomputing 289: 55–67.

[35] [35] Sun, P., Wen, Y., Ta, D.N.B. and Xie, H. (2016). Metaflow: A scalable metadata lookup service for distributed file systems in data centers, IEEE Transactions on Big Data 4(2): 203–216.

[36] [36] Toptsis, A.A. (1993). B**-tree: A data organization method for high storage utilization, Proceedings of ICCI’93: 5th International Conference on Computing and Information, Sudbury, ON, Canada, pp. 277–281.

[37] [37] Wieczorek, M., Siłka, J., and Woźniak, M. (2020). Neural network powered COVID-19 spread forecasting model, Chaos, Solitons Fractals 140, Article no. 110203.

[38] [38] Woźniak, M., Wieczorek, M., Siłka, J. and Połap, D. (2020). Body pose prediction based on motion sensor data and recurrent neural network, IEEE Transactions on Industrial Informatics, DOI: 10.1109/TII.2020.3015934.

[39] [39] Wu, S., Jiang, D., Ooi, B.C. and Wu, K.-L. (2010). Efficient B-tree based indexing for cloud data processing, Proceedings of the VLDB Endowment 3(1–2): 1207–1218.