Spatio-temporal queries in HBase

Geoscience gives insights into our surroundings and benefits many aspects of our life. Nowadays, with massive sensors deployed to sense all kinds of parameters for environments, tens of billions, even trillions of sensed data are collected and need to be analyzed for surveillance or other purposes. From many perspectives, users always issue queries according to specific spatial and temporal predicates. For these applications, relational databases are overwhelmed by the large scale and high rate insertions, and NoSQL database could be considered a feasible solution. HBase, a popular key-value store system, is capable to solve the storage problem, but fails to provide in-built spatio-temporal querying capability. Many previous works tackle the problem by designing schema, i.e., designing row key and column key formation for HBase, which we don´t believe is an effective solution. In this paper, we address this problem from nature level of HBase, and propose an index structure as a built-in component for HBase. STEHIX (Spatio-TEmporal Hbase IndeX) is adapted to two-level architecture of HBase and suitable for HBase to process spatio-temporal queries. It is composed of index in the meta table (the first level) and region index (the second level) for indexing inner structure of HBase regions. Base on this structure, two common queries, range query and kNN query are solved by proposing algorithms, respectively. For achieving load balancing and scalable kNN query, two optimizations are also presented. We implement STEHIX and conduct experiments on real dataset, and the results show our design outperforms a previous work in many aspects.