K Nearest Neighbour Joins for Big Data on MapReduce: A Theoretical and Experimental Analysis
| Autor: | Frédéric Magoulès, Justine Rochas, Lea El Beze, Ge Song, Fabrice Huet |
|---|---|
| Přispěvatelé: | Mathématiques et Informatique pour la Complexité et les Systèmes (MICS), CentraleSupélec, Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), Laboratoire d'Excellence ANR-11-LABX-0031-01 |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Performance Evaluation
Theoretical computer science Computer science Computation Big data Joins 02 engineering and technology computer.software_genre Load management Knowledge extraction 020204 information systems 0202 electrical engineering electronic engineering information engineering MapReduce [INFO]Computer Science [cs] business.industry kNN Load balancing (computing) Computer Science Applications Computational Theory and Mathematics Programming paradigm 020201 artificial intelligence & image processing Algorithm design Data mining business computer Information Systems |
| Zdroj: | IEEE Transactions on Knowledge and Data Engineering IEEE Transactions on Knowledge and Data Engineering, Institute of Electrical and Electronics Engineers, 2016, 28 (9), pp.2376-2392. ⟨10.1109/TKDE.2016.2562627⟩ |
| ISSN: | 1041-4347 |
| Popis: | Given a point $p$ and a set of points $S$ , the kNN operation finds the $k$ closest points to in $S$ . It is a computational intensive task with a large range of applications such as knowledge discovery or data mining. However, as the volume and the dimension of data increase, only distributed approaches can perform such costly operation in a reasonable time. Recent works have focused on implementing efficient solutions using the MapReduce programming model because it is suitable for distributed large scale data processing. Although these works provide different solutions to the same problem, each one has particular constraints and properties. In this paper, we compare the different existing approaches for computing kNN on MapReduce, first theoretically, and then by performing an extensive experimental evaluation. To be able to compare solutions, we identify three generic steps for kNN computation on MapReduce: data pre-processing, data partitioning, and computation. We then analyze each step from load balancing, accuracy, and complexity aspects. Experiments in this paper use a variety of datasets, and analyze the impact of data volume, data dimension, and the value of k from many perspectives like time and space complexity, and accuracy. The experimental part brings new advantages and shortcomings that are discussed for each algorithm. To the best of our knowledge, this is the first paper that compares kNN computing methods on MapReduce both theoretically and experimentally with the same setting. Overall, this paper can be used as a guide to tackle kNN-based practical problems in the context of big data. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|