American Institute of Mathematical Sciences

Advanced
January  2016, 1(1): 81-91. doi: 10.3934/bdia.2016.1.81

Spatio-temporal keywords queries in HBase

Xiaoying Chen 1, , Chong Zhang 1, , Zonglin Shi 1, and  Weidong Xiao 1,

1. 

Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073, China, China, China, China

Received  May 2015 Revised  August 2015 Published  September 2015

With the amount of data accumulated to tens of billions of scale, HBase, a distributed key-value database, plays a significant role in providing effective and high-throughput data service and management. However, for the applications involving spatio-temporal data, there is no good solution, due to inefficient query processing in HBase. In this paper, we propose spatio-temporal keyword searching problem for HBase, which is a meaningful issue in real life and a new challenge in this platform. To solve this problem, a novel access model for HBase is designed, containing row keys for indexing spatio-temporal dimensions and Bloom filters for fast detecting the existence of query keywords. And then, two algorithms for spatio-temporal keyword queries are developed, one is suitable for the queries with ordinary selectivity, the other is a parallel algorithm based on MapReduce aiming for the large range queries. We evaluate our algorithms on a real dataset, and the empirical results show that they are capable to handle spatio-temporal keyword queries efficiently.
Keywords: Spatio-temporal keyword query, bloom filter, Hilbert curve, MapReduce., HBase.
Mathematics Subject Classification: Primary: 68W15; Secondary: 68P2.
Citation: Xiaoying Chen, Chong Zhang, Zonglin Shi, Weidong Xiao. Spatio-temporal keywords queries in HBase. Big Data & Information Analytics, 2016, 1 (1) : 81-91. doi: 10.3934/bdia.2016.1.81
References:
[1]

, HBase,, 2015. Available from: , ().   Google Scholar

[2]

, Hadoop,, 2015. Available from: , ().   Google Scholar

[3]

J. Blustein and A. El-Maazawi, Bloom filters. a tutorial, analysis, and survey, Halifax, NS: Dalhousie University, (2002), 1-31. Google Scholar

[4]

C. Cheng, C. Sun, X. Xu and D. Zhang, A multi-dimensional index structure based on improved VA-file and CAN in the cloud, International Journal of Automation and Computing, 11 (2014), 109-117. doi: 10.1007/s11633-014-0772-y.  Google Scholar

[5]

G. Cong, C. S. Jensen and D. Wu, Efficient retrieval of the top k most relevant spatial web objects, VLDB Endowment, 2 (2009), 337-348. doi: 10.14778/1687627.1687666.  Google Scholar

[6]

I. D. Felipe, V. Hristidis and N. Rishe, Keyword search on spatial databases, In ICDE, (2008), 656-665. doi: 10.1109/ICDE.2008.4497474.  Google Scholar

[7]

C. S. Jensen, D. Lin and B. C. Ooi, Query and update efficient B$^+$-tree based indexing of moving objects, VLDB Endowment, 30 (2004), 768-779. doi: 10.1016/B978-012088469-8.50068-1.  Google Scholar

[8]

B. Moon, H. V. Jagadish, C. Faloutsos and J. H. Saltz, Analysis of the clustering properties of the Hilbert space-filling curve, IEEE Transactions on Knowledge and Data Engineering, 13 (2001), 124-141. doi: 10.1109/69.908985.  Google Scholar

[9]

S. Nishimura, S. Das, D. Agrawal and A. E. Abbadi, MD-HBase: A Scalable Multi-dimensional Data Infrastructure for Location Aware Services, In MDM, 1 (2011), 7-16. doi: 10.1109/MDM.2011.41.  Google Scholar

[10]

W. Zhou, J. Lu, Z. Luan, S. Wang, G. Xue and S. Yao, SNB-index: A SkipNet and B+ tree based auxiliary Cloud index, Cluster Computing, 17 (2014), 453-462. doi: 10.1007/s10586-013-0246-y.  Google Scholar

