In recent years, mobile devices such as smart phones and tablet computers have become popular part of our daily life. Simultaneously, with the increasing prevalence of the Global Positioning System (GPS), a large number of location-based applications, such as Foursquare and Flickr, have been developed. People are able to share their real-time events with friends anytime and anywhere as long as the Internet is available. For example, people can check into a specifi c location and can note their activities, and they can see their friends’shared real time information using the Foursquare application. These location-based applications induce that the amount of multi-attribute data, which at least consist of locations and time-stamps are dramatically increasing. In order to retrieve and manage this data effectively, different database management systems (DBMSs) have been developed. For traditional relational database management systems (RDBMSs), there are several index structures, such as k-dimensional (k-d) trees (Bentley 1975), quad trees (Finkel and Bentley 1974), and R-trees (Guttman 1984). However, RDBMSs are unable to deal with thousands of millions of queries effi ciently when the amount of data is large (Nishimura et al. 2013). On the other hand, distributed relational database management systems (DRDBMSs) have been developed and are able to deal with multi-attribute accesses. However, DRDBMSs are unable to maintain and retrieve data among servers effi ciently because they take a lot of time to make sure the data is consistent by appropriately locking and updating the data.