{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T03:05:47Z","timestamp":1761102347934,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2018,10,21]],"date-time":"2018-10-21T00:00:00Z","timestamp":1540080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computers"],"abstract":"<jats:p>Due to their large sizes and\/or dimensions, the classification of Big Data is a challenging task using traditional machine learning, particularly if it is carried out using the well-known K-nearest neighbors classifier (KNN) classifier, which is a slow and lazy classifier by its nature. In this paper, we propose a new approach to Big Data classification using the KNN classifier, which is based on inserting the training examples into a binary search tree to be used later for speeding up the searching process for test examples. For this purpose, we used two methods to sort the training examples. The first calculates the minimum\/maximum scaled norm and rounds it to 0 or 1 for each example. Examples with 0-norms are sorted in the left-child of a node, and those with 1-norms are sorted in the right child of the same node; this process continues recursively until we obtain one example or a small number of examples with the same norm in a leaf node. The second proposed method inserts each example into the binary search tree based on its similarity to the examples of the minimum and maximum Euclidean norms. The experimental results of classifying several machine learning big datasets show that both methods are much faster than most of the state-of-the-art methods compared, with competing accuracy rates obtained by the second method, which shows great potential for further enhancements of both methods to be used in practice.<\/jats:p>","DOI":"10.3390\/computers7040054","type":"journal-article","created":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T08:43:36Z","timestamp":1540284216000},"page":"54","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["Norm-Based Binary Search Trees for Speeding Up KNN Big Data Classification"],"prefix":"10.3390","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9991-304X","authenticated-orcid":false,"given":"Ahmad B. A.","family":"Hassanat","sequence":"first","affiliation":[{"name":"Information Technology College, Mutah University; Karak 61710, Jordan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,10,21]]},"reference":[{"key":"ref_1","unstructured":"Bol\u00f3n-Canedo, V., Remeseiro, B., Sechidis, K., Martinez-Rego, D., and Alonso-Betanzos, A. (2017, January 26\u201328). Algorithmic challenges in Big Data analytics. Proceedings of the European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, Bruges, Belgium."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Maillo, J., Triguero, I., and Herrera, F. (2015, January 20\u201322). A mapreduce-based k-nearest neighbor approach for big data classification. Proceedings of the 2015 IEEE Trustcom\/BigDataSE\/ISPA, Helsinki, Finland.","DOI":"10.1109\/Trustcom.2015.577"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.knosys.2016.06.012","article-title":"kNN-IS: An Iterative Spark-based design of the k-Nearest Neighbors classifier for big data","volume":"117","author":"Maillo","year":"2017","journal-title":"Knowl.-Based Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.neucom.2015.08.112","article-title":"Efficient kNN classification algorithm for big data","volume":"195","author":"Deng","year":"2016","journal-title":"Neurocomputing"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1016\/j.patcog.2017.09.038","article-title":"Clustering-based k-nearest neighbor classification for large-scale data with neural codes representation","volume":"74","author":"Gallego","year":"2018","journal-title":"Pattern Recognit."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/j.neucom.2017.12.061","article-title":"Efficient tree classifiers for large scale datasets","volume":"284","author":"Wang","year":"2018","journal-title":"Neurocomputing"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1774","DOI":"10.1109\/TNNLS.2017.2673241","article-title":"Efficient knn classification with different numbers of nearest neighbors","volume":"29","author":"Zhang","year":"2018","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_8","unstructured":"Hassanat, A.B., Abbadi, M.A., Altarawneh, G.A., and Alhasanat, A.A. (arXiv, 2014). Solving the problem of the K parameter in the KNN classifier using an ensemble learning approach, arXiv."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1089\/big.2018.0064","article-title":"Furthest-pair-based binary search tree for speeding big data classification using k-nearest neighbors","volume":"6","author":"Hassanat","year":"2018","journal-title":"Big Data"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional binary search trees used for associative searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Commun. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(91)90074-R","article-title":"Satisfying general proximity\/similarity queries with metric trees","volume":"40","author":"Uhlmann","year":"1991","journal-title":"Inf. Process. Lett."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., and Langford, J. (2006, January 25\u201329). Cover trees for nearest neighbor. Proceedings of the 23rd International Conference on Machine Learning, Pittsburgh, PA, USA.","DOI":"10.1145\/1143844.1143857"},{"key":"ref_13","unstructured":"Kibriya, A.M., and Frank, E. (2007, January 17\u201321). An empirical comparison of exact nearest neighbour algorithms. Proceedings of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases, Warsaw, Poland."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Cislak, A., and Grabowski, S. (2014, January 7\u201310). Experimental evaluation of selected tree structures for exact and approximate k-nearest neighbor classification. Proceedings of the Federated Conference on Computer Science and Information Systems (FedCSIS), Warsaw, Poland.","DOI":"10.15439\/2014F194"},{"key":"ref_15","unstructured":"(2018, March 11). Welcome to the UC Irvine Machine Learning Repository. Available online: http:\/\/archive.ics.uci.edu\/ml."},{"key":"ref_16","unstructured":"Fan, R.E. (2018, March 12). LIBSVM Data: Classification, Regression, and Multi-Label. Available online: https:\/\/www.csie.ntu.edu.tw\/~cjlin\/libsvmtools\/datasets\/."},{"key":"ref_17","first-page":"221","article-title":"Dimensionality invariant similarity measure","volume":"10","author":"Hassanat","year":"2014","journal-title":"J. Am. Sci."},{"key":"ref_18","first-page":"3291","article-title":"On enhancing the performance of nearest neighbour classifiers using hassanat distance metric","volume":"9","author":"Alkasassbeh","year":"2015","journal-title":"Can. J. Pure Appl. Sci."},{"key":"ref_19","first-page":"1","article-title":"Greedy algorithms for approximating the diameter of machine learning datasets in multidimensional euclidean space: Experimental results","volume":"7","author":"Hassanat","year":"2018","journal-title":"Adv. Distrib. Comput. Artif. Intell. J."}],"container-title":["Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-431X\/7\/4\/54\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:25:16Z","timestamp":1760196316000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-431X\/7\/4\/54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,21]]},"references-count":19,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,12]]}},"alternative-id":["computers7040054"],"URL":"https:\/\/doi.org\/10.3390\/computers7040054","relation":{},"ISSN":["2073-431X"],"issn-type":[{"type":"electronic","value":"2073-431X"}],"subject":[],"published":{"date-parts":[[2018,10,21]]}}}