Privacy-Preserving Bin-Packing With Differential Privacy

Abstract

With the emerging of e-commerce, package theft is at a high level: It is reported that 1.7 million packages are stolen or lost every day in the U.S. in 2020, which costs $25 million every day for the lost packages and the service. Information leakage during transportation is an important reason for theft since thieves can identify which truck is the target that contains the valuable products. In this paper, we address the privacy and security issues in bin-packing, which is an algorithm used in delivery centers to determine which packages should be loaded together to a certain truck. Data such as the weight of the packages is needed when assigning items into trucks, which can be called bins. However, the information is sensitive and can be used to identify the contents in the package. To provide security and privacy during bin-packing, we propose two different privacy-preserving data publishing methods. Both approaches use differential privacy (DP) to hide the existence of any specific package to prevent it from being identified by malicious users. The first approach combines differential privacy with k-anonymity, and the other one applies clustering before differential privacy. Our extensive analyses and experimental results clearly show that our proposed approaches have better privacy guarantees, better efficiency, and better performance than the existing works that use either differential privacy or k-anonymity.