Journal
EXPERT SYSTEMS WITH APPLICATIONS
Volume 42, Issue 10, Pages 4676-4686Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.eswa.2015.01.011
Keywords
Spatial index; Flash memory; Buffer management; R-tree
Categories
Funding
- National Science Foundation of China [61379037, 61472376]
- OATF project - University of Science and Technology of China
Ask authors/readers for more resources
R-tree has been widely used in spatial data management and data analysis to improve the performance of spatial data retrieval. However, the original R-tree is designed for magnetic disks, and has poor performance on flash memory, due to the special features of flash memory such as asymmetric read! write speeds (fast read, slow write) and the erase-before-write feature. Particularly, the original updating mechanism of R-tree usually has to update a few interior nodes when inserting an indexing item into or deleting an item from a leaf node, yielding many slow writes to flash memory. With the wide use of flash memory in many location-based fields, e.g., to store moving trajectories in intelligent transportation systems, how to optimize R-tree for flash memory has become a critical issue. In this paper, we propose a novel spatial index named Flash-Optimized R-tree that is optimized for flash memory. In particular, we propose to defer the node-splitting operations on R-tree by introducing overflow nodes, which results in an unbalanced tree structure. With this mechanism, we can reduce random writes to flash memory and improve the overall performance of R-tree. In addition, we present a new buffering scheme to efficiently cache the updates to the tree, which can further reduce random writes to flash memory. We conduct extensive experiments on real flash-memory storage devices as well as a flash memory simulation platform to evaluate the performance of our proposal, and the results suggest the efficiency of our proposal with respect to different metrics. (C) 2015 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available