show all references

References:
[1]

, HBase,, 2015. Available from: , ().   Google Scholar

[2]

, Hadoop,, 2015. Available from: , ().   Google Scholar

[3]

J. Blustein and A. El-Maazawi, Bloom filters. a tutorial, analysis, and survey, Halifax, NS: Dalhousie University, (2002), 1-31. Google Scholar

[4]

C. Cheng, C. Sun, X. Xu and D. Zhang, A multi-dimensional index structure based on improved VA-file and CAN in the cloud, International Journal of Automation and Computing, 11 (2014), 109-117. doi: 10.1007/s11633-014-0772-y.  Google Scholar

[5]

G. Cong, C. S. Jensen and D. Wu, Efficient retrieval of the top k most relevant spatial web objects, VLDB Endowment, 2 (2009), 337-348. doi: 10.14778/1687627.1687666.  Google Scholar

[6]

I. D. Felipe, V. Hristidis and N. Rishe, Keyword search on spatial databases, In ICDE, (2008), 656-665. doi: 10.1109/ICDE.2008.4497474.  Google Scholar

[7]

C. S. Jensen, D. Lin and B. C. Ooi, Query and update efficient B$^+$-tree based indexing of moving objects, VLDB Endowment, 30 (2004), 768-779. doi: 10.1016/B978-012088469-8.50068-1.  Google Scholar

[8]

B. Moon, H. V. Jagadish, C. Faloutsos and J. H. Saltz, Analysis of the clustering properties of the Hilbert space-filling curve, IEEE Transactions on Knowledge and Data Engineering, 13 (2001), 124-141. doi: 10.1109/69.908985.  Google Scholar

[9]

S. Nishimura, S. Das, D. Agrawal and A. E. Abbadi, MD-HBase: A Scalable Multi-dimensional Data Infrastructure for Location Aware Services, In MDM, 1 (2011), 7-16. doi: 10.1109/MDM.2011.41.  Google Scholar

[10]

W. Zhou, J. Lu, Z. Luan, S. Wang, G. Xue and S. Yao, SNB-index: A SkipNet and B+ tree based auxiliary Cloud index, Cluster Computing, 17 (2014), 453-462. doi: 10.1007/s10586-013-0246-y.  Google Scholar

[1]

Cicely K. Macnamara, Mark A. J. Chaplain. Spatio-temporal models of synthetic genetic oscillators. Mathematical Biosciences & Engineering, 2017, 14 (1) : 249-262. doi: 10.3934/mbe.2017016
[2]

Francesca Sapuppo, Elena Umana, Mattia Frasca, Manuela La Rosa, David Shannahoff-Khalsa, Luigi Fortuna, Maide Bucolo. Complex spatio-temporal features in meg data. Mathematical Biosciences & Engineering, 2006, 3 (4) : 697-716. doi: 10.3934/mbe.2006.3.697
[3]

Noura Azzabou, Nikos Paragios. Spatio-temporal speckle reduction in ultrasound sequences. Inverse Problems & Imaging, 2010, 4 (2) : 211-222. doi: 10.3934/ipi.2010.4.211
[4]

Hirofumi Izuhara, Shunsuke Kobayashi. Spatio-temporal coexistence in the cross-diffusion competition system. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 919-933. doi: 10.3934/dcdss.2020228
[5]

Pietro-Luciano Buono, Daniel C. Offin. Instability criterion for periodic solutions with spatio-temporal symmetries in Hamiltonian systems. Journal of Geometric Mechanics, 2017, 9 (4) : 439-457. doi: 10.3934/jgm.2017017
[6]

Buddhi Pantha, Judy Day, Suzanne Lenhart. Investigating the effects of intervention strategies in a spatio-temporal anthrax model. Discrete & Continuous Dynamical Systems - B, 2020, 25 (4) : 1607-1622. doi: 10.3934/dcdsb.2019242
[7]

