Privacy preserving car-parking: adistributed approach

Abstract: There has been a substantial interest recently in privacy preserving problems in various application domains, including data publishing, data mining, classication, secret voting, private querying of database, playing mental poker, and many others. The main constraint is that entities involved in the system are unwilling to reveal the data they hold or make them public. However, they may want to collaborate and nd the solution of a bigger computational problem without revealing the privately held data. There are several approaches for addressing such issues, including cryptographic methods, transformation methods, and parallel and distributed computation techniques. In this thesis, these three methods are highlighted and a greater emphasis is placed on the last one. In particular, we discuss the theoretical backgrounds of optimization decomposition techniques. We further point out key literature associated with the privacy preserving problems and provide basic classications of their treatments. We focus to a particular interesting application, namely the car parking problem, or parking slot assignment problem. To solve the problem in a privacy preserving manner, a new parallel and distributed computation method is proposed. The goal is to allocate the parking slots to the cars, but without revealing anyone else the intended destinations. We apply decomposition techniques together with projected subgradient method to address this problem and the result is a decentralized privacy preserving car parking algorithm. We compare our algorithm with three other methods and numerically evaluate the performance of the proposed algorithm, in terms of optimality and as well as the computational speed. Despite the reduced computational complexity of the proposed algorithm, it provides close-to-optimal performance.