Microaggregation for Database and Location Privacy | SpringerLink
Skip to main content
Springer Nature Link
Log in

Microaggregation for Database and Location Privacy

  • Conference paper
Next Generation Information Technologies and Systems (NGITS 2006)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 4032))

Abstract

Data aggregation is a central principle underlying many applications in computer science, from artificial intelligence to data security and privacy. Microaggregation is a special clustering problem where the goal is to cluster a set of points into groups of at least k points in such a way that groups are as homogeneous as possible. A usual homogeneity criterion is the minimization of the within-groups sum of squares. Microaggregation appeared in connection with anonymization of statistical databases. When discussing microaggregation for information systems, points are database records. This paper extends the use of microaggregation for k-anonymity to implement the recent property of p-sensitive k-anonymity in a more unified and less disruptive way. Then location privacy is investigated: two enhanced protocols based on a trusted-third party (TTP) are proposed and thereafter microaggregation is used to design a new TTP-free protocol for location privacy.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Dalenius, T.: Finding a needle in a haystack - or identifying anonymous census records. Journal of Official Statistics 2(3), 329–336 (1986)

    Google Scholar 

  2. Defays, D., Anwar, N.: Micro-aggregation: a generic method. In: Proceedings of the 2nd International Symposium on Statistical Confidentiality, Luxemburg, Eurostat, pp. 69–78 (1995)

    Google Scholar 

  3. Defays, D., Nanopoulos, P.: Panels of enterprises and confidentiality: the small aggregates method. In: Proc. of 1992 Symposium on Design and Analysis of Longitudinal Surveys, Statistics Canada, Ottawa, pp. 195–204 (1993)

    Google Scholar 

  4. Domingo-Ferrer, J., Mateo-Sanz, J.M.: Practical data-oriented microaggregation for statistical disclosure control. IEEE Transactions on Knowledge and Data Engineering 14(1), 189–201 (2002)

    Article  Google Scholar 

  5. Domingo-Ferrer, J., Mateo-Sanz, J.M., Oganian, A., Torres, À.: On the security of microaggregation with individual ranking: analytical attacks. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10(5), 477–492 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  6. Domingo-Ferrer, J., Sebé, F., Solanas, A.: A polynomial-time approximation to optimal multivariate microaggregation (manuscript, 2005)

    Google Scholar 

  7. Domingo-Ferrer, J., Torra, V.: A quantitative comparison of disclosure control methods for microdata. In: Doyle, P., Lane, J.I., Theeuwes, J.J.M., Zayatz, L. (eds.) Confidentiality, Disclosure and Data Access: Theory and Practical Applications for Statistical Agencies, pp. 111–134. North-Holland, Amsterdam (2001), http://vneumann.etse.urv.es/publications/bcpi

    Google Scholar 

  8. Domingo-Ferrer, J., Torra, V.: Ordinal, continuous and heterogenerous k-anonymity through microaggregation. Data Mining and Knowledge Discovery 11(2), 195–212 (2005)

    Article  MathSciNet  Google Scholar 

  9. Edwards, A.W.F., Cavalli-Sforza, L.L.: A method for cluster analysis. Biometrics 21, 362–375 (1965)

    Article  Google Scholar 

  10. Gedik, B., Liu, L.: A customizable k-anonymity model for protecting location privacy. In: Proceedings of the International Conference on Distributed Computing Systems-ICDCS (2005)

    Google Scholar 

  11. Gordon, A.D., Henderson, J.T.: An algorithm for euclidean sum of squares classification. Biometrics 33, 355–362 (1977)

    Article  MATH  Google Scholar 

  12. Hansen, P., Jaumard, B., Mladenovic, N.: Minimum sum of squares clustering in a low dimensional space. Journal of Classification 15, 37–55 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  13. Hansen, S.L., Mukherjee, S.: A polynomial algorithm for optimal univariate microaggregation. IEEE Transactions on Knowledge and Data Engineering 15(4), 1043–1044 (2003)

    Article  Google Scholar 

  14. Hundepool, A., Van de Wetering, A., Ramaswamy, R., Franconi, L., Capobianchi, A., DeWolf, P.-P., Domingo-Ferrer, J., Torra, V., Brand, R., Giessing, S.: μ-ARGUS version 4.0 Software and User’s Manual. Statistics Netherlands, Voorburg NL (May 2005), http://neon.vb.cbs.nl/casc

  15. Laszlo, M., Mukherjee, S.: Minimum spanning tree partitioning algorithm for microaggregation. IEEE Transactions on Knowledge and Data Engineering 17(7), 902–911 (2005)

    Article  Google Scholar 

  16. Lenz, R., Vorgrimler, D.: Matching german turnover tax statistics. Technical Report FDZ-Arbeitspapier Nr. 4, Statistische Ämter des Bundes und der Länder-Forschungsdatenzentren (2005)

    Google Scholar 

  17. http://www.locatrix.com

  18. http://www.mapinfo.com

  19. Mokbel, M.F.: Towards privacy-aware location-based database servers. In: Proceedings of the Second International Workshop on Privacy Data Management-PDM 2006, Atlanta, GA. IEEE Computer Society Press, Los Alamitos (2006)

    Google Scholar 

  20. Oganian, A., Domingo-Ferrer, J.: On the complexity of optimal microaggregation for statistical disclosure control. Statistical Journal of the United Nations Economic Comission for Europe 18(4), 345–354 (2001)

    Google Scholar 

  21. Pagliuca, D., Seri, G.: Some results of individual ranking method on the system of enterprise accounts annual survey. Esprit SDC Project, Deliverable MI-3/D2 (1999)

    Google Scholar 

  22. Rosemann, M.: Erste Ergebnisse von vergleichenden Untersuchungen mit anonymisierten und nicht anonymisierten Einzeldaten am Beispiel der Kostenstrukturerhebung und der Umsatzsteuerstatistik. In: Ronning, G., Gnoss, R. (eds.) Anonymisierung wirtschaftsstatistischer Einzeldaten, Wiesbaden, Germany, pp. 154–183. Statistisches Bundesamt (2003)

    Google Scholar 

  23. Samarati, P.: Protecting respondents’ identities in microdata release. IEEE Transactions on Knowledge and Data Engineering 13(6), 1010–1027 (2001)

    Article  Google Scholar 

  24. Samarati, P., Sweeney, L.: Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. Technical report, SRI International (1998)

    Google Scholar 

  25. Sande, G.: Exact and approximate methods for data directed microaggregation in one or more dimensions. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10(5), 459–476 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  26. Sweeney, L.: Achieving k-anonymity privacy protection using generalization and suppression. International Journal of Uncertainty, Fuzziness and Knowledge Based Systems 10(5), 571–588 (2002)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  28. http://www.targusinfo.com

  29. http://www.telostar.com

  30. Torra, V.: Microaggregation for Categorical Variables: A Median Based Approach. In: Domingo-Ferrer, J., Torra, V. (eds.) PSD 2004. LNCS, vol. 3050, pp. 162–174. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  31. Truta, T.M., Vinay, B.: Privacy protection: p-sensitive k-anonymity property (manuscript, 2005)

    Google Scholar 

  32. UNECE. United nations economic commission for europe. questionnaire on disclosure and confidentiality - summary of replies. In: 1st Joint UNECE/Eurostat Work Session on Statistical Data Confidentiality, Thessaloniki, Greece (1999)

    Google Scholar 

  33. UNECE. United nations economic commission for europe. questionnaire on disclosure and confidentiality - summary of replies. In: 2nd Joint UNECE/Eurostat Work Session on Statistical Data Confidentiality, Skopje, Macedonia (2001)

    Google Scholar 

  34. Ward, J.H.: Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association 58, 236–244 (1963)

    Article  MathSciNet  Google Scholar 

  35. Warrior, J., McHenry, E., McGee, K.: They know where you are. IEEE Spectrum 40(7), 20–25 (2003)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Engineering and Maths, Rovira i Virgili University of Tarragona, Av. Països Catalans 26, E-43007, Tarragona, Catalonia

    Josep Domingo-Ferrer

Authors
  1. Josep Domingo-Ferrer
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. IBM Haifa Research Lab, 31905, Mount Carmel, Haifa, Israel

    Opher Etzion

  2. University of Haifa, Haifa, Israel

    Tsvi Kuflik

  3. Information and Software Engineering Department, George Mason University, VA 22030, Fairfax, USA

    Amihai Motro

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Domingo-Ferrer, J. (2006). Microaggregation for Database and Location Privacy. In: Etzion, O., Kuflik, T., Motro, A. (eds) Next Generation Information Technologies and Systems. NGITS 2006. Lecture Notes in Computer Science, vol 4032. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11780991_10

Download citation

  • DOI: https://doi.org/10.1007/11780991_10

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-35472-7

  • Online ISBN: 978-3-540-35473-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation