Subspace k-anonymity algorithm for location-privacy preservation based on locality-sensitive hashing

Abstract

Existing location-privacy-preserving methods primarily focus on solving the problem of location-privacy preservation in the global space. This not only increases the response time of the location service, it also degrades the data quality. In this paper, a k-anonymity algorithm based on locality-sensitive hashing is proposed to solve the problem of location-privacy preservation in the subspace. In the proposed algorithm, higher efficiency and higher quality of service are achieved by applying a bottom-up grid-search method. Further, reasonable division is obtained based on locality-sensitive hashing by retaining position characteristics. The results of experiments conducted to evaluate the proposed algorithm indicate that the proposed algorithm provides a smaller anonymous spatial region, higher data quality, and lower time cost than methods with no subspace.

Keywords

Location-privacy preservation locality-sensitive hashing bottom-up grid search subspace k-anonymity

Get full access to this article

View all access options for this article.

References

Zhang

Choo

K.-K.R.

Liu

and Wang

, Enhancing privacy through uniform grid and caching in location-based services, Future Generation Computer Systems-the International Journal of Escience 86 (2018), 881–892.

Wang

Huang

and Cheng

, Messages in a concealed bottle: achieving query content privacy with accurate location-based services, IEEE Transactions on Vehicular Technology 67(2018), 7698–7711.

Dimitriou

and Al Ibrahim

, “I wasn’t there” Deniable, privacy-aware scheme for decentralized location-based services, Future Generation Computer Systems-the International Journal of Escience 86 (2018), 253–265.

Abul

and Bayrak

, From location to location pattern privacy in location-based services, Knowledge and Information Systems 56 (2018), 533–557.

Chen

and Chen

, LPPS: A distributed cache pushing based k-anonymity location privacy preserving scheme, Mobile Information Systems 2016 (2016), 1–16.

Jia

and Zhang

, Nonexposure accurate location k-anonymity algorithm in LBS, The Scientific World Journal 2014 (2014), 619357–619357.

Shin

K.G.

Chen

and Hu

, Privacy protection for users of location-based services, IEEE Wireless Communications 19 (2012), 30–39.

Jin

and Dai

, Leveraging spatial diversity for privacy-aware location-based services in mobile networks, IEEE Transactions on Information Forensics and Security 13 (2018), 1524–1534.

Sweeney

, K-anonymity: A model for protecting privacy, International Journal of Uncertainty Fuzziness and Knowledge-Based Systems 10 (2002), 557–570.

10.

Biswas

and Sairam

A.S.

, Modeling privacy approaches for location based services, Computer Networks 140 (2018), 1–14.

11.

Ghaffari

Ghadiri

Manshaei

M.H.

and Lahijani

M.S.

, P(4)QS: A peer-to-peer privacy preserving query service for location-based mobile applications, IEEE Transactions on Vehicular Technology 66 (2017), 9458–9469.

12.

Zhang

Tong

and Zhong

, On designing satisfaction-ratio-aware truthful incentive mechanisms for k-anonymity location privacy, IEEE Transactions on Information Forensics and Security 11 (2016), 2528–2541.

13.

Gorisse

Cord

and Precioso

, Locality-sensitive hashing for chi2 distance, IEEE Transactions on Pattern Analysis and Machine Intelligence 34 (2012), 402–409.

14.

Zhang

Chen

, Liu

Zhu

and Wu

, Location prediction based on transition probability matrices constructing from sequential rules for spatial-temporal k-anonymity dataset, Plos One 11(8), e0160629.

15.

Kim

J.S.

and Li

K.J.

, Location k-anonymity in indoor spaces, Geoinformatica 20 (2016), 415–451.

16.

Bhaladhare

P.R.

and Jinwala

D.C.

, Novel approaches for privacy preserving data mining in k-anonymity model, Journal of Information Science and Engineering 32 (2016), 63–78.

17.

Caballero-Gil

Molina-Gil

Hernandez-Serrano

Leon

and Soriano-Ibanez

, Providing k-anonymity and revocation in ubiquitous VANETs, Ad Hoc Networks 36 (2016), 482–494.

18.

Liu

C.G.

Liu

I.H.

Yao

W.S.

and Li

J.S.

