AbstractKnowledge of patients’ location information (postal/zip codes) is critical in public health research. However, the inclusion of location information makes it easier to determine the identity of the individuals in the data sets. An efficient way to anonymize location information is through aggregation. In order to aggregate the locations efficiently, the data holder needs to know the locations’ adjacency information. A location adjacency matrix is big, and requires constant updates, thus it cannot be stored at the data holder's end. A possible solution would be to have the adjacency matrix stored on a cloud server, the data holder can then query the required adjacency records. However, queries reveal information on patients’ locations, thus, we need to privately query the cloud server's database. Existing private information retrieval protocols are inefficient for our context, therefore, in this paper, we present an efficient protocol to privately query the server's database for adjacency information and thus preserving patients’ privacy.