Nowadays, location-based services (LBSs), which refer to those services that are based on location (or spatial) data, are broadly used in our daily life. Some popular types of LBS include “search-nearby” which searches objects (e.g., restaurants, hotels and shops) near a location, “spatial crowdsourcing” which allows people to post tasks to be performed at a location (these people are called “requesters”) and people to pick some tasks to perform (these people are called “workers”), and “trace tracking” which records the trace of a movement (e.g., the moving trace of a hiker). Each type of LBS usually relies on some computation based on spatial data (which is termed as spatial computation). For example, the “search-nearby” service relies on spatial keyword query to find all obje...[ Read more ]

Nowadays, location-based services (LBSs), which refer to those services that are based on location (or spatial) data, are broadly used in our daily life. Some popular types of LBS include “search-nearby” which searches objects (e.g., restaurants, hotels and shops) near a location, “spatial crowdsourcing” which allows people to post tasks to be performed at a location (these people are called “requesters”) and people to pick some tasks to perform (these people are called “workers”), and “trace tracking” which records the trace of a movement (e.g., the moving trace of a hiker). Each type of LBS usually relies on some computation based on spatial data (which is termed as spatial computation). For example, the “search-nearby” service relies on spatial keyword query to find all objects that are near a given query location and contain a given query keyword, the “spatial crowdsourcing” service relies on spatial matching to match between tasks and workers, and the “trace tracking” service relies on trajectory data management.

In this thesis, we introduce three techniques for boosting the spatial computations that are central to LBSs, namely the collective spatial keyword query which is one type of spatial keyword query and finds a set of spatial objects that cover all the given query keywords and have the smallest distance from the query location, worst-case optimized spatial matching which matches two sets of spatial objects with the smallest worst-case cost, and direction-preserving trajectory which simplifies the trajectory while preserving the direction information embedded in the trajectory data.