Traffic Signal Control plays a vital role in modern traffic management. However, most existing methods focus exclusively on vehicle flow, neglecting the critical role of pedestrians, leading to suboptimal performance in intersections with mixed vehicle-pedestrian traffic. Pedestrian behavior presents unique challenges due to its irregularity and flexibility, such as non-lane-based movements and uncertain crossing directions, which cannot be modeled by existing methods. To address this limitation, we propose VPLight, a comprehensive framework designed to manage bothVehicle andPedestrian dynamics in traffic signal control. Specifically, we first design the Pedestrian Feature Extractor to capture the spatiotemporal dynamics of pedestrian movement, offering a robust representation of their irregular patterns. Subsequently, to coordinate traffic signal control at multiple intersections, we develop a novel communication approach called V-Comm to enable effective integration among intersections. Extensive experiments show that VPLight outperforms state-of-the-art baselines with significant margins (up to +44.04%). Our results demonstrate that VPLight can remarkably address the challenges of mixed vehicle-pedestrian traffic control and enhance the overall traffic flow efficiency across the road network.

Abstract Graph Neural Networks (GNNs) have become essential for solving graph-level tasks, such as classification and regression, across diverse domains including social networks and biology. However, existing GNNs struggle with the expressivity that captures complex structural patterns, and the generalization that ensures robust performance on diverse and noisy datasets. To address these challenges, we propose a novel GNN model that integrates a k -path rooted subgraph encoder, an adaptive graph contrastive learning approach, and a consistency-aware loss. The k -path rooted subgraph encoder enhances expressivity by capturing and distinguishing intricate substructures, with theoretical guarantees for counting paths and cycles. The adaptive graph contrastive learning framework improves generalization by generating domain-aware graph augmentations based on edge importance, while the consistency-aware loss ensures task-relevant properties are preserved across augmented views. Extensive experiments on 26 datasets spanning graph classification, regression, and realistic scenarios such as noise, class imbalance, and few-shot learning show that our model achieves superior performance against 18 state-of-the-art GNN models in both effectiveness and efficiency. The code is released in https://anonymous.4open.science/r/GEGNN .

Estimating spatial distributions is important in data analysis, such as traffic flow forecasting and epidemic prevention. To achieve accurate spatial distribution estimation, the analysis needs to collect sufficient user data. However, collecting data directly from individuals could compromise their privacy. Most previous works focused on private distribution estimation for one-dimensional data, which does not consider spatial data relation and leads to poor accuracy for spatial distribution estimation. In this paper, we address the problem of private spatial distribution estimation, where we collect spatial data from individuals and aim to minimize the distance between the actual distribution and estimated one under Local Differential Privacy (LDP). To leverage the numerical nature of the domain, we project spatial data and its relationships onto a one-dimensional distribution. We then use this projection to estimate the overall spatial distribution. Specifically, we propose a reporting mechanism called Disk Area Mechanism (DAM), which projects the spatial domain onto a line and optimizes the estimation using the sliced Wasserstein distance. Through extensive experiments, we show the effectiveness of our DAM approach on both real and synthetic data sets, compared with the state-of-the-art methods, such as Multi-dimensional Square Wave Mechanism (MDSW) and Subset Exponential Mechanism with Geo-I (SEM-Geo-I). Our results show that our DAM always performs better than MDSW and is better than SEM-Geo-I when the data granularity is fine enough.

Uncertain butterflies are fundamental and popular graphlet motifs within uncertain bipartite networks, serving as a crucial metric in structural analysis. Despite extensive research have studied butterflies sufficiently on deterministic networks, few of works explore uncertain butterflies. In this paper, we introduce the Most Probable Maximum Weighted Butterfly (MPMB), which holds the highest probability of becoming a maximum weighted butterfly on an uncertain bipartite network. Proved that searching MPMBs is NP-Hard, we then proposed two samplingbased methods, namely Ordering Sampling (OS), and Ordering-Listing Sampling (OLS). The OS method is suitable for singletrial sampling, while the OLS method is optimized for multiple trials, which first finds candidate butterflies in rough before searching MPMBs. Our experimental results indicate that our basic method (OS) performs 1000× faster than the baseline and the optimized method (OLS) achieves another 180× speedup.

Structural graph clustering (SCAN) is one of the most popular graph clustering paradigms, and has attracted plenty of attention recently. Existing solutions assume that the input graphs is homogeneous, i.e., the vertices are of the same type. However, in many real applications, such as bibliographic networks and knowledge graphs, the input graphs is heterogeneous information networks which consist of multi-typed and interconnected objects, which makes SCAN cannot be applied to cluster. Therefore, in this paper, we study the SCAN problem over heterogeneous information networks. Based on the concept of meta-path, we propose two new structural graph clustering models first. Following these two new models, we design new algorithms to support the efficient clustering of a heterogeneous information network. We conduct extensive experiments on six real heterogeneous information networks, and the results demonstrate the effectiveness of our new models and the efficiency of our proposed clustering algorithms.

Ridesharing services play an essential role in modern transportation, which significantly reduces traffic congestion and exhaust pollution. In the ridesharing problem, improving the sharing rate between riders can not only save the travel cost of drivers but also utilize vehicle resources more efficiently. The existing online-based and batch-based methods for the ridesharing problem lack the analysis of the sharing relationship among riders, leading to a compromise between efficiency and accuracy. In addition, the graph is a powerful tool to analyze the structure information between nodes. Therefore, in this paper, we propose a framework, namely StructRide, to utilize the structure information to improve the results for ridesharing problems. Specifically, we extract the sharing relationships between riders to construct a shareability graph. Then, we define a novel measurement, namely shareability loss, for vehicles to select groups of requests such that the unselected requests still have high probabilities of sharing with other requests. Our SARD algorithm can efficiently solve dynamic ridesharing problems to achieve dramatically improved results. Through extensive experiments, we demonstrate the efficiency and effectiveness of our SARD algorithm on two real datasets. Our SARD can run up to 72.68 times faster and serve up to 50% more requests than the state-of-the-art algorithms.

