디지털 라이브러리[ 검색결과 ]
쿼드 트리를 이용한 동적 공간 분할 기반 차분 프라이버시 k-평균 클러스터링 알고리즘
http://doi.org/10.5626/JOK.2018.45.3.288
최근 공개되는 데이터에 적용하는 다양한 프라이버시 보호 기법들이 연구가 되어왔다. 그 중 차분 프라이버시는 본래의 데이터에 확률적인 노이즈를 더하여 공격자의 사전 지식에 상관없이 개인 정보를 보호한다. 기존 차분 프라이버시를 만족하는 k-평균 클러스터링은 데이터로부터 차분 프라이버시를 만족하는 히스토그램 형태로 바꾼 뒤. k-평균 클러스터링 알고리즘을 수행한다. 하지만 이는 데이터의 분포와 상관없이 등간격으로 히스토그램을 만들기 때문에 노이즈가 삽입되는 버킷이 많아지는 단점이 있다. 이를 해결하기 위해 본 논문에서는 데이터의 분포를 더 적은 버킷으로 나타낼 수 있는 쿼드 트리를 이용하여 히스토그램을 만든 뒤 k-평균을 찾는 알고리즘을 제안한다. 또한, 실험을 통해 기존의 알고리즘보다 더 좋은 성능을 가지는 것을 보인다.
공간 웹 객체의 효율적인 검색 기법
공간 웹 객체는 웹 문서에 지리정보를 포함하고 있는 문서들을 말한다. 최근 스마트폰과 같은 장치의 발달로 인하여 공간 웹 객체를 생성하는 서비스가 많이 늘어났다. 트위터나 페이스북 같은 서비스에서는 사용자가 게시한 간단한 글이 게시한 위치정보와 함께 저장된다. 이러한 공간 웹 객체의 검색을 위해서는 공간 정보와 문자 정보를 동시에 이용하는 검색이 필요하다. 기존의 공간 웹 객체 검색 방식은 R트리와 역색인 파일(inverted file) 방법을 많이 사용했다. 하지만 이 방법은 인덱스를 구축하는데 많은 공간을 필요로 한다는 단점이 있다. 또한 검색하는 키워드가 많을 때는 효율적이지만, 검색하는 키워드가 적을 때는 비효율적이다. 본 논문에서는 쿼드 트리(quad-tree)와 패트리샤 트라이(patricia trie)를 이용하는 공간 웹 객체 검색 방식을 제안한다. 제안하는 기법은 검색하는 키워드가 적을 때 기존의 기법보다 좋다는 것을 보여준다. 또한 인덱스를 저장하는 공간이 기존의 기법보다 훨씬 적게 사용된다는 것을 실험을 통하여 증명하였다.
