Bichromatic reverse nearest neighbor query without information leakage

Lu Wang, Xiaofeng Meng*, Haibo HU, Jianliang XU

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

3 Citations (Scopus)


Bichromatic Reverse Nearest Neighbor (BRNN) Query is an important query type in location-based services (LBS) and has many real life applications, such as site selection and resource allocation. However, such query requires the client to disclose sensitive location information to the LBS. The only existing method for privacy-preserving BRNN query adopts the cloaking-region paradigm, which blurs the location into a spatial region. However, the LBS can still deduce some information (albeit not exact) about the location. In this paper, we aim at strong privacy wherein the LBS learns nothing about the query location. To this end, we employ private information retrieval (PIR) technique, which accesses data pages anonymously from a database. Based on PIR, we propose a secure query processing framework together with various indexing and optimization techniques. To the best knowledge, this is the first research that preserves strong location privacy in BRNN query. Extensive experiments under real world and synthetic datasets demonstrate the practicality of our approach.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Proceedings Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part I
EditorsCyrus Shahabi, Muhammad Aamir Cheema, Matthias Renz, Xiaofang Zhou
PublisherSpringer Verlag
Number of pages16
ISBN (Print)9783319181196
Publication statusPublished - 2015
Event20th International Conference on Database Systems for Advanced Applications, DASFAA 2015 - Hanoi, Viet Nam
Duration: 20 Apr 201523 Apr 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Conference on Database Systems for Advanced Applications, DASFAA 2015
Country/TerritoryViet Nam

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Bichromatic RNN
  • Location privacy
  • Privacy preservation
  • Private information retrieval


Dive into the research topics of 'Bichromatic reverse nearest neighbor query without information leakage'. Together they form a unique fingerprint.

Cite this