A grid-based k-nearest neighbor join for large scale datasets on MapReduce

Miyoung Jang; Young Sung Shin; Jae Woo Chang

doi:10.1109/HPCC-CSS-ICESS.2015.189

A grid-based k-nearest neighbor join for large scale datasets on MapReduce

Miyoung Jang
, Young Sung Shin
, Jae Woo Chang^*

^*Corresponding author for this work

Jeonbuk National University

Research output: Contribution to conference › Conference paper › peer-review

9 Scopus citations

Abstract

Because MapReduce supports efficient parallel data processing, MapReduce-based query processing algorithms have been widely studied. Among various query types, k-nearest neighbor join, which aims to produce the k nearest neighbors of each point of a dataset from another dataset, has been considered most important in data analysis. Existing k-NN join query processing algorithms on MapReduce suffer from high index construction and computation costs which make them unsuitable for big data processing. In this paper, we propose a new grid-based k-NN join query processing algorithm on MapReduce. First, we design a dynamic grid index that represents the distribution of join datasets. Based on this index, we prune out unnecessary cells for the join with the distance-based filtering. This can reduce the data transmission and computation overheads. From performance analysis, we show that our algorithm outperforms the existing scheme up to seven times in terms of query processing time while achieving high query result accuracy.

Original language	English
Title of host publication	Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	888-891
Number of pages	4
ISBN (Electronic)	9781479989362
DOIs	https://doi.org/10.1109/HPCC-CSS-ICESS.2015.189
State	Published - 2015.11.23
Event	17th IEEE International Conference on High Performance Computing and Communications, IEEE 7th International Symposium on Cyberspace Safety and Security and IEEE 12th International Conference on Embedded Software and Systems, HPCC-ICESS-CSS 2015 - New York, United States Duration: 2015.08.24 → 2015.08.26

Publication series

Name	Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015

Conference

Conference	17th IEEE International Conference on High Performance Computing and Communications, IEEE 7th International Symposium on Cyberspace Safety and Security and IEEE 12th International Conference on Embedded Software and Systems, HPCC-ICESS-CSS 2015
Country/Territory	United States
City	New York
Period	15.08.24 → 15.08.26

Keywords

Bitmap encryption
Cloud computing
Density aware
Grid index
Location data protection

Quacquarelli Symonds(QS) Subject Topics

Computer Science & Information Systems

Access to Document

10.1109/HPCC-CSS-ICESS.2015.189

Cite this

