Distance Comparison Operations (DCOs), which decide whether the distance between a data vector and a query is within a threshold, are a critical performance bottleneck in vector similarity search. Recent DCO methods that avoid full-dimensional distance computations promise significant speedups, but their readiness for production vector database systems remains an open question. To address this, we conduct a comprehensive benchmark of 8 DCO algorithms across 10 datasets (with up to 100M vectors and 12,288 dimensions) and diverse hardware configurations (CPUs with/without SIMD, and GPUs). Our study reveals that these methods are not silver bullets: their efficiency is highly sensitive to data dimensionality, degrades under out-of-distribution queries, and is unstable across hardware. Yet, our evaluation also demonstrates often-overlooked merits: they can accelerate index construction and data updates. Despite these benefits, their unstable performance, which can be slower than a full-dimensional scan, leads us to conclude that recent algorithmic advancements in DCO are not yet ready for production deployment.

Vectors are used to represent unstructured data with their embeddings and associated attributes. Similarity search over large-scale vector datasets has gained significant interest from both industry and academia. It aims to identify the k nearest neighbors to a query object from vectors that satisfy a given attribute filter constraint. Despite its popularity, most solutions focus on single-sourced data and overlook the need for vector retrieval across federated datasets. To fill this gap, we introduce a new problem, federated vector similarity search with filters, which enables privacy-preserving vector retrieval over multi-sourced data held by mutually untrusted providers. While some solutions can be adapted, they struggle with low recall, excessive search latency, or high communication cost. To address these challenges, we propose FedVS, a privacy-preserving framework enhanced with indexing and pruning based on Trusted Execution Environment (TEE). We also provide a comprehensive theoretical analysis, including complexity, security, and approximation guarantees for recall. Moreover, we deploy our solution over real-world vector databases and conduct extensive experiments. The results demonstrate that our solution outperforms state-of-the-art methods in both effectiveness and efficiency.

Efficient vector search is a foundational capability of vector databases. However, most prior research overlooks its critical role in federated databases for applications like financial risk control and smart healthcare. In these privacy-sensitive scenarios, a vector search engine must not only deliver high performance but also guarantee privacy across federated databases. Current solutions, however, struggle with scalability for high-dimensional vectors, and offer limited query support. To bridge this gap, this paper introduces FedVSE, a privacy-preserving vector search engine for federated databases. FedVSE supports both KNN and hybrid queries, matching the versatility of modern vector databases. It leverages Intel SGX for hardware-enabled security and offers highly optimized query processing via indexing and pruning. Conference audiences can interact with FedVSE in real time and observe how it enables real-world services like cross-platform trajectory similarity search.

Approximate Nearest Neighbor (ANN) search is a foundational yet computationally demanding query in vector databases, critical for applications such as information retrieval and generative AI inference. Hierarchical graph-based methods have attracted significant attention due to their promising query performances compared to other indexes for ANN search. However, these methods still face efficiency bottlenecks because they rely on exhaustive and level-by-level traversals within hierarchical graphs. This paper introduces SHG, a novel hierarchical graph-based index that enhances search efficiency by bypassing intermediate and redundant levels. Specifically, SHG leverages a hierarchical vector compression method to reduce the time spent on distance computations, and employs a new data structure called shortcuts to determine the number of intermediate levels that can be safely skipped. Extensive experiments demonstrate that our solution achieves 1.5–1.8× speedup compared to state-of-the-art methods. Meanwhile, our method significantly improves the robustness of ANN search, boosting recall by up to 20% for certain queries on benchmark datasets.

Efficient indexing is fundamental to managing and analyzing multi-dimensional data. A growing trend is to directly learn the storage layout of multi-dimensional data using simple machine learning models, leading to the concept of Learned Index . Compared to conventional indexing methods that have been used for decades (e.g., k d-tree and R-tree variants), learned indexes have demonstrated empirical advantages in both space and time efficiency on modern architectures. However, there is a lack of comprehensive evaluation across existing multi-dimensional learned indexes under a standardized benchmark, making it challenging to identify the most suitable index for specific data types and query patterns. This gap also hinders the widespread adoption of learned indexes in practical applications. In this paper, we present the first in-depth empirical study to answer the question: how good are multi-dimensional learned indexes? We evaluate ten recently published indexes under a unified experimental framework, which includes standardized implementations, datasets, query workloads, and evaluation metrics. We thoroughly investigate the evaluation results and discuss the findings that may provide insights for future learned index design.

