NobleBlocks

Research indexJournal article

A MapReduce-based kNN Join Query Processing Algorithm for Analyzing Large-scale Data

Lee, Kim, Chang

Journal of KIISE15 Apr 2015

NobleIDark:/48914/w1/20260524/A5C78C1EDOI10.5626/jok.2015.42.4.504

Paywalled

The full text is at the publisher

You can read the abstract here, or open it at the publisher.

Read at the publisher

Abstract

Recently, the amount of data is rapidly increasing with the popularity of the SNS and the development of mobile technology. So, it has been actively studied for the effective data analysis schemes of the large amounts of data. One of the typical schemes is a Voronoi diagram based on kNN join algorithm (VkNN-join) using MapReduce. For two datasets R and S, VkNN-join can reduce the time of the join query processing involving big data because it selects the corresponding subset Sj for each Ri and processes the query with them. However, VkNN-join requires a high computational cost for constructing the Voronoi diagram. Moreover, the computational overhead of the VkNN-join is high because the number of the candidate cells increases as the value of the k increases. In order to solve these problems, we propose a MapReduce-based kNN-join query processing algorithm for analyzing the large amounts of data. Using the seed-based dynamic partitioning, our algorithm can reduce the overhead for constructing the index structure. Also, it can reduce the computational overhead to find the candidate partitions by selecting corresponding partitions with the average distance between two seeds. We show that our algorithm has better performance than the existing scheme in terms of the query processing time.

Discussion

Citations

Topics

More

Suggest a correction or report