User-centric query optimization over web data services

Abstract

Web-based data services have become more and more popular. Users from different fields are interested in different web-based data services. In this thesis, we consider three application scenarios with different queries and objectives. We propose effective methods to process and optimize users' queries over web data services. In the first application, users are interested in datasets provided in Cloud Data Market (e.g., Windows Azure Data Market), which is an emerging cloud service that enables data owners to sell their datasets in a public cloud. Users (i.e., buyers) can access their interested data in data market via a RESTful API. Accessing data in the data market may not be free. We present PayLess, a system that helps users to process and optimize their SQL queries such that they pay less. In the second application, mobile users of location-based services (LBS) issue range/K-NN queries over points-of-interest (e.g., restaurants, cafes), and they require accurate query results with up-to-date travel times. Lacking the monitoring infrastructure for road traffic, the LBS may obtain live travel times of routes from online route APIs (e.g., Google Directions API and Bing Maps API) in order to offer accurate results. Our goal is to reduce the number of external requests issued by the LBS significantly while preserving accurate query results. In the third application, emerging spatial crowdsourcing web services enable the users (i.e., crowdsourcing workers) to complete spatial crowdsourcing tasks (like taking photos, conducting citizen journalism) that are tagged with both time and location features. We study the problem of online recommending an optimal route for a crowdsourcing worker, such that he can (i) reach his destination on time and (ii) receive the maximum reward for tasks along the route. We show that no algorithms can achieve a non-zero competitive ratio in this problem. Therefore, we propose several heuristics, and powerful pruning rules to speed up the methods. For each application scenario above, we evaluate the performance of our solutions on both synthetic data and real data. Our experimental results show that our solutions are effective and scalable.