(57)【特許請求の範囲】
【請求項１】
データクレンジングを行うシステムであって、プロセッサ及びメモリを有し、
前記プロセッサは、
前記メモリからデータテーブルを読み出し、
前記データテーブルのレコード間の類似度を算出し、
前記データテーブルの各レコードを一意に識別可能とするカラムの組であるＵＣＣ（Ｕｎｉｑｕｅ  Ｃｏｌｕｍｎ  Ｃｏｍｂｉｎａｔｉｏｎ）を検出し、
前記類似度及びＵＣＣを表示する
データクレンジングシステム。
【請求項２】
前記プロセッサは、
前記データテーブルからハッシュ行列を生成し、
その生成したハッシュ行列を用いて、前記類似度の算出及び前記ＵＣＣの検出を行う
請求項１に記載のデータクレンジングシステム。
【請求項３】
前記プロセッサは、ＭｉｎＨａｓｈ法に基づいて、前記データテーブルのレコード間の類似度を算出する
請求項２に記載のデータクレンジングシステム。
【請求項４】
前記プロセッサは、
その生成したハッシュ行列から、前記データテーブルの各カラムのカーディナリティを算出し、
その算出したカーディナリティが所定の閾値以下のカラムをＵＣＣの候補から除外する
請求項２に記載のデータクレンジングシステム。
【請求項５】
前記プロセッサは、
前記データテーブルの内容を表示するにあたり、類似度の高いレコードを上位に表示すると共に、前記ＵＣＣに含まれるカラムを他のカラムと区別可能な態様で表示し、
前記データテーブルの値の変更を受け付ける
請求項１に記載のデータクレンジングシステム。
【請求項６】
前記プロセッサは、
複数のＵＣＣが存在する場合、ＵＣＣの選択を受け付け、
その選択されたＵＣＣに含まれるカラムを他のカラムと区別可能な態様で表示する
請求項５に記載のデータクレンジングシステム。
【請求項７】
前記プロセッサは、
前記ＵＣＣに含まれるカラムの値が変更された場合、ＵＣＣの再検出を行う
請求項５に記載のデータクレンジングシステム。
【請求項８】
データクレンジングを行う方法であって、
データテーブルを取得し、
前記データテーブルのレコード間の類似度を算出し、
前記データテーブルの各レコードを一意に識別可能とするカラムの組であるＵＣＣ（Ｕｎｉｑｕｅ  Ｃｏｌｕｍｎ  Ｃｏｍｂｉｎａｔｉｏｎ）を検出し、
前記類似度及びＵＣＣを表示する
データクレンジング方法。
【請求項９】
データクレンジングを行うシステムに、
データテーブルを取得し、
前記データテーブルのレコード間の類似度を算出し、
前記データテーブルの各レコードを一意に識別可能とするカラムの組であるＵＣＣ（Ｕｎｉｑｕｅ  Ｃｏｌｕｍｎ  Ｃｏｍｂｉｎａｔｉｏｎ）を検出し、
前記類似度及びＵＣＣを表示する
ことを実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データクレンジングに関する。
【背景技術】
【０００２】
企業内に散在するデータを統合し、業務分析に活用するソリューションが注目されている。その実現のためには、トランザクションデータに含まれる属性が過不足なく格納されているマスタデータが必要である。マスタデータは、それが表現するエンティティのインスタンスとレコードとが１対１に対応付けられている必要がある。すなわち、各レコードは、他のレコードに対して一意に識別可能である必要がある。【０００３】
しかし、多くの企業のマスタデータは、活用に適さない状態であることが多い。すなわち、多くのマスタデータが、人間によって入力されたデータを基に作成されているため、入力ミスや運用上の不備などの様々な原因により、レコードの一意性を失っており、重複レコードを含んでいることが多い。それ以外にも、企業合併等で複数のマスタデータを統合する際に、重複レコードが問題となることもある。【０００４】
なお、レコードの一意性とは、マスタデータのエンティティに関する意味論上の一意性であることに注意する。例えば、従業員マスタや顧客マスタなど、人物をエンティティの単位とするマスタデータの場合、個人名や住所表記などのデータには、表記の揺れ、別称、又は省略など、表現としての曖昧さが生じ得る。また、いわゆる半角文字と全角文字の区別など、文字符号化の多様性による曖昧さも生じ得る。または、全くの同姓同名であっても別人ということも生じ得る。したがって、人物をエンティティの単位とするマスタデータでは、このような表記上の曖昧さが存在することを前提として（可能ならば一定のルールに従って表記を統一した上で）、各レコードがただ一人の人物に対応しており、同一人物が複数のレコードに存在しないことが重要である。【０００５】
マスタデータにおける重複レコードとは、表記上の異同に関わらず、そのレコードの示すエンティティが重複していることをいう。企業内のデータを活用するためには、マスタデータに含まれ得るこのような重複レコードを、人手で調査及び修正する作業が必要である。この作業は、一般にデータクレンジングと呼ばれる。【０００６】
データクレンジングを支援する技術として、類似するレコードを検出する技術が知られている。重複レコードは、表記上の曖昧さを含むため、単純な文字列マッチングで検出できるとは限らない。しかし、レコード間の表記上の差異が少ないもの、すなわち、類似するレコード同士は、重複レコードである可能性が高い。特許文献１には、データテーブルの各レコードから特徴ベクトルを生成して相互に比較することにより、類似するレコードを検出する技術が開示されている。【０００７】
データテーブルにおいて、レコードを一意に識別可能とするカラムは、「キー」と呼ばれる。キーは人工的に作成することもあるが、カラムに格納されている値（「カラム値」という）が全て異なる場合（つまり一意性が保証されている場合）、当該カラムは、キーとして採用可能である。また、１つのカラムでは一意性を保証できなくとも、複数のカラムの組み合わせが一意性を保証するならば、当該複数のカラムの組み合わせは、複合キーとして採用可能である。このような、レコードを一意に識別可能とするカラムの組み合わせをＵＣＣ（Ｕｎｉｑｕｅ  Ｃｏｌｕｍｎ  Ｃｏｍｂｉｎａｔｉｏｎ）と呼ぶ。特許文献２には、ＵＣＣを検出する技術が開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許出願公開第２００７／０００５５５６号明細書
【特許文献２】国際公開第２０１４／１９１０５９号
【発明の概要】
【発明が解決しようとする課題】
【０００９】
マスタデータのデータクレンジングを支援するために上述の類似するレコードを検出する技術を採用したとしても、或るレコードを重複レコードと見做して削除すべきか、それともそのレコード自体は残し、表記揺れ等を修正すべきかなどの最終的な判断は、データクレンジングの担当者が行う。データクレンジングの担当者は、目視で重複レコードを発見し、レコードを削除すべきか、それとも表記を修正すべきかなどを判断する必要がある。しかしながら、企業内マスタデータが、１００個を超えるような多数のカラムで構成されていたり、多くのカラムが用途不明であったりすることも多い。このような場合、データクレンジングの担当者の作業負担は、非常に大きい。【００１０】
また、表記揺れの統一や全角文字と半角文字との統一など、データテーブルを修正した結果、レコードの一意性を保証していたキー（カラム）が、一意性を保証しなくなることが発生し得る。特に、レコードの一意性を保証している複合キーが、データテーブルの修正によって一意性を保証しなくなった場合、データクレンジング担当者が、その複合キーの一意性の喪失を見落としてしまう可能性が高い。【００１１】
すなわち、従来技術では、データクレンジング担当者の作業負担が大きく、また、当該担当者の修正作業によって生じ得るキー又は複合キーの喪失が見落とされてしまうおそれがある。そこで本発明の目的は、データクレンジングの作業効率及び／又は作業精度を向上させることにある。
【課題を解決するための手段】
【００１２】
一実施例に係るデータクレンジングシステムは、プロセッサ及びメモリを有する。当該プロセッサは、メモリからデータテーブルを読み出し、データテーブルのレコード間の類似度を算出し、前記データテーブルの各レコードを一意に識別可能とするカラムの組であるＵＣＣ（Ｕｎｉｑｕｅ  Ｃｏｌｕｍｎ  Ｃｏｍｂｉｎａｔｉｏｎ）を検出する。
【発明の効果】
【００１３】
本発明によれば、データクレンジングの作業効率及び／又は作業精度を向上させることができる。
【図面の簡単な説明】
【００１４】
【図１】データクレンジングシステムの物理的な構成例を示す。
【図２】データクレンジングシステムが有する機能の構成例を示す。
【図３】メタデータ生成部に含まれる機能の例を示す。
【図４】データ表示処理の例を示すフローチャートである。
【図５】データテーブルの例を示す。
【図６】類似レコードマトリクスの例を示す。
【図７】ＵＣＣリストの例を示す。
【図８】メタデータ生成処理の例を示すフローチャートである。
【図９】ハッシュ行列の例を示す。
【図１０】ＭｉｎＨａｓｈシグネチャの例を示す。
【図１１】ポジションリストインデックス（ＰＬＩ）の例を示す。
【図１２】類似レコードマトリクスの生成処理の一例を示すフローチャートである。
【図１３】ＵＣＣ候補カラムの抽出処理の一例を示すフローチャートである。
【図１４】ＵＣＣリストの生成処理の一例を示すフローチャートである。
【図１５】データ編集処理の一例を示すフローチャートである。
【図１６】メタデータ再生成処理の一例を示すフローチャートである。
【図１７】データテーブル表示画面の例を示す。
【図１８】改良データテーブル表示画面の例を示す。
【発明を実施するための形態】
【００１５】
以下、実施例を説明する。以下の説明では、「ｘｘｘテーブル」又は「ｘｘｘリスト」の表現にて情報を説明することがあるが、情報は、どのようなデータ構造で表現されていてもよい。すなわち、情報がデータ構造に依存しないことを示すために、「ｘｘｘテーブル」又は「ｘｘｘリスト」を「ｘｘｘ情報」と呼ぶことができる。さらに、各情報の内容を説明する際に、「識別情報」、「識別子」、「名」、「名前」、「ＩＤ」という表現を用いるが、これらについてはお互いに置換が可能である。
【００１６】
また、以下の説明では、「プログラム」を主語として処理を説明する場合があるが、プログラムは、プロセッサ（例えばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ））によって実行されることで、定められた処理を、適宜に記憶資源（例えばメモリ）及び通信インターフェイスデバイスのうちの少なくとも１つを用いながら行うため、処理の主語が、プロセッサ、そのプロセッサを有する装置とされてもよい。プロセッサが行う処理の一部又は全部が、ハードウェア回路で行われてもよい。コンピュータプログラムは、プログラムソースからインストールされてよい。プログラムソースは、プログラム配布サーバ又は記憶メディア（例えば可搬型の記憶メディア）であってもよい。
【００１７】
また、以下の説明では、同種の要素を区別して説明する場合には、「ＰＬＩ３０３Ａ」、「ＰＬＩ３０３Ｂ」のように、参照符号を使用し、同種の要素を区別しないで説明する場合には、「ＰＬＩ３０３」のように参照符号のうちの共通番号のみを使用することがある。
【００１８】
図１は、データクレンジングシステム１００の物理的な構成例を示す。
【００１９】
データクレンジングシステム１００は、計算機の一例であり、プロセッサ１０１、メモリ１０２、ストレージ１０３、ネットワークインタフェース１０４及びコンソール１０５を有する。データクレンジングシステム１００の例は、パーソナルコンピュータ、ラックマウントサーバ又はブレードサーバ等である。プロセッサ１０１は、メモリ１０２、ストレージ１０３、ネットワークインタフェース１０４及びコンソール１０５と、双方向通信可能に接続されている。データクレンジングシステム１００は、これらの構成要素の一部のみを有しても良いし、複数の同じ構成要素を有してもよい。
【００２０】
プロセッサ１０１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）等のハードウェアによる演算装置であり、メモリ１０２からプログラムを読み出して実行する。
【００２１】
メモリ１０２は、揮発性の半導体メモリから構成され、プログラムやデータなどを保持する。メモリ１０２の例は、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＭＲＡＭ（Ｍａｇｎｅｔｏｒｅｓｉｓｔｉｖｅ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＦｅＲＡＭ（Ｆｅｒｒｏｅｌｅｃｔｒｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
【００２２】
ストレージ１０３は、不揮発性の記憶装置から構成され、プログラムやデータなどを保持する。ストレージ１０３の例は、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）、又はこれらの組み合わせなどである。
【００２３】
ネットワークインタフェース１０４は、例えば、ＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃｏｎｔｒｏｌｌｅｒ）等の通信デバイスで構成され、ネットワーク１０６と接続される。ネットワークインタフェース１０４は、ネットワーク１０６を介して他の装置と通信するためのプロトコルを制御する。ネットワーク１０６の例は、イーサネット（登録商標）、ＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ）８０２．１１規格に基づく無線ネットワーク、ＳＯＮＥＴ／ＳＤＨ（Ｓｙｎｃｈｒｏｎｏｕｓ  Ｏｐｔｉｃａｌ  Ｎｅｔｗｏｒｋ／Ｓｙｎｃｈｒｏｎｏｕｓ  Ｄｉｇｉｔａｌ  Ｈｉｅｒａｒｃｈｙ）規格に基づく広域ネットワーク、又は、これら複数のネットワーク技術を組み合わせたネットワークなどである。
【００２４】
コンソール１０５は、例えば、キーボード及びマウス等の入力装置と、液晶表示パネル等のディスプレイ装置とから構成される。コンソール１０５は、入力装置から入力された操作に対応する操作信号を受信し、その操作信号の内容をプロセッサ１０１に通知してよい。そして、コンソール１０５は、プロセッサ１０１から出力される、テキスト情報、グラフィカル情報に基づくテキスト及び画像等を、ディスプレイ装置に表示する。
【００２５】
ストレージ１０３に格納されているＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）やユーザプログラムは、データクレンジングシステム１００の起動時又はそれ自身の実行時に、メモリ１０２に読み出されてよい。そして、プロセッサ１０１が、メモリ１０２に読み出されたＯＳ及びユーザプログラムを実行することによって、データクレンジングシステム１００の有する各種機能が実現されてよい。プロセッサ１０１が実行するプログラムは、リムーバブルメディア（ＣＤ−ＲＯＭ、フラッシュメモリ等）又はネットワークなどを介してデータクレンジングシステム１００に導入され、ストレージ１０３に格納されてよい。このため、データクレンジングシステム１００は、リムーバブルメディアからデータを読み込むインターフェースを有してよい。
【００２６】
図２は、データクレンジングシステム１００が有する機能の構成例を示す。
【００２７】
データクレンジングシステム１００は、機能として、表示部２０２、操作部２０３、データ編集部２０４、入出力部２０５及びメタデータ生成部２０６を有する。これらの機能は、メモリ１０２に格納されたプログラムがプロセッサ１０１で実行されることにより実現されてよい。
【００２８】
操作部２０３は、コンソール１０５を通じて入力された操作内容を、各種命令として解釈する。操作部２０３は、データ表示命令を表示部２０２に渡し、データ編集命令をデータ編集部２０４に渡してよい。
【００２９】
入出力部２０５は、ストレージ１０３に格納されているデータファイル１０７を読み出し、データテーブル２０１としてメモリ１０２に格納する。
【００３０】
メタデータ生成部２０６は、メモリ１０２に格納されているデータテーブル２０１に基づいて、メタデータ２０７を生成する。メタデータ生成部２０６は、その生成したメタデータ２０７をメモリ１０２に格納してよい。メタデータ生成部２０６の詳細については後述する。
【００３１】
表示部２０２は、コンソール１０５を通じてデータクレンジングに関する情報を表示する。表示部２０２は、データテーブル２０１及びメタデータ２０７に係る情報を、コンソール１０５を通じて表示してよい。また、表示部２０２は、操作部２０３から受領したデータ表示命令の内容に応じて、情報の表示態様を変えてよい。
【００３２】
なお、処理負荷の分散や可用性の向上等のため、上述の機能の一部又は全部は、複数のデータクレンジングシステム１００に分散されてもよい。また、データクレンジングシステム１００は、１つの物理的な計算機で、又は、複数の論理的又は物理的な計算機で構成されてもよい。データクレンジングシステム１００が複数の物理計算機で構成される場合、上述の機能は、複数のプロセッサ１０１がネットワーク１０６を介して通信を行うことで、実現されてよい。
【００３３】
図３は、メタデータ生成部２０６に含まれる機能の例を示す。
【００３４】
メタデータ生成部２０６は、機能として、類似レコード検出部２０８、ＵＣＣ検出部２０９、ハッシュ行列生成部２１０を含んでよい。メタデータ２０７は、類似レコードマトリクス２５０、ＵＣＣリスト２６０を含んでよい。
【００３５】
ハッシュ行列生成部２１０は、データテーブル２０１から、ハッシュ行列３０１（図９参照）を生成する。
【００３６】
類似レコード検出部２０８は、ハッシュ行列生成部２１０が生成したハッシュ行列３０１を用いて、データテーブル２０１に含まれるレコード間の類似度を算出する。類似レコード算出部２０８は、その算出した類似度を、類似レコードマトリクス２５０に格納してよい。
【００３７】
ＵＣＣ検出部２０９は、ハッシュ行列生成部２１０が生成したハッシュ行列３０１を用いて、データテーブル２０１からＵＣＣ（カラムのセット）を検出する。ＵＣＣ検出部２０９は、その検出したＵＣＣを、ＵＣＣリスト２６０に登録してよい。
【００３８】
類似レコード検出部２０８とＵＣＣ検出部２０９とは、ハッシュ行列生成部２１０が生成した同じハッシュ行列３０１を用いてよい。これにより、類似レコード検出用のハッシュ行列と、ＵＣＣ検出用のハッシュ行列とを別々に生成する場合と比較して、システム全体の処理量を減らすことができる。
【００３９】
図４は、データ表示処理の例を示すフローチャートである。
【００４０】
入出力部２０５は、ストレージ１０３からデータファイル１０７を読み出す（ステップＳ４０２）。
【００４１】
入出力部２０５は、例えば、ＣＳＶ（Ｃｏｍｍａ−Ｓｅｐａｒａｔｅｄ  Ｖａｌｕｅｓ）形式等のフォーマットでシリアライズされているデータファイル１０７をパージングして、データテーブル２０１（図５参照）を生成する（ステップＳ４０４）。
【００４２】
メタデータ生成部２０６は、その生成したデータテーブル２０１からメタデータ２０７を生成し、メモリ１０２に格納する（ステップＳ４０６）。当該処理の詳細については後述する。
【００４３】
表示部２０２は、データテーブル２０１及びメタデータ２０７を、コンソール１０５を通じて表示する（ステップＳ４０８）。当該表示例については後述する（図１７、図１８参照）。
【００４４】
図５は、データテーブル２０１の例を示す。
【００４５】
データテーブル２０１は、本実施例におけるデータクレンジングの対象データである。データテーブル２０１には、どのようなデータが格納されていてもよい。データテーブル２０１は、複数のレコードと複数のカラムとから構成されており、レコードの各カラムには、値（カラム値又はセル値という）が格納されてよい。
【００４６】
本実施例では、説明のために、各レコードに、レコードを一意に識別可能なレコードＩＤ（Ｒ００１、Ｒ００２、…）を付与する。また、各カラムに、カラムを一意に識別可能なカラムＩＤ（Ｃ００１、Ｃ００２、…）を付与する。レコードＩＤ及び／又はカラムＩＤは、元のデータファイル１０７に含まれている必要はなく、入出力部２０５のパージング処理によって付与されてよい。レコードＩＤはレコード名と呼んでもよい。カラムＩＤはカラム名と呼んでもよい。
【００４７】
図５の例は、レコードＩＤ「Ｒ００１」のレコードは、カラムＩＤ「Ｃ００１」にカラム値「ＡＡＡ」、カラムＩＤ「Ｃ００２」にカラム値「ＣＣＣ」、カラムＩＤ「Ｃ００３」にカラム値「０」、カラムＩＤ「Ｃ００４」にカラム値「０」を有することを示す。
【００４８】
図６は、類似レコードマトリクス２５０の例を示す。類似レコードマトリクス２５０は、メタデータ２０７に含まれてよい。
【００４９】
類似レコードマトリクス２５０は、データテーブル２０１に含まれる２つのレコード間の類似度を管理する。
【００５０】
類似レコードマトリクス２５０における各行と各列には、それぞれ、データテーブル２０１に含まれる各レコードＩＤが付与されてよい。行のレコードＩＤと列のレコードＩＤとの交点のセルには、当該行のレコードＩＤのレコードと、当該列のレコードＩＤのレコードとの間の類似度が格納されてよい。
【００５１】
類似度は、値が大きいほど類似することを示す、０〜１の範囲を取り得る値であってよい。図６の例は、レコードＩＤ「Ｒ００２」と「Ｒ００１」との間の類似度が「０．８０」である（比較的類似している）ことを示す。
【００５２】
図７は、ＵＣＣリスト２６０の例を示す。ＵＣＣリスト２６０は、メタデータ２０７に含まれてよい。
【００５３】
ＵＣＣリスト２６０は、データテーブル２０１の各レコードを一意に識別可能なカラムＩＤの組（つまりＵＣＣ）を管理する。
【００５４】
例えば、カラムＩＤ「Ｃ００１」のカラム値とカラムＩＤ「Ｃ００２」のカラム値との組によって、データテーブル２０１の全てのレコードを一意に識別可能な場合、そのカラムＩＤ「Ｃ００１」及び「Ｃ００２」の組は、ＵＣＣである。この場合、ＵＣＣリスト２６０には、カラムＩＤ「Ｃ００１」及び「Ｃ００２」の組が格納される。
【００５５】
ＵＣＣリスト２６０において、各ＵＣＣには、ＵＣＣ（カラムＩＤの組）を一意に識別可能なＵＣＣ  ＩＤ（Ｕ００１、Ｕ００２、…）が付与されてよい。
【００５６】
図８は、メタデータ生成処理の例を示すフローチャートである。
【００５７】
メタデータ生成部２０６は、或るハッシュ関数を用いて、データテーブル２０１の各カラム値のハッシュ値を算出する（ステップＳ６０２）。
【００５８】
メタデータ生成部２０６は、その算出したハッシュ値を用いて、データテーブル２０１に対するハッシュ行列３０１（図９参照）を生成する（ステップＳ６０４）。
【００５９】
メタデータ生成部２０６は、その生成したハッシュ行列３０１を用いて、類似レコードマトリクス２５０（図６参照）及びＵＣＣリスト２６０（図７参照）を生成する（ステップＳ６０６）。
【００６０】
図９は、ハッシュ行列３０１の例を示す。
【００６１】
ハッシュ行列３０１は、データテーブル２０１の各カラム値に対して、或るハッシュ関数を適用して算出されるハッシュ値で構成される行列である。ハッシュ行列３０１は、異なるハッシュ関数毎に生成されてよい。本実施例では、各ハッシュ関数を一意に識別可能なＩＤを「ハッシュ関数ＩＤ」と呼ぶ。
【００６２】
ハッシュ行列３０１は、各行と各列に、それぞれ、データテーブル２０１の各レコードＩＤと各カラムＩＤとを有してよい。行のレコードＩＤと列のカラムＩＤとの交点のセルには、データテーブル２０１の当該レコードＩＤのレコードにおける、当該カラムＩＤのカラム値のハッシュ値が格納されてよい。
【００６３】
なお、図９では、説明のために、行にレコードＩＤ、列にカラムＩＤが付与されている。実際にメモリに格納されるハッシュ行列３０１には、このようなＩＤが付与されていなくてもよい。
【００６４】
図１０は、ＭｉｎＨａｓｈシグネチャ３０２の例を示す。
【００６５】
ＭｉｎＨａｓｈシグネチャ３０２は、ＭｉｎＨａｓｈ法に用いられる。ＭｉｎＨａｓｈシグネチャ３０２は、ハッシュ行列３０１に基づいて生成されてよい。
【００６６】
説明のために、図１０のＭｉｎＨａｓｈシグネチャ３０２の各行には、ハッシュ行列３０１の各レコードＩＤが付与されてよい。また、各列には、図９で述べた各ハッシュ関数ＩＤ（ｈ１、ｈ２、…）が付与されてよい。
【００６７】
ＭｉｎＨａｓｈシグネチャ３０２のレコードＩＤとハッシュ関数ＩＤとの交点のセルには、そのハッシュ関数ＩＤのハッシュ関数から生成されたハッシュ行列３０１における、そのレコードＩＤに属する複数のハッシュ値のうちの最小のハッシュ値が格納される。例えば、図９のハッシュ行列３０１が、ハッシュ関数ＩＤ「ｈ１」のハッシュ関数から生成されたものであるとすると、図１０のＭｉｎＨａｓｈシグネチャ３０２における、レコードＩＤ「Ｒ００１」とハッシュ関数ＩＤ「ｈ１」との交点のセルには、図９のハッシュ行列３０１のレコードＩＤ「Ｒ００１」のレコードに属する複数のハッシュ値「１２３４」、「４１２２」、「５６２８」、…、のうちの最小のハッシュ値「１２３４」が格納される。同様に、レコードＩＤ「Ｒ００１」とハッシュ関数ＩＤ「ｈ２」との交点の欄には、ハッシュ関数ＩＤ「ｈ２」のハッシュ関数から生成ハッシュ行列のレコードＩＤ「Ｒ００１」に属する複数のハッシュ値のうちの最小のハッシュ値が格納される。
【００６８】
なお、ハッシュ関数ＩＤ「ｈ１」のハッシュ関数で算出したハッシュ値を循環シフトし、その循環シフトした値と乱数との間でＸＯＲを算出し、その算出した値を、ハッシュ関数ＩＤ「ｈ２」に係るハッシュ値に相当する値として用いてもよい。この場合、ＭｉｎＨａｓｈシグネチャ３０２において、ハッシュ関数ＩＤ「ｈ２」のセルには、ハッシュ関数ＩＤ「ｈ２」に係るハッシュ値に相当する値のうちの最小値が格納されてよい。
【００６９】
図１１は、ポジションリストインデックス（ＰＬＩ）３０３の例を示す。
【００７０】
ＰＬＩ３０３は、データテーブル２０１のカラムＩＤ毎に生成されてよい。図１１の例において、ＰＬＩ３０３Ａはデータテーブル２０１のカラムＩＤ「Ｃ００１」に係るＰＬＩである。ＰＬＩ３０３Ｂ、３０３Ｃ、３０３Ｄについても同様である。
【００７１】
或るカラムＩＤに係るＰＬＩ３０３は、ハッシュ行列３０１における当該カラムＩＤの列に同一ハッシュ値を有する複数のレコードＩＤと、当該同一ハッシュ値と、を対応付けて管理する。
【００７２】
図１１の例において、ＰＬＩ３０３Ａは、ハッシュ行列３０１において、カラムＩＤ「Ｃ００１」の列に同一ハッシュ値「１２３４」を有する複数のレコードＩＤ「Ｒ００１」及び「Ｒ００３」が存在することを示す。
【００７３】
ＰＬＩ３０３の構造は、一般にハッシュテーブルとして知られるデータ構造に類似していることに注目されたい。ＰＬＩ３０３は、ハッシュ行列３０１が有するハッシュ値を活用してハッシュテーブルを生成し、二つ以上のエントリがあるバケットのみを取り出したものであってよい。
【００７４】
図１２は、類似レコードマトリクス２５０の生成処理の一例を示すフローチャートである。当該処理は、図８のステップＳ６０６の処理に相当する。
【００７５】
メタデータ生成部２０６は、データテーブル２０１に対応するＭｉｎＨａｓｈシグネチャ３０２を生成する（ステップＳ８０４）。ＭｉｎＨａｓｈシグネチャ３０２は、上述の図１０で説明したように生成されてよい。
【００７６】
メタデータ生成部２０６は、その生成したＭｉｎＨａｓｈシグネチャ３０２の複数の列を、幾つかのグループに分割してよい。ここでは、分割された各グループを、「バンド」と呼ぶ（ステップＳ８０６）。
【００７７】
メタデータ生成部２０６は、ＭｉｎＨａｓｈシグネチャ３０２の各レコードＩＤについて、バンドに属する列のハッシュ値を結合してよい。そして、メタデータ生成部２０６は、その結合したハッシュ値に対して所定のハッシュ関数を適用し、ハッシュ値を算出してよい（ステップＳ８０８）。メタデータ生成部２０６は、各バンドに対してこの処理を実行してよい。このハッシュ値の算出過程は、いわゆるＬＳＨ（Ｌｏｃａｌｉｔｙ  Ｓｅｎｓｉｔｉｖｅ  Ｈａｓｈｉｎｇ：局所性鋭敏型ハッシング）として知られるアルゴリズムであってよい。この場合、ハッシュ値が同一なレコードの組は、類似している可能性が高いことが知られている。
【００７８】
メタデータ生成部２０６は、そのハッシュ値が同一な全てのレコードの組のそれぞれについて、ステップＳ８１４の処理を実行する（ＬＯＯＰ２）。各ループ処理で選択されるレコードの組を「選択レコードの組」という。
【００７９】
メタデータ生成部２０６は、選択レコードの組のＭｉｎＨａｓｈシグネチャ３０２のハッシュ値が一致する確率を算出する（ステップＳ８１４）。この確率は、Ｊａｃｃａｒｄ距離と呼ばれる２集合間の類似度の指標を近似することが知られている。そこでこの確率を類似度とし、類似レコードマトリクス２５０に格納する。
【００８０】
図１３は、ＵＣＣ候補カラムの抽出処理の一例を示すフローチャートである。
【００８１】
本処理は、ＵＣＣリスト２６０の生成処理（図１４参照）の前に、ＵＣＣに含まれる可能性の高いカラム（「ＵＣＣ候補カラム」という）を抽出する処理である。この処理を行うことにより、ＵＣＣ検出の処理量を減らすことができる。
【００８２】
メタデータ生成部２０６は、ハッシュ行列３０１の全カラムのそれぞれについて、ステップＳ９０４〜Ｓ９０８を実行する（ＬＯＯＰ１）。各ループ処理で選択されるカラムを「選択カラム」という。
【００８３】
メタデータ生成部２０６は、ハッシュ行列３０１の選択カラムのハッシュ値を用いて、データテーブル２０１の当該選択カラムのカーディナリティを算出する（ステップＳ９０４）。カラムのカーディナリティは、当該カラムに格納されているカラム値の種類の数（異なり数）であってよい。ハッシュ値からカーディナリティを近似する方法として、ＨｙｐｅｒＬｏｇＬｏｇアルゴリズムを採用してもよい。
【００８４】
メタデータ生成部２０６は、その算出したカーディナリティが所定の閾値以下であるか否かを判定する（ステップＳ９０６）。当該判定結果が肯定的な場合（ステップＳ９０６：ＹＥＳ）、メタデータ生成部２０６は、選択カラムをＵＣＣ候補から除外する（ステップＳ９０８）。カーディナリティが低いカラムは、カラム値の異なり数が少ないため、ＵＣＣを構成する可能性が低いからである。
【００８５】
当該判定結果が否定的な場合（ステップＳ９０６：ＮＯ）、メタデータ生成部２０６は、特に何もしなくてよい。以上の処理により、ＵＣＣ候補カラムが抽出される。
【００８６】
図１４は、ＵＣＣリスト２６０の生成処理の一例を示すフローチャートである。当該処理は、図８のステップＳ６０６の処理に相当する。本処理は、図１３の処理で抽出されたＵＣＣ候補カラムから、ＵＣＣリストを生成する処理の例である。
【００８７】
メタデータ生成部２０６は、全てのＵＣＣ候補カラムのそれぞれについて、ステップＳ１００４〜Ｓ１００８を実行する（ＬＯＯＰ１）。各ループ処理で選択されるＵＣＣ候補カラムを、「選択ＵＣＣ候補カラム」という。
【００８８】
メタデータ生成部２０６は、選択ＵＣＣ候補カラムについて、ハッシュ行列３０１のハッシュ値を用いて、ＰＬＩ３０３を生成する（ステップＳ１００４）。
【００８９】
メタデータ生成部２０６は、ＰＬＩ３０３に、２以上のレコードＩＤを有するエントリが存在するか否かを判定する（ステップＳ１００６）。ＰＬＩ３０３に、２以上のレコードＩＤを有するエントリが存在しない場合（ステップＳ１００６：ＮＯ）、メタデータ生成部２０６は、選択ＵＣＣ候補カラムを、ＵＣＣリスト２６０に登録する（ステップＳ１００８）。選択ＵＣＣ候補カラムは、単独でレコードの一意性を保証し得るからである。ＰＬＩ３０３に、２以上のレコードＩＤを有するエントリが存在する場合（ステップＳ１００６：ＹＥＳ）、メタデータ生成部２０６は、特に何もしなくて良い。
【００９０】
次に、メタデータ生成部２０６は、上述の処理においてＵＣＣリストに登録されなかった残りのＵＣＣ候補カラムによる全ての組のそれぞれについて、ステップＳ１０１２〜Ｓ１０１６を実行する（ＬＯＯＰ２）。各ループ処理で選択されるＵＣＣ候補カラムの組を、「選択ＵＣＣ候補カラムの組」という。
【００９１】
メタデータ生成部２０６は、選択ＵＣＣ候補カラムの組に関するＰＬＩ３０３の各エントリをレコードＩＤの集合とみなし、共通集合を算出する（ステップＳ１０１２）。
【００９２】
メタデータ生成部２０６は、その算出した共通集合が空集合であるか否かを判定する（ステップＳ１０１４）。共通集合が空集合の場合（ステップＳ１０１４：ＹＥＳ）、メタデータ生成部２０６は、選択ＵＣＣ候補カラムの組を、ＵＣＣリスト２６０に登録する。この選択ＵＣＣ候補カラムの組は、当該カラムの組でレコードの一意性を保証し得るからである。共通集合が空集合でない場合（ステップＳ１０１４：ＮＯ）、メタデータ生成部２０６は、特に何もしなくてよい。
【００９３】
図１５は、データ編集処理の一例を示すフローチャートである。
【００９４】
データテーブル２０１が編集（修正）されると、それに応じてメタデータ２０７の内容も変化し得る。本処理は、データ編集処理と、それに応じて発生するメタデータ再生成処理の例である。
【００９５】
データ編集部２０４は、データ編集命令を受領すると（ステップＳ１１０２）、データテーブル２０１を編集する（ステップＳ１１０４）。このデータ編集命令は、コンソール１０５を通じてデータ編集の入力操作を受け付けた操作部２０３から、データ編集部２０４に渡されてよい。
【００９６】
メタデータ生成部２０６は、メタデータ２０７を再生成する（ステップＳ１１０６）。当該処理の詳細については後述する（図１６参照）。
【００９７】
表示部２０２は、編集されたデータテーブル２０１及び再生成されたメタデータ２０７の内容を、コンソール１０５を通じて表示する（ステップＳ１１０８）。
【００９８】
図１６は、メタデータ再生成処理の一例を示すフローチャートである。当該処理は、図１５のステップＳ１１０６の処理に相当する。
【００９９】
ここでは、レコード削除に係るデータ編集命令を受領した場合の例と、セル更新に係るデータ編集命令を受領した場合の例を示す。レコード削除に係るデータ編集命令は、例えば、クレンジング作業において、重複レコードと判定されたレコードを削除する場合に発行される。セル更新に係るデータ編集命令は、例えば、表記を統一するためにデータを書き換える場合に発行される。
【０１００】
メタデータ生成部２０６は、受領したデータ編集命令が、レコード削除及びセル更新の何れであるかを判定する（ステップＳ１２０２）。
【０１０１】
まず、レコード削除に係るデータ編集命令を受領した場合について説明する。当該処理では、ＰＬＩ３０３と類似レコードマトリクス２５０とを更新する処理が実行される。
【０１０２】
メタデータ生成部２０６は、削除対象のレコードに属する各カラム値のハッシュ値を、ハッシュ行列３０１から取得する（ステップＳ１２０６）。
【０１０３】
メタデータ生成部２０６は、各カラムのＰＬＩ３０３から、それぞれ、その取得したハッシュ値と、削除対象のレコードＩＤとを削除する（ステップＳ１２０８）。
【０１０４】
メタデータ生成部２０６は、削除対象のレコードＩＤを、ハッシュ行列３０１、ＭｉｎＨａｓｈシグネチャ３０２、及び、類似レコードマトリクス２５０から削除する（ステップＳ１２１０）。そして、本処理を終了する。
【０１０５】
次に、セル値の更新に係るデータ編集命令を受領した場合について説明する。当該処理では、ＵＣＣリスト２６０の更新処理が実行される。本処理の説明において、更新されたセル値を「更新セル値」という。
【０１０６】
メタデータ生成部２０６は、更新セル値からハッシュ値を算出し、その算出したハッシュ値を用いてハッシュ行列３０１を更新する（ステップＳ１２２２〜Ｓ１２２４）。
【０１０７】
メタデータ生成部２０６は、更新セル値を含むカラムのＰＬＩ３０３を更新する（ステップＳ１２２６）。
【０１０８】
メタデータ生成部２０６は、その更新セル値を含むカラムＩＤ（「更新カラムＩＤ」という）が、ＵＣＣリスト２６０に含まれているかを判定する（ステップＳ１２２８）。当該判定結果が肯定的な場合（Ｓ１２２８：ＹＥＳ）、メタデータ生成部２０６は、次のステップＳ１２３０の処理に進み、否定的な場合（ステップＳ１２２８：ＮＯ）、本処理を終了する。
【０１０９】
メタデータ生成部２０６は、更新カラムＩＤを含む各ＵＣＣについて、次のステップＳ１２３２〜Ｓ１２３６の処理を行う（ステップＳ１２３０）。
【０１１０】
すなわち、メタデータ生成部２０６は、更新カラムＩＤのＰＬＩ３０３から、更新されたハッシュ値のエントリを取得する。そして、メタデータ生成部２０６は、その取得したエントリのレコードＩＤ群と、他のＰＬＩ３０３のエントリのレコードＩＤ群との間の共通集合を算出する（ステップＳ１２３２）。
【０１１１】
メタデータ生成部２０６は、その算出した共通集合が空集合であるか否かを判定する（ステップＳ１２３４）。すなわち、メタデータ生成部２０６は、その取得したレコードＩＤ群が、他の何れのＰＬＩ３０３のレコードＩＤ群にも含まれていないか、それとも、他の何れかのＰＬＩ３０３のレコードＩＤ群に含まれているかを判定する。
【０１１２】
メタデータ生成部２０６は、共通集合が空集合で無い場合（ステップＳ１２３４：ＮＯ）、その空集合でないＰＬＩ３０３のカラムＩＤの組を、ＵＣＣリスト２６０から削除する（ステップＳ１２３６）。このカラムＩＤの組は、セル値の更新によってＵＣＣでなくなったからである。
【０１１３】
メタデータ生成部２０６は、共通集合が空集合の場合（ステップＳ１２３４：ＹＥＳ）、特に何もしなくてよい。
【０１１４】
なお、メタデータ生成部２０６は、上記の処理に加えて、類似レコードマトリクス２５０の更新処理を実行してもよい。
【０１１５】
以上の処理では、更新セル値を含むカラムがＵＣＣに属する場合にのみ、ＵＣＣリスト２６０の更新処理が実行される。すなわち、本実施例によれば、セル値が更新された場合におけるＵＣＣリスト２６０の更新処理量を減らすことができる。
【０１１６】
図１７は、データテーブル表示画面４００の例を示す。本画面は、図４のステップＳ４０８又は図１５のステップＳ１１０８の処理によって表示されてよい。
【０１１７】
表示部２０２は、データテーブル２０１に基づいて、図１７に示すようなデータテーブル表示画面４００を生成し、コンソール１０５に表示してよい。データテーブル表示画面４００には、データテーブル２０１のレコードＩＤとカラムＩＤとが合わせて表示されてよい。
【０１１８】
図１８は、改良データテーブル表示画面４０１の例を示す。本画面は、図４のステップＳ４０８又は図１５のステップＳ１１０８の処理によって表示されてよい。
【０１１９】
表示部２０２は、データテーブル２０１及びメタデータ２０７に基づいて、図１８に示すような改良データテーブル表示画面４０１を生成し、コンソール１０５に表示してよい。
【０１２０】
改良データテーブル表示画面４０１には、ＵＣＣリスト２６０に属するカラムＩＤ又はカラムＩＤ群を選択可能なボタン４０２が含まれてよい。データクレンジングの担当者がこのボタン４０２を押下すると、データテーブルにおけるそのボタン４０２によって選択されたカラムＩＤ又はカラムＩＤ群に相当する列が、他の列と区別可能な態様で（例えば異なる色で）強調表示されてよい（図１８の斜線部分を参照）。
【０１２１】
また、改良データテーブル表示画面４０１のレコード間の類似度表示エリア４０３には、類似レコードマトリクス２５０における当該レコード間の類似度が表示されてよい。このとき、表示部２０２は、類似度が高いレコードをできるだけ上位に表示してよい。例えば、表示部２０２は、類似度が高い順にレコードをソートして表示してよい。
【０１２２】
なお、図１８の改良データテーブル表示画面４０１は、あくまでメタデータ２０７に含まれる情報をコンソール１０５に表示する一例であり、その表示態様はこれに限定されるものではない。
【０１２３】
本実施例によれば、類似度の高いレコードを上位に表示することができる。これにより、データクレンジングの担当者は、データクレンジングが必要と思われるレコードを容易に見つけることができる。
【０１２４】
また、本実施例によれば、ＵＣＣに属するカラムを認識可能な態様で表示することができる。これにより、データクレンジングの担当者は、何れのセル値を修正するとＵＣＣの関係が喪失し得るのかを容易に認識することができる。
【０１２５】
さらに、本発明によれば、類似度の高いレコードとＵＣＣに属するカラムとを合わせて表示することができる。これにより、データクレンジングの担当者は、レコードの意味論上の一意性と表記上の一意性とを一致させつつ、データを修正することができる。すなわち、データクレンジングの担当者は、データクレンジングの作業を効率的に行うことができる。
【０１２６】
上述した実施例は、本発明の説明のための例示であり、本発明の範囲を実施例にのみ限定する趣旨ではない。当業者は、本発明の要旨を逸脱することなしに、他の様々な態様で本発明を実施することができる。
【０１２７】
例えば、或る実施例の構成の一部を他の実施例の構成に置き換えてもよい。或る実施例の構成に他の実施例の構成を加えてもよい。各実施例の構成の一部に対して、他の構成を追加、削除又は置換してもよい。
【０１２８】
また、上述した実施例における各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等により、ハードウェアで実現してもよく、プロセッサがそれぞれの機能を実現するプログラムを解釈し実行することにより、ソフトウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリ、ハードディスクドライブ、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等の記憶装置、又は、ＩＣカード、ＳＤカード、ＤＶＤ等の記録媒体に格納することができる。
【０１２９】
また、図面には、説明のために必要と考えられる制御線及び／又は情報線が示されており、実装において必要な全ての制御線及び／又は情報線が示されているわけではない。すなわち、図示されていない場合であっても、ほぼ全ての構成が相互に接続されていてよい。
【符号の説明】
【０１３０】
１００：データクレンジングシステム  ２０１：データテーブル  ２０６：メタデータ生成部  ２０８：類似レコード検出部  ２０９：ＵＣＣ検出部  ２１０：ハッシュ行列生成部
【図１】
0006549786.tif 000002
【図２】
0006549786.tif 000003
【図３】
0006549786.tif 000004
【図４】
0006549786.tif 000005
【図５】
0006549786.tif 000006
【図６】
0006549786.tif 000007
【図７】
0006549786.tif 000008
【図８】
0006549786.tif 000009
【図９】
0006549786.tif 000010
【図１０】
0006549786.tif 000011
【図１１】
0006549786.tif 000012
【図１２】
0006549786.tif 000013
【図１３】
0006549786.tif 000014
【図１４】
0006549786.tif 000015
【図１５】
0006549786.tif 000016
【図１６】
0006549786.tif 000017
【図１７】
0006549786.tif 000018
【図１８】
0006549786.tif 000019