κ-anonymization device, method, and program

Patent metadata

Field	Value
Publication number	US-11507684-B2
Application number	US-201816652225-A
Country	US
Kind code	B2
Filing date	Oct 9, 2018
Priority date	Oct 11, 2017
Publication date	Nov 22, 2022
Grant date	Nov 22, 2022

Abstract

A k-anonymization device includes: a list creation unit 1 that creates, based on generalization hierarchies about attribute values of attributes of a database, lists of values, each being obtained by generalizing each attribute value of each attribute of the database to each generalization level of the corresponding generalization hierarchy, and codes representing the values; a search unit 3 that searches for a node with k-anonymity of a lattice structure in parallel by determining whether a generalized database obtained by generalizing the database to generalization levels corresponding to each node of the lattice structure has k-anonymity based on the generalized database represented by the codes, which is obtained by referring to the created lists; and an output unit 4 that outputs a generalized database obtained by generalizing the database to generalization levels corresponding to a node with k-anonymity, which was found by the search, of the lattice structure.

First claim

What is claimed is:

1. A k-anonymization device comprising:
processing circuitry configured to:
create, based on generalization hierarchies about attribute values of attributes of a database, lists of values, each being obtained by generalizing each attribute value of each attribute of the database to each generalization level of the corresponding generalization hierarchy, and codes representing the values;
store the created lists in a memory;
search for a node with k-anonymity, based on an assumption that a lattice structure is made up of nodes representing generalization levels of the attributes of the database, of the lattice structure in parallel by determining whether a generalized database obtained by generalizing the database to generalization levels corresponding to each node of the lattice structure has k-anonymity based on the generalized database represented by the codes, which is obtained by referring to the lists read from the memory; and
output a generalized database obtained by generalizing the database to generalization levels corresponding to a node with k-anonymity, which was found by the search, of the lattice structure.

2. The k-anonymization device according to claim 1 , wherein
when the database is compressed, the processing circuitry decompresses the database and creates the lists based on the decompressed database.

3. The k-anonymization device according to claim 1 or 2 , wherein
the processing circuitry conducts a depth-first search for a node with k-anonymity of the lattice structure in parallel.

4. The k-anonymization device according to claim 1 or 2 , wherein
the unit processing circuitry conducts a width-first search for a node with k-anonymity of the lattice structure in parallel.

5. A k-anonymization method, implemented by processing circuitry of a k-anonymization device, comprising:
a list creation step in which the processing circuitry creates, based on generalization hierarchies about attribute values of attributes of a database, lists of values, each being obtained by generalizing each attribute value of each attribute of the database to each generalization level of the corresponding generalization hierarchy, and codes representing the values;
a search step in which the processing circuitry searches for a node with k-anonymity, based on an assumption that a lattice structure is made up of nodes representing generalization levels of the attributes of the database, of the lattice structure in parallel by determining whether a generalized database obtained by generalizing the database to generalization levels corresponding to each node of the lattice structure has k-anonymity based on the generalized database represented by the codes, which is obtained by referring to the created lists; and
an output step in which the processing circuitry outputs a generalized database obtained by generalizing the database to generalization levels corresponding to a node with k-anonymity, which was found by the search, of the lattice structure.

6. A non-transitory computer-readable storage medium storing instructions which when executed cause a computer function as the k-anonymization device according to claim 1 .

Assignees

• Nippon Telegraph & Telephone

Inventors

• Hasegawa Satoshi
• Okada Rina
• Masaki Shogo

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/21

  Design, administration or maintenance of databases · CPC title

• G06F21/6227 Primary

  where protection concerns the structure of data, e.g. records, types, queries · CPC title

• G06F21/6254

  by anonymising data, e.g. decorrelating personal data from the owner's identification · CPC title

• G06F16/2228

  Indexing structures · CPC title