The rise of graph analytics platforms has led to the development of various benchmarks for evaluating and comparing platform performance. However, existing benchmarks often fall short of fully assessing performance due to limitations in core algorithm selection, data generation processes (and the corresponding synthetic datasets), as well as the neglect of API usability evaluation. To address these shortcomings, we propose a novel graph analytics benchmark. First, we select eight core algorithms by extensively reviewing both academic and industrial settings. Second, we design an efficient and flexible data generator and produce eight new synthetic datasets as the default datasets for our benchmark. Lastly, we introduce a multi-level large language model (LLM)-based framework for API usability evaluation-the first of its kind in graph analytics benchmarks. We conduct comprehensive experimental evaluations on existing platforms (GraphX, PowerGraph, Flash, Grape, Pregel+, Ligra, and G-thinker). The experimental results demonstrate the superiority of our proposed benchmark.

Streaming data collection is indispensable for stream data analysis, such as event monitoring. However, publishing these data directly leads to privacy leaks. w -event privacy is a valuable tool to protect individual privacy within a given time window while maintaining high accuracy in data collection. Most existing w -event privacy studies on infinite data stream only focus on homogeneous privacy requirements for all users. In this paper, we propose personalized w -event privacy protection that allows different users to have different privacy requirements in private data stream estimation. Specifically, we design a mechanism that allows users to maintain constant privacy requirements at each time slot, namely Personalized Window Size Mechanism (PWSM). Then, we propose two solutions to accurately estimate stream data statistics while achieving w -Event є -Personalized Differential Privacy (( w,є )-EPDP), namely Personalized Budget Distribution (PBD) and Personalized Budget Absorption (PBA). PBD always provides at least the same privacy budget for the next time step as the amount consumed in the previous release. PBA fully absorbs the privacy budget from the previous k time slots, while also borrowing from the privacy budget of the next k time slots, to increase the privacy budget for the current time slot. We prove that both PBD and PBA outperform the state-of-the-art private stream estimation methods while satisfying the privacy requirements of all users. We demonstrate the efficiency and effectiveness of our PBD and PBA on both real and synthetic datasets, compared with the recent uniformity w -event approaches, Budget Distribution (BD) and Budget Absorption (BA). Our PBD achieves 68% less error than BD on average on real datasets. Besides, our PBA achieves 24.9% less error than BA on average on synthetic datasets.

Blockchains have gained wide adoption for secure data processing. As blockchain data volumes grow, the demand for efficient data analysis, especially aggregate queries, becomes increasingly critical. However, current blockchains lack native support for efficient analytical query processing, forcing users to either maintain full replicas or rely on third-party services without integrity guarantees. In this paper, we propose an efficient framework, Merkle Bloom Filter Tree (MBFT), for authenticated aggregate queries that combine boolean keywords and range predicates on blockchains. At its core is a Bloom filter-based authenticated data structure that supports both types of predicates, constructed per block for efficient transaction indexing. For temporal predicates, we optimize time window queries through value pruning and block consolidation. We design a novel Merge Bloom Filter (MBF) for space-efficient handling of dynamic sets during query authentication. We provide a theoretical analysis of the storage overhead caused by the Bloom filter's false positive rates. Our framework employs data sketches to support various aggregate operations. Extensive experiments demonstrate that MBFT has improved the query speed by up to 286× compared to state-of-the-art authenticated query solutions.

Approximate nearest neighbor search (ANNS) is a fundamental problem in vector databases and AI infrastructures. Recent graph-based ANNS algorithms have achieved high search accuracy with practical efficiency. Despite the advancements, these algorithms still face performance bottlenecks in production, due to the random memory access patterns of graph-based search and the high computational overheads of vector distance. In addition, the performance of a graph-based ANNS algorithm is highly sensitive to parameters, while selecting the optimal parameters is cost-prohibitive, e.g., manual tuning requires repeatedly re-building the index. This paper introduces VSAG , an open-source framework that aims to enhance the in production performance of graph-based ANNS algorithms. VSAG has been deployed at scale in the services of Ant Group, and it incorporates three key optimizations: ( i) efficient memory access : it reduces L3 cache misses with pre-fetching and cache-friendly vector organization; ( ii) automated parameter tuning : it automatically selects performance-optimal parameters without requiring index rebuilding; ( iii) efficient distance computation : it leverages modern hardware, scalar quantization, and smartly switches to low-precision representation to dramatically reduce the distance computation costs. We evaluate VSAG on real-world datasets. The experimental results show that VSAG achieves the state-of-the-art performance and provides up to 4× speedup over HNSWlib (an industry-standard library) while ensuring the same accuracy.

Annotation through crowdsourcing draws incremental attention, which relies on an effective selection scheme given a pool of workers. Existing methods propose to select workers based on their performance on tasks with ground truth, while two important points are missed. 1) The historical performances of workers in other tasks. In real-world scenarios, workers need to solve a new task whose correlation with previous tasks is not well-known before the training, which is called cross-domain. 2) The dynamic worker performance as workers will learn from the ground truth. In this paper, we consider both factors in designing an allocation scheme named cross-domain-aware worker selection with training approach. Our approach proposes two estimation modules to both statistically analyze the cross-domain correlation and simulate the learning gain of workers dynamically. A framework with a theoretical analysis of the worker elimination process is given. To validate the effectiveness of our methods, we collect two novel real-world datasets and generate synthetic datasets. The experiment results show that our method outperforms the baselines on both real-world and synthetic datasets.

The advancement in location technology and the increase in trajectory data have made trajectory data mining a focal point in the field of spatiotemporal data analysis. Unlike the extensive research focused on the similarity of entire trajectories, this paper delves into subtrajectory similarity within collections containing a large number of trajectories, under a specified trajectory similarity metric. We propose the Top-k Representative Similar Subtrajectory Query problem, with the objective of identifying the top-k representative subtrajectories which are most similar to the query trajectory within a large trajectory set. To ensure diversity in the results, we adopt the concept of representative similarity, where only the subtrajectory with the highest similarity score to the query trajectory is reported, thus avoiding the redundancy in the top-$k$results. To address the challenge of high computational costs, we propose a learning-based framework, leveraging a deep learning model called Representative Similarity Score Estimation (RSSE) to approximate subtrajectory similarity scores efficiently and reduce the candidate set significantly. Empirical evaluations conducted on various real-world datasets substantiate the effectiveness and efficiency of our proposed method.