Jang, M., Shin, Y. S., & Chang, J. W. (2015). A grid-based k-nearest neighbor join for large scale datasets on MapReduce. In Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015 (pp. 888-891). Article 7336277 (Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HPCC-CSS-ICESS.2015.189

Jang, Miyoung ; Shin, Young Sung ; Chang, Jae Woo. / A grid-based k-nearest neighbor join for large scale datasets on MapReduce. Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 888-891 (Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015).

@inproceedings{f7de21b440ae40bca05da672d2b66d5d,

title = "A grid-based k-nearest neighbor join for large scale datasets on MapReduce",

abstract = "Because MapReduce supports efficient parallel data processing, MapReduce-based query processing algorithms have been widely studied. Among various query types, k-nearest neighbor join, which aims to produce the k nearest neighbors of each point of a dataset from another dataset, has been considered most important in data analysis. Existing k-NN join query processing algorithms on MapReduce suffer from high index construction and computation costs which make them unsuitable for big data processing. In this paper, we propose a new grid-based k-NN join query processing algorithm on MapReduce. First, we design a dynamic grid index that represents the distribution of join datasets. Based on this index, we prune out unnecessary cells for the join with the distance-based filtering. This can reduce the data transmission and computation overheads. From performance analysis, we show that our algorithm outperforms the existing scheme up to seven times in terms of query processing time while achieving high query result accuracy.",

keywords = "Bitmap encryption, Cloud computing, Density aware, Grid index, Location data protection",

author = "Miyoung Jang and Shin, \{Young Sung\} and Chang, \{Jae Woo\}",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 17th IEEE International Conference on High Performance Computing and Communications, IEEE 7th International Symposium on Cyberspace Safety and Security and IEEE 12th International Conference on Embedded Software and Systems, HPCC-ICESS-CSS 2015 ; Conference date: 24-08-2015 Through 26-08-2015",

year = "2015",

month = nov,

day = "23",

doi = "10.1109/HPCC-CSS-ICESS.2015.189",

language = "English",

series = "Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "888--891",

booktitle = "Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015",

}

Jang, M, Shin, YS & Chang, JW 2015, A grid-based k-nearest neighbor join for large scale datasets on MapReduce. in Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015., 7336277, Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015, Institute of Electrical and Electronics Engineers Inc., pp. 888-891, 17th IEEE International Conference on High Performance Computing and Communications, IEEE 7th International Symposium on Cyberspace Safety and Security and IEEE 12th International Conference on Embedded Software and Systems, HPCC-ICESS-CSS 2015, New York, United States, 15.08.24. https://doi.org/10.1109/HPCC-CSS-ICESS.2015.189

A grid-based k-nearest neighbor join for large scale datasets on MapReduce. / Jang, Miyoung; Shin, Young Sung; Chang, Jae Woo.
Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 888-891 7336277 (Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015).

Research output: Contribution to conference › Conference paper › peer-review

TY - GEN

T1 - A grid-based k-nearest neighbor join for large scale datasets on MapReduce

AU - Jang, Miyoung

AU - Shin, Young Sung

AU - Chang, Jae Woo

PY - 2015/11/23

Y1 - 2015/11/23

N2 - Because MapReduce supports efficient parallel data processing, MapReduce-based query processing algorithms have been widely studied. Among various query types, k-nearest neighbor join, which aims to produce the k nearest neighbors of each point of a dataset from another dataset, has been considered most important in data analysis. Existing k-NN join query processing algorithms on MapReduce suffer from high index construction and computation costs which make them unsuitable for big data processing. In this paper, we propose a new grid-based k-NN join query processing algorithm on MapReduce. First, we design a dynamic grid index that represents the distribution of join datasets. Based on this index, we prune out unnecessary cells for the join with the distance-based filtering. This can reduce the data transmission and computation overheads. From performance analysis, we show that our algorithm outperforms the existing scheme up to seven times in terms of query processing time while achieving high query result accuracy.

AB - Because MapReduce supports efficient parallel data processing, MapReduce-based query processing algorithms have been widely studied. Among various query types, k-nearest neighbor join, which aims to produce the k nearest neighbors of each point of a dataset from another dataset, has been considered most important in data analysis. Existing k-NN join query processing algorithms on MapReduce suffer from high index construction and computation costs which make them unsuitable for big data processing. In this paper, we propose a new grid-based k-NN join query processing algorithm on MapReduce. First, we design a dynamic grid index that represents the distribution of join datasets. Based on this index, we prune out unnecessary cells for the join with the distance-based filtering. This can reduce the data transmission and computation overheads. From performance analysis, we show that our algorithm outperforms the existing scheme up to seven times in terms of query processing time while achieving high query result accuracy.

KW - Bitmap encryption

KW - Cloud computing

KW - Density aware

KW - Grid index

KW - Location data protection

UR - https://www.scopus.com/pages/publications/84961696308

U2 - 10.1109/HPCC-CSS-ICESS.2015.189

DO - 10.1109/HPCC-CSS-ICESS.2015.189

M3 - Conference paper

AN - SCOPUS:84961696308

T3 - Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015

SP - 888

EP - 891

BT - Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 17th IEEE International Conference on High Performance Computing and Communications, IEEE 7th International Symposium on Cyberspace Safety and Security and IEEE 12th International Conference on Embedded Software and Systems, HPCC-ICESS-CSS 2015

Y2 - 24 August 2015 through 26 August 2015

ER -

Jang M, Shin YS, Chang JW. A grid-based k-nearest neighbor join for large scale datasets on MapReduce. In Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015. Institute of Electrical and Electronics Engineers Inc. 2015. p. 888-891. 7336277. (Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015). doi: 10.1109/HPCC-CSS-ICESS.2015.189

A grid-based k-nearest neighbor join for large scale datasets on MapReduce

Abstract

Publication series

Conference

Keywords

Quacquarelli Symonds(QS) Subject Topics

Access to Document

Other files and links

Fingerprint

Cite this