(A) bitmap based incognito algorithm : design and implementation = 비트맵 기반의 Incognito 구현과 성능평가

국문 초록 (Abstract)

현대사회에서 우리는 많은 데이터들을 쉽게 접하고 구할 수 있다. 일반적으로 이러한 데이터들이 유포될 때에는 질병관계와 같은 중요성을 띠는 정보들은 제거된 채 유포된다. 그러나 때때로 외부데이터들과 서로 조인되어 중요정보들이 드러날 수 있는데 이것을‚ '조인 공격'이라고 한다. K-anonymization(또는 k-anonymity)은 이러한 조인 공격에 대하여 데이터를 일반화/구체화시킴으로써 사용자에게 다수개의 결과를 반환하여 데이터 해독에 모호성을 부여하는 기법을 말한다. Incognito는 이러한 k-anonymity을 지원하는 최신 알고리즘이다. 그러나 현재 Incognito는 정렬에 기반하고 있기 때문에 연산과정에서 오버헤드를 가지게 된다. 이 논문에서, 우리는 bitmap에 기반한 변형된 Incognito를 제시한다. 변형된 Incognito는 bitwise AND / OR과 bit-count 연산만을 필요로 하기 때문에 기존 방법보다 좀 더 직관적이고 빠른 속도를 보여준다. 그리고 이러한 연산들(AND/OR, count)만을 사용하여 필요로 하는 모든 데이터를 구할 수 있기 때문에 데이터가 저장된 실제 테이블로의 접근이 필요 없다. 또한 bitmap은 테이블과 비교하여 매우 작은 크기를 가지기 때문에 메모리에 로드되어 사용될 확률이 높다. 위에서 설명한 특징들로 인하여 bitmap기반의 Incognito는 기존 Incognito보다 우수한 성능을 가진다는 것을 보장할 수 있다. 또한 bitmap 기반 Incognito는 SIMD와 같은 최신 CPU 기능을 적용할 수 있다는 장점을 가진다.

목차 (Table of Contents)

• List of Tables
• List of Figures
• 1. Introduction
• 1.1 Background
• 1.2 Paper Organization and Contributions
• 2. Related Work
• 2.1 Basic Definitions
• 2.2 Binary Search Algorithm
• 3. Incognito
• 3.1 Incognito Algorithm
• 3.2 Advantages and Disadvantages of Incognito
• 4. Improvement of Incognito by using Bitmap
• 4.1 Generalization and generation nodes by using bitwise operations
• 4.2 Bitmap-based Incognito Algorithm
• 4.3 Advantages of Bitmap-based Incognito
• 5. Optimization
• 5.1 1-Level(1-subset) Optimization
• 5.2 Reusing Optimization
• 5.3 Pruning Optimization
• 5.4 Pre-Pruning Optimization
• 6. Performance Evaluation
• 7. Conclusion and Future Work
• References
• Abstract