With the development of ubiquitous smart devices, shared mobility services, such as food delivery, ridesharing and crowdsourced parcel delivery, and the related problems, such as task assignment and route planning have drawn much attention from academia and industry. Specifically, shared mobility services enable one worker to deliver more than one package/passenger together such that their routes can share some common sub-routes. Tardiness (the exceeded time) can harm users' experience and reduce the revenue of workers and platforms, which is not well handled in the existing studies. In this paper, we propose a framework, TrendSharing, to minimize the total tardiness when serving all tasks. In TrendSharing, we first build a flow tree to group tasks together. Then, we propose a concept of trend, which represents a group of tasks with high sharability in the flow tree. Furthermore, we devise a decision factor$\epsilon$-score to properly select the trend from the flow tree. In addition, we devise an indicator k-regret to quantify the likelihood of tardiness for each task and devise a greedy algorithm to conduct task assignment. We observe that the insertion operation that is widely used by existing works has little effect on the objective of minimizing total tardiness. Thus, we adopt a simple yet effective strategy, which will continuously append newly planned routes to the workers' existing routes. Moreover, we design an algorithm to plan a route for the trend with an approximation ratio of 2.5. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches on real datasets.

Ridesharing services, such as Uber or Didi, have attracted considerable attention in recent years due to their positive impact on environmental protection and the economy. Existing studies require quick responses to orders, which lack the flexibility to accommodate longer wait times for better grouping opportunities. In this paper, we address a NP-hard ridesharing problem, called Minimal Extra Time RideSharing (METRS), which balances waiting time and group quality (i.e., detour time) to improve riders' satisfaction. To tackle this problem, we propose a novel approach called WATTER (WAit To be fasTER), which leverages an order pooling management algorithm allowing orders to wait until they can be matched with suitable groups. The key challenge is to customize the extra time threshold for each order by reducing the original optimization objective into a convex function of threshold, thus offering a theoretical guarantee to be optimized efficiently. We model the dispatch process using a Markov Decision Process (MDP) with a carefully designed value function to learn the threshold. Through extensive experiments on three real datasets, we demonstrate the efficiency and effectiveness of our proposed approaches.

Urban traffic flow data is useful in transport ap-plications, playing an important role in various tasks such as road planning, site selection, ad services, etc. However, traffic flow data is the composition of personal driving trajectories, which can reveal sensitive information such as home and work locations, leading to privacy issues. Thus publishing traffic flow data while not disclosing private information remains a challenge for urban managers. To address this challenge, we study the noisy publication of traffic flow data in this paper. The noise is added to the data with respect to the differential privacy paradigm, which ensures data safety but deteriorates its utility. On the other hand, we find that the inherent relations of the flow data inherited from the road network structure can be used to correct data without hurting the privacy property. Hence, we propose post-processing techniques, which exploit the data's inherent relations for corrections over the global and local differentially private traffic flow data, respectively. Extensive experiments on real data show that the proposed post-processing techniques improve the data utility by 29.7%-41.1% and 17.3%-48.6% subjecting to the global and local differential privacy paradigm, respectively.

The popularity of decentralized finance has drawn attention to liquidity mining (LM). In LM, a user deposits her cryptocurrencies into liquidity pools to provide liquidity for exchanges and earn yields. Different liquidity pools offer varying yields and require different pairs of cryptocurrencies. A user can exchange a cryptocurrency for another with some exchange costs. Thus, an LM solution consists of exchange transactions and deposit transactions, guaranteeing (1) each exchange transaction must exchange one cryptocurrency for another at a specific rate (i.e., the exchange constraint); (2) the amounts of cryptocurrencies deposited in a liquidity pool must exceed the required threshold (i.e., the minimum constraint); (3) each deposit transaction must deposit a specific pair of cryptocurrencies at a certain rate in a liquidity pool (i.e., the deposit constraint); and (4) the cryptocurrencies used in the solution do not exceed the cryptocurrencies that the user has (i.e., the budget constraint). Selecting the most profitable LM solution is challenging due to the vast number of candidate solutions. To address this challenge, we define the yield maximization liquidity mining (YMLM) problem. Given a set of liquidity pools, a set of the user's cryptocurrencies, a set of exchange rates, and an evaluation function, YMLM aims to find an LM solution with maximal yields, satisfying the minimum, exchange, deposit, and budget constraints. We prove that YMLM is NP-hard and cannot be solved by algorithms with constant approximation ratios. To tackle YMLM, we propose two algorithms, namely YMLM\_GD and YMLM\_SK, with parameterized approximation ratios. Extensive experiments on both real and synthetic datasets show that our approaches outperform the baselines in yields.

Coin mixing methods are widely used to enhance anonymity in cryptocurrency transactions by obfuscating the linkages between recipients and senders. Specifically, coin mixing methods combine several users' transactions into a CoinJoin transaction and decompose the original transactions' outputs into a set of decomposed outputs with similar amounts. However, existing methods have two shortcomings. Firstly, CoinJoin transactions lack anonymity guarantees. Secondly, the number of decomposed outputs is not minimized. To tackle these two shortcomings, we develop a platform named CMixing for mixing transactions with anonymity guarantees and minimal fees. For a CoinJoin transaction obtained by CMixing, the probability of adversaries correctly guessing the original output of a decomposed output does not exceed c , where c is a privacy requirement. Thus, the first shortcoming is solved. Additionally, CMixing uses an approximation algorithm to decompose original outputs, which approximately minimizes the number of decomposed outputs. Thus, the second shortcoming is solved. Our demonstration will showcase how users can use CMixing to make CoinJoin transactions. We will also show the fees saved and the level of anonymity achieved using our algorithm.

Recently, transportation-as-a-service (TaaS) becomes an increasing trend, and online taxi platforms start to apply electric vehicles to serve passengers. Since the recharging time of an electric vehicle is long and non-negligible, it is necessary to smartly arrange the recharging schedules of electric vehicles in working schedules. In order to maximize the number of served taxi-calling tasks, online taxi platforms assign electric vehicles whose remaining electric power is enough to serve the dynamically arriving taxi-calling tasks and schedule suitable idle vehicles to recharging piles to recharge. We formally define the power-aware electric vehicle assignment (PAEVA) problem to serve as many taxi-calling tasks as possible under the constraints of remaining electric power and deadline. We prove that the PAEVA problem is NP-hard. To solve PAEVA, we design a novel strategy to help arrange the schedules of electric vehicles. Specifically, the strategy requires that, in a time slot and an area gird, the ratio of the number of electric vehicles whose remaining electric power is higher than a threshold$\alpha$to the number of predicted taxi-calling tasks should be higher than a threshold$\beta$. We propose two approximation approaches with theoretical guarantees to adaptively determine the values of the two thresholds of the strategy. We evaluate our solutions’ effectiveness and efficiency by comprehensive experiments on real datasets.

