Search

A crowdsourcing task in real-world applications often consists of thousands of atomic tasks. A common practice to distribute a large-scale crowdsourcing task is to pack atomic tasks into task bins and send to crowd workers in batches. It is challenging to decompose a large-scale crowdsourcing task into task bins to ensure reliability at a minimal total cost. In this paper, we propose the Smart Large-scAle task DEcomposer (SLADE) problem, which aims to decompose a large-scale crowdsourcing task to achieve the desired reliability at a minimal cost. We prove its NP-hardness and study two variants of the problem. For the homogeneous SLADE problem, we propose a greedy algorithm and an approximation framework using an optimal priority queue (OPQ) structure with provable approximation ratio. For the heterogeneous SLADE problem, we extend this framework and prove its approximation guarantee. Extensive experiments validate the effectiveness and efficiency of the solutions. © 2019 IEEE.

A central issue in on-demand taxi dispatching platforms is task assignment, which designs matching policies among dynamically arrived drivers (workers) and passengers (tasks). Previous matching policies maximize the profit of the platform without considering the preferences of workers and tasks (e.g., workers may prefer high-rewarding tasks while tasks may prefer nearby workers). Such ignorance of preferences impairs user experience and will decrease the profit of the platform in the long run. To address this problem, we propose preference-aware task assignment using online stable matching. Specifically, we define a new model, Online Stable Matching under Known Identical Independent Distributions (OSM-KIID). It not only maximizes the expected total profits (OBJ-1), but also tries to satisfy the preferences among workers and tasks by minimizing the expected total number of blocking pairs (OBJ-2). The model also features a practical arrival assumption validated on real-world dataset. Furthermore, we present a linear program based online algorithm $\lpalg$, which achieves an online ratio of at least $1-1/e$ on OBJ-1 and has at most $0.6\cdot \E\$ blocking pairs expectedly, where $\E\$ is the total number of edges in the compatible graph. We also show that a natural Greedy can have an arbitrarily bad performance on OBJ-1 while maintaining around $0.5\cdot \E\$ blocking pairs. Evaluations on both synthetic and real datasets confirm our theoretical analysis and demonstrate that $\lpalg$ strictly dominates all the baselines on both objectives when tasks notably outnumber workers. \end{abstract}

Pricing is essential for the commercial success of spatial crowdsourcing applications. The spatial crowdsourcing platform prices tasks according to the demand and the supply in the crowdsourcing market to maximize its total revenue. Traditional pricing strategies seek a unified optimal price for a single global market. Yet spatial crowdsourcing needs to dynamically price for multiple local markets fragmented by the spatiotemporal distributions of tasks and workers and the mobility of workers. Dynamic pricing in spatial crowdsourcing is challenging because the supply in local markets can be limited and dependent, leading to global dependencies when pricing tasks in each local market. To this end, we define the Global Dynamic Pricing (GDP) problem in spatial crowdsourcing. We further propose a MAtching-based Pricing Strategy (MAPS) with guaranteed bound, which efficiently approximates the expected total revenue for markets with limited supply, effectively distributes the dependent supply and dynamically prices the tasks. Extensive evaluations on both synthetic and real-world datasets demonstrate the effectiveness and efficiency of MAPS. © 2018 Association for Computing Machinery.

Crowdsourcing has been shown to be effective in a wide range of applications, and is seeing increasing use. A large-scale crowdsourcing task often consists of thousands or millions of atomic tasks, each of which is usually a simple task such as binary choice or simple voting. To distribute a large-scale crowdsourcing task to limited crowd workers, a common practice is to pack a set of atomic tasks into a task bin and send to a crowd worker in a batch. It is challenging to decompose a large-scale crowdsourcing task and execute batches of atomic tasks, which ensures reliable answers at a minimal total cost. Large batches lead to unreliable answers of atomic tasks, while small batches incur unnecessary cost. In this paper, we investigate a general crowdsourcing task decomposition problem, called the Smart Large-scAle task DEcomposer (SLADE) problem, which aims to decompose a large-scale crowdsourcing task to achieve the desired reliability at a minimal cost. We prove the NP-hardness of the SLADE problem and propose solutions in both homogeneous and heterogeneous scenarios. For the homogeneous SLADE problem, where all the atomic tasks share the same reliability requirement, we propose a greedy heuristic algorithm and an efficient and effective approximation framework using an optimal priority queue (OPQ) structure with provable approximation ratio. For the heterogeneous SLADE problem, where the atomic tasks can have different reliability requirements, we extend the OPQ-based framework leveraging a partition strategy, and also prove its approximation guarantee. Finally, we verify the effectiveness and efficiency of the proposed solutions through extensive experiments on representative crowdsourcing platforms.

