  Location-Based Service (LBS) is rapidly becoming the next ubiquitous
technology for a wide range of mobile applications. To support applications
that demand nearest-neighbor and history queries, an LBS spatial indexer must
be able to efficiently update, query, archive and mine location records, which
can be in contention with each other. In this work, we propose MOIST, whose
baseline is a recursive spatial partitioning indexer built upon BigTable. To
reduce update and query contention, MOIST groups nearby objects of similar
trajectory into the same school, and keeps track of only the history of school
leaders. This dynamic clustering scheme can eliminate redundant updates and
hence reduce update latency. To improve history query processing, MOIST keeps
some history data in memory, while it flushes aged data onto parallel disks in
a locality-preserving way. Through experimental studies, we show that MOIST can
support highly efficient nearest-neighbor and history queries and can scale
well with an increasing number of users and update frequency.