, K-anonymity against neighborhood attacks in weighted social networks, Security and Communication Networks 8 (2015), 3864–3882.

19.

Nayahi

J.J.V.

and Kavitha

, An efficient clustering for anonymizing data and protecting sensitive labels, International Journal of Uncertainty Fuzziness and Knowledge-Based Systems 23 (2015), 685–714.

20.

Gkountouna

and Terrovitis

, Anonymizing collections of tree-structured data, IEEE Transactions on Knowledge and Data Engineering 27 (2015), 2034–2048.

21.

Wang

S.L.

Tsai

Y.C.

Kao

H.Y.

and Hong

T.P.

, On anonymizing transactions with sensitive items, Applied Intelligence 41 (2014), 1043–1058.

22.

Wang

L.E.

and Li

X.X.

, A clustering-based bipartite graph privacy-preserving approach for sharing high-dimensional data, International Journal of Software Engineering and Knowledge Engineering 24 (2014), 1091–1111.

23.

Fahad

Tari

Almalawi

Goscinski

Khalil

and Mahmood

, PPFSCADA: Privacy preserving framework for SCADA data publishing, Future Generation Computer Systems-the International Journal of Escience 37 (2014), 496–511.

24.

Loukides

Gkoulalas-Divanis

and Shao

, Efficient and flexible anonymization of transaction data, Knowledge and Information Systems 36 (2013), 153–210.

25.

Ghinita

Kalnis

and Tao

, Anonymous publication of sensitive transactional data, IEEE Transactions on Knowledge and Data Engineering 23 (2011), 161–174.

26.

Wang

and Lin

, MapReduce based personalized locality sensitive hashing for similarity joins on large scale data, Computational Intelligence and Neuroscience 2015 (2015), 217216–217216.

27.

Y.H.

T.H.

Zhong

S.M.

Cao

Wang

and Al-Dhelaan

, Improved locality-sensitive hashing method for the approximate nearest neighbor problem, Chinese Physics B 23 (2014), 217–225.

28.

and Zou

, An incremental community detection method for social tagging systems using locality-sensitive hashing, Neural Networks 58 (2014), 14–28.

29.

Zhang

Cui

Liu

and Zhang

, An adaptive mean shift clustering algorithm based on locality-sensitive hashing, Optik 123 (2012), 1891–1894.

30.

Chen

Horng

S.J.

and Huang

C.P.

, Locality sensitive hashing for sampling-based algorithms in association rule mining, Expert Systems with Applications 38 (2011), 12388–12397.

31.

Cao

Jiang

and Girke

, Accelerated similarity searching and clustering of large compound sets by geometric embedding and locality sensitive hashing, Bioinformatics 26 (2010), 953–959.

32.

Koga

Ishibashi

and Watanabe

, Fast agglomerative hierarchical clustering algorithm using locality-sensitive hashing, Knowledge and Information Systems 12 (2007), 25–53.

33.

Zamora

Mendoza

and Allende

, Hashing-based clustering in high dimensional data, Expert Systems with Applications 62 (2016), 202–211.

34.

Pan

and Manocha

, Fast probabilistic collision checking for sampling-based motion planning using locality-sensitive hashing, International Journal of Robotics Research 35 (2016), 1477–1496.

35.

Al-Qershi

O.M.

and Khoo

B.E.

, Copy-move forgery detection using on locality sensitive hashing and k-means clustering, In: Information science and applications (ICISA), Springer Singapore, 2016, pp. 663–672.

36.

Zhang

Zhu

and Zhang

, BitHash: An efficient bitwise locality sensitive hashing method with applications, Knowledge-Based Systems 97 (2016), 40–47.

37.

Zhu

Xiao

and Sun

, A multi-objective memetic algorithm based on locality-sensitive hashing for one-to-many-to-one dynamic pickup-and-delivery problem, Information Sciences 329 (2016), 73–89.

38.

Datar

Immorlica

Indyk

and Mirrokni

V.S.

, Locality-sensitive hashing scheme based on p-stable distributions, In: Twentieth Symposium on Computational Geometry, New York: ACM, 2004, pp. 253–262.

39.

Zheng

and Gao

, Efficient algorithms for k-anonymous location privacy in participatory sensing, In: IEEE INFOCOM, New York: IEEE, 2012, pp. 2399–2407.