위치 기반 서비스에서 K-anonymity를 보장하는 가중치 근접성 그래프 기반 최근접 질의처리 알고리즘

장미영,장재우 대한공간정보학회 2012 Spatial Information Research Vol.20 No.4

Location-based services (LBS) are increasingly popular due to the improvement of geo-positioning capabilities and wireless communication technology. However, in order to enjoy LBS services, a user requesting a query must send his/her exact location to the LBS provider. Therefore, it is a key challenge to preserve user’s privacy while providing LBS. To solve this problem, the existing method employs a 2PASS cloaking framework that not only hides the actual user location but also reduces bandwidth consumption. However, 2PASS does not fully guarantee the actual user privacy because it does not take the real user distribution into account. Hence, in this paper, we propose a nearest neighbor query processing algorithm that supports K-anonymity property based on the weighted adjacency graph(WAG). Our algorithm not only preserves the location of a user by guaranteeing k-anonymity in a query region, but also improves a bandwidth usage by reducing unnecessary search for a query result. We demonstrate from experimental results that our algorithm outperforms the existing one in terms of query processing time and bandwidth usage. 무선 통신 기술 및 GPS(Global Positioning System)등의 발달로 인하여 위치 기반 서비스 (Location-Based Services: LBS)가 크게 발전하는 추세이다. 그러나 위치 기반 서비스를 이용하기 위해 질의 요청자는 자신의 정확한 위치 정보를 위치 기반 서비스 제공자에게 전송해야 한다. 따라서 위치 기반 서비스를 제공하면서 질의 요청자의 위치 정보를 보호하는 것이 중요한 과제이다. 이 문제를 해결하기 위해, 기존 기법은 실제 사용자의 위치를 숨기며 네트워크 사용을 줄일 수 있는 2PASS 기법을 사용하였다. 그러나 이 기법은 실제 사용자 분포를 고려하지 않기 때문에 실제 사용자 위치 보호를 완전히 보장하지 않는다. 따라서 본 논문에서는 K-anonymity를 보장하는 가중치 근접성 그래프 기반 최근접 질의처리 알고리즘을 제안한다. 제안하는 알고리즘은 질의 영역 내 K-anonymity를 보장함으로써 사용자의 위치 정보를 보호할 뿐만 아니라 불필요한 질의 결과 탐색을 줄여 네트워크 효율을 증가시킨다. 마지막으로, 성능평가를 통해 제안하는 기법이 기존 연구에 비해 질의 처리 시간 및 네트워크 효율 측면에서 우수함을 보인다.

위치기반 서비스에서 프라이버시를 위한 연속질의와 질의 로그 익명화 기법

박소미(Somi Park),배주호(Juho Bai),박석(Seog Park) 한국정보과학회 2011 정보과학회논문지 : 데이타베이스 Vol.38 No.2

LBS(Location Based Services) are rapidly spread on the basis of GPS-added mobile devices. There are many studies for privacy preserving on LBS because, if LBS Server is exposed by attacker, leaked log can be used to find the exact location and personal information of user by inference attack. In this paper, we propose new anonymizing technique for continuous queries on LBS. It makes the same anonymized groups for continuous queries. It prevents intersected query attack and the intersected set of anonymized groups satisfies Location k-anonymity value. We also provide new architecture for query log anonymizing on LBS server. If attacker can search log record on the server, Object Diversify and Attribute Unlink techniques protect privacy personal information by strategies that anoymize who the actual issuer is, what he looks for, and where he is. This study offers a half reduced processing time on anonymizing process. And it provides determinate anonymized group on large scaled user service or anonymizing environment. 최근 GPS를 탑재한 모바일 기기들의 발전으로 위치기반 서비스의 이용이 확산되고 있다. 그러나 위치기반 서비스는 사용자의 위치정보가 누출될 경우 추론 공격 등을 통해 정확한 위치뿐만이 아니라 신변 정보까지 노출될 수 있는 가능성을 가져 위치정보를 보호하기 위한 위치기반 서비스 익명화 기법에 대한 연구가 대두되고 있다. 본 논문에서는 첫째, 기존 기법의 문제점인 연속적인 질의에 대한 교차공격을 방지할 수 있는 새로운 익명화 기법을 제시한다. 이 기법은 연속적인 질의에 대한 익명화 그룹이 동일하게 생성될 수 있도록 하여 그 그룹들의 교집합이 Location k-anonymity를 만족할 수 있도록 한다. 둘째, 익명화 서버의 질의 로그에 대해 사용자의 질의에 대한 프라이버시를 동시에 고려하는 기법을 제안한다. Object Diversify와 Attribute Unlink 기법을 통하여 공격자가 서버에 저장된 질의 로그에 접근 가능한 경우, 어떠한 사용자가 실제 질의자이고, 어디에서 무엇을 찾고자 하는지를 모호하게 만들어 프라이 버시를 보호한다. 본 연구는 기존 기법들의 문제점을 해결하기 위한 익명화 기법을 이용하여 수행시간을 약 50% 단축하고, 사용자 수나 익명화에 필요한 값이 증가 하더라도 익명화 그룹 범위를 일정 범위로 제한하는 방법을 제시한다.

단일방송채널환경에서 k-최근접질의 처리를 위한 힐버트 곡선과 최소영역 사각형 기반의 분산 공간 인덱싱 기법

이정형(Junghyung Yi),정성원(Sungwon Jung) 한국정보과학회 2010 정보과학회논문지 : 데이타베이스 Vol.37 No.4

본 논문은 단일무선방송채널환경에서 힐버트곡선과 최소영역사각형을 이용하여 공간데이터를 방송하고 이를 가지고 k-최근접질의 처리를 효과적으로 처리하는 기법에 관한 논문이다. 기존 방식은 k-최근 접질의 처리시 백트랙킹문제가 발생하여 질의처리에 오랜 시간이 걸리거나 검색범위를 빠르게 줄이지 못하여 많은 정보를 수신해야 하는 단점이 존재하였다. 제안하는 방법은 공간데이터를 힐버트 곡선 순서대로 방송하되 방송중인 공간데이터를 제외한 나머지 공간데이터를 최소영역사각형으로 그룹화하고 이를 인덱스 테이블로 구성하는 방법이다. 그리고 이를 이용하여 클라이언트가 알려지지 않은 데이터의 위치를 예측하여 빠르게 검색범위를 줄여나가 불필요한 정보를 제거하여 적은 튜닝시간과 접근지연시간을 갖도록 하는 것이다. This paper deals with an efficient index scheduling technique based on Hilbert curve and MBR for k-NN query in a single wireless broadcast channel environment. Previous works have two major problems. One is that they need a long time to process queries due to the back-tracking problem. The other is that they have to download too many spatial data since they can not reduce search space rapidly. Our proposed method broadcasts spatial data based on Hilbert curve order where a distributed index table is also broadcast with each spatial data. Each entry of index table represents the MBR which groups spatial data. By predicting the unknown location of spatial data, our proposed index scheme allows mobile clients to remove unnecessary data and to reduce search space rapidly. As a result, our method gives the decreased tuning time and access latency.

다양한 유형의 공간객체를 위한 R<SUP>m</SUP>-tree 기반의 mkNN 질의처리기법

장동주(Dongjue Jang),안수연(Sooyeon An),정성원(Sungwon Jung) 한국정보과학회 2011 정보과학회논문지 : 데이타베이스 Vol.38 No.5

본 논문에서는 다양한 유형의 위치기반 데이터들을 하나의 R-트리로 통합한 Rm-트리구조와 이 Rm-트리를 이용하여 질의포인트로부터 각 유형별로 k개의 가까운 위치기반 데이터를 찾는 mkNN(multi-type k Nearest Neighbor) 질의처리기법을 제안하였다. 특히, 다양한 유형의 위치기반 데이터들을 각 유형별로 독립된 R-트리로 유지하지 않고, 하나의 Rm-트리로 통합하여 관리함으로써 mkNN 질의처리시 같은 레벨의 공간의 반복탐색을 줄일 수 있도록 하였다. 그리고 각 유형에 대한 위치데이터를 관리하는 부가적인 유형정보 자료구조로서 위치데이터들을 포함하는 지역정보를 담은 TMBR(Type Minimum Bounding Rectangle), 데이터 개수정보를 담은 l-entry를 새로이 고안하여 mkNN 질의처리시 효율적인 휠터링(filtering)과 검색과정이 이루어지도록 하였다. In this paper, we propose an Rm-tree that integrates with location data of various types. We also propose an efficient mkNN query processing technique based on the Rm-tree that computes to find k nearest neighbors with m types for a given query point p. Especially, our proposed mkNN query processing method is able to reduce the repetitive traversal of the search space to compute multi-type k nearest neighbors. We add TMBR(Type Minimum Bounding Rectangle) and l-entry to Rm-tree to have the efficient filtering and searching performance for the processing of mkNN query.

대용량 위치 데이터에서 효율적인 k-최근접 질의 처리 기법

최도진(Dojin Choi),임종태(Jongtae Lim),유승훈(Seunghun Yoo),복경수(Kyoungsoo Bok),유재수(Jaesoo Yoo) 한국콘텐츠학회 2017 한국콘텐츠학회논문지 Vol.17 No.8

스마트 기기의 대중화로 다양한 위치 기반 서비스가 제공되고 있다. 최근에는 소셜 서비스와 결합한 위치 기반 소셜 서비스들이 생겨나고 있다. 이러한 위치 기반 소셜 네트워크 서비스에서는 사용자 중심의 가장 가까운 위치를 검색하는 k-최근접 질의 처리의 요구가 증가된다. 본 논문에서는 대규모 사용자 환경에서 질의를 효율적으로 처리하기 위한 근사 k-최근접 질의 처리 기법을 제안한다. 제안하는 기법은 빅데이터 분산 처리기술을 활용하여 효율적인 스트림 처리를 수행한다. 본 논문에서는 대량의 위치 데이터에 대한 색인을 위해 전통적인 그리드 색인 기법을 변형한 색인 기법을 제안한다. 제안하는 질의 처리기법은 사용자의 진행방향을 고려하여 해당 셀을 우선적으로 탐색한다. 이를 통해 k개의 근사 결과 집합을 생성할 수 있다. 제안하는 기법의 우수성을 입증하기 위해 기존 기법과 다양한 성능 평가를 수행한다. With the growing popularity of smart devices, various location based services have been providing to users. Recently, some location based social applications that combine social services and location based services have been emerged. The demands of a k-nearest neighbors(k-NN) query which finds k closest locations from a user location are increased in the location based social network services. In this paper, we propose an approximate k-NN query processing method for fast response time in a large number of users environments. The proposed method performs efficient stream processing using big data distributed processing technologies. In this paper, we also propose a modified grid index method for indexing a large amount of location data. The proposed query processing method first retrieves the related cells by considering a user movement. By doing so, it can make an approximate k results set. In order to show the superiority of the proposed method, we conduct various performance evaluations with the existing method.

클라이언트가 이동하는 환경에서 효율적인 연속 k-최근접 질의 처리를 위한 색인 구조

박용훈,서동민,윤종현,신재룡,최길성,유재수 한국정보과학회 2010 데이타베이스 연구 Vol.26 No.2

The interest of Location-Based Services (LBS) has highly increased according to the development of location aware techniques and mobile devices and also the researches on LBS have been progressed in recent years. In this paper, we propose ISR-tree (Incremental Search R-tree) which processes continuous k-NN queries efficiently in the environment composed of static objects and moving clients submitting queries. In ISR-tree, the leaf-nodes maintain the entries of their neighbor nodes and the entries help to find the neighbor leaf-nodes without visiting internal nodes when k-NN queries are processed. As a result, ISR-tree saves the cost to visit internal nodes. We prove the superiority of ISR-tree through the comparison with previous works. 최근 위치 인식 기술과 휴대 장치의 발달로 인해 이동하는 객체를 기반으로 하는 위치 기반 서비스(Location Based Service, LBS)의 관심이 점점 증가하고 있고 그에 관련된 연구들이 활발하게 진행되고 있다. 본 논문에서는 고정된 객체와 이동하는 질의 환경에서 연속 k-최근접 질의를 효율적으로 수행하는 색인구조인 ISR-tree(Incremental Search R-tree)를 제안한다. 이 구조는 단말 노드에서 이웃 노드들의 정보를유지하여 k-최근접 질의 처리시 중간 노드에 대한 탐색횟수를 감소시켰을 뿐만 아니라 연속 질의 처리를 위한질의 재수행시 중간 노드를 탐색하지 않는다. 제안하는 기법의 우수성을 평가하기 위해 R-tree와의 비교를수행하였다.

도로 네트워크에서 부분적으로 주어진 방문 순서에 따른 경로 질의 계산 방법

안수연(SooYeon Ahn),정성원(Sungwon Jung) 한국정보과학회 2013 정보과학회논문지 : 데이타베이스 Vol.40 No.5

논문에서는 도로 네트워크 환경에서 부분적으로 주어진 방문순서에 따라 출발지로부터 각 타입의 포인트 데이터 한 개씩을 방문하여 도착지에 도달하는 근접최단경로를 찾기 위하여, 방문할 후보 포인트 데이터를 선정하는 효과적인 비용함수와 후보 포인트 데이터를 방문하는 근접최단경로를 찾는 경로 검색 기법 PRGA(Partial sequenced Route computation Greedy Algorithm)와 GCPRA(Globally Considered Partial sequenced Route computation Algorithm)를 제안하였다. PRGA은 Greedy 알고리즘을 사용하여 근접최단경로를 구하는 방법이며, GCPRA은 후보 포인트로 구성된 가능한 모든 경로를 고려하여 근접최단경로 구하는 기법이다. 제안한 두 개의 근접최단경로 검색기법의 성능분석 결과 기존의 기법 보다 더 최단경로에 근접한 경로를 생성하는 것으로 나타났다. This paper addresses the problem of finding the approximate shortest route that visits one candidate point for each POI (Point Of Interest) type from the start to the destination by using a partially given visiting sequence of POI types. We first propose an effective cost function that selects candidate points for each POI types. We then propose two approximate shortest route computation algorithms, PRGA (Partial sequenced Route computation Greedy Algorithm) and GCPRA (Globally Considered Partial sequenced Route computation Algorithm), which pass through the selected candidate points in road networks according to a partially given visiting sequence of POI types. PRGA computes an approximate shortest route based on a greedy algorithm, whereas GCPRA computes an approximate shortest route by considering all possible routes of candidate points. The performance analysis of the two proposed algorithms shows that they generate the better approximate shortest routes than the existing methods.

이동 객체 환경에서 거리 관계 패턴 기반 k-최근접 질의 처리 기법

박용훈(Yong Hun Park),서동민(Dong Min Seo),복경수(Kyoung Soo Bok),이병엽(Byoung Yup Lee),유재수(Jae Soo Yoo) 한국정보과학회 2009 정보과학회논문지 : 데이타베이스 Vol.36 No.3

최근 유클리드 공간 상에서 효율적인 k-최근접(k-Nearest Neighbors) 질의 처리를 위해 그리드 구조 기반의 많은 색인 기법들이 연구되었다. 하지만 기존 기법들은 k-최근접 객체들을 연산하기 위해 불필요한 셀을 접근하여 연산 자원을 낭비하거나 근접한 셀을 알아내는데 매우 큰 연산 비용을 초래한다. 그래서 본 논문에서는 한 셀과 주변 셀과의 거리 관계를 나타내는 거리 관계 패턴을 이용하여 k-최근접질의 처리시 적은 연산 비용과 적은 저장 공간을 사용하는 새로운 k-최근접 질의 처리 기법을 제안한다. 본 논문에서는 k-최근접 질의 처리의 대표적인 기법인 CPM과 성능을 비교하여 제안하는 기법의 우수성을 입증한다. Recently, various methods have been proposed to process k-NN (k-Nearest Neighbors) queries efficiently. However the previous methods have problems that they access additional cells unnecessarily and spend the high computation cost to find the nearest cells. In this paper, to overcome the problems, we propose a new method to process k-NN queries using the patterns of the distance relationship between the cells in a grid. The patterns are composed of the relative coordinates of cells sorted by the distance from certain points. Since the proposed method finds the nearest cells to process k-NN queries with traversing the patterns sequentially, it saves the computation cost. It is shown through the various experiments that out proposed method is much better than the existing method, CPM, in terms of the query processing time and the storage overhead.

다중 무선 방송채널에서 kNN 질의 처리를 위한 R-tree 인덱스 스케줄링 기법

정의준(Euijun Jung),정성원(Sungwon Jung) 한국정보과학회 2010 정보과학회논문지 : 데이타베이스 Vol.37 No.2

본 논문은 다중 무선 방송채널환경에서 R-tree를 이용하여 kNN 질의처리의 효과적인 인덱스 스케줄링 기법에 관한 논문이다. 기존 방식은 kNN질의처리 시 노드를 여러 개 얻어야 할 때 child들이 다중 채널 방송스케줄 상 같은 타임 슬롯에 위치하고 있어 원하는 데이터를 얻기 위해서 다음 사이클로 넘어가 데이터를 얻는 시간이 길어지는 단점이 존재하였다. 제안하는 방법은 방송채널에 인덱스 스케줄링을 하기 전에 kNN을 수행하여 R-tree의 각 노드의 child의 접근빈도를 구한 후 구해진 접근 빈도를 기반으로 인덱스 스케줄링 시 방문이 많이 되어 접근빈도가 높은 child들을 다중채널 상에 직렬로 할당하고 접근이 적게 되는 노드는 병렬로 할당하여 질의처리 시 각 노드의 child들을 탐색할 때 겹치는 부분을 줄여 사용자가 원하는 데이터를 빠르게 얻을 수 있는 인덱스 스케줄링 기법이다. This paper proposes an efficient index scheduling technique for kNN query processing in multiple wireless broadcast channel environment. Previous works have to wait for the next cycle if the required child nodes of the same parent node are allocated in the same time slot on multiple channel. Our proposed method computes the access frequencies of each node of R tree at the server before the generation of the R-tree index broadcast schedule. If they have high frequencies, we allocate them serially on the single channel. If they have low frequencies, we allocate them in parallel on the multiple channels. As a result, we can reduce the index node access conflicts and the long broadcast cycle. The performance evaluation shows that our scheme gives the better performance than the existing schemes.

다중 무선 방송채널에서 kNN 질의 처리를 위한 R-tree 스케줄링 기법

신광현(Kwanghyun Shin),정성원(Sungwon Jung) 한국정보과학회 2011 정보과학회논문지 : 데이타베이스 Vol.38 No.3

본 논문에서는 다중 무선 방송채널환경에서 효과적인 kNN 질의처리를 위한 R-tree 인덱싱 방송 스케줄링 기법인 RCAED을 제안하였다. 특히, 다중 무선 방송채널환경에서 채널간의 R-tree 인덱스 노드간의 접근 충돌을 최소화하기 위하여 각 타임 슬롯에서 충돌가능성이 적은 인덱스 노드들을 동일한 타임 슬롯에 우선 할당하는 방법을 고안하였다. 또한 각 방송 채널 안에서 충돌가능성이 높은 노드들을 선택하여 충돌시 빠른 시간 안에 충돌한 인덱스 노드를 재검색할 수 있도록 빈 슬롯에 반복시켜 할당하는 방법을 제시하였다. In this paper, we propose an R-tree index broadcast scheduling technique called RCAED for the efficient processing of KNN query in multiple wireless broadcast channels. Especially, we suggest a method to identify the groups of R-tree index nodes that have the low probability of having the access conflicts with each other when they are allocated to the same time slot of multiple broadcast channels. We also propose a method for allocating the index nodes with high access conflict probabilities to the available empty time slots multiple times to speed up the re-access of the conflicted R-tree index nodes.