Despite remarkable advancements in graph contrastive learning techniques, the identification of interdependent relationships when maximizing cross-view mutual information remains a challenging issue, primarily due to the complexity of graph topology. In this study, we propose to formulate cross-view interdependence from the innovative perspective of information flow. Accordingly, IDEAL, a simple yet effective framework, is proposed for interdependence-adaptive graph contrastive learning. Compared with existing methods, IDEAL concurrently addresses same-node and distinct-node interdependence, circumvents the reliance on additional distribution mining techniques, and is augmentation-aware. Besides, the objective of IDEAL takes advantage of both contrastive and generative learning objectives and is thus capable of learning a uniform embedding distribution while retaining essential semantic information. The effectiveness of IDEAL is validated by extensive empirical evidence. It consistently outperforms state-of-the-art self-supervised methods by considerable margins across seven benchmark datasets with diverse scales and properties and, at the same time, showcases promising training efficiency.

With the rapid development of mobile Internet technology, on-demand car-hailing services have become essential for people's daily commuting. Order dispatch is a critical problem in on-demand car-hailing services. However, in most existing works, the service provider is asked to set a unified pick-up distance to prevent long waiting time for requesters. Indeed, different requesters have different tolerance for pick-up distance, and some requesters may accept longer pick-ups if offered discounts for payment. Regarding this fact, we formulate discount-based order dispatch as a coupling of two subproblems, discount determination and order dispatch, aiming to dispatch more orders and thereby more platform profits. We propose customized methods to solve the problems for shared and non-shared mobility services, respectively. We also conduct extensive experiments to evaluate the effectiveness and efficiency of our proposed methods on a real dataset, which shows that our methods can achieve 170% improvements in non-shard services and 43% improvements in ridesharing services on average in terms of attained profit compared to the widely adopted baselines.

Data collection is indispensable for spatial crowd-sourcing services, such as resource allocation, policymaking, and scientific explorations. However, privacy issues make it challenging for users to share their information unless receiving sufficient compensation. Differential Privacy (DP) is a promising mechanism to release helpful information while protecting individuals’ privacy. However, most DP mechanisms only consider a fixed compensation for each user’s privacy loss. In this paper, we design a task assignment scheme that allows workers to dynamically improve their utility with dynamic distance privacy leakage. Specifically, we propose two solutions to improve the total utility of task assignment results, namely Private Utility Conflict-Elimination (PUCE) approach and Private Game Theory (PGT) approach, respectively. We prove that PUCE achieves higher utility than the state-of-the-art works. We demonstrate the efficiency and effectiveness of our PUCE and PGT approaches on both real and synthetic data sets compared with the recent distance-based approach, Private Distance Conflict-Elimination (PDCE). PUCE is always better than PDCE slightly. PGT is 50% to 63% faster than PDCE and can improve 16% utility on average when worker range is large enough.

Similar subtrajectory search is a finer-grained operator that can better capture the similarities between one query trajectory and a portion of a data trajectory than the traditional similar trajectory search, which requires that the two checking trajectories are similar in their entirety. Many real applications (e.g., trajectory clustering and trajectory join) utilize similar subtrajectory search as a basic operator. It is considered that the time complexity is O ( mn 2 ) for exact algorithms to solve the similar subtrajectory search problem under most trajectory distance functions in the existing studies, where m is the length of the query trajectory and n is the length of the data trajectory. In this paper, to the best of our knowledge, we are the first to propose an exact algorithm to solve the similar subtrajectory search problem in O ( mn ) time for most of widely used trajectory distance functions (e.g., WED, DTW, ERP, EDR and Frechet distance). Through extensive experiments on three real datasets, we demonstrate the efficiency and effectiveness of our proposed algorithms.

The payment channel network (PCN) is a promising solution to increase the throughput of blockchains. However, unidirectional transactions can deplete a user's deposits in a payment channel (PC), reducing the success ratio of transactions (SRoT). To address this depletion issue, rebalance protocols are used to shift tokens from well-deposited PCs to under-deposited PCs. To improve SRoT, it is beneficial to increase the balance of a PC with a lower balance and a higher weight (i.e., more transaction executions rely on the PC). In this paper, we define the utility of a transaction and the utility-aware rebalance (UAR) problem. The utility of a transaction is proportional to the weight of the PC and the amount of the transaction, and inversely proportional to the balance of the receiver. To maximize the effect of improving SRoT, UAR aims to find a set of transactions with maximized utilities, satisfying the budget and conservation constraints. The budget constraint limits the number of tokens shifted in a PC. The conservation constraint requires that the number of tokens each user sends equals the number of tokens received. We prove that UAR is NP-hard and cannot be approximately solved with a constant ratio. Thus, we propose two heuristic algorithms, namely Circuit Greedy and UAR_DC. Extensive experiments show that our approaches outperform the existing approach by at least 3.16 times in terms of utilities.

With the development of traffic prediction technology, spatiotemporal prediction models have attracted more and more attention from academia communities and industry. However, most existing researches focus on reducing model's prediction error but ignore the error caused by the uneven distribution of spatial events within a region. In this paper, we study a region partitioning problem, namely optimal grid size selection problem (OGSS), which aims to minimize the real error of spatiotemporal prediction models by selecting the optimal grid size. In order to solve OGSS, we analyze the upper bound of real error of spatiotemporal prediction models and minimize the real error by minimizing its upper bound. Through in-depth analysis, we find that the upper bound of real error will decrease then increase when the number of model grids increase from 1 to the maximum allowed value. Then, we propose two algorithms, namely Ternary Search and Iterative Method, to automatically find the optimal grid size. Finally, the experiments verify that the error of prediction has the same trend as its upper bound, and the change trend of the upper bound of real error with respect to the increase of the number of model grids will decrease then increase. Meanwhile, in a case study, by selecting the optimal grid size, the order dispatching results of a state-of-the-art prediction-based algorithm can be improved up to 13.6%, which shows the effectiveness of our methods on tuning the region partition for spatiotemporal prediction models.

Due to the transparency of blockchain, adversaries can observe the details of a transaction, and then utilize the amount as a unique quasi-identifier to make deanonymization. Nowadays, to obscure the linkages between receivers and senders within a transaction on the blockchain, mixing services are widely applied in many real applications to enhance cryptocurrencies' anonymity. The basic idea of mixing services is to hide an output within several other outputs in a transaction such that adversaries cannot distinguish them by their amounts since they are purposely selected to have the same amount. For a set of original outputs with different amounts, mixing services need to decompose them into a set of decomposed outputs, where any decomposed output has some other decomposed outputs with the same amount. Since the transaction fee is related to the number of outputs, we are motivated to decompose original outputs into a minimal set of decomposed outputs, which is challenging to guarantee the privacy-preserving effect at the same time. In this paper, we formally define the anonymity-aware output decomposition (AA-OD) problem, which aims to find a c-decomposition with a minimum number of decomposed outputs for a given original output set. A c-decomposition guarantees that for any original output$o$, there are at most$c$of all decomposed outputs with an amount of$x$coming from$o$. We prove that the AA-OD problem is NP-hard. Thus, we propose an approximation algorithm, namely Boggart11Boggart is a magical creature in J. K. Rowling's Harry Potter series who can shift his shape and no one knows what it looks like., to solve the AA-OD problem with a (2/c + 3)-approximation bound on the number of decomposed outputs. We verify the efficiency and effectiveness of our approach through comprehensive experiments on both real and synthetic data sets.

Listing all k-cliques is a fundamental problem in graph mining, with applications in finance, biology, and social network analysis. However, owing to the exponential growth of the search space as$k$increases, listing all k-cliques is algorithmically challenging. DDegree and DDegCol are the state-of-the-art algorithms that exploit ordering heuristics based on degree ordering and color ordering, respectively. Both DDegree and DDegCol induce high time and space overhead for set intersections cause they construct and maintain all induced subgraphs. Meanwhile, it is non-trivial to implement the data level parallelism to further accelerate on DDegree and DDegCol. In this paper, we propose two efficient algorithms SDegree and BitCol for k-clique listing. We mainly focus on accelerating the set intersections for k-clique listing. Both SDegree and BitCol exploit the data level parallelism for further acceleration with single instruction multiple data (SIMD) or vector instruction sets. Furthermore, we propose two preprocessing techniques Pre-Core and Pre-List, which run in linear time. The preprocessing techniques significantly reduce the size of the original graph and prevent exploring a large number of invalid nodes. In the theoretical analysis, our algorithms have a comparable time complexity and a slightly lower space complexity than the state-of-the-art algorithms. The comprehensive experiments reveal that our algorithms outperform the state-of-the-art algorithms by 3.75x for degree ordering and 5.67x for color ordering on average.

In spite of its wide usage in various applications, existing construction methods for Knowledge Base (KB) are still on their way to obtaining 100% correct facts. Thus, employing crowd workers to validate a KB has been proposed to improve its reliability. Most of the existing works focus on devising games with proper incentives to engage workers in validating more facts, but rarely consider matching facts with proper workers. Facts have diverse domains (topics), which naturally require workers of different expertise. In addition, they also generally have different utilities, i.e., some are more heavily used than others. Thus, distinguishing the facts in terms of utility to give them different validation priorities is meaningful, especially when the budget is limited. To this end, we study the crowdsourced fact validation problem which considers worker domains and fact utilities, and find that with some reductions, it can be solved by the existing minimum cost network flow method. However, directly employing that method requires a huge time cost. We thereby propose an optimized network flow method which reduces the network complexity to save the time cost by properly grouping the facts. Furthermore, we propose an incremental validation method, which utilizes the previous results for validating an evolving KB. We finally conduct extensive experiments to demonstrate the effectiveness of the proposed methods.

Nowadays, ridesharing becomes a popular commuting mode. Dynamically arriving riders post their origins and destinations, then the platform assigns drivers to serve them. In ridesharing, different groups of riders can be served by one driver if their trips can share common routes. Recently, many ridesharing companies (e.g., Didi and Uber) further propose a new mode, namely "ridesharing with meeting points". Specifically, with a short walking distance but less payment, riders can be picked up and dropped off around their origins and destinations, respectively. In addition, meeting points enables more flexible routing for drivers, which can potentially improve the global profit of the system. In this paper, we first formally define the Meeting-Point-based Online Ridesharing Problem (MORP). We prove that MORP is NP-hard and there is no polynomial-time deterministic algorithm with a constant competitive ratio for it. We notice that a structure of vertex set, k -skip cover, fits well to the MORP. k -skip cover tends to find the vertices (meeting points) that are convenient for riders and drivers to come and go. With meeting points, MORP tends to serve more riders with these convenient vertices. Based on the idea, we introduce a convenience-based meeting point candidates selection algorithm. We further propose a hierarchical meeting-point oriented graph (HMPO graph), which ranks vertices for assignment effectiveness and constructs k -skip cover to accelerate the whole assignment process. Finally, we utilize the merits of k -skip cover points for ridesharing and propose a novel algorithm, namely SMDB, to solve MORP. Extensive experiments on real and synthetic datasets validate the effectiveness and efficiency of our algorithms.

With the rapid development of mobile technology, nowadays, people spend a large amount of time on mobile devices. The locations and contexts of users are easily accessed by mobile advertising brokers, and the brokers can send customers related location-based advertisements. In this paper, we consider an important location-based advertising problem, namely maximum utility advertisement assignment (MUAA) problem, with the estimation of the interests of customers and the contexts of the vendors, we want to maximize the overall utility of ads by determining the ads sent to each customer subject to the constraints of the capacities of customers, the distance ranges and the budgets of vendors. We prove that the MUAA problem is NP-hard and intractable. Thus, we propose one offline approach, namely the${\sf reconciliation\ approach}$, which has an approximation ratio of$(1-\epsilon)\cdot \theta$. In addition, we also address the online scenario, in which customers arrive in a streaming fashion, with one novel online algorithm, namely the${\sf online\ adaptive\ factor-aware\ approach}$, which has a competitive ratio (compared to the optimal solution of the offline scenario) of$\frac{\ln (g)+1}{\theta }$,$g>e$, where$e$is the base of the natural logarithm. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets.

In this paper, we study the privacy-preserving task assignment problem in spatial crowdsourcing, where the locations of both workers and tasks, prior to their release to the server, are perturbed with Geo-Indistinguishability (a differential privacy notion for location-based systems). Different from the previously studied online setting, where each task is assigned immediately upon arrival, we target the batch-based setting, where the server maximizes the number of successfully assigned tasks after a batch of tasks arrive. To achieve this goal, we propose the k-Switch solution, which first divides the workers into small groups based on the perturbed distance between workers/tasks, and then utilizes Homomorphic Encryption (HE) based secure computation to enhance the task assignment. Furthermore, we expedite HE-based computation by limiting the size of the small groups under k. Extensive experiments demonstrate that, in terms of the number of successfully assigned tasks, the k-Switch solution improves batch-based baselines by 5.9X and the existing online solution by 1.74X, with no privacy leak.

To encourage users to buy more products, many online stores offer coupons. When a customer finds that the price of the products she/he wants to order is below the threshold of a coupon, she/he might want to place the order together with others to meet this threshold and enjoy more instant rebates. However, to conduct these orders and deliver products to receivers, users may need to pay extra delivery costs. When an order comprises several receivers' requests, the products in the order should first be delivered from stores to an assigned warehouse, packed into different packages, and delivered to the different receivers. It may be costly than directly delivering products from stores to receivers. For the benefits of buyers, we propose a platform, the Crowdrebate platform, which collects requests from users, groups requests into a set of orders to get more rebates, and relays products to different receivers in an order. The platform will make a profit by getting a proportion from the benefit of the receiver (defined as the rebate minus the extra cost) of orders as its revenue. In this paper, we define the Crowdrebate problem, which aims to maximize the benefit of receivers. We prove the NP-hardness of the Crowdrebate problem. Therefore, we propose a heuristic solution to address the problem. Moreover, we evaluate the effectiveness and efficiency of our algorithm via comprehensive experiments.

In privacy-preserving blockchain systems, to protect a sender's identity of a transaction in privacy-preserving blockchain systems, ring signature (RS) schemes have been widely implemented, which allow users to obscure consumed tokens via including "mixin'' (i.e., chaff tokens). However, recent works point out that existing RS schemes are vulnerable to the "chain-reaction'' analysis, where adversaries eliminate mixins of RSs by utilizing the fact that each token can only be consumed in a RS. By "chain-reaction'' analysis, adversaries can find some definite token-RS pair sets (DTRSs) to confirm the sender's identity of a RS. Besides, the existing RS schemes do not consider the diversity of mixins when generating a RS. Moreover, since the transaction fee is proportional to the number of mixins, a use is motivated to use a RS with the minimum number of mixins. In this paper, we formally define the diversity-aware mixins selection (DA-MS) problem, which aims to generate a RS with the minimum number of mixins satisfying the constraints of its diversity and the anonymity of other RSs. We prove the DA-MS problem is $\#P$ and propose a breadth-first search algorithm to get the optimal solution. Furthermore, to efficiently solve the DA-MS problem, we propose two practical configurations and two approximation algorithms with theoretic guarantees. Through comprehensive experiments on real data sets as well as synthetic data sets, we illustrate the effectiveness and the efficiency of our solutions.

With the rapid development of smart mobile devices, the car-hailing platforms (e.g., Uber or Lyft) have attracted much attention from the academia and the industry. In this paper, we consider a dynamic car-hailing problem, namely maximum revenue vehicle dispatching (MRVD), in which rider requests dynamically arrive and drivers need to serve riders such that the entire revenue of the platform is maximized. We prove that the MRVD problem is NP-hard and intractable. To handle the MRVD problem, we propose a queueing-based vehicle dispatching framework, which first uses existing machine learning models to predict the future vehicle demand of each region, then estimates the idle time periods of drivers through a double-sided queueing model for each region. With the information of the predicted vehicle demands and estimated idle time periods of drivers, we propose two batch-based vehicle dispatching algorithms to efficiently assign suitable drivers to riders such that the expected overall revenue of the platform is maximized during each batch processing. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets. In summary, our methods can achieve 3% ~ 10% increase on overall revenue without sacrificing on running speed compared with the state-of-the-art solutions.

With the rapid development of crowdsourcing platforms that aggregate the intelligence of Internet workers, crowdsourcing has been widely utilized to address problems that require human cognitive abilities. Considering great dynamics of worker arrival and departure, it is of vital importance to design a task assignment scheme to adaptively select the most beneficial tasks for the available workers. In this paper, in order to make the most efficient utilization of the worker labor and balance the accuracy of answers and the overall latency, we a) develop a parameter estimation model that assists in estimating worker expertise, question easiness, and answer confidence; b) propose a quality-assured synchronized task assignment scheme that executes in batches and maximizes the number of potentially completed questions (MCQ) within each batch. We prove that MCQ problem is NP-hard and present two greedy approximation solutions to address the problem. The effectiveness and efficiency of the approximation solutions are further evaluated through extensive experiments on synthetic and real datasets. The experimental results show that the accuracy and the overall latency of the MCQ approaches outperform the existing online task assignment algorithms in the synchronized task assignment scenario.

Ubiquitous smart devices and high-quality wireless networks enable people to participate in spatial crowdsourcing tasks easily, which require workers to physically move to specific locations to conduct their assigned tasks. Spatial crowdsourcing has attracted much attention from both academia and industry. In this paper, we consider a spatial crowdsourcing scenario, where the tasks may have some dependencies among them. Specifically, one task can only be dispatched when its dependent tasks have already been assigned. In fact, task dependencies are quite common in many real-life applications, such as house repairing and holding sports games. We formally define the dependency-aware spatial crowdsourcing (DA-SC), which focuses on finding an optimal worker-and-task assignment under the constraints of dependencies, skills of workers, moving distances and deadlines to maximize the successfully assigned tasks. We prove that the DA-SC problem is NP-hard and thus intractable. Therefore, we propose two approximation algorithms, including a greedy approach and a game-theoretic approach, which can guarantee the approximate bounds of the results in each batch process. Through extensive experiments on both real and synthetic data sets, we demonstrate the efficiency and effectiveness of our DA-SC approaches.

The dramatic development of shared mobility in food delivery, ridesharing, and crowdsourced parcel delivery has drawn great concerns. Specifically, shared mobility refers to transferring or delivering more than one passenger/package together when their traveling routes have common sub-routes or can be shared. A core problem for shared mobility is to plan a route for each driver to fulfill the requests arriving dynamically with given objectives. Previous studies greedily and incrementally insert each newly coming request to the most suitable worker with a minimum travel cost increase, which only considers the current situation and thus not optimal. In this paper, we propose a demand-aware route planning (DARP) for shared mobility services. Based on prediction, DARP tends to make optimal route planning with more information about requests in the future. We prove that the DARP problem is NP-hard, and further show that there is no polynomial-time deterministic algorithm with a constant competitive ratio for the DARP problem unless P=NP. Hence, we devise an approximation algorithm to realize the insertion operation for our goal. With the insertion algorithm, we devise a prediction based solution for the DARP problem. Extensive experiment results on real datasets validate the effectiveness and efficiency of our technique.

