Abstract
The recent and rapid growth of GPS-enabled devices has resulted in an explosion of spatial data. There are three main challenges for managing and querying such data: the massive volume of data, the need for a high insertion throughput and enabling real-time spatial queries. Although key–value store databases handle large-scale data effectively, they are not equipped with effective functions for supporting spatial data. To solve this problem, we propose an efficient spatial index structure based on HBase, a standard key–value store database. We first use Geohash as the rowkey in HBase to sustain high insert throughput. We present a novel data structure, the binary Geohash rectangle-partition tree, that partitions data into subrectangles, then add these subrectangles into an R-Tree to support spatial queries. Our experiments demonstrate high scalability and an improved performance with spatial queries, when compared with a state-of-the-art system. They also show a good real-time query-processing capability, with response times of less than one second.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
GeoHash. http://geohash.org
Openstreetmap. http://www.openstreetmap.org
PostGIS. http://postgis.net
Aji, A., Wang, F., Vo, H., Lee, R., Liu, Q., Zhang, X., Saltz, J.: Hadoop GIS: a high performance spatial data warehousing system over mapreduce. Proc. VLDB Endow. 6(11), 1009–1020 (2013)
Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509–517 (1975)
Chang, F., Dean, J., Ghemawat, S., Hsieh, W.C., Wallach, D.A., Burrows, M., Chandra, T., Fikes, A., Gruber, R.E.: Bigtable: a distributed storage system for structured data. ACM Trans. Comput. Syst. (TOCS) 26(2), 4 (2008)
Dean, J., Ghemawat, S.: Mapreduce: simplified data processing on large clusters. Commun. ACM 51(1), 107–113 (2008)
Eldawy, A., Mokbel, M.F.: A demonstration of spatialhadoop: an efficient mapreduce framework for spatial data. Proc. VLDB Endow. 6(12), 1230–1233 (2013)
Finkel, R.A., Bentley, J.L.: Quad trees a data structure for retrieval on composite keys. Acta informatica 4(1), 1–9 (1974)
George, L.: HBase: The Definitive Guide. O’Reilly Media Inc., Sebastopol (2011)
Guttman, A.: R-Trees: A Dynamic Index Structure for Spatial Searching, vol. 14. ACM, New York (1984)
Kisung, L., Ganti, R.K., Srivatsa, M., Liu, L.: Efficient spatial query processing for big data. Framework 7(11), 4–12 (2014)
Morton, G.M.: A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing. International Business Machines Company, New York (1966)
Nishimura, S., Das, S., Agrawal, D., Abbadi, A.E.: MD-HBase: a scalable multi-dimensional data infrastructure for location aware services. In: 2011 12th IEEE International Conference on Mobile Data Management (MDM), vol. 1, pp. 7–16. IEEE (2011)
Pal, S., Das, I., Majumder, S., Gupta, A.K., Bhattacharya, I.: Embedding an extra layer of data compression scheme for efficient management of big-data. In: Mandal, J.K., Satapathy, S.C., Sanyal, M.K., Sarkar, P.P., Mukhopadhyay, A. (eds.) Information Systems Design and Intelligent Applications, pp. 699–708. Springer, India (2015)
Schumacker, R.A., Brand, B., Gilliland, M.G., Sharp, W.H.: Study for applying computer-generated images to visual simulation. Technical report, DTIC Document (1969)
Thusoo, A., Sarma, J.S., Jain, N., Shao, Z., Chakka, P., Anthony, S., Liu, H., Wyckoff, P., Murthy, R.: Hive: a warehousing solution over a map-reduce framework. Proc. VLDB Endow. 2(2), 1626–1629 (2009)
White, T.: Hadoop: The Definitive Guide. O’Reilly Media Inc., Sebastopol (2012)
Yuan, J., Zheng, Y., Xie, X., Sun, G.: Driving with knowledge from the physical world. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 316–324. ACM (2011)
Yuan, J., Zheng, Y., Zhang, C., Xie, W., Xie, X., Sun, G., Huang, Y.: T-drive: driving directions based on taxi trajectories. In: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 99–108. ACM (2010)
Acknowledgments
This work was partly supported by the research promotion program for national-level challenges Research and development for the realization of next-generation IT platforms? by MEXT, Japan and the Strategic Innovation Promotion Program of the Japanese Cabinet Office.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Van, L.H., Takasu, A. (2015). An Efficient Distributed Index for Geospatial Databases. In: Chen, Q., Hameurlain, A., Toumani, F., Wagner, R., Decker, H. (eds) Database and Expert Systems Applications. Globe DEXA 2015 2015. Lecture Notes in Computer Science(), vol 9261. Springer, Cham. https://doi.org/10.1007/978-3-319-22849-5_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-22849-5_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-22848-8
Online ISBN: 978-3-319-22849-5
eBook Packages: Computer ScienceComputer Science (R0)