  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.
