(57)【要約】  k-匿名化装置は、データベースの各属性の各属性値についての一般化階層に基づいて、データベースの各属性の各属性値を一般化階層の各一般化レベルまで一般化した値とその値を表す符号のリストを生成するリスト生成部１と、ラティス構造の各ノードに対応する一般化レベルまでデータベースを一般化した一般化データベースがk-匿名性を有するかどうかを、生成されたリストを参照することにより得られる符号で表された一般化データベースに基づいて判定することにより、k-匿名性を有するラティス構造のノードを並列に探索する探索部３、探索により見つかった、k-匿名性を有するラティス構造のノードに対応する一般化レベルまでデータベースを一般化した一般化データベースを出力する出力部４と、を備えている。
2019073967.tif 000002
【特許請求の範囲】
【請求項１】
データベースの各属性の各属性値についての一般化階層に基づいて、上記データベースの各属性の各属性値を上記一般化階層の各一般化レベルまで一般化した値とその値を表す符号のリストを生成するリスト生成部と、
上記生成されたリストが記憶されるリスト記憶部と、
ラティス構造は上記データベースの各属性の一般化レベルを表すノードから構成されるとして、上記ラティス構造の各ノードに対応する一般化レベルまで上記データベースを一般化した一般化データベースがk-匿名性を有するかどうかを、上記リスト記憶部から読み込んだリストを参照することにより得られる上記符号で表された上記一般化データベースに基づいて判定することにより、k-匿名性を有する上記ラティス構造のノードを並列に探索する探索部と、
上記探索により見つかった、k-匿名性を有する上記ラティス構造のノードに対応する一般化レベルまで上記データベースを一般化した一般化データベースを出力する出力部と、
を含むk-匿名化装置。
【請求項２】
請求項１のk-匿名化装置であって、
上記データベースが圧縮されている場合には、上記リスト生成部は、上記データベースを解凍処理し、その解凍処理されたデータベースに基づいて上記リストを生成する、
k-匿名化装置。
【請求項３】
請求項１又は２のk-匿名化装置であって、
上記探索部は、k-匿名性を有する上記ラティス構造のノードを並列に深さ優先で探索する、
k-匿名化装置。
【請求項４】
請求項１又は２のk-匿名化装置であって、
上記探索部は、k-匿名性を有する上記ラティス構造のノードを並列に幅優先で探索する、
k-匿名化装置。
【請求項５】
リスト生成部が、データベースの各属性の各属性値についての一般化階層に基づいて、上記データベースの各属性の各属性値を上記一般化階層の各一般化レベルまで一般化した値とその値を表す符号のリストを生成するリスト生成ステップと、
探索部が、ラティス構造は上記データベースの各属性の一般化レベルを表すノードから構成されるとして、上記ラティス構造の各ノードに対応する一般化レベルまで上記データベースを一般化した一般化データベースがk-匿名性を有するかどうかを、上記生成されたリストを参照することにより得られる上記符号で表された上記一般化データベースに基づいて判定することにより、k-匿名性を有する上記ラティス構造のノードを並列に探索する探索ステップと、
出力部が、上記探索により見つかった、k-匿名性を有する上記ラティス構造のノードに対応する一般化レベルまで上記データベースを一般化した一般化データベースを出力する出力ステップと、
を含むk-匿名化方法。
【請求項６】
請求項１から４の何れかのk-匿名化装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データベースを秘匿化する技術に関する。
【背景技術】
【０００２】
データベースに対して個別データを確定的手法により秘匿する技術として、非特許文献１から３がある。これらの非特許文献１から３の秘匿処理では、データを一般化処理又はレコード削除することで、同じレコードがk個以上存在する(k-匿名性)ようにデータを加工することを行う。この加工を、k-匿名化と言う。【０００３】
一般化処理とは、データを汎化することである。例えば、「りんご」を一般化すると「果物」になり、「13歳」を一般化すると「10代」になる。一般化処理の多くは、一般化階層と呼ばれる値の汎化及び特化関係を表す木構造を準備し、その木構造を辿ることで値のコーディングを行い処理をする。例えば、一般化処理の場合には、一般化階層の階層を上げる処理を行う。【０００４】
図７に、一般化階層の例を示す。図７は、それぞれ日付、性別、住所の一般化階層の例を表す。【０００５】
従来技術の多くは、k-匿名性を満たす最低限の一般化及び削除処理を行う。これは、各属性ごとの一般化レベルの上げ方の組み合わせの中で最も一般化及び削除処理の少ないものを選択することに相当する。これを、最適なk-匿名化とも言う。各属性ごとの一般化レベルのまとまりをノードとした場合、レベルの上げ方の組み合わせは、ラティス構造で表現できる。最適なk-匿名化は、このラティス構造の中から、最適なk-匿名化を行うノードを効率良く探索する問題となる。【０００６】
図８に、ラティス構造の例を示す。図８は、図７で示した日付（高さ３）、性別（高さ２）、住所（高さ５）の階層の一般化階層のラティス構造の例である。（０，０，０）はそれぞれレベル０の値であり、例えば日付を１階層上げた場合（１，０，０）となる。図８の右側に示すラティスのレベルは、階層上げを何回行ったかを表している。【０００７】
この探索問題は、NP困難であることが示されており、ヒューリスティクスに効率良く実行する方法が様々研究されている（例えば、非特許文献１から３参照）。これらのアルゴリズムは、「ラティス構造内のあるノードがk-匿名性を満たす場合、任意の上位ノードも、k-匿名性を満たす」という性質に基づいてラティス構造内の探索空間を狭め、高効率化を図っている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Khaled El Emam, Fida Kamal Dankar, Romeo Issa, Elizabeth Jonker, Daniel Amyot, Elise Cogo, Jean-Pierre Corriveau, Mark Walker, Sadrul Chowdhury, Regis Vaillancourt, et al. "A globally optimal k-anonymity method for the de-identification of health data. Journal of the American Medical Informatics Association", Vol. 16, No. 5, pp. 670-682, 2009.
【非特許文献２】Florian Kohlmayer, Fabian Prasser, Claudia Eckert, Alfons Kemper, and Klaus A Kuhn. "Flash: efficient, stable and optimal k-anonymity", In Privacy, Security, Risk and Trust (PASSAT), 2012 International Conference on and 2012 International Confernece on Social Computing (SocialCom), pp. 708-717. IEEE, 2012.
【非特許文献３】Kristen LeFevre, David J DeWitt, and Raghu Ramakrishnan. "Incognito: Efficient full-domain k-anonymity", In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 49-60, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
昨今のビッグデータブームにより、匿名化の対象となるデータも、大規模データが対象となることが想定される。従来技術では、秘匿処理の際、レコード数や属性数が増えるに連れ処理時間やメモリ使用量が増えることが問題であった。より具体的には、レコード数の増加により一般化処理に要する時間やメモリ使用量が線形に増加し、属性数の増加によりラティス構造内のノードが指数的に増え、ラティス構造の探索による最適なk-匿名化ノードの候補の発見に時間を要していた。【００１０】
この発明の目的は、従来よりも、メモリ消費量を減らしつつ、実用的な処理時間でk-匿名化を行うk-匿名化装置、方法及びプログラムを提供することである。
【課題を解決するための手段】
【００１１】
この発明の一態様によるk-匿名化装置は、データベースの各属性の各属性値についての一般化階層に基づいて、上記データベースの各属性の各属性値を一般化階層の各一般化レベルまで一般化した値とその値を表す符号のリストを生成するリスト生成部と、生成されたリストが記憶されるリスト記憶部と、ラティス構造はデータベースの各属性の一般化レベルを表すノードから構成されるとして、ラティス構造の各ノードに対応する一般化レベルまでデータベースを一般化した一般化データベースがk-匿名性を有するかどうかを、リスト記憶部から読み込んだリストを参照することにより得られる符号で表された一般化データベースに基づいて判定することにより、k-匿名性を有するラティス構造のノードを並列に探索する探索部と、探索により見つかった、k-匿名性を有するラティス構造のノードに対応する一般化レベルまでデータベースを一般化した一般化データベースを出力する出力部と、を備えている。
【発明の効果】
【００１２】
従来よりも、メモリ消費量を減らしつつ、実用的な処理時間でk-匿名化を行うことができる。
【図面の簡単な説明】
【００１３】
【図１】k-匿名化装置の例を示すブロック図。
【図２】k-匿名化方法の例を示す流れ図。
【図３】データベースの例を示す図。
【図４】符号化及びリストの例を示す図。
【図５】高さ優先探索のアルゴリズムの例を示す図。
【図６】幅優先探索のアルゴリズムの例を示す図。
【図７】一般化階層の例 に示す図。
【図８】ラティス構造の例を示す図。
【発明を実施するための形態】
【００１４】
以下、図面を参照して、この発明の一実施形態について説明する。
【００１５】
図１に示すように、k-匿名化装置は、リスト生成部１、リスト記憶部２、探索部３及び出力部４を例えば備えている。
【００１６】
k-匿名化方法は、k-匿名化装置の各部が、図２及び以下に例示するステップＳ１からステップＳ４の処理を行うことにより実現される。
【００１７】
k-匿名化の対象となるデータベースは、例えば列指向データベース又は列指向によるデータ管理がされているデータベースである。k-匿名化の対象となるデータベースは、列単位でデータが格納され、それぞれ列の部分ごとに圧縮されているデータベースであってもよい。k-匿名化の対象となるデータベースは、通常のファイル形式のものや、オンメモリで動作するデータベースであってもよい。
【００１８】
＜リスト生成部１＞
リスト生成部１には、k-匿名化の対象となるデータベースと、データベースの各属性の各属性値についての一般化階層と入力される。データベースの例及び一般化階層の例を、それぞれ図３及び図７に示す。
【００１９】
リスト生成部１は、一般化レベルごとのデータの事前計算を行う。
【００２０】
言い換えれば、リスト生成部１は、データベースの各属性の各属性値についての一般化階層に基づいて、データベースの各属性の各属性値を一般化階層の各一般化レベルまで一般化した値とその値を表す符号のリストを生成する。生成されたリストは、リスト記憶部２に記憶される。
【００２１】
その際、リスト生成部１は、データベースが圧縮されている場合には、データベースを解凍処理し、その解凍処理されたデータベースに基づいてリストを生成する。
【００２２】
以下、リスト生成部１の処理について詳細に説明する。
【００２３】
例えば、データベースが列指向データベースであり、列の部分ごとに圧縮されているデータベースである場合には、リスト生成部１は、まずデータベースから１列を取り出し、取り出した１列について解凍処理を行うことにより、その列の属性の各属性値を得る。例えば、図３のデータベースの１列目の「住所」という属性から「東京都武蔵野市緑町X-X-X」「神奈川県横須賀市光の丘Y-Y-Y」「神奈川県厚木市森ノ宮Z-Z-Z」という３個の属性値が得られたとする。
【００２４】
そして、リスト生成部１は、入力された一般化階層を用いて、得られた各属性値を、一般化階層の各一般化レベルまで一般化した値を得る。例えば、図４の上図に示すように、「東京都武蔵野市緑町X-X-X」という属性値を、一般化階層の住所の一般化レベル０まで一般化した値として「東京都武蔵野市緑町X-X-X」が得られ、一般化階層の住所の一般化レベル１まで一般化した値として「東京都武蔵野市緑町」が得られ、一般化階層の住所の一般化レベル２まで一般化した値として「東京都武蔵野市」が得られ、一般化階層の住所の一般化レベル３まで一般化した値として「東京都」が得られ、一般化階層の住所の一般化レベル４まで一般化した値として「関東地方」が得られたとする。
【００２５】
そして、リスト生成部１は、一般化後データの値（図４の例では、文字列）と、その値を表す符号のリストを生成する。その際、一般化後のデータのユニークな文字列の数が255以下であった場合は1byteの符号で、65535以下であった場合は2byteの符号で、4294967295以下であった場合は4byteの符号で一般化した値を表現することで、メモリの消費量を抑えることができる。
【００２６】
符号化は、各一般化レベルごとに行われる。例えば、図４では、一般化階層の住所の一般化レベル２の一般化した値は、「東京都武蔵野市」「神奈川県横須賀市」「神奈川県厚木市」の３個である。このため、一般化階層の住所の一般化レベル２の一般化した値は、1byteの符号で表現することができる。図４では、「東京都武蔵野市」に「０」、「神奈川県横須賀市」に「１」、「神奈川県厚木市」に「２」という符号を割り当てている。
【００２７】
また、図４では、一般化階層の住所の一般化レベル３の一般化した値は、「東京都」「神奈川県」の２個である。このため、一般化階層の住所の一般化レベル３の一般化した値は、1byteの符号で表現することができる。図４では、「東京都」に「０」、「神奈川」に「１」という符号を割り当てている。
【００２８】
図４が、一般化階層の住所のリストの例である。リスト生成部１は、上記の処理を、データベースの各属性に対して行うことにより、一般化階層の各属性のリストを生成する。
【００２９】
＜リスト記憶部２＞
リスト生成部１で生成されたリスト、一般化階層の各属性のリストは、リスト記憶部２に記憶される。
【００３０】
＜探索部３＞
探索部３は、ラティス構造の各ノードに対応する一般化レベルまでデータベースを一般化した一般化データベースがk-匿名性を有するかどうかを、リスト記憶部２から読み込んだリストを参照することにより得られる符号で表された一般化データベースに基づいて判定することにより、k-匿名性を有するラティス構造のノードを並列に探索する（ステップＳ３）。探索により見つかったk-匿名性を有するラティス構造のノードは、出力部４に出力される。
【００３１】
ここで、ラティス構造は、データベースの各属性の一般化レベルを表すノードから構成される。ラティス構造の例は、図８に示したラティス構造である。
【００３２】
例えば、探索部３は、ラティス構造のノードを並列に深さ優先で探索する。図５に、深さ優先探索のアルゴリズムの例を示す。探索部３が、ステップＳ３１からステップＳ３１２の処理を行う。
ステップＳ３１において、探索部３は、「空のスタックを用意する。」処理を行う。
ステップＳ３２において、探索部３は、「ラティス構造のボトムノードをスタックに入力する。」処理を行う。
ステップＳ３３において、探索部３は、スタックが空であるかどうかを判断する。スタックが空でない場合には、ステップＳ３４からステップＳ３１１の処理が行われる。スタックが空である場合には、処理を終了する。
ステップＳ３４において、探索部３は、「スタックからノードを取り出す。」処理を行う。
ステップＳ３５において、探索部３は、「取り出したノードに探索済みフラグを付ける。」処理を行う。
ステップＳ３６において、探索部３は、「取り出したノードに対応する一般化レベルまでデータベースを一般化する。その際、リストに保持されているデータを参照する形で一般化を行う。」処理を行う。言い換えれば、ステップＳ３６において、探索部３は、リスト記憶部２から読み込んだリストを参照することにより符号で表された一般化データベースを得る処理を行う。事前に得られたリストを用いることにより、一般化処理を行う際の消費メモリ量を少なくすることができる。
ステップＳ３７において、探索部３は、取り出したノードに対応する一般化レベルまで一般化され符号で表された一般化データベースがk-匿名性を満たしていないか判断する。その際、探索部３は、符号化されたデータを組み合わせてクロス集計を計算し、最小のクロス集計値をk-匿名性のk値として評価すれば良い。削除が伴う場合は、k-匿名性を満たさないレコードを削除し、改めてk-匿名性を評価すれば良い。
符号で表された一般化データベースがk-匿名性を満たしていない場合には、ステップＳ３８の処理が行われる。符号で表された一般化データベースがk-匿名性を満たしている場合には、ステップＳ３９及びステップＳ３１０の処理が行われる。
ステップＳ３８において、探索部３は、「現在のノードに接続している親ノードのうち、未探索な親ノードをスタックに入力する。」処理を行う。
ステップＳ３９において、探索部３は、「現在のノードを最適なk-匿名性を満たすノードとする。」処理を行う。
ステップＳ３１０において、探索部３は、「現在のノードに接続している親ノードはこれ以上の探索の必要がないため、再帰的に探索済みフラグを付ける。」処理を行う。  
【００３３】
ステップＳ３３からステップＳ３１２のwhileループ内が独立な処理のため、複数スレッドを用いた効率的な探索が可能である。言い換えれば、探索部３は、スタックに積まれた各ノードに対して、whileループ内の処理を並列に行うことができる。
【００３４】
より効率を高めるために、探索部３は、例えばスレッドセーフなスタックを用いることができる。そうすることで、明示的にロックを取得せずに済むので、さらに効率が良い実行が可能となる。例えば、スレッドセーフなスタックとして、Java（登録商標）言語であればBlockingDeque などがある。
【００３５】
探索部３は、ラティス構造のノードを並列に幅優先で探索してもよい。図６に、幅優先探索のアルゴリズムの例を示す。探索部３が、ステップＳ３１’からステップＳ３１２’の処理を行う。この幅優先探索のアルゴリズムは、スタックをキューに変えた以外は、図５の深さ優先探索のアルゴリズムと同じである。
【００３６】
＜出力部４＞
出力部４には、データベースと、一般化階層と、探索部３の探索により見つかったk-匿名性を有するラティス構造のノードとが入力される。
【００３７】
まず、出力部４は、データベース及び一般化階層を用いて、探索部３の探索により見つかったk-匿名性を有するラティス構造のノードに対応する一般化レベルまでデータベースを一般化する。そして、一般化したデータベース、言い換えればk-匿名化されたデータベースを出力する。
【００３８】
このようにして、出力部４は、探索部３の探索により見つかった、k-匿名性を有する上記ラティス構造のノードに対応する一般化レベルまでデータベースを一般化した一般化データベースを出力する（ステップＳ４）。
【００３９】
探索部３の探索により見つかったk-匿名性を有するラティス構造のノードが複数ある場合には、出力部４は、これらの複数のノードの少なくとも１つのそれぞれに対応する一般化レベルまでデータベースを一般化した一般化データベースを出力する。
【００４０】
上記実施形態のポイントの１つは、リスト生成部１における事前計算で一般化処理を行う際に更に符号化処理を行うことである。これにより、探索部３では、符号で表された一般化データベースに対する処理を行うことができるため、探索部３の処理におけるメモリ消費量を減らすことができる。
【００４１】
従来技術の場合、すなわち単一スレッドによる処理を行う場合、一般化処理を適宜行ったほうが消費メモリ量が少なくて済む。しかしながら、従来技術を単純に複数スレッドによる処理に拡張した場合、並列化により同時に複数の一般化処理を行ってしまうため、一時的に大量のメモリを消費する可能性がある。そのため、上記の実施形態のように、符号化しコンパクトに一度だけ一般化されたデータを保持し、探索部３における並列処理時には参照する。これにより、並列数を上げた場合にも、消費メモリ量が並列数に対し比例で増えない利点がある。例えば、図７の場合、日付が３つ、性別が２、住所が５つの一般化データが得られる。
【００４２】
［プログラム及び記録媒体］
例えば、k-匿名化装置の各部における処理をコンピュータによって実現する場合、k-匿名化装置の各部が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各部の処理がコンピュータ上で実現される。
【００４３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４４】
また、各部の処理は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理の少なくとも一部をハードウェア的に実現することとしてもよい。
【００４５】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図１】
2019073967.tif 000003
【図２】
2019073967.tif 000004
【図３】
2019073967.tif 000005
【図４】
2019073967.tif 000006
【図５】
2019073967.tif 000007
【図６】
2019073967.tif 000008
【図７】
2019073967.tif 000009
【図８】
2019073967.tif 000010
【手続補正書】
【提出日】令和2年3月24日(2020.3.24)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
図８に、ラティス構造の例を示す。図８は、図７で示した日付（深さ３）、性別（深さ２）、住所（深さ５）の階層の一般化階層のラティス構造の例である。（０，０，０）はそれぞれレベル０の値であり、例えば日付を１階層上げた場合（１，０，０）となる。図８の右側に示すラティスのレベルは、階層上げを何回行ったかを表している。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
【非特許文献１】Khaled El Emam, Fida Kamal Dankar, Romeo Issa, Elizabeth Jonker, Daniel Amyot, Elise Cogo, Jean-Pierre Corriveau, Mark Walker, Sadrul Chowdhury, Regis Vaillancourt, et al. "A globally optimal k-anonymity method for the de-identification of health data. Journal of the American Medical Informatics Association", Vol. 16, No. 5, pp. 670-682, 2009.
【非特許文献２】Florian Kohlmayer, Fabian Prasser, Claudia Eckert, Alfons Kemper, and Klaus A.Kuhn. "Flash: efficient, stable and optimal k-anonymity", In Privacy, Security, Risk and Trust (PASSAT), 2012 International Conference on and 2012 International Conference on Social Computing (SocialCom), pp. 708-717. IEEE, 2012.
【非特許文献３】Kristen LeFevre, David J.DeWitt, and Raghu Ramakrishnan. "Incognito: Efficient full-domain k-anonymity", In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 49-60, 2005.
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
【図１】k-匿名化装置の例を示すブロック図。
【図２】k-匿名化方法の例を示す流れ図。
【図３】データベースの例を示す図。
【図４】符号化及びリストの例を示す図。
【図５】深さ優先探索のアルゴリズムの例を示す図。
【図６】幅優先探索のアルゴリズムの例を示す図。
【図７】一般化階層の例を示す図。
【図８】ラティス構造の例を示す図。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】変更
【補正の内容】
【００２９】
＜リスト記憶部２＞
リスト生成部１で生成された、一般化階層の各属性のリストは、リスト記憶部２に記憶される。
【手続補正５】
【補正対象書類名】図面
【補正対象項目名】図２
【補正方法】変更
【補正の内容】
【図２】
2019073967.tif 000011
【国際調査報告】
2019073967.tif 000012
2019073967.tif 000013
2019073967.tif 000014
2019073967.tif 000015