The advent and prosperity of the GPS equipped devices and reliable location technologies has resulted in a wide growth of location based service. As a certain type of geo-spatial application, moving objects on fixed networks must sustain high update rate for millions of devices, and provide efficient real-time querying on multi-attributes such as time-period and arbitrary spatial dimension. Traditional DBMSs support complex index structures which can effectively cope with spatio-temporal data. However, current relational databases have encountered the ever-increasing scale of datasets, which make a claim for scalability of data manage system. Meanwhile, key-value store databases are designed to be scalable, available and distributed, without much support for data organization including management of spatio-temporal data. In this paper, we present a novel hybrid index structure to organize data, combining a statistical based R-tree for indexing space and applying Hilbert curve for traversing approaching space. With key-value store, which insures effective querying response time and high insert rates, we propose rules for generating target row key which take skewed data handing into account. The cluster of HBase consists 8 nodes, with data volume in a level of millions. Our implementation proves that range queries and k-NN queries sustain response time in hundreds of milliseconds.