Search

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., Comment: IEEE ICDE 2024

Recently, more and more higher education institutions have been using student feedback questionnaires (SFQ) to evaluate teaching. However, existing SFQ systems have two shortcomings. The first is that the respondent of an SFQ is not anonymous. The second is that the statistical report of SFQs can be manipulated. To tackle these two shortcomings, we develop a novel SFQ system, namely PSFQ. In PSFQ, the respondent of an SFQ is mixed with multiple users by a ring signature. PSFQ uses an advanced ring signature approach to minimize the size of a ring signature when anonymity satisfies the requirements. Thus, the first shortcoming has been overcome. Moreover, all answers are encrypted by homomorphic encryption and stored on the blockchain, enabling users to verify the correctness of the statistical reports. Our demonstration will showcase how PSFQ provides confidential SFQ responses while ensuring the correctness of statistical reports. © 2023, VLDB Endowment. All rights reserved.

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. PVLDB Reference Format: © 2023, VLDB Endowment. All rights reserved.

Over the past years, Machine Learning-as-a-Service (MLaaS) has received a surging demand for supporting Machine Learning-driven services to offer revolutionized user experience across diverse application areas. MLaaS provides inference service with low inference latency based on an ML model trained using a dataset collected from numerous individual data owners. Recently, for the sake of data owners' privacy and to comply with the "right to be forgotten (RTBF)" as enacted by data protection legislation, many machine unlearning methods have been proposed to remove data owners' data from trained models upon their unlearning requests. However, despite their promising efficiency, almost all existing machine unlearning methods handle unlearning requests independently from inference requests, which unfortunately introduces a new security issue of inference service obsolescence and a privacy vulnerability of undesirable exposure for machine unlearning in MLaaS. In this paper, we propose the ERASER framework for machinE unleaRning in MLaAS via an inferencE seRving-aware approach. ERASER strategically choose appropriate unlearning execution timing to address the inference service obsolescence issue. A novel inference consistency certification mechanism is proposed to avoid the violation of RTBF principle caused by postponed unlearning executions, thereby mitigating the undesirable exposure vulnerability. ERASER offers three groups of design choices to allow for tailor-made variants that best suit the specific environments and preferences of various MLaaS systems. Extensive empirical evaluations across various settings confirm ERASER's effectiveness, e.g., it can effectively save up to 99% of inference latency and 31% of computation overhead over the inference-oblivion baseline.

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. © 2022 IEEE.

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. © 2021 IEEE.

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. © 2021 ACM.

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. © 2021 ACM.

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. © 2021 IEEE.

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. © 2021 ACM.

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. © 2021 IEEE.

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. © 2020 IEEE.

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. © 2020 IEEE.

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. © 2020 IEEE.

By allowing users to obscure their transactions via including "mixins" (chaff coins), ring signature schemes have been widely used to protect a sender's identity of a transaction in privacy-preserving blockchain systems, like Monero and Bytecoin. However, recent works point out that the existing ring signature scheme is vulnerable to the "chain-reaction" analysis (i.e., the spent coin in a given ring signature can be deduced through elimination). Especially, when the diversity of mixins is low, the spent coin will have a high risk to be detected. To overcome the weakness, the ring signature should be consisted of a set of mixins with high diversity and produce observations having "similar" distributions for any two coins. In this paper, we propose a notion, namely $\epsilon$-coin-indistinguishability ($\epsilon$-CI), to formally define the "similar" distribution guaranteed through a differential privacy scheme. Then, we formally define the CI-aware mixins selection problem with disjoint-superset constraint (CIA-MS-DS), which aims to find a mixin set that has maximal diversity and satisfies the constraints of $\epsilon$-CI and the budget. In CIA-MS-DS, each ring signature is either disjoint with or the superset of its preceding ring signatures. We prove that CIA-MS-DS is NP-hard and thus intractable. To solve the CIA-MS-DS problem, we propose two approximation algorithms, namely the Progressive Algorithm and the Game Theoretic Algorithm, with theoretic guarantees. Through extensive experiments on both real data sets and synthetic data sets, we demonstrate the efficiency and the effectiveness of our approaches., Comment: 14 pages

Recently, transportation-as-a-service (TaaS) becomes an increasing trend, and online car-hailing companies start to apply Electric Vehicles (EV) to serve passengers. We make the market analysis which shows this is a good entrepreneurial opportunity. However, there are many different challenges compared with traditional vehicle hailing. For instance, since the charging time of EVs is long and non-negligible, it is necessary to smartly arrange the charging periods of EVs during the working schedule. Particularly, in order to maximize the number of accomplished tasks, online EV taxi platforms assign vehicles whose left electric power is enough to serve the dynamically arriving tasks, and schedule suitable idle vehicles to the limited charging stations to recharge. In this thesis technical part, we focus on solving this challenge. We formally define the power-aware electric vehicle hailing (PAEVH) problem to serve as many tasks as possible under the constraints of left power and deadline. However, we prove that the PAEVH problem is NP-hard, and thus intractable. We design a novel strategy to help arrange the schedules of EVs, and propose two approximate approaches with theoretical guarantees to adaptively determine the value of two major parameters of the strategy. Extensive experiments on real-world data sets validate the effectiveness and efficiency of our solutions. Finally, we decide our business strategy.