테이블 T 내의 정보를 k-익명성을 사용하여 보호하는 방법에 있어서,상기 T에 대한 (k, 2k-1)-커버를 생성하는 단계;상기 생성된 (k, 2k-1)-커버를 (k, 2k-1)-파티션으로 변환하는 단계; 및상기 (k, 2k-1)-파티션에 기반하여 상기 T를 K-익명성을 제공하는 테이블로 변환하는 단계를 포함하며, 상기 (k, 2k-1)-커버의 일반화 길이는 k-익명성 최적해의 (1 + ln 2k) 배 이하인, k-익명성을 사용한 정보 보호 방법.

제1항에 있어서,상기 T에 대한 (k, 2k-1)-커버들을 생성하는 단계는,상기 T의 부분집합들을 원소로 갖는 집합 F를 생성하는 단계;상기 F 내의 모든 원소들 각각에 대해서 일반화 길이를 계산하는 단계;상기 F 내의 원소들 중 상기 원소 내의 커버되지 않은 레코드 당 일반화 길이가 가장 적은 원소를 선택하는 단계; 및상기 선택된 원소를 상기 (k, 2k-1)-커버 내의 테이블로서 추가하는 단계;를 포함하는, k-익명성을 사용한 정보 보호 방법.

제2항에 있어서,상기 선택된 원소의 크기가 2k - 1보다 클 경우, 상기 선택된 원소에서 임의의 2k - 1개의 레코드들만을 제외한 나머지 레코드들을 제거하는 단계를 더 포함하고, 상기 부분집합들 각각의 대표는 서포트 k의 일반화된 빈발 아이템 집합인, k-익명성을 사용한 정보 보호 방법.

제2항에 있어서,상기 부분집합들은 일반화 길이가 0 및 m / β 사이인 닫힌 일반화된 빈발 아이템 집합이고, 상기 m은 준식별자 속성의 총 개수이고, 상기 β는 미리 정의된 값인, k-익명성을 사용한 정보 보호 방법.

제1항에 있어서,상기 (k, 2k-1)-파티션의 일반화 길이 합은 상기 (k, 2k-1)-커버의 일반화 길의 합 이하인, k-익명성을 사용한 정보 보호 방법.

제1항에 있어서,상기 생성된 (k, 2k-1)-커버들을 (k, 2k-1)-파티션들로 변환하는 단계는,특정 레코드 t를 선택하는 단계;상기 (k, 2k-1)-커버 내의 테이블들 중, 상기 레코드 t를 포함하는 제1 테이블들의 포인터들을 포함하는 리스트 M을 생성하는 단계;상기 M 내의 k보다 더 큰 크기를 갖는 제2 테이블의 포인터를 제거하고, 상기 제2 테이블에서 상기 t를 제거하는 단계; 및상기 M 내의 k 이하의 크기를 갖는 제3 테이블 및 제4 테이블을 병합하는 단계를 포함하는, k-익명성을 사용한 정보 보호 방법.

제1항에 있어서,상기 (k, 2k-1)-파티션에 기반하여 상기 T를 K-익명성을 제공하는 테이블로 변환하는 단계는,상기 (k, 2k-1)-파티션 내의 테이블 S를 선택하는 단계; 및상기 S 내의 튜플들을 최소 비용을 갖는 일반화된 값들로 교체하는 단계를 포함하고, 상기 S 내의 모든 튜플들은 동일한, k-익명성을 사용한 정보 보호 방법.

제1항에 있어서,상기 (k, 2k-1)-파티션에 기반하여 상기 T를 K-익명성을 제공하는 테이블로 변환하는 단계는,상기 (k, 2k-1)-파티션 내의 테이블 S를 선택하는 단계; 및상기 S 내의 튜플들을 삭제하는 단계를 포함하고, 상기 S 내의 모든 튜플들은 동일한, k-익명성을 사용한 정보 보호 방법.

테이블 T 내의 정보를 k-익명성을 사용하여 보호하는 방법에 있어서,상기 T의 부분집합들을 원소로 갖는 집합 F를 생성하는 단계;상기 F 내의 원소들을 상기 원소들 각각의 일반화 길이의 오름차순으로 정렬하는 단계;상기 F 내의 원소들 중 가장 작은 일반화 길이를 갖는 원소 S를 상기 F에서 제거하는 단계;상기 S에서 T 내의 튜플들 중 커버된 튜플들의 집합인 D에 포함되는 튜플들을 제거하는 단계;상기 S가 공집합이 아닐경우, 상기 S의 원소를 상기 D에 추가하고, 상기 S를 파티션 내에 테이블로서 추가하는 단계; 및상기 파티션에 기반하여 상기 T를 K-익명성을 제공하는 테이블로 변환하는 단계를 포함하는, k-익명화의 하한 생성 방법.

