IEICE TRANSACTIONS on Information
The Efficient Algorithms for Constructing Enhanced Quadtrees Using MapReduce
Summary :
MapReduce is considered as the de facto framework for storing and processing massive data due to its fascinating features: simplicity, flexibility, fault tolerance and scalability. However, since the MapReduce framework does not provide an efficient access method to data (i.e., an index), whole data should be retrieved even though a user wants to access a small portion of data. Thus, in this paper, we devise an efficient algorithm constructing quadtrees with MapReduce. Our proposed algorithms reduce the index construction time by utilizing a sampling technique to partition a data set. To improve the query performance, we extend the quadtree construction algorithm in which the adjacent nodes of a quadtree are integrated when the number of points located in the nodes is less than the predefined threshold. Furthermore, we present an effective algorithm for incremental update. Our experimental results show the efficiency of our proposed algorithms in diverse environments.
- Publication
- IEICE TRANSACTIONS on Information Vol.E99-D No.4 pp.918-926
- Publication Date
- 2016/04/01
- Publicized
- 2016/01/14
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2015DAP0005
- Type of Manuscript
- Special Section PAPER (Special Section on Data Engineering and Information Management)
- Category
Authors
Hongyeon KIM
Korea Univ. of Tech. & Edu.
Sungmin KANG
Korea Univ. of Tech. & Edu.
Seokjoo LEE
Korea Univ. of Tech. & Edu.
Jun-Ki MIN
Korea Univ. of Tech. & Edu.
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hongyeon KIM, Sungmin KANG, Seokjoo LEE, Jun-Ki MIN, "The Efficient Algorithms for Constructing Enhanced Quadtrees Using MapReduce" in IEICE TRANSACTIONS on Information,
vol. E99-D, no. 4, pp. 918-926, April 2016, doi: 10.1587/transinf.2015DAP0005.
Abstract: MapReduce is considered as the de facto framework for storing and processing massive data due to its fascinating features: simplicity, flexibility, fault tolerance and scalability. However, since the MapReduce framework does not provide an efficient access method to data (i.e., an index), whole data should be retrieved even though a user wants to access a small portion of data. Thus, in this paper, we devise an efficient algorithm constructing quadtrees with MapReduce. Our proposed algorithms reduce the index construction time by utilizing a sampling technique to partition a data set. To improve the query performance, we extend the quadtree construction algorithm in which the adjacent nodes of a quadtree are integrated when the number of points located in the nodes is less than the predefined threshold. Furthermore, we present an effective algorithm for incremental update. Our experimental results show the efficiency of our proposed algorithms in diverse environments.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2015DAP0005/_p
Copy
@ARTICLE{e99-d_4_918,
author={Hongyeon KIM, Sungmin KANG, Seokjoo LEE, Jun-Ki MIN, },
journal={IEICE TRANSACTIONS on Information},
title={The Efficient Algorithms for Constructing Enhanced Quadtrees Using MapReduce},
year={2016},
volume={E99-D},
number={4},
pages={918-926},
abstract={MapReduce is considered as the de facto framework for storing and processing massive data due to its fascinating features: simplicity, flexibility, fault tolerance and scalability. However, since the MapReduce framework does not provide an efficient access method to data (i.e., an index), whole data should be retrieved even though a user wants to access a small portion of data. Thus, in this paper, we devise an efficient algorithm constructing quadtrees with MapReduce. Our proposed algorithms reduce the index construction time by utilizing a sampling technique to partition a data set. To improve the query performance, we extend the quadtree construction algorithm in which the adjacent nodes of a quadtree are integrated when the number of points located in the nodes is less than the predefined threshold. Furthermore, we present an effective algorithm for incremental update. Our experimental results show the efficiency of our proposed algorithms in diverse environments.},
keywords={},
doi={10.1587/transinf.2015DAP0005},
ISSN={1745-1361},
month={April},}
Copy
TY - JOUR
TI - The Efficient Algorithms for Constructing Enhanced Quadtrees Using MapReduce
T2 - IEICE TRANSACTIONS on Information
SP - 918
EP - 926
AU - Hongyeon KIM
AU - Sungmin KANG
AU - Seokjoo LEE
AU - Jun-Ki MIN
PY - 2016
DO - 10.1587/transinf.2015DAP0005
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E99-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2016
AB - MapReduce is considered as the de facto framework for storing and processing massive data due to its fascinating features: simplicity, flexibility, fault tolerance and scalability. However, since the MapReduce framework does not provide an efficient access method to data (i.e., an index), whole data should be retrieved even though a user wants to access a small portion of data. Thus, in this paper, we devise an efficient algorithm constructing quadtrees with MapReduce. Our proposed algorithms reduce the index construction time by utilizing a sampling technique to partition a data set. To improve the query performance, we extend the quadtree construction algorithm in which the adjacent nodes of a quadtree are integrated when the number of points located in the nodes is less than the predefined threshold. Furthermore, we present an effective algorithm for incremental update. Our experimental results show the efficiency of our proposed algorithms in diverse environments.
ER -
English
