skip to main content
10.1145/1739041.1739100acmotherconferencesArticle/Chapter ViewAbstractPublication PagesedbtConference Proceedingsconference-collections
research-article

Privacy preserving group nearest neighbor queries

Published: 22 March 2010 Publication History

Abstract

User privacy in location-based services has attracted great interest in the research community. We introduce a novel framework based on a decentralized architecture for privacy preserving group nearest neighbor queries. A group nearest neighbor (GNN) query returns the location of a meeting place that minimizes the aggregate distance from a spread out group of users; for example, a group of users can ask for a restaurant that minimizes the total travel distance from them. We identify the challenges in preserving user privacy for GNN queries and provide a comprehensive solution to this problem. In our approach, users provide their locations as regions instead of exact points to a location service provider (LSP) to preserve their privacy. The LSP returns a set of candidate answers that includes the actual group nearest neighbor. We develop a private filter that determines the actual group nearest neighbor from the retrieved candidate answers without revealing user locations to any involved party, including the LSP. We also propose an efficient algorithm to evaluate GNN queries with respect to the provided set of regions (the users' imprecise locations). An extensive experimental study shows the effectiveness of our proposed technique.

References

[1]
Location-based mobile social networking. http://www.abiresearch.com/research/1001722-Location-Based+Mobile+Social+Networking, 2008.
[2]
Loopt. http://www.loopt.com, 2008.
[3]
Privacy concerns a major roadblock for location-based services says survey. http://www.govtech.com/gt/articles/104064, 2007.
[4]
N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. SIGMOD Rec., 19(2):322--331, 1990.
[5]
C. Bettini, S. Mascetti, X. S. Wang, and S. Jajodia. Anonymity in location-based services: Towards a general framework. In MDM, pages 69--76, 2007.
[6]
D. Bickson, D. Dolev, G. Bezman, and B. Pinkas. Peer-to-peer secure multi-party numerical computation. IEEE P2P, 0:257--266, 2008.
[7]
C.-Y. Chow, M. F. Mokbel, and X. Liu. A peer-to-peer spatial cloaking algorithm for anonymous location-based services. In ACMGIS, pages 171--178, 2006.
[8]
B. Gedik and L. Liu. Protecting location privacy with personalized k-anonymity: Architecture and algorithms. IEEE TMC, 7(1):1--18, 2008.
[9]
G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi, and K.-L. Tan. Private queries in location based services: anonymizers are not necessary. In SIGMOD, pages 121--132, 2008.
[10]
G. Ghinita, P. Kalnis, and S. Skiadopoulos. Mobihide: A mobile peer-to-peer system for anonymous location-based queries. In SSTD, pages 221--238, 2007.
[11]
G. Ghinita, P. Kalnis, and S. Skiadopoulos. Privé: Anonymous location-based queries in distributed mobile systems. In WWW, pages 371--389, 2007.
[12]
M. Gruteser and D. Grunwald. Anonymous usage of location-based services through spatial and temporal cloaking. In MobiSys, pages 31--42, 2003.
[13]
A. Guttman. R-trees: a dynamic index structure for spatial searching. In SIGMOD, pages 47--57, 1984.
[14]
T. Hashem and L. Kulik. Safeguarding location privacy in wireless ad-hoc networks. In Ubicomp, pages 372--390, 2007.
[15]
G. R. Hjaltason and H. Samet. Ranking in spatial databases. In SSD, pages 83--95, 1995.
[16]
H. Hu and J. Xu. Non-exposure location anonymity. In ICDE, pages 1120--1131, 2009.
[17]
A. Khoshgozaran and C. Shahabi. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In SSTD, pages 239--257, 2007.
[18]
H. Li, H. Lu, B. Huang, and Z. Huang. Two ellipse-based pruning methods for group nearest neighbor queries. In GIS, pages 192--199, 2005.
[19]
M. F. Mokbel, C.-Y. Chow, and W. G. Aref. The new casper: query processing for location services without compromising privacy. In VLDB, pages 763--774, 2006.
[20]
R. Muntz, T. Barclay, J. Dozier, C. Faloutsos, A. Maceachren, J. Martin, C. Pancake, and M. Satyanarayanan. IT Roadmap to a Geospatial Future. The National Academies Press, 2003.
[21]
S. Namnandorj, H. Chen, K. Furuse, and N. Ohbo. Efficient bounds in finding aggregate nearest neighbors. In DEXA, pages 693--700, 2008.
[22]
D. Papadias, Q. Shen, Y. Tao, and K. Mouratidis. Group nearest neighbor queries. In ICDE, page 301, 2004.
[23]
D. Papadias, Y. Tao, K. Mouratidis, and C. K. Hui. Aggregate nearest neighbor queries in spatial databases. TODS, 30(2):529--576, 2005.
[24]
N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In SIGMOD, pages 71--79, 1995.
[25]
M. Strassman and C. Collier. Case study: The development of the find friends application. In Location-Based Services, pages 27--40. 2004.
[26]
K. F. Yanmin Luo, Hanxiong Chen and N. Ohbo. Efficient methods in finding aggregate nearest neighbor by projection-based filtering. In ICCSA, pages 821--833, 2007.
[27]
M. L. Yiu, C. S. Jensen, X. Huang, and H. Lu. Spacetwist: Managing the trade-offs among location privacy, query performance, and query accuracy in mobile services. In ICDE, pages 366--375, 2008.

Cited By

View all
  • (2024)A review of graph neural networks: concepts, architectures, techniques, challenges, datasets, applications, and future directionsJournal of Big Data10.1186/s40537-023-00876-411:1Online publication date: 16-Jan-2024
  • (2024)A Lightweight WiFi Fingerprint Indoor Localization Privacy Protection Scheme Based on Group Anonymity2024 4th International Conference on Computer Science and Blockchain (CCSB)10.1109/CCSB63463.2024.10735613(613-617)Online publication date: 6-Sep-2024
  • (2024)Blockchain-Based Multi-factor K-Anonymity Group Location Privacy Protection SchemeComputer Supported Cooperative Work and Social Computing10.1007/978-981-99-9640-7_3(34-47)Online publication date: 5-Jan-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
EDBT '10: Proceedings of the 13th International Conference on Extending Database Technology
March 2010
741 pages
ISBN:9781605589459
DOI:10.1145/1739041
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 March 2010

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. group nearest neighbor queries
  2. location
  3. privacy
  4. private filter

Qualifiers

  • Research-article

Conference

EDBT/ICDT '10
EDBT/ICDT '10: EDBT/ICDT '10 joint conference
March 22 - 26, 2010
Lausanne, Switzerland

Acceptance Rates

Overall Acceptance Rate 7 of 10 submissions, 70%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)13
  • Downloads (Last 6 weeks)2
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)A review of graph neural networks: concepts, architectures, techniques, challenges, datasets, applications, and future directionsJournal of Big Data10.1186/s40537-023-00876-411:1Online publication date: 16-Jan-2024
  • (2024)A Lightweight WiFi Fingerprint Indoor Localization Privacy Protection Scheme Based on Group Anonymity2024 4th International Conference on Computer Science and Blockchain (CCSB)10.1109/CCSB63463.2024.10735613(613-617)Online publication date: 6-Sep-2024
  • (2024)Blockchain-Based Multi-factor K-Anonymity Group Location Privacy Protection SchemeComputer Supported Cooperative Work and Social Computing10.1007/978-981-99-9640-7_3(34-47)Online publication date: 5-Jan-2024
  • (2023)A Framework of Vehicle Usage Optimization for Tour PurposesApplied Sciences10.3390/app13191097313:19(10973)Online publication date: 5-Oct-2023
  • (2022)EPGQ: Efficient and Private Feature-Based Group Nearest Neighbor Query Over Road NetworksIEEE Internet of Things Journal10.1109/JIOT.2022.31774749:20(20492-20502)Online publication date: 15-Oct-2022
  • (2022)PPAQ: Privacy-Preserving Aggregate Queries for Optimal Location Selection in Road NetworksIEEE Internet of Things Journal10.1109/JIOT.2022.31741849:20(20178-20188)Online publication date: 15-Oct-2022
  • (2022)Location-based Alert System Using Searchable Encryption with Hilbert Curve Encoding2022 IEEE International Conference on Big Data (Big Data)10.1109/BigData55660.2022.10020428(1445-1454)Online publication date: 17-Dec-2022
  • (2021)Secure and Practical Group Nearest Neighbor Query for Location-Based Services in Cloud ComputingSecurity and Communication Networks10.1155/2021/56865062021Online publication date: 25-Sep-2021
  • (2021)Cohesive Group Nearest Neighbor Queries on Road-Social Networks under Multi-CriteriaIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.297494333:11(3520-3536)Online publication date: 1-Nov-2021
  • (2021)PGRide: Privacy-Preserving Group Ridesharing Matching in Online Ride Hailing ServicesIEEE Internet of Things Journal10.1109/JIOT.2020.30302748:7(5722-5735)Online publication date: 1-Apr-2021
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media