Querying the shortest path between two locations is a fundamental task in many applications, and has been extensively studied for static road networks. However, in reality, the travel costs of road segments evolve over time, and hence the road network can be modeled as a time-dependent graph. In this paper, we study the shortest path query over large-scale time-dependent road networks. We first present a tree decomposition method to model the time-dependent road network as a tree structure that preserves travel costs. To further improve query efficiency, a set of shortcuts is selected and built on the constructed tree structure. Specifically, we formally define a shortcut selection problem over the tree decomposition of the time-dependent road network. This problem, which is proven to be NP-hard, aims to select and build the most effective shortcut set. We first devise a dynamic programming method with exact results to solve the selection problem. To obtain the optimal shortcut set quickly, we design an approximation algorithm that guarantees a 0.5-approximation ratio. Based on the novel tree structure, we devise a shortcut-based algorithm to answer the shortest path query over time-dependent road networks. Finally, we conduct extensive performance studies using large-scale real-world road networks. The results demonstrate that our method can achieve better efficiency and scalability than the state-of-the-art method.

Flight planning, a pivotal challenge in the airline industry, strives to achieve economic and flexible scheduling of airplanes to serve designated flight itineraries. As the demand for air transportation soars, traditional planning methods can be inefficient in managing large-scale flights. Thus, we introduce Swift, a data-driven system tailored to enhance the scalability and effectiveness of flight planning. Swift primarily employs the bipartite graph model to derive optimal and economic flight plans for airlines. Our method not only minimizes the number of required planes but also ensures a balanced workload across these planes. Furthermore, Swift offers the capability of dynamic updates to flight plans in response to unexpected incidents at airports, such as bad weather conditions. Besides, Swift incorporates other functionalities like predicting future flight demand and monitoring real-time flight trajectories. Conference participants can interact with this system and explore our flight planning solution in real-world scenarios.

One of the most important challenges in shared mobility services ( e.g. , ride-sharing and parcel delivery) is planning routes for workers by considering real road conditions. To tackle this challenge, the "insertion operator", which computes the optimal route for the worker to serve ( i.e. , insert) the newly appeared delivery request, has been acted as the fundamental operation in existing solutions. However, existing works implicitly assume a static road network, hence are hard to fulfill the real-world scenario, where travel time between two locations is not constant at different times of a day. By contrast, we focus on the insertion operator over time-dependent road networks that capture the periodic pattern of road conditions. We also show that the time complexity of existing solutions would degrade into cubic time and hence such solutions can no longer satisfy the real-time requirement under this real-world setting. To satisfy the need for real-time computation, we propose a data summary to model the time-dependent travel time functions between pairs of vertices in the route. Based on the data summary, we design an efficient solution that can enumerate the best insertion position in linear time while satisfying complex spatiotemporal constraints. Finally, extensive experiments are conducted on real datasets from several applications of shared mobility. The results show that our solution is up to 44.5X faster than the state-of-the-art solution.

Vector databases have emerged as crucial tools for managing and retrieving representation embeddings of unstructured data. Given the explosive growth of data, vector data is often distributed and stored across multiple organizations. However, privacy concerns and regulations like GDPR present new challenges in collaborative and secure queries, also known as federated queries, over those vector data distributed across various data owners. Although existing research has attempted to enable such query services for low-dimensional data, such as relational and spatial data, these solutions can be inefficient in answering vector similarity queries involving high-dimensional data. Therefore, we are motivated to develop a new prototype system called FedSQ that (1) ensures privacy protection across data owners and (2) balances query efficiency and result accuracy when processing federated vector similarity queries. To achieve these goals, FedSQ utilizes advanced secure multi-party computation techniques to prevent information leakage during query processing and incorporates indexing and sampling based optimizations to strike a proper performance balance.

Data federation has emerged as a novel database system enabling collaborative queries across mutually distrusted data owners. Federated equi-join, a commonly used operation in data federation, combines relations from distinct data owners while preserving their data privacy. Due to the wide applications of this query, many solutions to federated equi-joins have been proposed. However, it is still challenging for practitioners to choose the most appropriate algorithm due to various reasons, including incomplete evaluation protocols (e.g., lack of evaluating multi-way equi-joins), under-explored performance metric (main memory usage), and absence of a standardized comparison. Motivated by this reason, this paper conducts a comprehensive experimental study and builds a new benchmark, called${\sf FEJ-Bench}$, for federated equi-joins. The experimental study and the benchmark consist of eight state-of-the-art algorithms and five datasets. Our evaluation reveals the query efficiency ranking, its impact factors, and potential research opportunities. Finally, we open-source${\sf FEJ-Bench}$on GitHub, which is the first benchmark for federated equi-joins. Our findings aim to guide researchers and practitioners in deploying federated equi-joins in practice.

Federated Trajectory Matching (FTM) is gaining increasing importance in big trajectory data analytics, supporting diverse applications such as public health, law enforcement, and emergency response. FTM retrieves trajectories that match with a query trajectory from a large-scale trajectory database, while safeguarding the privacy of trajectories in both the query and the database. A naive solution to FTM is to process the query through Secure Multi-party Computation (SMC) across the entire database, which is inherently secure yet inevitably slow due to the massive secure operations. A promising acceleration strategy is to filter irrelevant trajectories from the database based on the query, thus reducing the SMC operations. However, a key challenge is how to publish the query in a way that both preserves privacy and enables efficient trajectory filtering. In this paper, we design${\sf GIST}$, a novel framework for efficient Federated Trajectory Matching.${\sf GIST}$is grounded in Geo-Indistinguishability, a privacy criterion dedicated to locations. It employs a new privacy mechanism for the query that facilitates efficient trajectory filtering. We theoretically prove the privacy guarantee of the mechanism and the accuracy of the filtering strategy of${\sf GIST}$. Extensive evaluations on five real datasets show that${\sf GIST}$is significantly faster and incurs up to 2 orders of magnitude lower communication cost than the state-of-the-arts.

Online real estate platforms are gaining increasing popularity, where a central issue is to match brokers with clients for potential housing transactions. Mainstream platforms match brokers via top-k recommendation. Yet we observe through extensive data analysis that such top-k recommendation tends to overload the top brokers, which notably degrades their service quality. In this paper, we propose to avoid such overloading in broker matching via the paradigm shift from recommendation to assignment. To this end, we design learned assignment with contextual bandits (LACB), a data-driven capacity-aware assignment scheme for broker matching which estimates broker-specific workload capacity in an online fashion and assigns brokers to clients from a global perspective to maximize the overall service quality. Extensive evaluations on synthetic and real-world datasets from an industrial online real estate platform validate the efficiency and effectiveness of our solution.

Similarity search is getting increasingly useful in real applications. This paper focuses on the in-memory similarity search, i.e., the range query and k nearest neighbor (kNN) query, under arbitrary metric spaces, where the only known information is the distance function to measure the similarity between two objects. Although lots of research has studied this problem, the query efficiency of existing solutions is still unsatisfactory. To further improve the query efficiency, we are inspired by the tree embeddings, which map each object into a unique leaf of a well-structured tree solely based on the distances. Unlike existing embedding techniques (e.g., Lipschitz embeddings and pivot mapping) for similarity search, where an extra multi-dimensional index is needed to index the embedding space (e.g., Lp metrics), we directly use this tree to answer similarity search. This seems to be promising, but it is challenging to tailor tree embeddings for efficient similarity search. Specifically, we present a novel index called LiteHST, which is based on the most popular tree embedding (HST) and heavily customized for similarity search in the node structure and storage scheme. We propose a new construction algorithm with lower time complexity than existing methods and prove the optimality of LiteHST in the distance bound. Based on this new index, we also design optimization techniques that heavily reduce the number of distance computations and hence save running time. Finally, extensive experiments demonstrate that our solution outperforms the state-of-the-art in the query efficiency by a large margin.

Range aggregation is a primitive operation in spatial data applications and there is a growing demand to support such operations over a data federation, where the entire spatial data are separately held by multiple data providers (a.k.a., data silos). Data federations notably increase the amount of data available for data-intensive applications such as smart mobility planning and public health emergency responses. Yet they also challenge the conventional implementation of range aggregation queries because the raw data cannot be shared within the federation and the data partition at each data silo is fixed during query processing. These constraints limit the design space of distributed range aggregation query processing. In this work, we propose approximate algorithms for efficient range aggregation over spatial data federation. We devise novel single-silo sampling algorithms that process queries in parallel and design a level sampling based algorithm which reduces the time complexity of local queries at each data silo to O(log 1/), where is the approximation ratio of the accuracy guarantee. Extensive evaluations with real-world data show that compared with state-of-the-arts, our solutions reduce the time cost and communication cost by up to 85.1x and 5.5x respectively, with average approximate errors of below 2.8%.

Data federations notably increase the amount of data available for data-intensive applications such as smart mobility planning and public health emergency responses. Yet they also challenge the conventional implementation of range aggregation queries because the raw data cannot be shared within the federation and the data partition at each data silo is fixed during query processing. In this work, we propose the first-of-its-kind approximate algorithms for efficient range aggregation over spatial data federation. We devise novel single-silo sampling algorithms that process queries in parallel and design a level sampling based algorithm which reduces the time complexity of local queries at each data silo to$O(\log\frac{1}{\epsilon})$, where ∊ is the approximation ratio of the accuracy guarantee. Extensive experiments on real-world dataset validate the efficiency and effectiveness of the solutions.

Hierarchically Separated Tree (HST) is the most popular solution to embed a metric space into a tree metric. By using HSTs, many optimization problems, which are hard on defined metrics, become easier to get good approximation bounds with respect to the effectiveness, e.g., task assignment, trip planning, and facility location planning. Existing work focuses on constructing HSTs for arbitrary metric spaces, which makes a general-purpose algorithm take at least O(n2)-time to get tight distortion guarantees O(log(n)). Here, distortion is a prevalent measurement of HSTs' effectiveness and usability. However, we observe that (1) in many applications that HSTs are applied, only Lp metrics are used (e.g., Euclidean space), (2) the state-of-the-art solution is still time-consuming to construct HSTs for large-scale data, and (3) distortions of existing algorithms are only satisfactory for high-dimensional data. Thus, in this paper, we are motivated to study the Embedding Lp metrics through Tree metrics (ELT) problem. We aim to design a faster algorithm than O(n2) time to construct HSTs with not only O(log(n)) distortion guarantees but also good and robust empirical results. Specifically, we first present a divide-and-conquer based general framework and prove that it has a distortion guarantee of O(log(n)). To achieve a better time complexity than O(n2), we next design two optimization techniques: reducing to nearest neighbor search (by indexing) and sampling. Finally, extensive experiments demonstrate that our algorithm DCsam outperforms the state-of-the-art algorithms by a large margin in terms of both distortion and running time.

The increasing concerns on data security limit the sharing of data distributedly stored at multiple data owners and impede the scale of spatial queries over big urban data. In response, data federation systems have emerged to perform secure queries across multiple data owners leveraging secure multi-party computation. However, existing systems are designed for relational data. They are highly inefficient on spatial queries and limited in usability. In this demonstration, we introduce Hu-Fu, the first data federation system for secure spatial queries with high efficiency and usability. Hu-Fu is designed from the perspectives of the query user and the data owner for high usability and decomposes a spatial query into as many plaintext operators and as few secure operators as possible for high efficiency. We demonstrate the deployment and usage of Hu-Fu via cross-company taxi-calling, a popular smart city application.

Data isolation has become an obstacle to scale up query processing over big data, since sharing raw data among data owners is often prohibitive due to security concerns. A promising solution is to perform secure queries over a federation of multiple data owners leveraging secure multi-party computation (SMC) techniques, as evidenced by recent federation work over relational data. However, existing solutions are highly inefficient on spatial queries due to excessive secure distance operations for query processing and their usage of general-purpose SMC libraries for secure operation implementation. In this paper, we propose Hu-Fu, the first system for efficient and secure spatial query processing on a data federation. The idea is to decompose the secure processing of a spatial query into as many plaintext operations and as few secure operations as possible, where fewer secure operators are involved and all secure operators are implemented dedicatedly. As a working system, Hu-Fu supports not only query input in native SQL, but also heterogeneous spatial databases ( e.g. , PostGIS, Simba, GeoMesa, and SpatialHadoop) at the backend. Extensive experiments show that Hu-Fu usually outperforms the state-of-the-arts in running time and communication cost while guaranteeing security.

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 addition, previous route planning solutions fail to exploit the appearance patterns of future requests hidden in historical data for optimization. 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 propose two insertion-based frameworks to solve the URPSM problem. The first is built upon the plain-insertion widely used in prior studies, which processes online requests only, whereas the second relies on a new insertion operator called prophet-insertion that handles both online and predicted requests. Novel dynamic programming algorithms are designed to accelerate both insertions to only linear time. Theoretical analysis shows that no online algorithm can have a constant competitive ratio for the URPSM problem under the competitive analysis model, yet our prophet-insertion-based framework can achieve a constant optimality ratio under the instance-optimality model. Extensive experimental results on real datasets show that our insertion-based solutions outperform the state-of-the-art algorithms in both effectiveness and efficiency by a large margin (e.g., up to 30 \( \times \) more effective in the objective and up to 20 \( \times \) faster).

Metric embeddings have been widely used in approximate algorithms to guarantee the effectiveness of geometric problems. Among the metric embedding techniques, Hierarchically Separated Tree (HST) is one of the most prevalent data structures, which maps the points of the original metric space into a tree-based metric space. A few selected applications of the HST include clustering, task assignment, trip planning, privacy preservation, information routing in wireless sensor networks, etc. Despite the popularity in ensuring the effectiveness, the HST-based solutions can be inefficient in large-scale datasets, since the state-of-the-art construction method has high time and space complexity (O(n3) andO(n2) in the worst-case). Moreover, existing studies overlook the insertion of new points in real applications (deletions can be trivially supported), which can cause the reconstruction of the whole HST. To address these limitations, we focus on designing an efficient index for embedding arbitrary metric spaces by tree metric spaces. Specifically, for construction, we design a dynamic programming-based method, which significantly reduces the time and space complexity toO(n2) andO(n) respectively. For insertion of new points, we propose a new data structure, called Hierarchically Separated Forest (HSF),i.e., a collection of HSTs. An HSF can efficiently support insertion of new points with a tight theoretical guarantee (O(logn)). Finally, extensive experiments demonstrate the superior performance of our proposed algorithms with respect to the effectiveness and the running time. For instance, compared with the state-of-the-art algorithms, our construction method is up to 29.8× faster and our insertion method is up to 491× faster.

Spatial crowdsourcing has stimulated various new applications such as taxi calling and food delivery. A key enabler for these spatial crowdsourcing based applications is to plan routes for crowd workers to execute tasks given diverse requirements of workers and the spatial crowdsourcing platform. Despite extensive studies on task planning in spatial crowdsourcing, few have accounted for the location privacy of tasks, which may be misused by an untrustworthy platform. In this paper, we explore efficient task planning for workers while protecting the locations of tasks. Specifically, we define the Privacy-Preserving Task Planning (PPTP) problem, which aims at both total revenue maximization of the platform and differential privacy of task locations. We first apply the Laplacian mechanism to protect location privacy, and analyze its impact on the total revenue. Then we propose an effective and efficient task planning algorithm for the PPTP problem. Extensive experiments on both synthetic and real datasets validate the advantages of our algorithm in terms of total revenue and time cost.

With the rapid development of smartphones, spatial crowdsourcing platforms are getting popular. A foundational research of spatial crowdsourcing is to allocate micro-tasks to suitable crowd workers. Many existing studies focus on the offline scenario, where all the spatiotemporal information of micro-tasks and crowd workers is given. In this paper, we focus on the online scenario and identify a more practical micro-task allocation problem, called theGlobalOnlineMicro-taskAllocation in spatial crowdsourcing(GOMA) problem. We first extend the state-of-the-art algorithm for the online maximum weighted bipartite matching problem to the GOMA problem as the baseline algorithm. Although the baseline algorithm provides a theoretical guarantee for the worst case, its average performance in practice is not good enough since the worst case happens with a very low probability in the real world. Thus, we consider the average performance of online algorithms,a.k.a.random order model. We propose a two-phase-based framework, based on which we present the TGOA algorithm with a$\frac{1}{4}$-competitive ratio under the random order model. To improve its efficiency, we further design the TGOA-Greedy and TGOA-OP algorithm following this framework, which runs faster than the TGOA algorithm with a competitive ratio of$\frac{1}{8}$and$\frac{1}{4}$, respectively. We also revisit the average performance of Greedy, which has long been considered as the worst due to its unbounded competitive ratio in the worst case. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on synthetic and real datasets.

Ridesharing services have gained global popularity as a convenient, economic, and sustainable transportation mode in recent years. One fundamental challenge in these services is planning the shared-routes ( i.e. , sequences of origins and destinations) among the passengers for the vehicles, such that the platform's total revenue is maximized. Though many methods can solve this problem, their effectiveness is still far from optimal on either empirical study ( e.g. , over 31% lower total revenue than our approach) or theoretical study ( e.g. , arbitrarily bad or impractical theoretical guarantee). In this paper, we study the shared-route planning queries in ridesharing services and focus on designing efficient algorithms with good approximation guarantees. Particularly, our idea is to iteratively search the most profitable route among the unassigned requests for each vehicle, which is simpler than the existing methods. Unexpectedly, we prove this simple method has an approximation ratio of 0.5 to the optimal result. Moreover, we also design an index called additive tree to improve the efficiency and apply randomization to improve the approximation guarantee. Finally, experimental results on two real datasets demonstrate that our additive-tree-based approach outperforms the state-of-the-art algorithms by obtaining up to 31.4%--127.4% higher total revenue.

With the increasing awareness towards protecting environment, people are paying more attention to the electric vehicles (EVs). Accompanying the rapid growing number of EVs, challenges raise at the same time about how to place EV chargers (EVC), within a city, to satisfy multiple types of charging demand. To provide a better EVC station deployment plan to benefit the whole society, we propose a problem called Social-Aware Optimal Electric Vehicle Charger Deployment (SOCD) on road network. The SOCD problem is hard and different from existing work in three aspects, 1) we assume that the charging demand should be satisfied not only in urban areas but also in relatively rural areas; 2) our work is the first one that considers an EVC station should have multiple types of charging plugs, which is more reasonable in real world; 3) different from the regional deployment solutions in previous literature, our SOCD directly works on a real road network and EVC stations are placed at appropriate POIs laying on the road network. We show that the SOCD problem is NP-hard. To deal with the hardness, we design two heuristic algorithms whose efficiency and effectiveness can be experimentally demonstrated. Furthermore, we investigate the incremental case, that is, given an existing EVC station deployment plan and extra more budget, we need to decide where and how many to place more chargers. Finally, we conduct extensive experiments on real road network of Shanghai to demonstrate both effectiveness and efficiency of our algorithms.

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.

Recently, crowdsourcing has emerged as a new computing paradigm to solve problems that need human intrinsic, such as image annotation. However, there are two limitations in existing crowdsourcing platforms, i.e. non-transparent incentive mechanism and isolated profiles of workers, which harms the interests of both requesters and workers. Meanwhile, Blockchain technology introduces a solution to build a transparent, immutable data model in the Byzantine environment. Moreover, Blockchain systems (e.g. Ethereum) can also support the Tuning-complete script called smart contracts. Thus, we are motivated to use the feature of the transparent data model and smart contract in Blockchain to address the two limitations. Based on the proposed solutions, we have designed a Blockchain based framework which supports foundations of general crowdsourcing platforms. In addition, our framework also has following novel features: (1) it provides the transparent incentive mechanisms; (2) it supports a trusted worker's profile sharing in a cross-platform mode.

Last-mile delivery (LMD) refers to the movement of goods from transportation origins to the final destinations. It has widespread applications such as urban logistics, e-commerce, etc. One fundamental problem in last-mile delivery is route planning, which schedules multiple couriers' routes, i.e. , sequences of origins and destinations of the requests under certain optimization objectives. Prior studies usually designed heuristic solutions to two strongly NP-hard optimization objectives: minimizing the makespan ( i.e. , maximum travel time) of couriers and total latency ( i.e. , waiting time) of requesters. There is no algorithm with theoretical guarantees for either optimization objective in practical cases. In this paper, we propose a theoretically guaranteed solution framework for both objectives. It achieves both approximation ratios of 6ρ, where ρ is the approximation ratio of a core operation, called k LMD, which plans for one courier a route consisting of k requests. Leveraging a spatial index called hierarchically separated tree, we further design an efficient approximation algorithm for k LMD with ρ = O (log n ), where n is the number of requests. Experimental results show that our approach outperforms state-of-the-art methods by averagely 48.4%-96.0% and 49.7%-96.1% for both objectives. Especially in large-scale real datasets, our algorithm has 29.3x-108.9x shorter makespan and 20.2x-175.1x lower total latency than the state-of-the-art algorithms.

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.

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.