The DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
kNN-IS: An Iterative Spark-based design of the k-Nearest Neighbors classifier for big data
Open accessAbstract
The k-Nearest Neighbors classifier is a simple yet effective widely renowned method in data mining. The actual application of this model in the big data domain is not feasible due to time and memory restrictions. Several distributed alternatives based on MapReduce have been proposed to enable this method to handle large-scale data. However, their performance can be further improved with new designs that fit with newly arising technologies.In this work we provide a new solution to perform an exact k-nearest neighbor classification based on Spark. We take advantage of its in-memory operations to classify big amounts of unseen cases against a big training dataset. The map phase computes the k-nearest neighbors in different training data splits. Afterwards, multiple reducers process the definitive neighbors from the list obtained in the map phase. The key point of this proposal lies on the management of the test set, keeping it in memory when possible. Otherwise, it is split into a minimum number of pieces, applying a MapReduce per chunk, using the caching skills of Spark to reuse the previously partitioned training set. In our experiments we study the differences between Hadoop and Spark implementations with datasets up to 11 million instances, showing the scaling-up capabilities of the proposed approach. As a result of this work an open-source Spark package is available.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
UCI Machine Learning Repository
Asuncion, A. (2007) · Medical Entomology and Zoology · Cited by 25,411
MapReduce: simplified data processing on large clusters
Dean, J., & Ghemawat, S. (2008) · Communications of the ACM · doi:10.1145/1327452.1327492 · Cited by 18,476
Nearest neighbor pattern classification
Cover, T., & Hart, P. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1053964 · Cited by 16,936
Advances in Neural Information Processing Systems 19
(2007) · The MIT Press eBooks · doi:10.52202/085713 · Cited by 15,539
Witten, I. H. (2008) · Cited by 9,143
Ghemawat, S., Gobioff, H., & Leung, S.-T. (2003) · ACM SIGOPS Operating Systems Review · doi:10.1145/1165389.945450 · Cited by 4,984
Validity of the single processor approach to achieving large scale computing capabilities
Amdahl, G. M. (1967) · Proceedings of the April 18-20, 1967, spring joint computer conference on - AFIPS '67 (Spring) · doi:10.1145/1465482.1465560 · Cited by 4,339
Distance Metric Learning for Large Margin Nearest Neighbor Classification
Weinberger, K. Q., & Saul, L. K. (2009) · Journal of Machine Learning Research · doi:10.5555/1577069.1577078 · Cited by 4,044
Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing
Zaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J. H., McCauley, M., Franklin, M. J. M., Shenker, S. J., & Stoica, I. G. (2012) · Cited by 3,622
Data-intensive applications, challenges, techniques and technologies: A survey on Big Data
Philip Chen, C. L., & Zhang, C.-Y. (2014) · Information Sciences · doi:10.1016/j.ins.2014.01.015 · Cited by 3,047
Using MPI: Portable parallel programming with the message-passing interface
(1995) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(95)90199-x · Cited by 2,854
White, T. (2009) · Cited by 2,800
Alcalá‐Fdez, J., Fernández, A., Luengo, J., Derrac, J., García, S., Sánchez, L., & Herrera, F. (2011) · Repositorio de la Universidad de Oviedo (RUO) · Cited by 2,730
Self-citationAn optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,300
Keulen, D. S. (2014) · Cited by 1,677
Introduction to Machine Learning
(2019) · Series in Machine Perception and Artificial Intelligence · doi:10.1142/9789811201967_0001 · Cited by 1,639
Map-Reduce for Machine Learning on Multicore
Chu, C.-T., Kim, S. K., Lin, Y.-A., Yu, Y., Bradski, G., Ng, A. Y., & Olukotun, K. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0040 · Cited by 1,229
Introduction to Machine Learning
(2010) · Kybernetes · doi:10.1108/k.2010.06739hae.001 · Cited by 1,183
Witten, I. H., & Frank, E. (2005) · Cited by 815
Lynch, C. (2008) · Nature · doi:10.1038/455028a · Cited by 705
HaLoop: efficient iterative data processing on large clusters
Bu, Y., Howe, B., Balazinska, M., & Ernst, M. D. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920881 · Cited by 693
The Top Ten Algorithms in Data Mining
(2009) · Chapman & Hall/CRC eBooks · doi:10.1201/9781420089653 · Cited by 670
Using MPI: Portable parallel programming with the message-passing interface
(2000) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(00)90207-4 · Cited by 654
Efficient kNN classification algorithm for big data
Deng, Z., Zhu, X., Cheng, D., Zong, M., & Zhang, S. (2016) · Neurocomputing · doi:10.1016/j.neucom.2015.08.112 · Cited by 603
Self-labeled techniques for semi-supervised learning: taxonomy, software and empirical study
Triguero, I., García, S., & Herrera, F. (2015) · Knowledge and Information Systems · doi:10.1007/s10115-013-0706-y · Cited by 573
Self-citationStudy on density peaks clustering based on k-nearest neighbors and principal component analysis
Du, M., Ding, S., & Jia, H. (2016) · Knowledge-Based Systems · doi:10.1016/j.knosys.2016.02.001 · Cited by 520
Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation
Feamster, N., & Mogul, J. (2013) · Cited by 355
Similarity-based Classification: Concepts and Algorithms
Chen, Y., Garcia, E. K., Gupta, M. R., Rahimi, A., & Cazzanti, L. (2009) · doi:10.5555/1577069.1577096 · Cited by 292
Big Data, Big Analytics: Emerging Business Intelligence and Analytic Trends for Today's Businesses
Minelli, M., Chambers, M., & Dhiraj, A. (2013) · doi:10.1002/9781118562260 · Cited by 263
Efficient processing of k nearest neighbor joins using MapReduce
Lu, W., Shen, Y., Chen, S., & Ooi, B. C. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2336664.2336674 · Cited by 250
Efficient parallel kNN joins for large data in MapReduce
Zhang, C., Li, F., & Jestes, J. (2012) · Proceedings of the 15th International Conference on Extending Database Technology · doi:10.1145/2247596.2247602 · Cited by 250
Luengo, J., García, S., & Herrera, F. (2012) · Knowledge and Information Systems · doi:10.1007/s10115-011-0424-2 · Cited by 241
Self-citationMRPR: A MapReduce solution for prototype reduction in big data classification
Triguero, I., Peralta, D., Bacardit, J., García, S., & Herrera, F. (2015) · Neurocomputing · doi:10.1016/j.neucom.2014.04.078 · Cited by 220
Self-citationFernández, A., del Río, S., López, V., Bawakid, A., del Jesus, M. J., Benítez, J. M., & Herrera, F. (2014) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1134 · Cited by 214
Self-citationLearning Spark: Lightning-Fast Big Data Analytics
Karau, H., Konwinski, A., Wendell, P., & Zaharia, M. (2015) · O'Reilly Media, Inc. eBooks · Cited by 162
Challenges for MapReduce in Big Data
Grolinger, K., Hayes, M., Higashino, W. A., L’Heureux, A., Allison, D. S., & Capretz, M. A. M. (2014) · IEEE World Congress on Services (SERVICES) · doi:10.1109/services.2014.41 · Cited by 160
Triguero, I., del Río, S., López, V., Bacardit, J., Benítez, J. M., & Herrera, F. (2015) · Knowledge-Based Systems · doi:10.1016/j.knosys.2015.05.027 · Cited by 150
Self-citationThe Conference on Uncertainty in Artificial Intelligence (UAI 2017)
Belle, V. (2017) · Cited by 139
Proceedings of the 14th International Conference on Extending Database Technology
Ailamaki, A., Amer-Yahia, S., Pate, J., Risch, T., Senellart, P. P., & Stoyanovich, J. (2011) · doi:10.1145/1951365 · Cited by 110
Mapreduce is Good Enough?If All You Have is a Hammer, Throw Away Everything That's Not a Nail!
Lin, J. (2012) · Big Data · doi:10.1089/big.2012.1501 · Cited by 90
Instance selection of linear complexity for big data
González, Á. A., Díez-Pastor, J.-F., Rodríguez, J. J., & García‐Osorio, C. (2016) · Knowledge-Based Systems · doi:10.1016/j.knosys.2016.05.056 · Cited by 83
Data and task parallelism in ILP using MapReduce
Srinivasan, A., Faruquie, T. A., & Joshi, S. (2011) · Machine Learning · doi:10.1007/s10994-011-5245-8 · Cited by 56
Distributed In-Memory Processing of All k Nearest Neighbor Queries
Chatzimilioudis, G., Costa, C., Demetrios Zeinalipour-yazti, A., Lee, W.-C., & Pitoura, E. (2015) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2015.2503768 · Cited by 30
Tagging and classifying facial images in cloud environments based on KNN using MapReduce
Kai, S., Kang, H., & Park, H. (2015) · Optik · doi:10.1016/j.ijleo.2015.07.080 · Cited by 24
Cited by
A survey on missing data in machine learning
Emmanuel, T., Maupong, T., Mpoeleng, D., Semong, T., Mphago, B., & Tabona, O. (2021) · Journal of Big Data · doi:10.1186/s40537-021-00516-9 · Cited by 1,067
Effects of Distance Measure Choice on K-Nearest Neighbor Classifier Performance: A Review
Abu Alfeilat, H. A., Hassanat, A. B. A., Lasassmeh, O., Tarawneh, A. S., Alhasanat, M. B., Eyal Salman, H. S., & Prasath, V. B. S. (2019) · Big Data · doi:10.1089/big.2018.0175 · Cited by 667
The state of the art and taxonomy of big data analytics: view from new big data framework
Mohamed, A., Najafabadi, M. K., Wah, Y. B., Zaman, E. A. K., & Maskat, R. (2020) · Artificial Intelligence Review · doi:10.1007/s10462-019-09685-9 · Cited by 265
Ramírez-Gallego, S., Fernández, A., García, S., Chen, M., & Herrera, F. (2018) · Information Fusion · doi:10.1016/j.inffus.2017.10.001 · Cited by 140
Self-citationFog-assisted personalized healthcare-support system for remote patients with diabetes
Devarajan, M., Subramaniyaswamy, V., Vijayakumar, V., & Ravi, L. (2019) · Journal of Ambient Intelligence and Humanized Computing · doi:10.1007/s12652-019-01291-5 · Cited by 105
Metadata
- Authors
- Maillo, J., Ramírez, S., Triguero, I., & Herrera, F.
- Venue
- Knowledge-Based Systems
- Publisher
- Elsevier BV
- Published
- 2017-02
- Volume
- 117
- Pages
- 3-15
- ISSN
- 0950-7051 (ISSN-L)
- OpenAlex
- W2432436793
- Cited by
- 316
- References
- 44
- FWCI
- 71.34
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.