With the rapid development of smart mobile devices, the car-hailing platforms (e.g., Uber or Lyft) have attracted much attention from both the academia and the industry. In this paper, we consider an important dynamic car-hailing problem, namely maximum revenue vehicle dispatching (MRVD), in which rider requests dynamically arrive and drivers need to serve as many riders as possible such that the entire revenue of the platform is maximized. We prove that the MRVD problem is NP-hard and intractable. To handle the MRVD problem, we propose a queueing-based vehicle dispatching framework, which first uses existing machine learning algorithms to predict the future vehicle demand of each region, then estimates the idle time periods of drivers through a queueing model for each region. With the information of the predicted vehicle demands and estimated idle time periods of drivers, we propose one batch-based vehicle dispatching algorithm to efficiently assign suitable drivers to riders such that the expected entire revenue of the platform is maximized during each batch processing. Through experiments over real data sets, we demonstrate the efficiency and effectiveness of our proposed framework.

Nowadays, the locations and contexts of users are easily accessed by mobile advertising brokers, and the brokers can send customers related location-based advertisement. In this paper, we consider a location-based advertising problem, namely maximum utility advertisement assignment (MUAA) problem, with the estimation of the interests of customers and the contexts of the vendors, we want to maximize the overall utility of ads by determining the ads sent to each customer subject to the constraints of the capacities of customers, the distance ranges and the budgets of vendors. We prove that the MUAA problem is NP-hard and intractable. Thus, we propose one offline approach, namely the reconciliation approach, which has an approximation ratio of (1 - ε) · θ, where θ = min(a1/2n1c, a2/n2c, ⋯,am/nmc), and nz is the larger value between the number of valid vendors and the capacity aiof customer ui. Experiments on real data sets confirm the efficiency and effectiveness of our proposed approach.

Spatial crowdsourcing services, such as Uber and Grabhub, become popular recently. Task assignment plays an important role in offering high-quality services. However, most of the existing solutions for task assignment only focus on the entire performance of the platform and do not optimize the maximum assignment delay. As a result, they cannot handle some real world scenarios which require minimizing the maximum delay in task assignment. In this paper, we study the minimizing maximum delay spatial crowdsourcing (MMD-SC) problem and propose solutions aiming at achieving a worst case controlled task assignment. The MMD-SC problem assumes that both workers and requesters come dynamically and considers not only the workers' travel costs but also the buffering time of tasks, thus it is very challenging due to two-sided online setting. To address these challenges, in this work, we propose a space embedding based online random algorithm with a competitive ratio of O(log n) and two efficient heuristic algorithms, namely the threshold based greedy approach and the batch-based approach. In addition, we demonstrate the effectiveness and efficiency of our methods via extensive experiments on both synthetic and real datasets.

With the popularity of smart devices and the development of high-speed wireless networks, the spatial crowdsourcing has attracted much attention from both academia and industry (e.g., Uber and TaskRabbit). Specifically, a spatial crowdsourcing platform assigns workers to location-based tasks according to their current positions, then the workers need to physically move to the specified locations to conduct the assigned tasks. In this paper, we consider an important spatial crowdsourcing problem, namely cooperation-aware spatial crowdsourcing (CA-SC), where spatial tasks (e.g., collecting the Wi-Fi signal strength in one building) are time-constrained and require more than one worker to complete thus the cooperation among assigned workers is essential to the result. Our CA-SC problem is to assign workers to spatial tasks such that the overall cooperation quality is maximized. We prove that the CA-SC problem is NP-hard by reducing from the k-set packing problem, thus intractable. To tackle the CA-SC problem, we propose task-priority greedy (TPG) approach and game theoretic (GT) approach with two optimization methods to quickly solve the CA-SC problem and achieve high total cooperation quality scores. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets.

Ridesharing plays a more and more important role in modern transport. In this paper, we propose solutions for the bonus-offering scenario of ridesharing platforms (service providers). When vehicles are in shortage, requesters are allowed to offer bonus so that their orders can get prioritized in the dispatch process. To enable self-motivated bonus bidding of requesters, we devise an auction mechanism, where requesters are supposed to submit their bids truthfully and the platform conducts order dispatch and pricing. Our goal is to maximize the overall utility of the auction, while ensuring desirable auction properties such as truthfulness and individual rationality. To realize that, we propose a greedy and a ranking approach for order dispatch and their corresponding pricing strategies. Extensive experiments on real data suggest that the ranking approach is both effective and efficient.

For decades, the crowdsourcing has gained much attention from both academia and industry, which outsources a number of tasks to human workers. Typically, existing crowdsourcing platforms include CrowdFlower, Amazon Mechanical Turk (AMT), and so on, in which workers can autonomously select tasks to do. However, due to the unreliability of workers or the difficulties of tasks, workers may sometimes finish doing tasks either with incorrect/incomplete answers or with significant time delays. Existing studies considered improving the task accuracy through voting or learning methods, they usually did not fully take into account reducing the latency of the task completion. This is especially critical, when a task requester posts a group of tasks (e.g., sentiment analysis), and one can only obtain answers of all tasks after the last task is accomplished. As a consequence, the time delay of even one task in this group could delay the next step of the task requester's work from minutes to days, which is quite undesirable for the task requester. Inspired by the importance of the task accuracy and latency, in this paper, we will propose a novel crowdsourcing framework, namely Fast and Reliable crOwdsourcinG framework (FROG), which intelligently assigns tasks to workers, such that the latencies of tasks are reduced and the expected accuracies of tasks are met. Specifically, our FROG framework consists of two important components, task scheduler and notification modules. For the task scheduler module, we formalize a FROG task scheduling (FROG-TS) problem, in which the server actively assigns workers to tasks to achieve high task reliability and low task latency. We prove that the FROG-TS problem is NP-hard. Thus, we design two heuristic approaches, request-based and batch-based scheduling. For the notification module, we define an efficient worker notifying (EWN) problem, which only sends task invitations to those workers with high probabilities of accepting the tasks. To tackle the EWN problem, we propose a smooth kernel density estimation approach to estimate the probability that a worker accepts the task invitation. Through extensive experiments, we demonstrate the effectiveness and efficiency of our proposed FROG platform on both real and synthetic data sets.

