1. bookVolume 30 (2020): Edition 4 (December 2020)
Détails du magazine
License
Format
Magazine
eISSN
2083-8492
Première parution
05 Apr 2007
Périodicité
4 fois par an
Langues
Anglais
access type Accès libre

ASA-graphs for efficient data representation and processing

Publié en ligne: 31 Dec 2020
Volume & Edition: Volume 30 (2020) - Edition 4 (December 2020)
Pages: 717 - 731
Reçu: 03 Aug 2020
Accepté: 20 Nov 2020
Détails du magazine
License
Format
Magazine
eISSN
2083-8492
Première parution
05 Apr 2007
Périodicité
4 fois par an
Langues
Anglais
Abstract

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.

Keywords

Adel’son-Vel’skii, G.M. and Landis, E.M. (1962). An algorithm for organization of information, Doklady Akademii Nauk146(2): 263–266.Search in Google Scholar

Altman, N.S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression, The American Statistician46(3): 175–185.10.1080/00031305.1992.10475879Search in Google Scholar

Baran, M. (2018). Closest paths in graph drawings under an elastic metric, International Journal of Applied Mathematics and Computer Science28(2): 387–397, DOI: 10.2478/amcs-2018-0029.10.2478/amcs-2018-0029Search in Google Scholar

Bayer, R. and McCreight, E. (1972). Organization and maintenance of large ordered indices, Acta Informatica1(3): 173–1.10.1007/BF00288683Search in Google Scholar

Chen, L. and Schott, R. (1996). Optimal operations on red-black trees, International Journal of Foundations of Computer Science7(03): 227–239.10.1142/S0129054196000178Search in Google Scholar

Comer, D. (1979). Ubiquitous B-tree, ACM Computing Surveys11(2): 121–137.10.1145/356770.356776Search in Google Scholar

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2009). Introduction to Algorithms, MIT Press, Cambridge, MA.Search in Google Scholar

Dan, L. (2007). Indexing and Querying Moving Objects Databases, PhD thesis, National University of Singapore, Singapore.Search in Google Scholar

Demaine, E.D., Harmon, D., Iacono, J. and Pǎtraşcu, M. (2007). Dynamic optimality—almost, SIAM Journal on Computing37(1): 240–251.10.1137/S0097539705447347Search in Google Scholar

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 Network32(3): 52–57.10.1109/MNET.2018.1700327Search in Google Scholar

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.Search in Google Scholar

Graefe, G. (2011). Modern B-tree techniques, Foundations and Trends ® in Databases3(4): 203–402.10.1561/1900000028Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

Haeupler, B., Sen, S. and Tarjan, R.E. (2015). Rank-balanced trees, ACM Transactions on Algorithms11(4): 1–26.10.1145/2689412Search in Google Scholar

Hibbard, T.N. (1962). Some combinatorial properties of certain trees with applications to searching and sorting, Journal of the ACM9(1): 13–28.10.1145/321105.321108Search in Google Scholar

Horzyk, A. (2013). Artificial Associative Systems and Associative Artificial Intelligence, Academic Publishing House EXIT, Warsaw, (in Polish).10.1007/978-3-642-29347-4_10Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

Horzyk, A., Starzyk, J.A. and Graham, J. (2017). Integration of semantic and episodic memories, Transactions on Neural Networks and Learning Systems28(12): 3084–3095.10.1109/TNNLS.2017.2728203Search in Google Scholar

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.Search in Google Scholar

Kim, W.-H., Seo, J., Kim, J. and Nam, B. (2018). clfB-tree: Cacheline friendly persistent B-tree for NVRAM, ACM Transactions on Storage14(1): 1–17.10.1145/3129263Search in Google Scholar

Knuth, D.E. (1998). Sorting and Searching. The Art of Computer Programming, Addison-Wesley, Boston, MA.Search in Google Scholar

Lewicki, A. and Pancerz, K. (2020). Ant-based clustering for flow graph mining, International Journal of Applied Mathematics and Computer Science30(3): 561–572, DOI: 10.34768/amcs-2020-0041.Search in Google Scholar

Mehta, D. and Sahni, S. (2004). Handbook of Datastructures and Applications, CRS Press Tylor & Francis Group, Boca Raton, FL.Search in Google Scholar

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 Computing17(3): 12–22.10.1109/MPRV.2018.03367731Search in Google Scholar

Pfaff, B. (2004). Performance analysis of BSTs in system software, ACM SIGMETRICS Performance Evaluation Review32(1): 410–411.10.1145/1012888.1005742Search in Google Scholar

Sagiv, Y. (1986). Concurrent operations on B*-trees with overtaking, Journal of Computer and System Sciences33(2): 275–296.10.1016/0022-0000(86)90021-8Search in Google Scholar

Sedgewick, R. and Wayne, K. (2011). Algorithms, Addison-Wesley, Upper Saddle River, NJ.Search in Google Scholar

Sharma, V., Kumar, R. and Kumar, N. (2018). DPTR: Distributed priority tree-based routing protocol for FANETs, Computer Communications122: 129–151.10.1016/j.comcom.2018.03.002Search in Google Scholar

Shen, M., Jiang, X. and Sun, T. (2018). Anomaly detection based on nearest neighbor search with locality-sensitive B-tree, Neurocomputing289: 55–67.10.1016/j.neucom.2018.02.012Search in Google Scholar

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 Data4(2): 203–216.10.1109/TBDATA.2016.2612241Search in Google Scholar

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.Search in Google Scholar

Wieczorek, M., Siłka, J., and Woźniak, M. (2020). Neural network powered COVID-19 spread forecasting model, Chaos, Solitons & Fractals140, Article no. 110203.Search in Google Scholar

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.10.1109/TII.2020.3015934Search in Google Scholar

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 Endowment3(1–2): 1207–1218.10.14778/1920841.1920991Search in Google Scholar

Articles recommandés par Trend MD

Planifiez votre conférence à distance avec Sciendo