Article

Privacy-preserving mobility monitoring using sketches of stationary sensor readings

Authors:

Christine Kopp,

Michael MayAuthors Info & Claims

ECMLPKDD'13: Proceedings of the 2013th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part III

Pages 370 - 386

https://doi.org/10.1007/978-3-642-40994-3_24

Published: 23 September 2013 Publication History

Abstract

Two fundamental tasks of mobility modeling are (1) to track the number of distinct persons that are present at a location of interest and (2) to reconstruct flows of persons between two or more different locations. Stationary sensors, such as Bluetooth scanners, have been applied to both tasks with remarkable success. However, this approach has privacy problems. For instance, Bluetooth scanners store the MAC address of a device that can in principle be linked to a single person. Unique hashing of the address only partially solves the problem because such a pseudonym is still vulnerable to various linking attacks. In this paper we propose a solution to both tasks using an extension of linear counting sketches. The idea is to map several individuals to the same position in a sketch, while at the same time the inaccuracies introduced by this overloading are compensated by using several independent sketches. This idea provides, for the first time, a general set of primitives for privacy preserving mobility modeling from Bluetooth and similar address-based devices.

References

[1]

Aggarwal, C.C., Yu, P.S.: A general survey of privacy-preserving data mining models and algorithms. In: Privacy-Preserving Data Mining, pp. 11-52 (2008)

[2]

Ashok, K., Ben-Akiva, M.E.: Dynamic origin-destination matrix estimation and prediction for real-time traffic management systems. In: International Symposium on the Theory of Traffic Flow and Transportation (1993)

[3]

Barceló, J., Montero, L., Marquès, L., Carmona, C.: Travel time forecasting and dynamic origin-destination estimation for freeways based on bluetooth traffic monitoring. Transportation Research Record: Journal of the Transportation Research Board 2175(1), 19-27 (2010)

[4]

Bergamini, L., Becchetti, L., Vitaletti, A.: Privacy-preserving environment monitoring in networks of mobile devices. In: Casares-Giner, V., Manzoni, P., Pont, A. (eds.) NETWORKING 2011 Workshops. LNCS, vol. 6827, pp. 179-191. Springer, Heidelberg (2011)

[5]

Bianchi, G., Bracciale, L., Loreti, P.: "Better than nothing" privacy with bloom filters: To what extent? In: Domingo-Ferrer, J., Tinnirello, I. (eds.) PSD 2012. LNCS, vol. 7556, pp. 348-363. Springer, Heidelberg (2012)

[6]

Broder, A., Mitzenmacher, M.: Network applications of bloom filters: A survey. Internet Mathematics 1(4), 485-509 (2004)

[7]

Cormode, G., Garofalakis, M.: Sketching probabilistic data streams. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, pp. 281-292. ACM (2007)

[8]

Cormode, G., Datar, M., Indyk, P., Muthukrishnan, S.: Comparing data streams using hamming norms (how to zero in). IEEE Transactions on Knowledge and Data Engineering 15(3), 529-540 (2003)

[9]

Cormode, G., Muthukrishnan, S., Yi, K.: Algorithms for distributed functional monitoring. ACM Transactions on Algorithms (TALG) 7(2), 21 (2011)

[10]

Davies, A.C., Yin, J.H., Velastin, S.A.: Crowd monitoring using image processing. Electronics & Communication Engineering Journal 7(1), 37-47 (1995)

[11]

Dwork, C.: Differential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 1-12. Springer, Heidelberg (2006)

[12]

Friedman, A., Wolff, R., Schuster, A.: Providing k-anonymity in data mining. The VLDB Journal 17(4), 789-804 (2008)

[13]

Ganguly, S., Garofalakis, M., Rastogi, R.: Tracking set-expression cardinalities over continuous update streams. The VLDB Journal 13(4), 354-369 (2004)

[14]

Gibbons, P.B.: Distinct-values estimation over data streams. In: Data Stream Management: Processing High-Speed Data. Springer (2009)

[15]

Gonçalves, N., José, R., Baquero, C.: Privacy preserving gate counting with collaborative bluetooth scanners. In: Meersman, R., Dillon, T., Herrero, P. (eds.) OTM 2011 Workshops. LNCS, vol. 7046, pp. 534-543. Springer, Heidelberg (2011)

[16]

Heikkila, J., Silvén, O.: A real-time system for monitoring of cyclists and pedestrians. In: Second IEEE Workshop on Visual Surveillance (VS 1999), pp. 74-81. IEEE (1999)

[17]

