도로 네트워크 환경에서 암호화된 공간데이터를 위한 K-최근접점 질의 처리 알고리즘 = A K-Nearest Neighbour Query Processing Algorithm for Encrypted Spatial Data in Road Network

다국어 초록 (Multilingual Abstract)

Due to the recent advancement of cloud computing, the research on database outsourcing has been actively done. Moreover, the number of users who utilize Location-based Services(LBS) has been increasing with the development in wireless communication technology and mobile devices. Therefore, LBS providers attempt to outsource their spatial database to service provider, in order to reduce costs for data storage and management. However, because unauthorized access to sensitive data is possible in spatial database outsourcing, it is necessary to study on the preservation of a user’s privacy. Thus, we, in this paper, propose a spatial data encryption scheme to produce outsourced database from an original database. We also propose a k-Nearest Neighbor(k-NN) query processing algorithm that efficiently performs k-NN by using the outsourced database. Finally, we show from performance analysis that our algorithm outperforms the existing one.

국문 초록 (Abstract)

최근 클라우드 컴퓨팅의 발전에 따라, 데이터베이스 아웃소싱(Outsourcing)에 대한 연구가 활발히 진행되고 있다. 또한 무선 통신 기술 및 모바일 기기의 발전으로 인해 위치 기반 서비스를 이용하는 사용자의 수가 증가하였다. 따라서 개인 또는 소규모의 사업자는 데이터 저장 및 관리 비용을 줄이기 위해 그들의 공간 데이터를 위치 기반 서비스 제공자에게 아웃소싱 한다. 그러나 사용자의 위치 정보는 시간대별 방문 장소 및 개인 정보를 지니고 있기 때문에, 이에 대한 허용되지 않은 접근 시 개인 정보 유출 문제가 발생한다. 따라서 위치 정보 아웃소싱을 위한 개인 정보 보호 연구가 필요하다. 이러한 문제를 해결하기 위해, 본 논문에서는 아웃소싱 환경에서 도로네트워크를 고려한 암호화된 공간 데이터베이스 기반 k-최근접점 질의 처리 알고리즘을 제안하였다. 제안하는 기법은 데이터베이스 아웃소싱을 위해 위치 데이터를 네트워크 거리 정보로 변환 및 암호화한 가공데이터를 생성하여 이를 서비스 제공자에게 전송한다. 또한, 전처리 과정을 통해 네트워크 노드와 POI 거리를 미리 저장하여 네트워크 탐색을 빠르게 수행하며, 질의 수행 시 최근접 대표 POI 및 암호화된 거리 정보를 이용하여 질의 결과 후보 집합을 탐색한다. 마지막으로, 질의 영역 재설정 과정을 통해 불필요한 후보 탐색을 줄임으로써 효율적으로 POI를 탐색한다. 마지막으로, 성능평가를 통해 제안하는 기법이 기존 방법에 비해 우수함을 보인다.

참고문헌 (Reference)

1 김용기, "공간 네트워크 데이터베이스에서 공간 제약을 고려한 경로 내 최근접 질의처리 알고리즘" 한국공간정보시스템학회 10 (10): 19-30, 2008

2 김용기, "공간 네트워크 데이터베이스에서 POI 기반 실체화 기법을 이용한 Closest Pairs 및 e-distance 조인 질의처리 알고리즘" 한국공간정보시스템학회 9 (9): 67-80, 2007

3 D. Sacharidis, "k-Anonymity in the Presence of ExternalDatabases" 22 (22): 392-403, 2010

4 Y. Yang, "Spatial Outsourcing for Location-based Services" 1082-1091, 2008

5 Wong, W. K, "Secure k-NN computation on encrypted databases" 139-152, 2009

6 National Institute of Standards and Technology, "Secure Hashing"

7 L. Qiu, "Protecting business intelligence and customer privacy while outsourcing data mining tasks" 1 : 99-120, 2008

8 A. Khoshgozaran, "Private Buddy Search: Enabling Private Spatial Queries in Social Networks" 04 : 166-173, 2009

9 T. Wang, "Privacy-Aware Mobile Services over Road Networks" 2 (2): 1042-1053, 2009

10 M. L. Yiu, "Outsourcing of Private Spatial Data for Search Services" 1140-1143, 2009

11 M. L. Yiu, "Outsourced Similarity Search on MetricData Assets" 24 (24): 338-352, 2012

12 R. Agrawal, "Order-Preserving Encryption forNumeric Data" 563-574, 2004

13 X. Jiang, "Multiple sensitive association protection in theoutsourced database" 2 : 123-137, 2010

14 P. Ciaccia, "M-tree: An Efficient Access Method for Similarity Search in Metric Spaces" 426-435, 1997

15 M. L. Yiu, "Enabling Search Services on Outsourced Private Spatial Data" 19 (19): 363-384, 2010

16 A. Khoshgozaran, "Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy" 239-257, 2007

17 T. Brinkhoff, "A Framework for Generating Network-Based Moving Objects" 6 (6): 153-180, 2002