Spatial crowdsourcing brings in a new approach for social media and location-based services (LBS) to collect location specific information via mobile users. For example, when a user checks in at a shop on Facebook, he will immediately receive and is asked to complete a set of tasks such as 'what is the opening hour of the shop'. It is non-Trivial to complete a set of tasks timely and accurately via spatial crowdsourcing. Since workers in spatial crowdsourcing are often transient and limited in number, these social media platforms need to properly allocate workers within the set of tasks such that all tasks are completed (i) with high quality and (ii) with a minimal latency (estimated by the arriving index of the last recruited worker). Solutions to quality and latency control in traditional crowdsourcing are inapplicable in this problem because they either assume sufficient workers or ignore the spatiotemporal factors. In this work, we define the Latency-oriented Task Completion (LTC) problem, which trades off quality and latency (number of workers) of task completion in spatial crowdsourcing. We prove that the LTC problem is NP-hard. We first devise a minimum-cost-flow based algorithm with a constant approximation ratio for the LTC problem in the offline scenario, where all information is known a prior. Then we study the more practical online scenario of the LTC problem, where workers appear dynamically and the platform needs to arrange tasks for each worker immediately based on partial information. We design two greedy-based algorithms with competitive ratio guarantees to solve the LTC problem in the online scenario. Finally, we validate the effectiveness and efficiency of the proposed solutions through extensive evaluations on both synthetic and real-world datasets. © 2018 IEEE.

There has been a dramatic growth of shared mobility applications such as ride-sharing, food delivery and crowdsourced parcel delivery. Shared mobility refers to transportation services that are shared among users, where a central issue is route planning. Given a set of workers and requests, route planning finds for each worker a route, i.e., a sequence of locations to pick up and drop off passengers/parcels that arrive from time to time, with different optimization objectives. Previous studies lack practicability due to their conflicted objectives and inefficiency in inserting a new request into a route, a basic operation called insertion. In this paper, we present a unified formulation of route planning called URPSM. It has a well-defined parameterized objective function which eliminates the contradicted objectives in previous studies and enables flexible multi-objective route planning for shared mobility. We prove the problem is NP-hard and there is no polynomial-time algorithm with constant competitive ratio for the URPSM problem and its variants. In response, we devise an effective and efficient solution to address the URPSM problem approximately. We design a novel dynamic programming (DP) algorithm to accelerate the insertion operation from cubic or quadric time in previous work to only linear time. On basis of the DP algorithm, we propose a greedy based solution to the URPSM problem. Experimental results on real datasets show that our solution outperforms the state-of-the-arts by 1.2 to 12.8 times in effectiveness, and also runs 2.6 to 20.7 times faster. © 2018 VLDB Endowment.

User authentication on smart devices is indispensable to keep data privacy and security. It is especially significant for emerging wearable devices such as smartwatches considering data sensitivity in them. However, conventional authentication methods are not applicable for wearables due to constraints of size and hardware, which makes present wearable devices lack convenient, secure and low-cost authentication schemes. To tackle this problem, we reveal a novel biometric authentication mechanism which makes use of sounds of human dental occlusion (i.e., tooth click). We demonstrate its feasibility by comprehensive measurement study, and design a prototype-BiLock with two Android platforms. Extensive real-world experiments have been conducted to evaluate the accuracy, robustness and security of BiLock in different environments. The results show that BiLock can achieve less than 5% average false reject rate and 0.95% average false accept rate even in a noisy environment. Comparative experiments also demonstrate that BiLock possesses advantages in robustness to noise and security against replay and observation attacks over existing voiceprinting schemes.

Taxi-calling apps are gaining increasing popularity for their eficiency in dispatching idle taxis to passengers in need. To precisely balance the supply and the demand of taxis, online taxicab platforms need to predict the Unit Original Taxi Demand (UOTD), which refers to the number of taxi-calling requirements submitted per unit time (e.g., every hour) and per unit region (e.g., each POI). Predicting UOTD is non-trivial for large-scale industrial online taxicab platforms because both accuracy and fexibility are essential. Complex non-linear models such as GBRT and deep learning are generally accurate, yet require labor-intensive model redesign after scenario changes (e.g., extra constraints due to new regulations). To accurately predict UOTD while remaining fexible to scenario changes, we propose Lin UOTD, a unifed linear regression model with more than 200 million dimensions of features. The simple model structure eliminates the need of repeated model redesign, while the high-dimensional features contribute to accurate UOTD prediction. We further design a series of optimization techniques for eficient model training and updating. Evaluations on two largescale datasets from an industrial online taxicab platform verify that Lin UOTD outperforms popular non-linear models in accuracy. We envision our experiences to adopt simple linear models with high-dimensional features in UOTD prediction as a pilot study and can shed insights upon other industrial large-scale spatio-temporal prediction problems. © 2017 ACM.

Cross-device interaction is becoming an increasingly hot topic as we often have multiple devices at our immediate disposal in this era of mobile computing. Various cross-device applications such as file sharing, multi-screen display, and cross-device authentication have been proposed and investigated. However, one of the most fundamental enablers remains unsolved: How to achieve ubiquitous multi-device localization? Though pioneer efforts have resorted to gesture-assisted or sensing-assisted localization, they either require extensive user participation or impose some strong assumptions on device sensing abilities. This introduces extra costs and constraints, and thus degrades their practicality. To overcome these limitations, we propose TUM, an acoustic-assisted localization scheme Towards Ubiquitous Multi-device localization. The basic idea of TUM is to utilize the dual-microphones and speakers to obtain distance cues among devices. At the same time it resolves the location ambiguity with the help of MEMS sensors. We devise techniques for distance constraint extraction, static localization, continuous localization, and multi-device localization, and build a prototype that runs on commodity devices. Extensive experiments show that TUM provides a real-time 3D relative localization service under 10cm mean error for both static and continuous localization.