A hybrid index model for efficient spatio-temporal search in HBase

Abstract

With advances in geo-positioning technologies and geo-location services, there are a rapidly growing massive amount of spatio-temporal data collected in many applications such as location-aware devices and wireless communication, in which an object is described by its spatial location and its timestamp. Consequently, the study of spatio-temporal search which explores both geo-location information and temporal information of the data has attracted significant concern from research organizations and commercial communities. This work study the problem of spatio-temporal \emph{k}-nearest neighbors search (ST$k$NNS), which is fundamental in the spatial temporal queries. Based on HBase, a novel index structure is proposed, called \textbf{H}ybrid \textbf{S}patio-\textbf{T}emporal HBase \textbf{I}ndex (\textbf{HSTI} for short), which is carefully designed and takes both spatial and temporal information into consideration to effectively reduce the search space. Based on HSTI, an efficient algorithm is developed to deal with spatio-temporal \emph{k}-nearest neighbors search. Comprehensive experiments on real and synthetic data clearly show that HSTI is three to five times faster than the state-of-the-art technique.

arXiv comment11 pages

References in corpus (7)

• Multi-View Spectral Clustering via Structured Low-Rank Matrix Factorization
• Deep Adaptive Feature Embedding with Local Sample Distributions for Person Re-identification
• Effective Multi-Query Expansions: Collaborative Deep Networks for Robust Landmark Retrieval
• What-and-Where to Match: Deep Spatially Multiplicative Integration Networks for Person Re-identification
• Iterative Views Agreement: An Iterative Low-Rank based Structured Optimization Method to Multi-View Spectral Clustering
• Structured Deep Hashing with Convolutional Neural Networks for Fast Person Re-identification
• Building a Balanced k-d Tree in O(kn log n) Time