Langheinrich, M.: Privacy by design - principles of privacy-aware ubiquitous systems. In: Abowd, G.D., Brumitt, B., Shafer, S. (eds.) UbiComp 2001. LNCS, vol. 2201, pp. 273-291. Springer, Heidelberg (2001)

[18]

Liebig, T., Xu, Z., May, M., Wrobel, S.: Pedestrian quantity estimation with trajectory patterns. In: Flach, P.A., De Bie, T., Cristianini, N. (eds.) ECML PKDD 2012, Part II. LNCS, vol. 7524, pp. 629-643. Springer, Heidelberg (2012)

[19]

Metwally, A., Agrawal, D., El Abbadi, A.: Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic. In: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, EDBT, pp. 618-629. ACM (2008)

[20]

Mir, D., Muthukrishnan, S., Nikolov, A., Wright, R.N.: Pan-private algorithms via statistics on sketches. In: Proceedings of the 30th Symposium on Principles of Database Systems of Data, pp. 37-48. ACM (2011)

[21]

Monreale, A.: Privacy by Design in Data Mining. PhD thesis, University Pisa (2011)

[22]

Preneel, B.: Analysis and design of cryptographic hash functions. PhD thesis, Katholieke Universiteit te Leuven (1993)

[23]

Rusu, F., Dobra, A.: Statistical analysis of sketch estimators. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, pp. 187-198. ACM (2007)

[24]

Self, S.G., Liang, K.Y.: Asymptotic properties of maximum likelihood estimators and likelihood ratio tests under nonstandard conditions. Journal of the American Statistical Association 82(398), 605-610 (1987)

[25]

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

[26]

Whang, K.Y., Vander-Zanden, B.T., Taylor, H.M.: A linear-time probabilistic counting algorithm for database applications. ACM Transactions on Database Systems (TODS) 15(2), 208-229 (1990)

Cited By

Stanciu VSteen MDobre CPeter ADing AMortier R(2021)Privacy-Preserving Crowd-Monitoring Using Bloom Filters and Homomorphic EncryptionProceedings of the 4th International Workshop on Edge Systems, Analytics and Networking10.1145/3434770.3459735(37-42)Online publication date: 26-Apr-2021
https://dl.acm.org/doi/10.1145/3434770.3459735
Ellersiek TAndrienko GAndrienko NHecker DStange HMueller M(2013)Using Bluetooth to track mobility patternsProceedings of the Fifth ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness10.1145/2533810.2533813(1-7)Online publication date: 5-Nov-2013
https://dl.acm.org/doi/10.1145/2533810.2533813

Recommendations

A Privacy-Preserving Location Monitoring System for Wireless Sensor Networks

Monitoring personal locations with a potentially untrusted server poses privacy threats to the monitored individuals. To this end, we propose a privacy-preserving location monitoring system for wireless sensor networks. In our system, we design two in-...
Privacy-Preserving Data Publishing: An Overview
Multi-level privacy preserving data publishing

Policedata is an important source of social media data and can be regarded as a technical assistance to increase government accountability and transparency. Notably, it contains large amounts of personal private information that should be preserved ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ECMLPKDD'13: Proceedings of the 2013th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part III

September 2013

685 pages

ISBN:9783642409936

Editors:
Hendrik Blockeel
Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium
,
Kristian Kersting
Fraunhofer IAIS, Department of Knowledge Discovery, Schloss Birlinghoven, University of Bonn, Sankt Augustin, Germany
,
Siegfried Nijssen
LIACS, Universiteit Leiden, Leiden, The Netherlands and KU Leuven, Department of Computer Science, Leuven, Belgium
,
Filip Železný
Department of Computer Science and Engineering, Czech Technical University, Prague 6, Czech Republic

Sponsors

XRCE: Xerox Research Centre Europe
Winton Capital Management: Winton Capital Management
Cisco Systems
Yahoo! Labs
CSKI: Czech Society for Cybernetics and Informatics

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 September 2013

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Stanciu VSteen MDobre CPeter ADing AMortier R(2021)Privacy-Preserving Crowd-Monitoring Using Bloom Filters and Homomorphic EncryptionProceedings of the 4th International Workshop on Edge Systems, Analytics and Networking10.1145/3434770.3459735(37-42)Online publication date: 26-Apr-2021
https://dl.acm.org/doi/10.1145/3434770.3459735
Ellersiek TAndrienko GAndrienko NHecker DStange HMueller M(2013)Using Bluetooth to track mobility patternsProceedings of the Fifth ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness10.1145/2533810.2533813(1-7)Online publication date: 5-Nov-2013
https://dl.acm.org/doi/10.1145/2533810.2533813

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents