With the development of mobile computing and the wide spread of mobile devices, mobile social network applications have become increasingly prevalent across mobile users. These applications rely on various location based services 5 (LBS) to make use of users’ location information and thus can provide users personalized services. Without an adequate location privacy preserving mechanism, users may be hesitant to use these applications. Researchers have proposed a variety of location privacy preserving mechanisms (LPPM) which allow users to make use of the LBS with reduced location 10 information [1, 2, 3, 4]. These LPPMs provide different trade-offs between location privacy and LBS utility, offering alternatives to better meet individual requirements of different users. However the comparison between LPPMs can be tricky due to a lack of reasonable privacy benchmark for location information. For given datasets and 15 adversary assumptions, many early researches define user’s privacy [2] by the “’uncertainty” of the adversary, which tells the probability that the adversary will make a wrong estimate. Then “incorrectness”, which is a combination of uncertainty and “inaccuracy”, is introduced as a better definition of privacy [5], since privacy deals with not only the probability of an error, but also the 20 magnitude of this error. This notion of privacy is reasonable, however it is difficult to measure the error magnitude, since no distance metric can be used for all situations. For example, one may suggest using the Euclidean distance, and then he will find that with a same distance, the privacy that the real location and the estimated location belong to a same region, can be different with that 25 they belong to two different regions. In recent years, differential privacy [6] gains popularity since it abstracts from the side information of the adversary. In the context of location privacy, geo-indistinguishability is introduced and supposed to be “independent of the prior”.