OST-Tree: An Access Method for Obfuscating Spatio-Temporal Data in Location Based Services

Since the development of location-based services, privacy-preserving has gained special attention and many algorithms aiming at protecting user´s privacy have been created such as obfuscation or k-anonymity. However, all of these researches separate the algorithms from the database level. Thus, the querying process has two phases, querying the database to retrieve the accurate positions of users and then modifying them to decrease the quality of location information. This two-phase process is time-consuming due to the number of disk accesses required to retrieve the user´s exact position. We address this problem by proposing OST-tree, a structure that embeds the user´s privacy policy in its node and obfuscates the spatio-temporal data. Experiments show that OST-tree provides an improvement over the algorithm separated from the database level for both querying costs and user´s privacy protection.