Recently, with the rapid development of mobile devices and the crowdsourcing platforms, the spatial crowdsourcing has attracted much attention from the database community. Specifically, spatial crowdsourcing refers to sending a location-based request to workers according to their positions, and workers need to physically move to specified locations to conduct tasks. Many works have studied task assignment problems in spatial crowdsourcing, however, their problem settings are different from each other. Thus, it is hard to compare the performances of existing algorithms on task assignment in spatial crowdsourcing. In this paper, we present a comprehensive experimental comparison of most existing algorithms on task assignment in spatial crowdsourcing. Specifically, we first give general definitions about spatial workers and spatial tasks based on definitions in the existing works such that the existing algorithms can be applied on the same synthetic and real data sets. Then, we provide a uniform implementation for all the tested algorithms of task assignment problems in spatial crowdsourcing (open sourced). Finally, based on the results on both synthetic and real data sets, we discuss the strengths and weaknesses of tested algorithms, which can guide future research on the same area and practical implementations of spatial crowdsourcing systems.

With the rapid advancement of mobile devices and crowdsourcing platforms, spatial crowdsourcing has attracted much attention from various research communities. A spatial crowdsourcing system periodically matches a number of locationbased workers with nearby spatial tasks (e.g., taking photos or videos at some specific locations). Previous studies on spatial crowdsourcing focus on task assignment strategies that maximize an assignment score based solely on the available information about workers/tasks at the time of assignment. These strategies can only achieve local optimality by neglecting the workers/tasks that may join the system in a future time. In contrast, in this paper, we aim to improve the global assignment, by considering both present and future (via predictions) workers/tasks. In particular, we formalize a new optimization problem, namely maximum quality task assignment (MQA). The optimization objective of MQA is to maximize a global assignment quality score, under a traveling budget constraint. To tackle this problem, we design an effective grid-based prediction method to estimate the spatial distributions of workers/tasks in the future, and then utilize the predictions to assign workers to tasks at any given time instance. We prove that the MQA problem is NPhard, and thus intractable. Therefore, we propose efficient heuristics to tackle the MQA problem, including MQA greedy and MQA divide-and-conquer approaches, which can efficiently assign workers to spatial tasks with high quality scores and low budget consumptions. Through extensive experiments, we demonstrate the efficiency and effectiveness of our approaches on both real and synthetic datasets.

Ridesharing enables drivers to share any empty seats in their vehicles with riders to improve the efficiency of transportation for the benefit of both drivers and riders. Different from existing studies in ridesharing that focus on minimizing the travel costs of vehicles, we consider that the satisfaction of riders (the utility values) is more important nowadays. Thus, we formulate the problem of utility-aware ridesharing on road networks (URR) with the goal of providing the optimal rider schedules for vehicles to maximize the overall utility, subject to spatial-temporal and capacity constraints. To assign a new rider to a given vehicle, we propose an efficient algorithm with a minimum increase in travel cost without reordering the existing schedule of the vehicle. We prove that the URR problem is NP-hard by reducing it from the 0-1 Knapsack problem and it is unlikely to be approximated within any constant factor in polynomial time through a reduction from the DENS k-SUBGRAPH problem. Therefore, we propose three efficient approximate algorithms, including a bilateral arrangement algorithm, an efficient greedy algorithm and a grouping-based scheduling algorithm, to assign riders to suitable vehicles with a high overall utility. Through extensive experiments, we demonstrate the efficiency and effectiveness of our URR approaches on both real and synthetic data sets.

With the rapid development of mobile devices and crowdsourcing platforms, the spatial crowdsourcing has attracted much attention from the database community. Specifically, the spatial crowdsourcing refers to sending location-based requests to workers, based on their current positions. In this paper, we consider a spatial crowdsourcing scenario, in which each worker has a set of qualified skills, whereas each spatial task (e.g., repairing a house, decorating a room, and performing entertainment shows for a ceremony) is time-constrained, under the budget constraint, and required a set of skills. Under this scenario, we will study an important problem, namelymulti-skill spatial crowdsourcing(MS-SC), which finds an optimal worker-and-task assignment strategy, such that skills between workers and tasks match with each other, and workers’ benefits are maximized under the budget constraint. We prove that the MS-SC problem is NP-hard and intractable. Therefore, we propose three effective heuristic approaches, including greedy,$g$-divide-and-conquer and cost-model-based adaptive algorithms to get worker-and-task assignments. Through extensive experiments, we demonstrate the efficiency and effectiveness of our MS-SC processing approaches on both real and synthetic data sets.

With the rapid development of mobile devices and the crowdsourcing platforms, the spatial crowdsourcing has attracted much attention from the database community, specifically, spatial crowdsourcing refers to sending a location-based request to workers according to their positions. In this paper, we consider an important spatial crowdsourcing problem, namely reliable diversity-based spatial crowdsourcing (RDB-SC), in which spatial tasks (such as taking videos/photos of a landmark or firework shows, and checking whether or not parking spaces are available) are time-constrained, and workers are moving towards some directions. Our RDB-SC problem is to assign workers to spatial tasks such that the completion reliability and the spatial/temporal diversities of spatial tasks are maximized. We prove that the RDB-SC problem is NP-hard and intractable. Thus, we propose three effective approximation approaches, including greedy, sampling, and divide-and-conquer algorithms. In order to improve the efficiency, we also design an effective cost-model-based index, which can dynamically maintain moving workers and spatial tasks with low cost, and efficiently facilitate the retrieval of RDB-SC answers. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets.

As one of the successful forms of using Wisdom of Crowd, crowdsourcing, has been widely used for many human intrinsic tasks, such as image labeling, natural language understanding, market predication and opinion mining. Meanwhile, with advances in pervasive technology, mobile devices, such as mobile phones and tablets, have become extremely popular. These mobile devices can work as sensors to collect multimedia data(audios, images and videos) and location information. This power makes it possible to implement the new crowdsourcing mode: spatial crowdsourcing. In spatial crowdsourcing, a requester can ask for resources related a specific location, the mobile users who would like to take the task will travel to that place and get the data. Due to the rapid growth of mobile device uses, spatial crowdsourcing is likely to become more popular than general crowdsourcing, such as Amazon Turk and Crowdflower. However, to implement such a platform, effective and efficient solutions for worker incentives, task assignment, result aggregation and data quality control must be developed. In this demo, we will introduce gMission, a general spatial crowdsourcing platform, which features with a collection of novel techniques, including geographic sensing, worker detection, and task recommendation. We introduce the sketch of system architecture and illustrate scenarios via several case analysis.