검색 상세

차분 프라이버시가 적용된 사용자 위치 기반의 최대 영향력 위치 선택 기법

The Most Influential Location Selection with Differentially Private User Locations

  • 박세화 (서강대학교 일반대학원)

초록/요약

During the past decades, it is possible to collect an individual location data due to the widespread use of mobile devices and social network services. The location based service providers have a great opportunity to provide more user friendly services through the data analysis. Especially, the optimal location selection queries have been of intense interest to the spatial database community. The location information of each client should be collected to process such a query. However, client location is considered sensitive information. Therefore, a privacy protection technique should be applied to optimal location selection problems. In this thesis, we propose a optimal location selection query-processing technique with differentially private client location information. Differential privacy is a de-facto standard privacy protection technique that applies a randomized mechanism to add controlled noise into statistical query results. Differential privacy has immunity from the linkage attack, while the existing techniques such as k-anonymity and l-diversity are vulnerable to it. Also, differential privacy can quantify the degree of privacy protection level using a privacy budget. Therefore, this study aims to propose an efficient optimal location selection query processing technique while protecting user's location with differentially private manner. Optimal location selection query is a traditional problem that identifies the most influential object in a given database which consists of potential objects $P$, existing facilities $F$, and client locations $C$. At this time, it is necessary to collect individual differentially private data, or to apply the differential privacy mechanism during the query processing of optimal location selection. In the former case, it is inevitable to decrease the query accuracy, so we propose a framework to apply a Laplace mechanism to an objective function of optimal location selection query. In addition, we present the influence region overlapping problem while applying differential privacy using the conventional approach. To remedy this problem, we propose a Voronoi region partitioning method to guarantee query accuracy. Furthermore, we present a network Voronoi region-based technique for the road network data. A Voronoi region partitioning method divides the Voronoi region of a potential location according to the combination of overlapping area, and it counts the number of clients in the partitioned region with differentially private manner. Then, it changes a sequential composition to a parallel composition while applying differential privacy to the optimal location selection query. Thus, it mitigates the degradation of accuracy due to the sequential composition. However, it needs more query processing time to compute the combination of overlapping area. In addition, we cannot exploit the existing pruning techniques because we cannot use the information of clients to prevent low accuracy problem. To address this issue, we propose a Voronoi envelope-based pruning heuristic to improve query performance. The Voronoi envelope-based pruning method which exploits existing facilities instead of the client's location. Also, we perform experiments of a real social network service and a real road network dataset to present that our proposed methods are enough to apply to real application services.

more

초록/요약

최근 모바일 환경의 보급과 기술 발전으로 인해 서비스 제공자가 사용자들의 위치 데이터를 직접 수집하고 분석하는 것이 가능해졌다. 그로 인해, 서비스 제공자들은 수집된 데이터를 이용해 사용자들에게 만족도 높은 서비스를 제공할 수 있게 되었다. 그 중에서도 최적장소 선택 질의(optimal location selection query)는 사용자들에게 영향을 가장 많이 끼칠 수 있는 최적장소를 찾아주는 질의로 상권 분석이나 공공기관 설치와 같은 실용적인 응용서비스에 적용될 수 있어 많은 연구자들의 관심이 집중되고 있다. 최적장소 선택 질의를 처리하기 위해서는 우선 개별 사용자들의 위치 정보를 수집해 분석해야 한다. 그러나 개인 위치 정보는 민감한 정보로 취급되기 때문에 무분별한 위치 정보 수집은 심각한 개인정보 노출 문제를 야기할 수 있다. 이와 같은 프라이버시 문제를 해결하기 위해서는 최적장소 선택 질의를 처리할 때 개인정보 보호 기법을 적용할 필요가 있다. 본 연구에서는 최적장소 선택 질의 중 가장 보편적인 최대 영향력 문제에 개인 위치정보를 보호하기 위한 차분 프라이버시(differential privacy)를 적용해 처리하는 방법에 대해 소개한다. 차분 프라이버시는 개인정보 보호기법 중 사실상의 표준으로 자리 잡고 있는 기술로서, 개별 사용자의 정보를 가린 채 전체 사용자 집단의 통계적인 정보를 제공할 수 있다는 장점을 지닌다. 특히, 다른 개인정보보호 기법들이 연결공격(linkage attack)에 취약한 반면, 차분 프라이버시는 연결공격으로부터 안전하다는 것이 기술적으로 증명되었다. 또한, k-익명화(k-anonymity), l-다양화(l-diversity)로 대표되는 개인정보보호 기법들이 데이터의 보호 정도와 유용성에 대한 정량화가 불가능했던 반면, 차분 프라이버시는 프라이버시 예산을 통해 질의 정확도와 개인정보 보호 정도에 대한 정량화가 가능하다는 장점도 지니고 있다. 그러나 차분 프라이버시를 적용할 경우 기존의 질의처리 기법을 그대로 사용하기 어렵다는 문제점이 있다. 따라서, 본 연구에서는 최대 영향력 위치 선택 과정 중에 차분 프라이버시를 적용해 사용자들의 위치정보를 보호하면서도 효율적으로 질의를 처리할 수 있는 방법을 제안하는 것을 목표로 한다. 최대 영향력 위치 선택 문제는 사용자들의 위치와 기존시설들의 집합이 주어진 상황에서 질의 요청자가 제시한 후보위치 집합 중 가장 적합한 위치를 찾는 질의를 말한다. 이 때, 사용자들의 개인정보를 보호하기 위해서는 처음부터 차분 프라이버시 기법이 적용된 개별 사용자의 정보를 수집하거나 질의처리 과정 중에 차분 프라이버시 매커니점을 적용해야 한다. 그러나 전자의 경우 질의 정확도가 매우 크게 하락하므로 본 연구에서는 질의처리 과정 중에 차분 프라이버시 기법을 적용한다. 또한, 차분 프라이버시 기법을 최대 영향력 문제에 단순하게 적용할 경우 후보위치들의 영향지역(influence region)이 중첩됨으로 인해 사용자 정보가 중복 노출되는 문제가 발생한다. 이런 문제를 해결하기 위해 보로노이 영역 분할 방법 기반의 빠르면서도 정확한 최적장소 질의처리를 수행하는 방법을 제안한다. 아울러 공간 데이터는 크게 유클리드 공간과 도로망 환경 데이터로 구분되므로 각각의 환경에 맞는 질의처리 방법을 제시한다. 보로노이 영역 분할 기법은 후보위치의 영향지역을 중첩 영역의 조합에 따라 분할하고, 분할된 영역마다의 사용자 수에 차분 프라이버시 기법을 적용한다. 이를 통해, 최대 영향력 위치 선택 문제에 차분 프라이버시를 적용할 때 발생하는 순차구성 문제(sequential composition)를 병렬구성(parallel composition)으로 변경함으로써 정확도를 향상시킬 수 있다. 그러나 이 과정에서 영역 조합을 구성하기 위해 필연적으로 질의처리 비용이 증가하게 되고, 순차구성으로 인한 정확도 하락을 방지하기 위해 질의처리 과정 동안 사용자 정보를 이용할 수 없기 때문에 기존의 사용자 정보 기반 가지치기 기법들을 사용할 수 없다. 본 연구에서는 사용자 정보 없이 질의처리 시간을 단축시키기 위해 공개 데이터인 기존시설 집합 기반의 확장 보로노이 영역을 새롭게 정의하고 이를 이용한 질의처리 기법을 제안한다. 아울러, 웹에 공개된 실제 소셜 네트워크 서비스 사용자들의 데이터와 도로망 데이터를 바탕으로 실험을 수행함으로써 제안 기법들이 실제 응용 서비스에 사용될 수 있는 수준의 정확도와 질의처리 시간을 지니고 있음을 보인다.

more
반출 Meta View 목록