제9항에 있어서,상기 파티션에 기반하여 상기 T를 K-익명성을 제공하는 테이블로 변환하는 단계는,상기 파티션 내의 테이블 Q를 선택하는 단계; 및상기 Q 내의 튜플들을 최소 비용을 갖는 일반화된 값들로 교체하는 단계를 포함하고, 상기 Q 내의 모든 튜플들은 동일한, k-익명화의 하한 생성 방법.

제9항에 있어서,상기 파티션에 기반하여 상기 T를 K-익명성을 제공하는 테이블로 변환하는 단계는,상기 파티션 내의 테이블 Q를 선택하는 단계; 및상기 Q 내의 튜플들을 삭제하는 단계를 포함하고, 상기 Q 내의 모든 튜플들은 동일한, k-익명화의 하한 생성 방법.

제9항에 있어서,상기 부분집합들은 일반화 길이가 (i - 1)m/β 및 im/β 사이인 닫힌 일반화된 빈발 아이템 집합이고, 상기 m은 준식별자 속성의 총 개수이고, 상기 β는 미리 정의된 값이고, 상기 i는 0 및 -β- 사이의 정수인, k-익명성을 사용한 정보 보호 방법.

테이블 T 내의 정보를 k-익명성을 사용하여 보호하는 방법에 있어서,상기 T 내에서 가장 빈발인 아이템 또는 가장 빈발인 일반화된 아이템 i를 선택하는 단계;상기 T 내에서 상기 i를 가진 레코드들의 집합을 선택하는 단계;상기 레코드들의 집합에서 가장 빈발인 아이템이나 가장 빈발인 일반화된 아이템을 검색하는 단계;상기 레코드들의 집합에서 빈발 아이템이나 빈발 일반화된 아이템이 없는 경우 상기 레코드 집합을 파티션의 테이블로서 추가하는 단계; 및상기 파티션에 기반하여 상기 T를 K-익명성을 제공하는 테이블로 변환하는 단계를 포함하는 k-익명성을 사용한 정보 보호 방법.

테이블 T 내의 정보를 k-익명성을 사용하여 보호하는 장치에 있어서,테이블 T의 정보를 저장하는 저장부;상기 T에 기반하여 K-익명성 테이블을 생성하는 제어부; 및생성된 K-익명성 테이블을 제공하는 인터페이스부를 포함하고,상기 제어부는, 상기 T에 대한 (k, 2k-1)-커버를 생성하고, 상기 생성된 (k, 2k-1)-커버를 (k, 2k-1)-파티션으로 변환함으로써 상기 T에 기반하여 K-익명성 테이블을 생성하고, 상기 (k, 2k-1)-커버의 일반화 길이는 k-익명성 최적해의 (1 + ln 2k) 배 이하인, k-익명성을 사용한 정보 보호 장치.

제14항에 있어서,상기 제어부는, 상기 T의 부분집합들을 원소로 갖는 집합 F를 생성하고, 상기 F 내의 모든 원소들 각각에 대해서 일반화 길이를 계산하고, 상기 F 내의 원소들 중 상기 원소 내의 커버되지 않은 레코드 당 일반화 길이가 가장 적은 원소를 선택하고, 상기 선택된 원소를 상기 (k, 2k-1)-커버 내의 테이블로서 추가함으로써 상기 T에 대한 (k, 2k-1)-커버들을 생성하는, k-익명성을 사용한 정보 보호 장치.

제14항에 있어서,상기 제어부는, 상기 (k, 2k-1)-커버 내의 테이블들 중, 레코드 t를 포함하는 제1 테이블들의 포인터들을 포함하는 리스트 M을 생성하고, 상기 M 내의 k보다 더 큰 크기를 갖는 제2 테이블의 포인터를 제거하고, 상기 제2 테이블에서 상기 t를 제거하고, 상기 M 내의 k 이하의 크기를 갖는 제3 테이블 및 제4 테이블을 병합함으로써, 상기 생성된 (k, 2k-1)-커버들을 (k, 2k-1)-파티션들로 변환하는, k-익명성을 사용한 정보 보호 장치.

제14항에 있어서,상기 제어부는, 상기 (k, 2k-1)-파티션 내의 테이블 S를 선택하고, 상기 S 내의 튜플들을 최소 비용을 갖는 일반화된 값들로 교체함으로써, 상기 (k, 2k-1)-파티션에 기반하여 상기 T를 K-익명성 테이블로 변환하고, 상기 S 내의 모든 튜플들은 동일한, k-익명성을 사용한 정보 보호 장치.

제14항에 있어서,상기 제어부는, 상기 (k, 2k-1)-파티션 내의 테이블 S를 선택하고, 상기 S 내의 튜플들을 삭제함으로써, 상기 (k, 2k-1)-파티션에 기반하여 상기 T를 K-익명성 테이블로 변환하고, 상기 S 내의 모든 튜플들은 동일한, k-익명성을 사용한 정보 보호 장치.