A @math -nearest neighbor ( @math NN) query determines the @math nearest points, using distance metrics, from a specific location. An all @math -nearest neighbor (A @math NN) query constitutes a variation of a @math NN query and retrieves the @math nearest points for each point inside a database. Their main usage resonates in spatial databases and they consist the backbone of many location-based applications and not only (i.e. @math NN joins in databases, classification in data mining). So, it is very crucial to develop methods that answer them efficiently. In this work, we propose a novel method for classifying multidimensional data using an A @math NN algorithm in the MapReduce framework. Our approach exploits space decomposition techniques for processing the classification procedure in a parallel and distributed manner. To our knowledge, we are the first to study the classification of multidimensional objects under this perspective. Through an extensive experimental evaluation we prove that our solution is efficient and scalable in processing the given queries. We investigate many different perspectives that can affect the total computational cost, such as different dataset distributions, number of dimensions, growth of @math value and granularity of space decomposition and prove that our system is efficient, robust and scalable.
In @cite_9 a minimum spanning tree based classification model is introduced and it can be viewed as an intermediate model between the traditional @math -nearest neighbor method and cluster based classification method. Another approach presented in @cite_2 recommends parallel implementation methods of several classification algorithms, including @math -nearest neighbor, bayesian model, decision tree, but does not contemplate the nor the perspective of dimensionality nor parameter @math .
@cite_9 @cite_2
2097568515 1834667845
Rapid growth of data has provided us with more information, yet challenges the tradition techniques to extract the useful knowledge. In this paper, we propose MCMM, a Minimum spanning tree (MST) based Classification model for Massive data with MapReduce implementation. It can be viewed as an intermediate model between the traditional K nearest neighbor method and cluster based classification method, aiming to overcome their disadvantages and cope with large amount of data. Our model is implemented on Hadoop platform, using its MapReduce programming framework, which is particular suitable for cloud computing. We have done experiments on several data sets including real world data from UCI repository and synthetic data, using Downing 4000 clusters, installed with Hadoop. The results show that our model outperforms KNN and some other classification methods on a general basis with respect to accuracy and scalability. Data mining has attracted extensive research for several decades. As an important task of data mining, classification plays an important role in information retrieval, web searching, CRM, etc. Most of the present classification techniques are serial, which become impractical for large dataset. The computing resource is under-utilized and the executing time is not waitable. Provided the program mode of MapReduce, we propose the parallel implementation methods of several classification algorithms, such as k-nearest neighbors, naive bayesian model and decision tree, etc. Preparatory experiments show that the proposed parallel methods can not only process large dataset, but also can be extended to execute on a cluster, which can significantly improve the efficiency.