Jingdong Wei, Jiangbo Zhou, Wenxia Chen, Zaili Zhen, Lixin Tian. Traveling waves in a nonlocal dispersal epidemic model with spatio-temporal delay. Communications on Pure & Applied Analysis, 2020, 19 (5) : 2853-2886. doi: 10.3934/cpaa.2020125
[8]

Wenjia Jing, Panagiotis E. Souganidis, Hung V. Tran. Large time average of reachable sets and Applications to Homogenization of interfaces moving with oscillatory spatio-temporal velocity. Discrete & Continuous Dynamical Systems - S, 2018, 11 (5) : 915-939. doi: 10.3934/dcdss.2018055
[9]

Raimund BÜrger, Gerardo Chowell, Elvis GavilÁn, Pep Mulet, Luis M. Villada. Numerical solution of a spatio-temporal gender-structured model for hantavirus infection in rodents. Mathematical Biosciences & Engineering, 2018, 15 (1) : 95-123. doi: 10.3934/mbe.2018004
[10]

Thomas Hillen, Jeffery Zielinski, Kevin J. Painter. Merging-emerging systems can describe spatio-temporal patterning in a chemotaxis model. Discrete & Continuous Dynamical Systems - B, 2013, 18 (10) : 2513-2536. doi: 10.3934/dcdsb.2013.18.2513
[11]

Lin Wang, James Watmough, Fang Yu. Bifurcation analysis and transient spatio-temporal dynamics for a diffusive plant-herbivore system with Dirichlet boundary conditions. Mathematical Biosciences & Engineering, 2015, 12 (4) : 699-715. doi: 10.3934/mbe.2015.12.699
[12]

Jinling Zhou, Yu Yang. Traveling waves for a nonlocal dispersal SIR model with general nonlinear incidence rate and spatio-temporal delay. Discrete & Continuous Dynamical Systems - B, 2017, 22 (4) : 1719-1741. doi: 10.3934/dcdsb.2017082
[13]

Zhi-Xian Yu, Rong Yuan. Traveling wave fronts in reaction-diffusion systems with spatio-temporal delay and applications. Discrete & Continuous Dynamical Systems - B, 2010, 13 (3) : 709-728. doi: 10.3934/dcdsb.2010.13.709
[14]

Rui Xu. Global convergence of a predator-prey model with stage structure and spatio-temporal delay. Discrete & Continuous Dynamical Systems - B, 2011, 15 (1) : 273-291. doi: 10.3934/dcdsb.2011.15.273
[15]

Zelik S.. Formally gradient reaction-diffusion systems in Rn have zero spatio-temporal topological. Conference Publications, 2003, 2003 (Special) : 960-966. doi: 10.3934/proc.2003.2003.960
[16]

Rodrigo A. Garrido, Ivan Aguirre. Emergency logistics for disaster management under spatio-temporal demand correlation: The earthquakes case. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2369-2387. doi: 10.3934/jimo.2019058
[17]

Yiwen Tao, Jingli Ren. The stability and bifurcation of homogeneous diffusive predator–prey systems with spatio–temporal delays. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021038
[18]

Hideo Ikeda, Masayasu Mimura, Tommaso Scotti. Shadow system approach to a plankton model generating harmful algal bloom. Discrete & Continuous Dynamical Systems, 2017, 37 (2) : 829-858. doi: 10.3934/dcds.2017034
[19]

Ayla Sayli, Ayse Oncu Sarihan. Statistical query-based rule derivation system by backward elimination algorithm. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1341-1356. doi: 10.3934/dcdss.2015.8.1341
[20]

Frank Trujillo. Uniqueness properties of the KAM curve. Discrete & Continuous Dynamical Systems, 2021, 41 (11) : 5165-5182. doi: 10.3934/dcds.2021072

 Impact Factor: 

Tools

Metrics

  • PDF downloads (89)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences