(57)【要約】  １つ又は複数の探索ロケータフィールドを含む探索基準を規定するステップ（７１）と、前記探索基準におけるエラートレランスを最大にし、同時に、予め定められた応答時間要件を満たす検索式を前記探索基準から決定するステップと、前記データベースから前記候補レコードを検索（７２）し、前記応答時間要件を満たす検索式を見つけることができなければ、追加探索基準を要求し、探索基準ロケータフィールドと対応する検索レコードフィールドを比較して、前記各候補レコードを評価するステップ（７３）と、前記候補レコードの評点が予め定められたしきい値を超えるか否かを判定するステップ（７５）と、前記候補の評点が前記しきい値を超えると、前記探索基準に応答して戻されるレコードリストに前記候補レコードを追加するステップを含む、患者データベース探索におけるデータ依存型フィルタリング方法。
2008546098.tif 000002
【特許請求の範囲】
【請求項１】
１つ又は複数の探索ロケータフィールドを含む探索基準を規定するステップと、
前記探索基準におけるエラートレランスを最大にし、同時に、予め定められた応答時間要件を満たす検索式を前記探索基準から決定するステップと、
前記データベースから前記候補レコードを検索し、前記応答時間要件を満たす検索式を見つけることができなければ、追加探索基準を要求するステップと、
探索基準ロケータフィールドと対応する検索レコードフィールドを比較して、前記各候補レコードを評価するステップと、
前記候補レコードの前記評点が予め定められたしきい値を超えるか否かを判定し、前記候補の評点が前記しきい値を超えると、前記探索基準に応答して戻されるレコードリストに前記候補レコードを追加するステップと、
が含まれていることを特徴とする患者データベース探索におけるデータ依存型フィルタリング方法。
【請求項２】
前記探索基準に名と姓が含まれることと、この方法に、さらに、前記探索基準における前記名と同等の名のリストをコンパイルするステップが含まれることを特徴とする請求項１に記載の方法。
【請求項３】
探索基準ロケータフィールドと対応する候補レコードフィールドを比較するステップに、
前記ロケータフィールドと前記候補レコードフィールド対のフィールド毎の比較を実施し、各フィールド対毎に事前定義されたフィールド比較法を利用して、フィールド対ｊに関する比較結果ベクトルｃjの成分を前記フィールド対に予め定められた文字数まで充填するステップと、
下記の式を利用し、１つ又は複数の確率に基づいて前記比較結果ｃjを評価するステップが含まれており、
【数１】
2008546098.tif 000009
ここで、Ｐ0j（ｃj）及びＰ1j（ｃj）が、前記フィールド対において一致する文字数の関数である確率であることと、さらに、
前記ロケータフィールドと前記候補レコードにおける前記対応するフィールドの両方が空白ではない全てのフィールドｊにわたる評点（ｃj）を合計して、第１の評点を算出するステップが含まれていることを特徴とする請求項１に記載の方法。
【請求項４】
前記探索基準において名と姓の両方が指定されると、前記探索基準において前記名と姓をスワップし、前記スワップしたロケータフィールドと前記候補レコードフィールドのフィールド毎の比較を実施する前記ステップを繰り返し、前記比較結果ｃjを評価し、全フィールドｊにわたる前記評点を合計して、第２の評点を求め、前記第１の評点及び前記第２の評点からスワップペナルティを引いた最大値を選択することを特徴とする請求項３に記載の方法。
【請求項５】
さらに、下記の式に従って前記評点を０〜１００の等級に変換するステップが含まれることと、
ｔｒａｎｓｆｏｒｍｅｄＳｃｏｒｅ＝（ｓｃｏｒｅ−ｍｉｎＳｃｏｒｅ）／（ｍａｘＳｃｏｒｅ−ｍｉｎＳｃｏｒｅ）％１００
ここで、
ｍａｘＳｃｏｒｅ＝Σj  ｍａｘＳｃｏｒｅj、
ｍｉｎＳｃｏｒｅ＝Σj  ｍｉｎＳｃｏｒｅjであり、
前記比較ベクトルのｊ番目の成分を生成するために用いられる前記ロケータフィールドが、前記探索基準において空白ではないことと、ｍａｘＳｃｏｒｅj＝可能性のある全てのｃj値にわたるｍａｘ（ｓｃｏｒｅ（ｃj））及びｍｉｎＳｃｏｒｅj＝可能性のある全てのｃj値にわたるｍｉ（ｓｃｏｒｅ（ｃj））であることを特徴とする請求項４に記載の方法。
【請求項６】
フィールドに関する前記フィールド比較法が、正確な距離一致、ハミング距離、及び、編集距離、及び、スワップを伴う編集距離、名距離、及び、姓距離の１つであることを特徴とする請求項３に記載の方法。
【請求項７】
さらに、戻される前記レコードリスト内の各候補レコード毎に、前記データベースから前記探索ロケータフィールドに関する最新の完全レコードを検索するステップと、
前記候補レコード内の非空値を有する各フィールド毎に、前記検索される完全レコード内のフィールド値を前記候補レコード内の対応する値に置換するステップと、
前記変更された完全レコードを前記データベースに追加するステップと、が含まれることを特徴とする請求項１に記載の方法。
【請求項８】
１つ又は複数の探索ロケータフィールドを含むデータベースから１つ又は複数のレコードを検索するための探索基準を規定するステップと、
前記データベースから検索すべき候補レコードの最大数、及び、前記レコードを検索する最長応答時間を決定するステップと、
前記探索基準における合っている文字数に基づいて検索される候補レコード数を決定するステップと、
前記探索基準におけるエラートレランスを最大にし、同時に、前記応答時間要件を満たす検索式を前記探索基準から決定するステップと、
前記データベースから前記候補レコードを検索し、前記応答時間要件を満たす検索式を見つけることができなければ、追加探索基準を要求するステップと、
が含まれていることを特徴とする患者データベース探索におけるデータ依存型フィルタリング方法。
【請求項９】
前記検索式を用いて検索可能な候補レコード数が、候補レコードの最小数未満であれば、前記探索基準において合っていると仮定される前記文字数を減らすことを特徴とする請求項８に記載の方法。
【請求項１０】
検索すべき候補レコードの前記最大数が、前記データベースに含まれている探索基準フィールドの確率を表わすデータベース値の頻度表から決定さることと、予め定められたしきい値より確率値の高いストリングがメモリに記憶されていることを特徴とする請求項８に記載の方法。
【請求項１１】
前記しきい値が、データベースサイズ、要求される応答時間、及び、前記探索基準と前記候補レコードとの比較速度に基づくことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記確率には、探索基準サブフィールドが前記データベースに含まれている確率が含まれることを特徴とする請求項１０に記載の方法。
【請求項１３】
さらに、
前記探索基準と第１の候補レコードを比較して、前記比較結果及び前記第１の候補レコードを表に記憶するステップと、
前記表を探索することによって各後続候補レコードを探索し、前記表に前記後続候補レコードが見つからない場合には、前記後続候補レコードと前記探索基準を比較して、前記比較結果及び前記後続候補レコードを前記表に記憶するステップが含まることを特徴とする、
請求項８に記載の方法。
【請求項１４】
前記検索式に前記１つ又は複数の探索ロケータフィールドから作成される論理式が含まれることを特徴とする請求項１８に記載の方法。
【請求項１５】
前記探索基準に探索フィールドが１つだけしか含まれていない場合、前記検索式が前記探索フィールドのサブストリングに基づくようにし、高頻度のストリングの辞書を探索し、前記辞書に前記探索サブストリングが見つからなければ、データベース照会を実施することを特徴とする請求項１４に記載の方法。
【請求項１６】
前記探索基準に３つ以上の探索フィールドが含まれる場合、探索基準対の論理積の論理和から前記論理式を作成することを特徴とする請求項１４に記載の方法。
【請求項１７】
前記探索基準に２つの探索フィールドが含まれる場合、全探索フィールドの比較と部分探索フィールドの比較の論理的組み合わせから前記論理式を作成することを特徴とする請求項１４に記載の方法。
【請求項１８】
患者データベース探索におけるデータ依存型フィルタリング方法のステップを実施するためにコンピュータによって実行可能な命令プログラムを明確に具体化する、コンピュータによって読み取り可能なプログラム記憶装置であって、前記方法に、
１つ又は複数の探索ロケータフィールドを含む探索基準を規定するステップと、
前記探索基準におけるエラートレランスを最大にし、同時に、予め定められた応答時間要件を満たす検索式を前記探索基準から決定するステップと、
前記データベースから前記候補レコードを検索し、前記応答時間要件を満たす検索式を見つけることができなければ、追加探索基準を要求するステップと、
探索基準ロケータフィールドと対応する検索レコードフィールドを比較して、前記各候補レコードを評価するステップと、
前記候補レコードの前記評点が予め定められたしきい値を超えるか否かを判定し、前記候補の評点が前記しきい値を超えると、前記探索基準に応答して戻されるレコードリストに前記候補レコードを追加するステップと
が含まれていることを特徴とするコンピュータ可読プログラム記憶装置。
【請求項１９】
前記探索基準に名と姓が含まれることと、この方法に、さらに、前記探索基準における前記名と同等の名のリストをコンパイルするステップが含まれることを特徴とする請求項１８に記載のコンピュータ可読プログラム記憶装置。
【請求項２０】
探索基準ロケータフィールドと対応する候補レコードフィールドを比較するステップに、
前記ロケータフィールドと前記候補レコードフィールド対のフィールド毎の比較を実施し、各フィールド対毎に事前定義されたフィールド比較法を利用して、フィールド対ｊに関する比較結果ベクトルｃjの成分を前記フィールド対に予め定められた文字数まで充填するステップと、
下記の式を利用し、１つ又は複数の確率に基づいて前記比較結果ｃjを評価するステップが含まれており、
【数２】
2008546098.tif 000010
ここで、Ｐ0j（ｃj）及びＰ1j（ｃj）が、前記フィールド対において一致する文字数の関数である確率であることと、さらに、
前記ロケータフィールドと前記候補レコードにおける前記対応するフィールドの両方が空白ではない全てのフィールドｊにわたる評点（ｃj）を合計して、第１の評点を算出するステップが含まれていることを特徴とする請求項１８に記載のコンピュータ可読プログラム記憶装置。
【請求項２１】
前記探索基準において名と姓の両方が指定されると、前記探索基準において前記名と姓をスワップし、前記スワップしたロケータフィールドと前記候補レコードフィールドのフィールド毎の比較を実施する前記ステップを繰り返し、前記比較結果ｃjを評価し、全フィールドｊにわたる前記評点を合計して、第２の評点を求め、前記第１の評点及び前記第２の評点からスワップペナルティを引いた最大値を選択することを特徴とする請求項２０に記載のコンピュータ可読プログラム記憶装置。
【請求項２２】
前記方法に、さらに、下記の式に従って前記評点を０〜１００の等級に変換するステップが含まれることと、
ｔｒａｎｓｆｏｒｍｅｄＳｃｏｒｅ＝（ｓｃｏｒｅ−ｍｉｎＳｃｏｒｅ）／（ｍａｘＳｃｏｒｅ−ｍｉｎＳｃｏｒｅ）％１００
ここで、
ｍａｘＳｃｏｒｅ＝Σj  ｍａｘＳｃｏｒｅj、
ｍｉｎＳｃｏｒｅ＝Σj  ｍｉｎＳｃｏｒｅjであり、
前記比較ベクトルのｊ番目の成分を生成するために用いられる前記ロケータフィールドが、前記探索基準において空白ではないことと、ｍａｘＳｃｏｒｅj＝可能性のある全てのｃj値にわたるｍａｘ（ｓｃｏｒｅ（ｃj））及びｍｉｎＳｃｏｒｅj＝可能性のある全てのｃj値にわたるｍｉ（ｓｃｏｒｅ（ｃj））であることを特徴とする請求項２１に記載のコンピュータ可読プログラム記憶装置。
【請求項２３】
フィールドに関する前記フィールド比較法が、正確な距離一致、ハミング距離、及び、編集距離、及び、スワップを伴う編集距離、名距離、及び、姓距離の１つであることを特徴とする請求項２０に記載のコンピュータ可読プログラム記憶装置。
【請求項２４】
前記方法に、さらに、戻される前記レコードリスト内の各候補レコード毎に、前記データベースから前記探索ロケータフィールドに関する最新の完全レコードを検索するステップと、
前記候補レコード内の非空値を有する各フィールド毎に、前記検索される完全レコード内のフィールド値を前記候補レコード内の対応する値に置換するステップと、
前記変更された完全レコードを前記データベースに追加するステップと、
が含まれることを特徴とする請求項１８に記載のコンピュータ可読プログラム記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
関連米国特許出願の相互参照
本出願は、その内容が参考までに本明細書において援用されている、２００５年５月３１日に提出された、Ｐｈａｎ他の米国仮特許出願第６０／６８６，０６５号、「Ｄａｔａ  Ｓｅｎｓｉｔｉｖｅ  Ｆｉｌｔｅｒｉｎｇ  ｉｎ  Ｓｅａｒｃｈ  ｆｏｒ  Ｐａｔｉｅｎｔ  Ｄｅｍｏｇｒａｐｈｉｃ  Ｒｅｃｏｒｄｓ」からの優先権を主張するものである。
【０００２】
本発明は、医療記録データベース照会の探索及びフィルタリングに関するものである。
【背景技術】
【０００３】
病院情報システムの重要な機能性は、何らかの入力基準に基づいて患者のレコードのエラートレラント探索を実施する能力である。例えば、病院職員は、わずかに姓、名、及び／または、誕生日だけを根拠に患者を識別しなければならないことがよくある。
【０００４】
こうした探索の２つの要件は、次の通りである、（１）病院データベースに記憶されている値に照らして、探索基準にはエラーが含まれている可能性があるので、探索はエラートレランスでなければならない、（２）探索は、例えば１−２秒といった指定時間内に終了すべきである。これら２つの要件は、エラートレランスを強めるには、応答時間を長くしなければならないという意味において競合性である。例えば、評価アルゴリズムによって、毎秒１０，０００のレコードと探索基準を比較することが可能であり、評価に割り当てられる時間が１秒であると仮定する。従って、応答時間を指定された限界内に保つためには、システムは、おそらく数百万のレコードを含んでいる人口統計的データベースから、可能性の高いレコードをせいぜい１０，０００ぐらいしか検索することができない。
【０００５】
通常、データベースレコードが満たさなければならない事前定義条件であるフィルタを設定することによって、より詳細な評価にとって適切なプールのレコードを検索することが可能である。基本的には、探索基準の少なくともいくつかの部分が合っていると仮定して、その情報に基づいて、データベースからレコードを検索する。姓及び名によって探索する例の場合、探索基準における名の最初の４文字及び／または姓の最初の５文字が合っているものと仮定することによって、フィルタを設定することが可能である。従って、検索されるプールは、探索基準として名の最初の４文字及び／または姓の５文字を有するレコードだけから構成されている。２つの論理結合子ＡＮＤ及びＯＲが、検索されるレコード数及びエラートレランスに異なる影響を及ぼすという点に留意されたい。ＡＮＤ結合子は、名の４文字と姓の５文字の両方が合っているものと仮定するが、検索することになるレコード数は、ＯＲ結合子を用いるよりもはるかに少なくなる、しかしながら、ＯＲ結合子は、名の４文字と姓の５文字のいずれかしか合っていると仮定しないので、エラートレラントは高くなる。
【０００６】
この方法の欠点は、前もってフィルタ位置を固定することによって、プールサイズが探査値の頻度によって大きく変動することになるという点である。例えば、探索基準が「Ｊａｍｅｓ  Ｓｍｉｔｈ」の場合、フィルタは、あまりにも多くのレコードを検索することになるであろうが、探索基準が「Ｚｂｉｇｎｉｅｗ  Ｂｒｚｅｚｉｎｓｋｉ」の場合、検索は少なすぎることになる。前者の場合、探索を完了するのに必要な時間は、指定の応答時間を超える可能性がある。後者の場合、「Ｚｂｉｇ」または「Ｂｒｚｅｚ」といった最初の数文字にキー入力ミスが生じると、対象とする「真の」レコードがプールに含まれない可能性がある（従って、探索が失敗することになる）。
【発明の開示】
【課題を解決するための手段】
【０００７】
本明細書に記載の本発明の典型的な実施形態には、一般に、患者の人口統計的レコードの探索において、人口統計的データベースから可能性の高いレコードを検索して、入力基準と比較するデータ依存型フィルタリング方法及びシステムが含まれている。フィルタは、特定の限定なしに、応答時間を維持しながら、最大エラートレランスを可能とする。本発明の実施形態の１つによるデータ依存型フィルタには、探索値の頻度によって決まるフィルタリング条件が用いられる。これらの頻度は、あらかじめ計算しておき、データベースの更新時に、定期的に（例えば、毎月、毎年）計算しなおすことが可能である。例えば、「Ｊａｍｅｓ  Ｓｍｉｔｈ」を探索する場合、フィルタは、データベースにあまりにも多くの「Ｊａｍｅｓ  Ｓｍｉｔｈ」項目が存在しており、厳格なフィルタリング条件を用いるか、または、追加情報を求めるのが望ましいことを承知しておくべきである。「Ｚｂｉｇｎｉｅｗ  Ｂｒｚｅｚｉｎｓｋｉ」の場合、フィルタは、めったにない名前であることを理解して、例えば、名の最初の２文字だけが合っており（４文字ではなく）、姓の最初の３文字だけが合っている（５文字ではなく）ものと仮定して、フィルタ条件を緩和すべきである。この種のフィルタは、エラートレランスを最大にし、同時に、応答時間が限界内に収まることを保証する。
【０００８】
本発明の態様の１つによれば、１つ又は複数の探索ロケータフィールドを含む探索基準を規定するステップと、前記探索基準におけるエラートレランスを最大にし、同時に、予め定められた応答時間要件を満たす検索式を前記探索基準から決定するステップと、前記データベースから前記候補レコードを検索し、前記応答時間要件を満たす検索式を見つけることができなければ、追加探索基準を要求し、探索基準ロケータフィールドと対応する検索レコードフィールドを比較して、前記各候補レコードを評価するステップと、前記候補レコードの評点が予め定められたしきい値を超えるか否かを判定するステップと、前記候補の評点が予め定められたしきい値を超えると、前記探索基準に応答して戻されるレコードリストに前記候補レコードを追加するステップを含む、患者データベース探索におけるデータ依存型フィルタリング方法が提供される。
【０００９】
本発明のもう１つの態様によれば、探索基準に名と姓が含まれるが、この方法には、さらに、前記探索基準における前記名と同等の名のリストをコンパイルするステップが含まれている。
【００１０】
本発明のもう１つの態様によれば、探索基準ロケータフィールドと対応する候補レコードフィールドを比較するステップには、前記ロケータフィールドと前記候補レコードフィールド対のフィールド毎の比較を実施し、各フィールド対毎に事前定義されたフィールド比較法を利用して、フィールド対ｊに関する比較結果ベクトルｃjの成分を前記フィールド対に予め定められた文字数まで充填するステップと、下記の式を利用し、１つ又は複数の確率に基づいて前記比較結果ｃjを評価するステップが含まれており、
【００１１】
【数３】
2008546098.tif 000003
【００１２】
ここで、Ｐ0j（ｃj）及びＰ1j（ｃj）は、前記フィールド対において一致する文字数の関数である確率であり、さらに、ロケータフィールドと前記候補レコードにおける対応するフィールドの両方が空白ではない全てのフィールドｊにわたる評点（ｃｊ）を合計して、第１の評点を算出するステップが含まれている。
【００１３】
本発明のもう１つの態様によれば、探索基準において名と姓の両方が指定されると、前記探索基準において前記名と姓をスワップし、スワップしたロケータフィールドと候補レコードフィールドのフィールド毎の比較を実施する前記ステップを繰り返し、前記比較結果ｃjを評価し、全フィールドｊにわたる前記評点を合計して、第２の評点を求め、前記第１の評点及び前記第２の評点からスワップペナルティを引いた最大値を選択する。
【００１４】
本発明のもう１つの態様によれば、この方法には、下記の式に従って前記評点を０〜１００の等級に変換するステップが含まれている。
ｔｒａｎｓｆｏｒｍｅｄＳｃｏｒｅ＝（ｓｃｏｒｅ−ｍｉｎＳｃｏｒｅ）／（ｍａｘＳｃｏｒｅ−ｍｉｎＳｃｏｒｅ）％１００
ここで、ｍａｘＳｃｏｒｅ＝Σj  ｍａｘＳｃｏｒｅj、ｍｉｎＳｃｏｒｅ＝Σj  ｍｉｎＳｃｏｒｅjであり、比較ベクトルのｊ番目の成分を生成するために用いられるロケータフィールドは、探索基準において空白ではなく、ｍａｘＳｃｏｒｅj＝可能性のある全てのｃj値にわたるｍａｘ（ｓｃｏｒｅ（ｃj））及びｍｉｎＳｃｏｒｅj＝可能性のある全てのｃj値にわたるｍｉ（ｓｃｏｒｅ（ｃj））である。
【００１５】
本発明のもう１つの態様によれば、フィールドに関するフィールド比較法は、正確な距離一致、ハミング距離、編集距離、及び、スワップを伴う編集距離、名距離、及び、姓距離の１つである。
【００１６】
本発明のもう１つの態様によれば、この方法には、戻される前記レコードリスト内の各候補レコード毎に、前記データベースから前記探索ロケータフィールドに関する最新の完全レコードを検索するステップと、前記候補レコード内の非空値を有する各フィールド毎に、検索される完全レコード内のフィールド値を候補レコード内の対応する値に置換するステップと、変更された完全レコードを前記データベースに追加するステップが含まれている。
【００１７】
本発明のもう１つの態様によれば、１つ又は複数の探索ロケータフィールドを含むデータベースから１つ又は複数のレコードを検索するための探索基準を規定するステップと、前記データベースから検索すべき候補レコードの最大数、及び、前記レコードを検索する最長応答時間を決定するステップと、前記探索基準における合っている文字数に基づいて検索される候補レコード数を決定するステップと、前記探索基準におけるエラートレランスを最大にし、同時に、前記応答時間要件を満たす検索式を前記探索基準から決定するステップと、前記データベースから前記候補レコードを検索し、前記応答時間要件を満たす検索式を見つけることができなければ、追加探索基準を要求するステップを含む、患者データベース探索におけるデータ依存型フィルタリング方法が提供される。
【００１８】
本発明のもう１つの態様によれば、前記検索式を用いて検索可能な候補レコード数が、候補レコードの最小数未満であれば、前記探索基準において合っていると仮定される前記文字数が減らされる。
【００１９】
本発明のもう１つの態様によれば、検索すべき候補レコードの最大数は、前記データベースに含まれている探索基準フィールドの確率を表わすデータベース値の頻度表から決定され、予め定められたしきい値より確率値の高いストリングがメモリに記憶されている。
【００２０】
本発明のもう１つの態様によれば、しきい値は、データベースサイズ、要求される応答時間、及び、前記探索基準と前記候補レコードとの比較速度に基づく。
【００２１】
本発明のもう１つの態様によれば、確率には、探索基準サブフィールドが前記データベースに含まれている確率が含まれている。
【００２２】
本発明のもう１つの態様によれば、この方法には、前記探索基準と第１の候補レコードを比較して、前記比較結果及び前記第１の候補レコードを表に記憶するステップと、
前記表を探索することによって各後続候補レコードを探索し、前記表に前記後続候補レコードが見つからない場合には、前記後続候補レコードと前記探索基準を比較して、前記比較結果及び前記後続候補レコードを前記表に記憶するステップが含まれている。
【００２３】
本発明のもう１つの態様によれば、検索式に前記１つ又は複数の探索ロケータフィールドから作成される論理式が含まれる。
【００２４】
本発明のもう１つの態様によれば、前記探索基準に探索フィールドが１つだけしか含まれていない場合、前記検索式が前記探索フィールドのサブストリングに基づくようにし、高頻度のストリングの辞書を探索し、前記辞書に前記探索サブストリングが見つからなければ、データベース照会を実施する。
【００２５】
本発明のもう１つの態様によれば、前記探索基準に３つ以上の探索フィールドが含まれる場合、探索基準対の論理積の論理和から前記論理式を作成する。
【００２６】
本発明のもう１つの態様によれば、前記探索基準に２つの探索フィールドが含まれる場合、全探索フィールドの比較と部分探索フィールドの比較の論理的組み合わせから前記論理式を作成する。
【００２７】
本発明のもう１つの態様によれば、患者データベース探索におけるデータ依存型フィルタリング方法のステップを実施するためにコンピュータによって実行可能な命令プログラムを明確に具体化する、コンピュータによって読み取り可能なプログラム記憶装置が提供される。
【発明を実施するための最良の形態】
【００２８】
本明細書に記載の本発明の典型的な実施形態には、一般に、患者の人口統計的レコード探索にデータ依存型フィルタリングを施すためのシステム及び方法が含まれている。従って、本発明は、さまざまな修正及び代替形態を受け入れることが可能であるが、その具体的実施形態が、図面に例証として示されており、本明細書において詳述されることになる。ただし、云うまでもないが、本発明を開示の特定の形態に制限するつもりは全くなく、それどころか、本発明は、本発明の精神及び範囲内に含まれる全ての修正、同等、及び、代替実施形態を網羅するものである。
【００２９】
医療データベースには、全フィールドの履歴が記録されているものもあるので、レコード検索では履歴レコードも探索するのが望ましい。本発明の実施形態の１つによれば、履歴情報を備えた患者の人口統計的レコードは、いくつかのレコードとして扱うことが可能であり、例えば、３つの名前と、２つの住所が存在するが、患者の人口統計的レコード１つおきに１つの値だけしかない場合、この患者について６つの人口統計的レコードが存在することになる。ある特定の患者に関する最新情報を検索する手段が存在し、それを用いて、一番上の候補のリストを戻さなければならないものと仮定することが可能である。
【００３０】
さらに、データベースには、名前（氏名、別名、偽名）及び住所（自宅住所、郵送先住所、請求先住所）のような、特定のフィールドに関して複数の値を有することに対応するものもある。人口統計的情報を表わすデータ構造は、異なるフィールドの区別を行うのが望ましい。検索及び評価の便宜上、本発明の実施形態の１つによるアルゴリズムでは、これらの可変要素を全て対称に取り扱う。フィールドの可変要素は、そのフィールドの履歴値と全く同様に扱われる。
【００３１】
さらに、人口統計的レコードから導き出される値を用いて、評価のためのレコードを検索することが可能である。これらの人口統計的レコードは、レコードリンケージ（ＲＬ）キーと呼ばれる。例えば、姓の最初の４文字と名の最後の４文字を連結することによって新たなストリングを作成し、データベースに記憶しておいて、後でそれを利用して、計算しなくても、データ列を見つけることができるようにすることが可能である。本発明の実施形態の１つによれば、それぞれのフィールドの「最新値」に関してＲＬキーの値をあらかじめ計算することになる。この事前計算は、履歴値の計算及び記憶にまで拡げることが可能である。
【００３２】
本発明の実施形態の１つによれば、典型的な医療データベースＤはｎのレコードを備えており、各レコードはｍのフィールドＦ1、Ｆ2、．．．、Ｆmを備えている。このデータベースからの典型的な検索要求には、あるレコードのフィールドＦ1、．．．、ＦIのおそらくノイズ値を表わした、１つ又は複数のストリングｓ1、．．．、ｓIに基づくレコードの検索を必然的に伴うことになる。
【００３３】
この要求に対する応答には下記の２つの部分が含まれる。
（１）第１の部分では、要求されるフィールドと入力値に基づいて、論理式Φが作成される。この式は、データベースＤからデータを検索するためのＳＱＬ照会とみなされる。この結果、ｋ個からなるレコード集合が生じる。
（２）第２の部分では、ｋ個の検索レコードが評価される。
【００３４】
解明のコストは、要求の完了に必要な時間と、所望の正確度によって判定される。全要求処理時間がある上限Ｔ未満であることも必要とされる。
全時間＝検索時間＋評価時間、
評価時間＝ｋ％ａ
ここで、ｋは検索レコード数であり、ａは各評価に必要な時間である。検索時間はレコード数に影響されやすいが、その依存性は線形ではない可能性がある。性能要件から、検索すべき最大数ｋを概算することが可能である。可能性のある検索式がいくつか存在する。
【００３５】
１つの式には、単純な論理式の論理和が含まれる。
Φ＝（Ｆ1＝ｓ1）∨（Ｆ2＝ｓ2）．．．∨（ＦI＝ｓI）
この式によって、少なくとも１つのストリングが合っていれば、対象とするレコードが確実に検索され、評価されることになる。
【００３６】
Ｘiがストリングｓiにおけるエラー数とする。単純な論理式φの場合、Ｓ（φ）がφを満たすレコード数であるとする。Φが対象とするレコードを検索できない確率は、次の通りであり、
【００３７】
【数４】
2008546098.tif 000004
【００３８】
Φ＝φ１∨φ２．．．∨φIを用いて検索されるレコード数は、次の通りである。
【００３９】
【数５】
2008546098.tif 000005
【００４０】
例えば、Ｉ＝３の場合、Φ＝φ１∨φ２∨φ3であり、しかも、次の通りである。
【００４１】
【数６】
2008546098.tif 000006
【００４２】
もう１つの式には、論理積が含まれる。
Ψ＝（Ｆ1＝ｓ1）＆（Ｆ2＝ｓ2）．．．＆（ＦI＝ｓI）
この場合、対象とするレコードが検索されない確率は、次の通りであり、
【００４３】
【数７】
2008546098.tif 000007
【００４４】
検索されるレコード数は、次の通りである。
Ｓ（Ψ）＝Ｓ（φ1＆φ2．．．＆φI）
【００４５】
これらの式の使用例として、ｎ＝１０6のレコードを備え、確率がＰ（φ1）＝０．０４、Ｐ（φ2）＝０．０３、及び、Ｐ（φ3）＝０．０２のデータベースを考察することにする。これは、Ｓ（φ1）＝４％１０4、Ｓ（φ2）＝３％１０4、及び、Ｓ（φ3）＝２％１０4を意味している。それぞれ、長さが２、６、及び、４のストリングS1、S2、S3が０．０５の誤り率で入力されるものと仮定する。S1、S2、S3にエラーが生じない確率は、それぞれ、０．５４０４、０．７３５１、及び、０．８１４５である。
【００４６】
検索式としてΦを利用すると、
Ｓ（Φ）＝８．７×１０4
及び
Ｆ（Φ）＝０．０２２６になる。
検索式としてΨを利用すると、
Ｓ（Ψ）＝２４、
及び、
Ｆ（Ψ）＝０．６７６５になる。
【００４７】
この例に示すように、ＯＲ論理だけ並びにＡＮＤ論理だけを利用した検索式では、逆の理由によって満足のいく結果が得られない可能性がある。ＯＲ論理では、検索及び評価しなければならないレコードが多すぎることになり、一方、ＡＮＤ論理では、対象とするレコードを入手できない確率が高すぎることになる。
【００４８】
このシナリオを改善する手法の１つは、より少ない数の項の論理積の論理和である式を用いることである。例えば、Ｉ＝３の場合、次のようになるであろう
Γ＝（φ1＆φ2）∨（φ2＆φ3）∨（φ3＆φ1）
これにより、上記例については、
Ｓ（Γ）＝２．６％１０4
及び
Ｆ（Γ）＝０．２１１０になる。
【００４９】
論理積の論理和を用いる式は、Ｉ＝２の場合には適用されない。前述の検索式は全ストリングとフィールド値の比較に基づくものであった。もう１つの式は、フィールド値の一部の比較に基づくものである。ｓ（ｉ）がストリングのｉ番目の文字を表わし、ｓ（ｉ，ｊ）がｉで始まり、ｊで終わるｓのサブストリングを表わすものとする。
【００５０】
下記形式の検索式について考察する。
Δ＝（（Ｆ1＝ｓ1）＆（Ｆ2（ｉ，ｊ）＝ｓ2（ｉ，ｊ）））∨（（Ｆ1（ｉ，ｊ）＝ｓ1（ｉ，ｊ））＆（Ｆ2＝ｓ2））
例えば、ｉ＝ｊ＝１の場合、Δは、第１のフィールドがｓ1に等しく、第２のフィールドの最初の文字がｓ2の最初の文字に等しいか、あるいは、第１のフィールドがｓ2に等しく、第１のフィールドの最初の文字がｓ1の最初の文字に等しい全てのレコードを検索する。
【００５１】
フィールドＦｉの最初の文字の確率がｘであると仮定すると、Ｐ（Ｆi（１）＝ｘ）＝０．１。これは、アルファベットには２６字あるので、控えめな推定値である。
【００５２】
この部分的比較式を適用して、上記数値例についてＳ（Δ）及びＦ（Δ）を計算することが可能である
Ｓ（Δ）＝０．５８×１０4＝（０．０４×０．１＋０．０３×０．１−０．０４×０．０３）×１０6
Ｆ（Δ）＝０．１８５５＝１−（０．５４０４×０．９５＋０．７３５１×０．９５−０．５４０４×０．７３５１）
対照的に、Φ＝（Ｆ1＝ｓ1）∨（Ｆ2＝ｓ2）の場合、
Ｓ（Φ）＝６．８８×１０4＝（０．０４＋０．０３−０．０４×０．０３）×１０6
Ｆ（Φ）＝０．１２１８＝（１−０．５４０４）×（１−０．７３５１）
となり、Ψ＝（Ｆ1＝ｓ1）∨（Ｆ2＝ｓ2）の場合、
Ｓ（Ψ）＝０．１２×１０4＝（０．０４×０．０３）×１０6、
Ｆ（Ψ）＝０．６０２８になる。
このΔ式を拡張して、次のように４つのパラメータｉ、ｊ、ｈ、ｋを取り扱う形式にすることが可能である
Δ（ｉ，ｊ，ｈ，ｋ）＝（（Ｆ1（ｉ，ｊ）＝ｓ1（ｉ，ｊ））＆（Ｆ2（ｈ，ｋ）＝ｓ2（ｈ，ｋ））。
この式では、ストリングｓ1の（ｊ−ｉ）及びストリングｓ2の（ｋ−ｈ）である、ｑ＝（ｊ−ｉ）＋（ｋ−ｈ）の文字を選択して、フィールドの対応する値と比較する。通常、異なるストリング（フィールド）に関する２つの文字群を利用するのは、１つのストリングから同じ数の文字を選択するよりも効率が良い。その理由は、２つのストリングにおける２つの文字群が独立していると仮定するのは道理に適うが、同じストリング内の文字群についてそう仮定するのは道理に適わないからである。例えば、「Ｓｍｉｔｈ」は平凡な姓であるが（確率Ｐ（ＬａｓｔＮａｍｅ＝“Ｓｍｉｔｈ”）＝０．０３）、条件付き確率Ｐ（ＬａｓｔＮａｍｅ（４，５）＝“ｔｈ”｜ＬａｓｔＮａｍｅ（１，３）＝“Ｓｍｉ”）は高い（０．３）。
【００５３】
比較する文字の識別は、必ずしもストリング内の自然位置に制限されるものではないという点に留意されたい。それは、左からの場合もあれば、右からの場合もあり、子音だけまたは母音だけ、あるいは、アルファベットの任意の部分集合をカウントする場合もある。さらに、文字の選択によって、独立性の仮定が道理に適うことが保証されるべきである。
【００５４】
１つの入力ストリングｓ1だけの場合、異なる問題が提示される。Ｓ（Ｆ1＝ｓ1）が大きすぎる場合、探索に時間を費やす前に、この条件を検出するのが道理に適う。制限時間内に評価すべき最大レコード数がｋmであると仮定する。その頻度がｋmを超えるフィールド値のリストを記憶しておくことが可能であり、ＳＱＬ検索の開始前に、ある特定のストリングｓ1とそのリストを照合することが可能である。こうした値の数は、ｎ／ｋm未満である。ストリング全体の探索によって対象とするレコードの検索に失敗する確率は、
１−（１−ｒ）lであり、
ここで、ｒは誤り率、ｌは入力ストリングの長さである。ほとんどの場合、問題は、Ｓ（Ｆ1＝ｓ1）が大きすぎるということではなく、むしろ、失敗の確率が高すぎるということである。例えば、ｓが入力された長さ１５の姓であり、誤り率が０．０５の場合、Ｆ（ＬａｓｔＮａｍｅ＝ｓ）＝０．５３６７になる。こうした失敗レベルが容認できない場合、探索条件を緩和すべきである。例えば、探索条件Ｆ1（ｉ，ｊ）＝ｓ（ｉ，ｊ）を用いることが可能である。ｊ−ｉ＝５の場合、対象とするレコードを検索できない確率は、０．２２６２に低下する。
【００５５】
従って、探索条件が１つのストリングの場合、その探索については部分探索がより有効なアプローチである。例えば、ストリング全体を探索するのではなく、データベース探索基準として最初の５または６文字を用いる方が良い。多すぎるレコード検索を回避するため、おそらくは、最初の実行前に、高頻度のストリングの辞書を作成すべきである。その後、ＳＱＬ照会に取りかかる前に、その辞書によってユーザの探索にフィルタリングが施される。ユーザの探索ストリングが辞書にある場合、ＳＱＬ照会は行われず、ユーザはより多くの情報を要求されることになる。部分比較を利用する検索式の場合、部分ストリングを事前計算するのが望ましい。
【００５６】
ユーザによって２つのストリングが提供される場合、検索式Δ（ｉ，ｊ，ｈ，ｋ）によって、検索及び評価するレコード数とエラートレランスとのバランスが良くなる。ユーザによって３つ以上のストリングが提供される場合、論理積式の論理和が有効な探索候補である。
【００５７】
本発明の実施形態の１つによれば、予備ステップとしてデータベース値の頻度情報を収集すべきである。患者探索が施される各フィールドのストリング内に、文字位置集合を事前定義することが可能である。患者探索が施されるフィールドについて、全てのレコードを走査し、全ての値の頻度をカウントすることになる。例えば、患者探索が、例えば、姓、名、誕生日、自宅住所、医療記録番号（ＭＲＮ）、及び、社会保障番号（ＳＳＮ）といったフィールドの組み合わせに基づくことが可能であると仮定する。位置集合は、任意とすることが可能であるが、単純化のため、選択位置が連続しており、ストリングの左（始め）から右（終わり）にカウントするものと仮定することが可能である。位置集合が与えられると、各別個の値の頻度がカウントされる。データベースの走査によって、姓、名、誕生日、自宅住所の最初のｉ文字及び、ＭＲＮ、ＳＳＮの最後のｉ文字によって形成される、後続する限定されない典型的なストリング値の頻度がカウントされる。値ｉは３、４、及び、５とすることが可能である。例えば、ｉ＝４で、名フィールドの場合、ストリング「ａｄｌｅ」の頻度には、名「Ａｄｌｅｒ」、「Ａｄｌｅｙ」、「Ａｄｌｅｅｎ」等がカウントされる。
【００５８】
次に、カウントをデータベースのサイズで割って、ストリング頻度が確率（割合）に変換される。データベース自体が更新されるので、確率は、カウント数よりもある時間期間にわたって安定している。
【００５９】
これら２つのステップは、定期的に、または、データベースが、その現在の状態を反映するため大幅な更新合併を受ける毎に反復される。
【００６０】
メモリには、予め定められたしきい値より確率の高いストリングが記憶されている。しきい値は、データベースサイズ及び必要な応答時間及び比較速度に基づいて決定される。例えば、１００万レコードのサイズのデータベースについて、頻度カウントが１００を超えるストリングだけを保持することが求められる場合、しきい値は１０2／１０6＝１０-4に設定される。すなわち、頻度が１００を超えるストリングだけが保持される。表に見つからないストリングは、頻度が極めて低いものとみなすことが可能である。現実的な名前の分布の歪みは、この条件を満たすストリング数が数百未満であることが多い。一方、例えば、社会保障番号（ＳＳＮ）の最後の４つの数字の分布がほぼ均一である（すなわち、４つの数字からなる任意のストリングの確率が同じである）ことが分かれば、その確率値だけを記憶する。
【００６１】
図７には、本発明の実施形態の１つによるデータ依存型検索フィルタリングプロセスのフローチャートが描かれている。データベース値の頻度情報が表にされているものと仮定して、ステップ７１で探索基準が規定される。探索基準には、医療人口統計的データベースの適合するレコードと突き合せられるフィールド値の１つ又は複数のストリングを含むことが可能である。この探索基準が与えられると、データベース探索エンジンが、頻度表を参照し、探索基準のｉ文字が合っているものと仮定した場合、各フィルタリング式毎に、プールがどれだけのレコードを備えることになるか、及び、どんな論理結合が用いられるかを決定する。探索基準が受け入れられると、電話番号、住所、ＳＳＮ等を取り出せるように、探索基準が標準化される。
【００６２】
図１には、本発明の実施形態の１つによる典型的なフィールド比較表が描かれている。この表には、表の各番号付き行毎に１つずつ、１８の可能性のある探索基準が示されている。留意すべきは、探索基準のこの選択は典型的なものであって、制限するものではなく、本発明の実施形態の１つに従って、より多くのまたはより少ない探索基準を用いることが可能である。「ロケータフィールド」と表示された列は、探索基準が設けられたロケータに対応し、一方、「レコードフィールド」と表示された列は、データベース内のレコードに対応する。「距離測定」と表示された列は、ロケータとその行のレコードを比較するために用いられるフィールド比較法を表わし、「限度」と表示された最後の列は、比較に用いられる文字数を表わしている。表の最後の行は、省略時比較において、２文字のＥｄｉｔＤｉｓｔａｎｃｅコンパレータが用いられることを表わしている。
【００６３】
探索フィールド構成情報から、探索基準で指定された名に相当する名のリスト、すなわち、指定された名が属するグループの少なくとも１つに属する全ての名のリストが検索される。人の名には、さまざまな変形がある可能性がある。例えば、ロバート−ボブ−ボビー、あるいは、テオドル−テッド−エドなどがある。こうした名の変形は等しいものとみなされる。ユーザがボブ・ホワイトを見つけたい場合、ロバート・ホワイト及びボビー・ホワイトを試す価値のある候補とみなすべきである。このリストは、ｓｃ．ｅｑｕｉｖａｌｅｎｔＦｉｒｓｔＮａｍｅＬｉｓｔと呼ばれる。
【００６４】
さらに、本発明の実施形態の1つでは、音声符号化に基づく探索をサポートするデータベースのために、名の音声符号化の計算が可能である。
【００６５】
もう一度図７を参照すると、ステップ７２において、以下で列挙する条件の任意の１つが真である全ての人口統計的レコードが、データベースから検索される（ここで、ｒｅｃ．はデータベース内のレコードを表わし、ｓｃ．は探索基準を表わしている）。評価には探索基準で指定されたフィールドだけが用いられるので、検索プロセスにおいてコストのかかる結合に起因する効率の悪さを阻止するため、候補に関して検索されるのは、探索基準で指定されたフィールドだけである。
【００６６】
一例として、探索基準が「Ｊｏｈｎ  Ｄｅｅｒ」であると仮定する。１００万レコードのデータベースにおいて、ストリング「ｊｏｈｎ」の確率が０．０１で、ストリング「ｄｅｅｒ」の確率が０．０１５であると仮定する。下記の状況の可能性がある。
ａ）名の最初の４文字が合っていると仮定すると、プールは１，０００，０００％０．０１＝１０，０００のレコードを有していることになる。
ｂ）姓の最初の３文字が合っていると仮定すると、プールは１５，０００のレコードを有していることになる。
ｃ）名の最初の４文字が合っている  ＡＮＤ  姓の最初の３文字が合っていると仮定すると、プールサイズは１，０００，０００％０．０１％０．０１５＝１５０になる。
ｄ）名の最初の４文字が合っている  ＯＲ  姓の最初の３文字が合っていると仮定すると、プールサイズは、約１，０００，０００％（０．０１＋０．０１５−０．０１％０．０１５）＝２４，８５０λ２５，０００になる。
【００６７】
応答時間要件を満たすため、検索されるプールのレコードは１０，０００を超えてはならないものと仮定する。従って、最大エラートレランスを可能にし、同時に、プールサイズを範囲内に保つフィルタリング条件（論理式）を見つけることが望ましい。例えば、上記オプション（ａ）は、最大のエラートレランスをもたらし、同時に、時間応答要件を満たすので最良である。オプション（ｂ）及び（ｄ）は、プールが大きくなりすぎるので、除外されることになるであろう。例えば、３番目の文字にエラーが生じると（正しい名前はＪｏｈｎ  Ｄｅａｒ）、オプション（ａ）ならそれでもレコードを検索するが、オプション（ｃ）は検索できないと思われるので、（ｃ）は、（ａ）ほど望ましくはない。
【００６８】
場合によっては、利用可能などのオプションからも、１０，０００未満のプールが供給されないことが起こりうる。「Ｊａｍｅｓ  Ｓｍｉｔｈ」を探索する例の場合、「ｊａｍｅ」の確率が０．１２で、「ｓｍｉ」の確率が０．１であれば、ＡＮＤ結合を利用するオプション（ｃ）でさえ、１，０００，０００％０．１２％０．１＝１２，０００を備えることになる。これは、指定時間内にその検索を完了できないことを表わしている。ユーザがより長い応答時間を受け入れない限り、システムは、例えば、自宅住所といったより多くの情報を求めるべきであり、その情報を利用して、さらにプールを制限することになる。例えば、自宅住所が「１２３  Ｍａｉｎ  Ｓｔ」の場合、「Ｊａｍｅ」＋「Ｓｍｉ」によってデータベースからレコードを検索するのではなく、「Ｊａｍｅ」＋「Ｓｍｉ」＋「Ｍａｉｎ」によって検索する。最良のフィルタは、自宅住所の最初の４文字によってレコードを検索するものと思われるが、結果は、１，０００，０００％０．００９＝９，０００レコードになる。
【００６９】
「Ｚｂｉｇｎｉｅｗ  Ｂｒｚｅｚｉｎｓｋｉ」といっためったにない名前の場合、「ｚｂｉｇ」の確率＝０．００００１で、「ｂｒｚ」の確率＝０．０００１であれば、名の４文字  ＯＲ  姓の３文字を仮定するオプションでさえ、わずかに約１，０００，０００％（０．０００１＋０．０００１）＝１１０レコードになる。この場合、名の３文字または姓の３文字だけが合っていると仮定することによって、仮定を緩和することが可能である。それによって、名の４番目の文字のエラーが許容される。
【００７０】
本発明の実施形態の１つによる典型的な制限のない条件リストは、次の通りである。条件に後続する「（ＲＬ  ｋｅｙ）」は、その条件が事前計算されたレコードリンケージであることを表わしている。
ａ．  名前
ｉ．Ｓｃ．ｌａｓｔｎａｍｅ＝ｒｅｃ．ｌａｓｔｎａｍｅ
ｉｉ．Ｓｃ．ｆｉｒｓｔｎａｍｅ＝ｒｅｃ．ｆｉｒｓｔｎａｍｅ
ｉｉｉ．Ｓｃ．ｌａｓｔｎａｍｅｐｈｏｎｅｔｉｃ＝ｒｅｃ．ｌａｓｔｎａｍｅｐｈｏｎｅｔｉｃ（ＲＬ  ｋｅｙ）
ｉｖ．  Ｓｃ．ｌａｓｔｎａｍｅ  ｈａｓ  ｌｅｎｇｔｈ＞＝４  ＡＮＤ  ｒｅｃ．ｌａｓｔｎａｍｅ  ｓｔａｒｔｓ  ｗｉｔｈ  ｓｃ．ｌａｓｔｎａｍｅ
ｖ．  （ｉｎｃｌｕｄｅＮｉｃｋＮａｍｅＩｎＱｕｅｒｙ＝ｔｒｕｅ）  ＡＮＤ  Ｒｅｃ．ｆｉｒｓｔｎａｍｅ  ｉｓ  ｐｒｅｓｅｎｔ  ｉｎ  ｓｃ．ｅｑｕｉｖａｌｅｎｔＦｉｒｓｔＮａｍｅｌｉｓｔ
ｖｉ．Ｒｅｃ．ｆｉｒｓｔｎａｍｅ＝ｓｃ．ｌａｓｔｎａｍｅ  ＡＮＤ  ｒｅｃ．ｌａｓｔｎａｍｅ＝ｓｃ．ｆｉｒｓｔｎａｍｅ
ｖｉｉ．Ｓｃ．ｌａｓｔＮａｍｅＦｉｒｓｔ４Ｃｈａｒｓ＝ｒｅｃ．ｌａｓｔＮａｍｅＦｉｒｓｔ４Ｃｈａｒｓ（ＲＬ  ｋｅｙ）
ｂ．住所
ｉ．Ｓｃ．ａｄｄｒｅｓｓＬｉｎｅ１＝ｒｅｃ．ａｄｄｒｅｓｓＬｉｎｅ１
ｉｉ．Ｓｃ．ｈｏｕｓｅＮｏ＝ｒｅｃ．ｈｏｕｓｅＮｏ（ＲＬ  ｋｅｙ）
ｉｉｉ．Ｓｃ．ｓｔｒｅｅｔＮａｍｅ＝ｒｅｃ．ｓｔｒｅｅｔＮａｍｅ（ＲＬ  ｋｅｙ）
ｃ．電話番号
ｉ．ｓｃ．ｐｈｏｎｅＮｏ＝ｒｅｃ．ｐｈｏｎｅＮｏ（局番後の７つの数字、ＲＬ  ｋｅｙ）
ｄ．誕生日
ｉ．  Ｓｃ．ｂｉｒｔｈＭｏｎｔｈ＝ｒｅｃ．ｂｉｒｔｈＭｏｎｔｈ  ＡＮＤ  ｓｃ．ｂｉｒｔｈＤａｔｅ＝ｒｅｃ．ｂｉｒｔｈＤａｔｅ  ＡＮＤ  ｓｃ．ｂｉｒｔｈＹｅａｒ＝ｒｅｃ．ｂｉｒｔｈＹｅａｒ
ｅ．個人識別子
ｉ．Ｓｃ．ＳＳＮ＝ｒｅｃ．ＳＳＮ
ｉｉ．Ｓｃ．ＳＳＮＬａｓｔ４Ｃｈａｒｓ＝ｒｅｃ．ＳＳＮＬａｓｔ４Ｃｈａｒｓ（ＲＬ  ｋｅｙ）
ｉｉｉ．Ｓｃ．ｐｅｒｓｏｎＮｕｍｂｅｒ＝ｒｅｃ．ｐｅｒｓｏｎＮｕｍｂｅｒ
ｉｖ．Ｓｃ．ｍｅｄｉｃａｌＲｅｃｏｒｄＮｕｍｂｅｒ＝ｒｅｃ．ｍｅｄｉｃａｌＲｅｃｏｒｄＮｕｍｂｅｒ
ステップ７３において、データベースから検索される各候補レコードは次のように評価される。特定のロケータと候補を比較して、探索基準フィールドに関する成分を備えた比較ベクトルが生成される。フィールド対フィールドの比較を実施して、比較ベクトルの成分が充填される。本発明の実施形態の１つによれば、図１にリストアップされたフィールド比較法が用いられる。このリストのフィールド比較法は、典型的なものであって、制限のためのものでなく、本発明の他の実施形態では、他のフィールド比較法を用いることが可能である。この比較構成に明示的に記載されていない各指定の探索基準については、省略時比較法を用いて、そのフィールドとデータベースから検索されるレコードの同じフィールドが比較される。
【００７１】
フィールドは、ある特定の（フィールド依存）上限で距離が飽和するという制約条件を追加して、フィールド間の指定のストリング距離を計算することによって比較される。上限を超える任意の距離がその限界に設定される、例えば、名が編集距離（５）（後述する）を用いて比較される場合、この距離が５未満であれば、２つのレコードにおける名の比較結果がそれらの間の編集距離であり、さもなければ、それは５に設定されることになる。
【００７２】
フィールド比較に関する典型的な制限のないストリング距離関数（全てのストリング・メトリクスが大文字と小文字を区別しない）のリストは、次の通りである。
ａ．正確な一致距離：ストリングが正確に一致すれば０、さもなければ１である。
ｂ．ハミング距離：同じ長さの２つのストリングが異なる（例えば、１０００と１０１０の間の距離が１で、１０００と０１００の間の距離が２）位置数をカウントする。２つのストリングの長さが異なる場合、距離は、長さの差と短いストリング間のハミング距離の和とすべきであり、長さの長いストリングの接頭辞は短いストリングの接頭辞に等しくなる。
ｃ．編集距離：あるストリングを別のストリングに変換するのに必要な基本（単一文字）編集操作（挿入、削除、置換）の最小数をカウントする（例えば、ＪｏｈｎとＪｏｎとの間の距離は１、ＪｏｈｎとＪｏｎｈとの間の距離は２、ＪｏｈｎとＪｏとの間の距離は２）。
ｄ．スワップを伴う編集距離：上記定義における特別操作として隣接文字のスワッピングを含む。（用いられる実施法がこの定義によると誤っているが、どの文字位置も、多くとも１回のスワッピング操作にしか含まれないものと仮定すると、正しい可能性があるので、この用途にとっては十分に有効である点に留意されたい）。
ｅ．名距離：２つのストリングが等しければ、その距離は０であり、一方がもう一方の接頭辞である場合、または、両方のストリングを含む、一般に用いられる名のグループが存在する場合、その距離は１であり、さもなければ、２つのストリングの間でスワップを伴う編集距離である。
ｆ．姓距離：２つのストリングが等しければ、その距離は０であり、そうではなく、一方がもう一方の接頭辞である場合、距離は１であり、編集距離が３以上で、２つのストリングの音声符号化が同じ場合には、姓距離は２であり、さもなければ、２つのストリングの間でスワップを伴う編集距離である。
【００７３】
次に、構成ファイルに指定された確率情報を利用して比較ベクトルを評価し、評点が求められる。フィールドｊに関する比較結果ｃjを評価するために用いられる典型的な制限のない式は、次の通りである
【００７４】
【数８】
2008546098.tif 000008
【００７５】
ｂＳｃｏｒｅは、ロケータフィールドと人口統計的レコードにおける対応するフィールドの両方が空白ではない、全てのｊにわたるｓｃｏｒｅ（ｃj）の和と定義される。この式における確率パラメータＰij（ｃj）は、ストリング頻度とデータの質を反映し、ｃjによって選択される値の範囲は、用いられる比較方法によっても左右される。
【００７６】
第１の確率Ｐ0j（ｃj）と第２の確率Ｐ1j（ｃj）に関する典型的な値が、図２及び３の表に表示されている。これらの表のそれぞれのフォーマットは同じである。図２を参照すると、索引ｊは行番号（すなわち、探索基準ロケータフィールド）を表わし、５までの数列が、対応するフィールド名の左に表示されている。５つの列は、本発明の実施形態の１つによれば、フィールド検索に用いられる最大文字数が、図１の表の「限度」列に記載のように、５文字であるという事実に対応する。ある特定の行に関して、左から右に進むにつれて、確率値が単調に増大し、共通の文字が存在するので、ロケータフィールドとレコードフィールドとの一致確率が高まるのを反映している。従って、「名」フィールドを参照すると、ロケータフィールドとレコードフィールドの最初の文字だけしか一致しない場合、確率値は０．００３と低くなり、一方、最初の５文字が一致すると、確率値は０．８５と高くなる。
【００７７】
名と姓の両方が探索基準で指定されている場合、探索基準において名と姓のスワッピングも行われ、ロケータと候補を比較し、比較ベクトルを評価して、ｃＳｃｏｒｅを求めるステップを繰り返すことによって、レコードと対照した新しい探索基準の評価が行われる。候補の評点はｍａｘ（ｂＳｃｏｒｅ，ｃＳｃｏｒｅ−ｓｗａｐＰｅｎａｌｔｙ）に設定される。ＳｗａｐＰｅｎａｌｔｙは、初めに、常用対数ｌｏｇ（１０）に当てられる。名前を含まないｂＳｃｏｒｅ計算からの全ての比較結果は、再利用可能であり、再計算する必要がない。
【００７８】
もう一度図７を参照すると、ステップ７４で、評点は次に０〜１００の等級に変換される。これは、探索基準において、特定されたフィールドに基づいてなされる。変換された評点は、次のように定義される
ｔｒａｎｓｆｏｒｍｅｄＳｃｏｒｅ＝（ｓｃｏｒｅ−ｍｉｎＳｃｏｒｅ）／（ｍａｘＳｃｏｒｅ−ｍｉｎＳｃｏｒｅ）％１００
ここで、ｓｃｏｒｅは、前述のステップで得られる評点であり、ｍａｘＳｃｏｒｅ及びｍｉｎＳｃｏｒｅは、指定の探索基準について達成できる可能性のある最大及び最小の評点であり、下記のように定義される。可能性のある全てのｃj値にわたって、最大評点は、
ｍａｘＳｃｏｒｅj＝ｍａｘ（ｓｃｏｒｅ（ｃj））
によって定義される。ある特定の探索基準集合に関して、ｍａｘＳｃｏｒｅは、全てのｊにわたるｍａｘＳｃｏｒｅｊの和と定義されるが、ここで、比較ベクトルのｊ番目の成分を生成するために用いられるロケータフィールドは探索基準において空白ではない。同様に、ある探索基準集合に関して、ｍｉｎＳｃｏｒｅj及びｍｉｎＳｃｏｒｅが定義される。開始時に、各ｊ毎に、ｍａｘＳｃｏｒｅj及びｍｉｎＳｃｏｒｅjが計算されるという点、及び、どの基準が指定されるかに基づいて、各探索毎に、ｍａｘＳｃｏｒｅ及びｍｉｎＳｃｏｒｅを計算する必要があるという点に留意されたい。
【００７９】
ステップ７５で、レコードが「良い」候補を表わしている場合、そのレコードは戻すべきレコードリストに追加される。本発明の実施形態の１つによれば、変換された一致評点が６５に初期設定された設定しきい値を超えると、候補は良いとみなされる。戻されるレコードリストの各候補レコード毎に、その個人識別子に関する完全な「最新」レコードが検索される。候補レコードに非空値のある各フィールド毎に、現在検索されている完全レコードの値が、候補レコードの値に置き換えられる。
【００８０】
個人名、住所、及び、電話番号フィールドがまとめられたデータベース行を表わす典型的な表が、図４に示されている。次にこの図を参照すると、この表には、Ｊｏｈｎ  Ｓｍｙｔｈｅを探索照会するための８つのデータ行が設けられている。「ＰｅｒｓＯｂｊＩｄ」と表示された最初の列は、照会によって探索される対象者の識別番号を表わしている。第２の列「ＦＮ」には名が記載され、第３の列「ＬＮ」には姓が記載され、第４の列「ＡｄｄｒｅｓｓＬｉｎｅ１」には対象者の住所が記載され、第５の列「Ｐｈ．＃」には対象者の電話番号が記載されており、一方、それぞれ、「Ｃｕｒｒ．Ｎａｍｅ？」、「Ｃｕｒｒ．Ａｄｄｒ．？」、及び、「Ｃｕｒｒ．Ｐｈ．？」と表示された第６、第７、及び、第８の列は、名前、住所、及び、電話番号フィールドが探索基準と一致するか否かを表わしている。例えば、ユーザがＪｏｈｎ  Ｓｍｙｔｈｅを探索して、住所及び電話番号を提供し、データベースには、図５の表に示すように、後で名前をＪａｃｋ  Ｓｍｙｔｈｅに変えたＪｏｈｎ  Ｓｍｉｔｈが含まれている場合、データベースレコードは、図４の表の最下行に示すように更新されることになり、戻される照会結果が図６の表に示されている。
【００８１】
本発明の実施形態の１つによれば、データベース値の頻度を利用して、探索基準とデータベース値の比較をさらに効率よくすることが可能である。探索基準が名に関するストリングＳＧ及び姓に関するストリングＳＬであると仮定する。検索されるプールには、（ＤＧ1，ＤＬ1）、（ＤＧ2，ＤＬ2）．．．（ＤＧ10000，ＤＬ10000）が含まれている。実は、１０，０００のストリングＤＧiの中には、多くの反復が存在している。１つは、全比較をスピードアップするのに有利である。ｉ＝１から始めて、ＳＧとＤＧiのそれぞれを比較するのではなく、ＳＧとＤＧ1を比較して、ＤＧ1を記憶し、結果を表に記入する。ｉ＝２の場合、表のＤＧiを探索し、見つかると、記憶されている結果を利用する。ＤＧiが見つからなければ、ＳＧとＤＧiの比較を行って、その結果を表に記憶する。
【００８２】
云うまでもないが、本発明は、さまざまな形態のハードウェア、ソフトウェア、ファームウェア、専用プロセス、または、それらの組み合わせによって実施可能である。実施形態の１つでは、本発明は、コンピュータ可読プログラム記憶装置で具現化される具体的なアプリケーションプログラムとして、ソフトウェアで実施することが可能である。アプリケーションプログラムは、任意の適合するアーキテクチャを含むマシンにアップロードし、そのマシンによって実行することが可能である。
【００８３】
図８は、本発明の実施形態の１つによるデータベース探索のデータ依存型フィルタリングを実施するための典型的なコンピュータシステムのブロック図である。図８を参照すると、本発明を実施するためのコンピュータシステム８１には、とりわけ、中央演算処理装置（ＣＰＵ）８２、メモリ８３、及び、入力／出力（Ｉ／Ｏ）インターフェイス８４を含むことが可能である。コンピュータシステム８１は、一般に、Ｉ／Ｏインターフェイス８４を介してディスプレイ８５及びマウス及びキーボードのような各種入力装置８６に結合されている。支援回路には、キャッシュ、電源、クロック回路、及び、通信バスのような回路を含むことが可能である。メモリ８３には、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、ディスクドライブ、テープドライブ等、または、それらの組み合わせを含むことが可能である。本発明は、データベース８８からのデータを処理するため、メモリ８３に記憶され、ＣＰＵ８２によって実行されるルーチン８７として実施することが可能である。従って、コンピュータシステム８１は、本発明のルーチン８７の実行時に、専用コンピュータシステムになる、汎用コンピュータシステムである。
【００８４】
コンピュータシステム８１には、オペレーティングシステム及びマイクロ命令コードも含まれている。本明細書に記載のさまざまなプロセス及び機能は、マイクロ命令コードの一部、あるいは、オペレーティングシステムを介して実行されるアプリケーションプログラムの一部（またはそれらの組み合わせ）とすることが可能である。さらに、コンピュータプラットフォームには、追加データ記憶装置及び印刷装置のような他の各種周辺装置を接続することも可能である。
【００８５】
さらに、云うまでもなく、添付の図に描かれた構成要素であるシステムコンポーネント及び方法ステップの一部は、ソフトウェアで実施することができるので、システムコンポーネント（またはプロセスステップ）間の実際の関係は、本発明のプログラムの仕方によって異なる可能性がある。本明細書に記載の本発明の教示を前提として、関連技術者には、本発明のこれらの及び同様の実施または構成を検討することが可能になるであろう。
【００８６】
本発明については望ましい実施形態に関連して詳述してきたが、当該技術者には明らかなように、付属の請求項に記載の本発明の精神及び範囲から逸脱することなく、さまざまな修正及び置換を施すことが可能である。
【図面の簡単な説明】
【００８７】
【図１】本発明の実施形態の１つによるフィールド比較法の表である。
【図２】本発明の実施形態の１つによる典型的な確率値Ｐ0j（ｃj）の表である。
【図３】本発明の実施形態の１つによる典型的な確率値Ｐ1j（ｃj）の表である。
【図４】本発明の実施形態の１つによる個人名、住所、及び、電話フィールドがまとめられたデータベース行を例示した表である。
【図５】本発明の実施形態の１つによるＪｏｈｎ  Ｓｍｙｔｈｅの典型的な候補を表わした表である。
【図６】本発明の実施形態の１つによるＪｏｈｎ  Ｓｍｙｔｈｅについて報告される典型的な照会結果を例示した表である。
【図７】本発明の実施形態の１つによるデータ依存型検索フィルタリングプロセスのフローチャートである。
【図８】本発明の実施形態の１つによるデータ依存型検索フィルタリングプロセスを実施するための典型的なコンピュータシステムのブロック図である。
【符号の説明】
【００８８】
８１  コンピュータシステム
８２  中央演算処理装置
８３  メモリ
８４  Ｉ／Ｏインターフェイス
８５  ディスプレイ
８６  入力装置
８８  データベース
【図１】
2008546098.tif 000011
【図２】
2008546098.tif 000012
【図３】
2008546098.tif 000013
【図４】
2008546098.tif 000014
【図５】
2008546098.tif 000015
【図６】
2008546098.tif 000016
【図７】
2008546098.tif 000017
【図８】
2008546098.tif 000018
【国際調査報告】
2008546098.tif 000019
2008546098.tif 000020
2008546098.tif 000021