Big Data has driven the need for datastores that can scale horizontally leading to the development of many different NoSQL database implementations, each with different persistence and query philosophies. Spatio-temporal data such as location data is one of the largest types of data being collected today. We describe a novel spatio-temporal index structure that leverages the horizontal scalability of NoSQL databases to achieve performant query and transformation semantics. We present performance characteristics gathered from testing with Accumulo.