(57)【要約】【課題】広告型メールのメール配信方法の適切さの判断に利用可能な情報を得る。【解決手段】広告型メールの送信元のＩＰアドレス集合を登録するための広告型メール送信元データベース１３ｅと、非広告型メールの送信元のＩＰアドレス集合を登録するための非広告型メール送信元データベース１３ａ〜１３ｄと、を含む分類用データベース１３を備えている。メールヘッダの送信元ＩＰアドレスに対する最近傍探索を広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行い、当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求める。広告型メールの送信元ＩＰアドレス集合は広告型メールのメール配信方法の適切さの判断に利用可能な情報として出力される。【選択図】図３
2011022876.tif 000002
【特許請求の範囲】
【請求項１】
メール分類用のＩＰアドレス集合を登録するための分類用データベースと、
受信メールのメールヘッダに含まれるメール送信元のＩＰアドレスを抽出し、抽出されたＩＰアドレスに最も近似する最近傍アドレスを、最近傍探索によって前記分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類する分類部と、
を備えたメールフィルタリングシステムにおいて、
前記分類用データベースは、広告型メールの送信元のＩＰアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のＩＰアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記分類部は、前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行い、当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求め、受信メールから抽出された前記ＩＰアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するよう構成され、
前記広告型メール送信元データベースに登録されたＩＰアドレス集合を、広告型メールのメール配信方法の適切さの判断に利用可能な情報として出力する出力手段と、
を備えていることを特徴とするメールフィルタリングシステム。
【請求項２】
前記分類用ＩＰデータベースは、非広告型メールを送信した送信元サーバのＩＰアドレス集合を登録するための非広告型メール送信元データベースとして、前記広告型メール以外の迷惑メールを送信した送信元サーバのＩＰアドレス集合を登録するための迷惑メール送信元データベースと、正常なメールを送信した送信元サーバのＩＰアドレス集合を登録するための正常メール送信元データベースと、を含み、
前記分類部は、前記最近傍探索を前記広告型メール送信元データベース、前記迷惑メール送信元データベース及び正常メール送信元データベースそれぞれに対して行い、当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求めるよう構成されている
請求項１記載のメールフィルタリングシステム。
【請求項３】
前記広告メール送信元ＩＰアドレスデータベースは、ユーザ毎にＩＰアドレス集合を分けて登録するよう構成されている
請求項１又は２記載のメールフィルタリングシステム。
【請求項４】
前記広告型メール送信元アドレスは、広告型メールに分類されたメールの送信元ＩＰアドレスと当該メールの宛先であるユーザのユーザデータとを関連付けて保存する
請求項１〜３のいずれか１項に記載のメールフィルタリングシステム。
【請求項５】
指定されたＩＰアドレスが送信元アドレスであるメールが、前記分類部において広告型メールに分類された件数及び／又は非広告型メールに分類された件数を集計する手段を更に備えている
請求項１〜４のいずれか１項に記載のメールフィルタリングシステム。
【請求項６】
コンピュータを、請求項１〜５のいずれか１項に記載のメールフィルタリングシステムとして機能させるためのコンピュータプログラム。
【請求項７】
受信メールのメールヘッダに含まれるメール送信元のＩＰアドレスを抽出し、抽出されたＩＰアドレスに最も近似する最近傍アドレスを、最近傍探索によって、メール分類用のＩＰアドレス集合を登録するための分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類するメールフィルタリングシステムにおいて、広告型メールのメール配信方法の適切さの判断に利用可能な情報を生成する情報生成方法であって、
前記分類用データベースは、広告型メールの送信元のＩＰアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のＩＰアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記情報生成方法は、
前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行うステップと、
当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求めるステップと、
受信メールから抽出された前記ＩＰアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するステップと、
前記広告型メール送信元データベースに登録されたＩＰアドレスを、広告型メールのメール配信方法の適切さの判断に利用可能な情報として出力するステップと、
を含む情報生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メールフィルタリングシステム、そのコンピュータプログラム、情報生成方法に関するものである。
【背景技術】
【０００２】
近年、電子メールの利用を妨げる問題として迷惑メール（スパムメール）が挙げられる。不特定多数に大量に送信される迷惑メールは、メールトラフィックの増大やウィルスメールの拡散などを招き、経済的な損失まで引き起こしている。このため、迷惑メールを適切に検出できるメールフィルタリングシステムが求められている。
【０００３】
メールフィルタリングシステムとしては、メールの内容となる本文・タイトルなどの文章（コンテンツ）を解析して迷惑メール（スパムメール）を検出するコンテンツ分析型のシステムが一般的である。
【０００４】
ここで、迷惑メール（広義の迷惑メール）には、有害な情報やウイルスを含むなどしてほとんどの人々にとって迷惑であると感じられるメール（狭義の迷惑メール）と、一般の企業が宣伝広告のために送信するメールであって、その情報を必要としない人々には有益でないものの、その情報を必要とする人々には有益であるメール（広告用のメール、メールマガジンなど）と、が存在する。
【０００５】
後者のメール（以下、「広告型メール」という）は、企業等の正常な宣伝広告活動の一環として行われているものであり、狭義の迷惑メールとは区別して考えることができるが、これまで、前者と後者のメールを区別してフィルタリングするという発想はなかった。
【０００６】
ここで、本発明者は、ＮＮＩＰＦ（Nearest Neighbor IP address based mail Filter）とよばれるメールフィルタリングシステムを開発・運用している（非特許文献１参照）。
このＮＮＩＰＦでは、ユーザが、組織外部からメールを受け取るときに使用するＭＴＡ（Mail Transfer Agent）をシステムに予め登録されている。また、ＮＮＩＰＦでは、正常な送信者のＩＰアドレス集合と迷惑メールの送信者のＩＰアドレス集合を予め登録している。
【０００７】
ＮＮＩＰＦは、ユーザがシステムに登録したＭＴＡ（ＭＴＡＯＢ；MTA On Border）が外部からメールを受信したときに生成してメールヘッダに付加したReceived行から、メール送信元のＩＰアドレスを割り出す。
【０００８】
そして、ＮＮＩＰＦは、割り出したＩＰアドレスに関する最近傍探索を、予め登録されている正常な送信者のＩＰアドレス集合及び迷惑メールの送信者のＩＰアドレス集合に対して行う。これにより、予め登録されている正常な送信者のＩＰアドレス集合のうち、割り出したＩＰアドレスに最も近い値を持つＩＰアドレス（最近傍アドレス）が検出されるとともに、予め登録されている迷惑メールの送信者のＩＰアドレス集合のうち、割り出したＩＰアドレスに最も近い値を持つＩＰアドレス（最近傍アドレス）が検出される。
【０００９】
さらに、ＮＮＩＰＦは、割り出したＩＰアドレスと、正常な送信者の最近傍アドレス及び迷惑メール送信者の最近傍アドレスそれぞれとの距離（アドレス空間内での距離）を求め、これらの距離に基づいて、迷惑メールらしさを示す「弁別度」（０〜１の値）を求める。この弁別度が０であれば、ほぼ確実に正常なメールであり、逆に１であれば、ほぼ確実に迷惑メールであると判断される。また、０から１の間の中間値は、１に近いほど、迷惑メールらしさが高いことを示す。
【００１０】
ここで、ＮＮＩＰＦは、受信したメールの送信元ＩＰアドレスが、ブラックリスト（迷惑メールＩＰアドレスのリスト）又はホワイトリスト（正常メールＩＰアドレスのリスト）と一致するか一致しないかという「ブラックリスト／ホワイトリスト」型の分類とは異なるものである。
【００１１】
送信元ＩＰアドレスを「ブラックリスト／ホワイトリスト」で確認する場合、送信元ＩＰアドレスが、「ブラックリスト／ホワイトリスト」に含まれるアドレスと１ビットでも異なると、「一致しない」と判定してしまい、迷惑メールを確実に検出しようとすると、迷惑メールが発信される可能性のある全てのサーバのＩＰアドレス集合がブラックリストに登録されている必要があるが、これは運用上不可能である。
【００１２】
これに対し、ＮＮＩＰＦは、正常な送信者の最近傍アドレス及び迷惑メール送信者の最近傍アドレスそれぞれとの距離を求め、これらの距離に基づいて、迷惑メールらしさを示す「弁別度」を求めるため、迷惑メール送信者や正常な送信者のＩＰアドレス全てが予め登録されていなくても、迷惑メールを識別することができる。
【００１３】
しかも、ＮＮＩＰＦでは、正しく運用した場合、９８％以上の精度で分類が行えることが確認されている。これは、迷惑メールは、過去に迷惑メールを送信したことのあるサーバのＩＰアドレスと似たアドレス値のＩＰアドレスのサーバから送信されることが多く、正常なメールは、以前から受信し続けている送信元サーバのＩＰアドレスと似たアドレス値のＩＰアドレスから送信されることが多いという事実に基づいている。
【００１４】
このような傾向が現れる理由は、ＩＰアドレスが、国別、組織別に系統立って割り当てられており、迷惑メール送信元のＩＰアドレス集合には、ＩＰアドレスの全空間において偏りが見られるからである。例えば、ある著名な優良企業から迷惑メールが来ることはほとんど無く、一方で、外国の格安プロバイダに割り当てられているＩＰアドレスから迷惑メールが来る可能性は、著名な優良企業からよりも高い。
この傾向は、ＩＰアドレスの割り当てルールが変更にならない限り普遍であるため、迷惑メールを送信するサーバのＩＰアドレスは、決して均一に分布することはなく、統計的に有意な偏りを持ち続けるため、継続的に分類することが可能である。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】和田俊和，ＮＮＩＰＦ，［ｏｎｌｉｎ］，２００７年，［平成２１年７月１３日検索］，インターネット＜http://vrl.sys.wakayama-u.ac.jp/~twada/NNIPF.html＞
【発明の概要】
【発明が解決しようとする課題】
【００１６】
さて、企業等の正常な宣伝広告活動の一環として行われる広告型メールにおいては、テレビ放送における視聴率のように、メール配信の効果を測定するなどメール配信方法の適切さを検討可能であることが望まれる。
【００１７】
この点に関し、本発明者は、広告型メールにおけるメール配信方法の適切さを、メールフィルタリングシステムにおける広告型メールの通過／ブロックに基づいて判断できるようにする、という着想を得た。
【００１８】
例えば、広告型メールは、広告型メールを宣伝広告主のサーバからではなく、広告型メールの送信を請け負う専門業者のサーバから送信されることが多い。したがって、宣伝広告主からすると、どの専門業者を選択すべきか、という選択基準として、例えば、宣伝広告主が望むユーザにメールが届きやすいか否かという点が重要となる。
つまり、広告型メールでの宣伝広告を望む企業からすると、自社の広告型メールが、メールフィルタリングシステムでブロックされずに、できるだけ通過することが望ましい。
【００１９】
しかし、従来のフィルタリングシステムでは、広告型メールに着目してこれを区別してフィルタリングするという発想が従来なかったのは、上述の通りであり、ブロックされたメールが広告メールであるか否かを判定することができなかった。
また、前記ＮＮＩＰＦにおいても、広告型メールに着目してフィルタリングをすることは行われていなかった。
【００２０】
しかも、従来の一般的なコンテンツ分析型のメールフィルタリングシステムでは、広告型メールの文章（コンテンツ）が正常なメールの文章と区別し難いことが多いため、広告型メールだけを適切に抽出することができない。同じ理由から，コンテンツ分析型で、広告型メールを（広義の）迷惑メールとして検出しようとすると、正常なメールまでも迷惑メールとして検出されるおそれが高くなる。
さらに、広告型メールが受信されるべきものなのか、それとも受信拒否されるべきものかは、各ユーザの選好によるところが大きいため、コンテンツの内容だけから、正常に受信すべき広告型メールと受信拒否すべき広告型メールとを適切に区別することが困難である。
【００２１】
このため、従来の一般的なコンテンツ分析型のメールフィルタリングシステムは、広告型メールのメール配信方法の適切さの判断には利用することが困難である。
【００２２】
本発明は、上記問題に鑑み、広告型メールのメール配信方法の適切さの判断材料となる情報を生成できるメールフィルタリングシステム等を提供することを目的とする。
【課題を解決するための手段】
【００２３】
本発明者は、広告型メールの送信元ＩＰアドレス（例えば、広告型メール配信業者のＩＰアドレス）には、狭義の迷惑メールや正常メールのアドレスとは識別可能な偏りがあることを見出した。つまり、前記ＮＮＩＰのように、メール送信元ＩＰアドレスを元に最近傍探索を行って弁別度を求める方式では、過去に広告型メールを送信したサーバのＩＰアドレス集合を予め登録しておけば、新たに受信したメールのフィルタリングの際に広告型メールを識別して、広告型メールらしさの弁別度を求めることが可能であり、これを利用して、広告型メールのメール配信方法の適切さの判断に利用可能な情報を生成できるという着想を得て、本発明を完成した。
【００２４】
（１）本発明は、
メール分類用のＩＰアドレス集合を登録するための分類用データベースと、
受信メールのメールヘッダに含まれるメール送信元のＩＰアドレスを抽出し、抽出されたＩＰアドレスに最も近似する最近傍アドレスを、最近傍探索によって前記分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類する分類部と、
を備えたメールフィルタリングシステムにおいて、
前記分類用データベースは、広告型メールの送信元のＩＰアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のＩＰアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記分類部は、前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行い、当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求め、受信メールから抽出された前記ＩＰアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するよう構成され、
前記広告型メール送信元データベースに登録されたＩＰアドレス集合を、広告型メールのメール配信方法の適切さの判断に利用可能な情報として出力する出力手段と、
を備えていることを特徴とするメールフィルタリングシステムである。
【００２５】
（２）前記分類用ＩＰデータベースは、非広告型メールを送信した送信元サーバのＩＰアドレス集合を登録するための非広告型メール送信元データベースとして、前記広告型メール以外の迷惑メールを送信した送信元サーバのＩＰアドレス集合を登録するための迷惑メール送信元データベースと、正常なメールを送信した送信元サーバのＩＰアドレス集合を登録するための正常メール送信元データベースと、を含み、
前記分類部は、前記最近傍探索を前記広告型メール送信元データベース、前記迷惑メール送信元データベース及び正常メール送信元データベースそれぞれに対して行い、当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求めるよう構成されているのが好ましい。
【００２６】
（３）前記広告メール送信元ＩＰアドレスデータベースは、ユーザ毎にＩＰアドレス集合を分けて登録するよう構成されているのが好ましい。
【００２７】
（４）前記広告型メール送信元アドレスは、広告型メールに分類されたメールの送信元ＩＰアドレスと当該メールの宛先であるユーザのユーザデータとを関連付けて保存するのが好ましい。
【００２８】
（５）指定されたＩＰアドレスが送信元アドレスであるメールが、前記分類部において広告型メールに分類された件数及び／又は非広告型メールに分類された件数を集計する手段を更に備えているのが好ましい。
【００２９】
（６）他の観点からみた本発明は、コンピュータを、上記（１）〜（４）のいずれか１項に記載のメールフィルタリングシステムとして機能させるためのコンピュータプログラムである。
【００３０】
（７）さらに他の観点からみた本発明は、受信メールのメールヘッダに含まれるメール送信元のＩＰアドレスを抽出し、抽出されたＩＰアドレスに最も近似する最近傍アドレスを、最近傍探索によって、メール分類用のＩＰアドレス集合を登録するための分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類するメールフィルタリングシステムにおいて、広告型メールのメール配信方法の適切さの判断に利用可能な情報を生成する情報生成方法であって、
前記分類用データベースは、広告型メールの送信元のＩＰアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のＩＰアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記情報生成方法は、
前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行うステップと、
当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求めるステップと、
受信メールから抽出された前記ＩＰアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するステップと、
前記広告型メール送信元データベースに登録されたＩＰアドレスを、広告型メールのメール配信方法の適切さの判断に利用可能な情報として出力するステップと、
を含む情報生成方法である。
【発明の効果】
【００３１】
本発明によれば、メールフィルタリングシステムから、広告型メールのメール配信方法の適切さの判断材料となる情報を出力することができる。
【図面の簡単な説明】
【００３２】
【図１】ＭＴＡＯＢの概念のメールフィルタリングシステムの配置を示す図である。
【図２】メールフィルタリングシステムの入出力機能を示す概略図である。
【図３】メールフィルタリングシステムの内部機能を示す概略図である。
【図４】分類用ＩＰアドレスデータベースの構成図である。
【図５】分類部の構成図である。
【図６】ＩＰアドレスからＩＰアドレス値への変換の説明図である。
【図７】Ｂ木の追加操作を示す図である。
【図８】Ｂ木の削除操作を示す図である。
【図９】Ｂ木の最近傍探索を示す図である。
【図１０】Ｂ＋木の追加操作を示す図である。
【図１１】Ｂ＋木の削除操作を示す図である。
【図１２】Ｂ＋木の最近傍探索を示す図である。
【図１３】Ｂ木のＧＩＰのファイルサイズと探索速度を示すグラフである。
【図１４】Ｂ木のＢＩＰのファイルサイズと探索速度を示すグラフである。
【図１５】Ｂ＋木のＧＩＰのファイルサイズと探索速度を示すグラフである。
【図１６】Ｂ＋木のＢＩＰのファイルサイズと探索速度を示すグラフである。
【図１７】サイズ比較の対数グラフである。
【図１８】ＧＩＰのｅｘａｃｔ  ｍａｔｃｈ平均速度のグラフである。
【図１９】ＢＩＰのｅｘａｃｔ  ｍａｔｃｈ平均速度のグラフである。
【図２０】最近傍探索平均速度のグラフである。
【図２１】追加・削除の動作の平均速度のグラフである。
【発明を実施するための形態】
【００３３】
以下、本発明の好ましい実施形態について添付図面を参照しながら説明する。
【００３４】
［１．最近傍探索型フィルタリングシステムの概要と用語の定義］
図１及び図２は、実施形態に係るメールフィルタリングシステム（フィルタリング用サーバ）１の運用形態を例示している。図１に示すように、メールユーザが使用するメール送受信ソフトウエアおよびそれが動作するコンピュータを、「ＵＭＡ」（User Mail Agent）という。また、ある組織（メールサーバを有する企業・大学などの団体、インターネットサービスプロバイダなど）Ｓに、複数のＭＴＡ（Mail Transfer Agent）が設置されている場合に、ＵＭＡに対して通常のメール受信のための受信メールボックスを提供するＭＴＡを、「Ｂａｓｅ  ＭＴＡ」という。また、メールユーザが、組織Ｓ外部からメールを受け取る際に、当該組織Ｓ内のＭＴＡであって、外部サーバからメールを受信するＭＴＡをＭＴＡＯＢ（MTA On the Border）という。
【００３５】
本実施形態では、Ｂａｓｅ  ＭＴＡは、メールを受信すると、実施形態に係るフィルタリングシステム（フィルタリング用サーバ））１にメールを転送するよう設定されている。図２に示すように、本フィルタリングシステム１は、転送されてきたメールを分類し、正常なメールは、メールユーザごとの分類済メールボックスに格納される。メールユーザは、フィルタリングシステム１を利用してメールを受信する場合、Ｂａｓｅ  ＭＴＡではなく、フィルタリングシステム１の分類済みメールボックスからメールを取得する。つまり、フィルタリングシステム１において、正常でないメール（迷惑メール・広告型メール）は、ブロックされ、正常なメールは通過する。
【００３６】
また、本フィルタリングシステム１は、メールを分類した結果に基づいて、広告型メールのメール配信方法の適切さの判断に利用可能な情報を出力する。
【００３７】
なお、本実施形態のフィルタリングシステム１は、Ｂａｓｅ  ＭＴＡと同じサーバに搭載されていてもよい。また、フィルタリングシステムの各機能は、同一サーバに搭載されている必要はなく、分散していてもよい。
【００３８】
［２．メールの送信元ＩＰアドレスについて］
各ＭＴＡは、メールを受信して転送する度に、メールヘッダに、図１に示すようなＲｅｃｅｉｖｅｄ行を付加する。Ｒｅｃｅｉｖｅｄ行には、「Ｆｒｏｍ」の後に、当該ＭＴＡへメールを送信したサーバのＩＰアドレスが記載され、「ｂｙ」の後に、当該ＭＴＡのＩＰアドレスが記載される。
【００３９】
メールは、複数のＭＴＡを転送されてくるため、一つのメールのメールヘッダには、複数のＲｅｃｅｉｖｅｄ行が付加されているのが一般的であるが、複数のＲｅｃｅｉｖｅｄ行のうち、組織Ｓの外部サーバからメールを受信するＭＴＡＯＢが「ｂｙ」の後に記載されているＲｅｃｅｉｖｅｄ行をみれば、そのＲｅｃｅｉｖｅｄ行の「Ｆｒｏｍ」の後のＩＰアドレスが、メール送信元のＩＰアドレスであることがわかる。ＭＴＡＯＢが「ｂｙ」の後に記載されているＲｅｃｅｉｖｅｄ行は、ユーザの属する組織ＳのＭＴＡＯＢが付加したものであるため、送信元ＩＰアドレスの偽装は困難であり、送信元の正しいＩＰアドレスが得られる。
【００４０】
本フィルタリングシステム１は、メールヘッダに含まれる送信元ＩＰアドレスを用いて、メールの分類を行う。
【００４１】
［３．メールフィルタリングシステムの構成］
図３は、本メールフィルタリングシステム（以下、単に「システム」という）１の機能ブロックを示している。なお、本システム１は、サーバ（コンピュータ）１にメールフィルタリング用コンピュータプログラムをインストールして構成されており、以下に説明するシステム１の機能は、当該プログラムがサーバ（コンピュータ）１によって実行されることで発揮されるものである。
【００４２】
本システム１は、メールユーザが各種設定などの入力を行うためのインターフェース部１１、メールを分類する分類部１２、分類のためのＩＰアドレスが登録された分類用ＩＰアドレスデータベース１３、メールユーザの情報（年齢、性別、地域、職業など）が登録されたユーザデータベース１４、指定ＩＰアドレスを記憶するための指定ＩＰアドレス記憶部１５、及び通過率データ記憶部１６、デーベース１３を検索するための検索部１７、及び指定ＩＰアドレスを送信元とするメールのフィルタ通過率算出部１８を備えている。
【００４３】
前記インターフェース部１１は、Ｗｅｂサーバとしての機能を有しており、ユーザは、（ＵＭＡが搭載された）ユーザコンピュータから、Ｗｅｂブラウザ機能によって、必要な情報の閲覧や入力を行うことができる。インターフェース部１１では、分類部１２に転送された各メールの分類状況をユーザに対して表示させたり、分類未確定のメールについて正常メールであるか非正常メール（受信したくない広告型メール又は迷惑メール）であるかの区別の入力をユーザから受け付けたり、システム１が誤って分類したメールやシステムが分類不能と判断したメールについて、ユーザが手動入力で適切に分類（広告型メール、迷惑メール、正常なメールのいずれか）するためのユーザからの入力を受け付けたりすることができる。
【００４４】
前記分類部１２では、当該分類部１２に転送されてきたメールを、自動的に、広告型メール、迷惑メール、正常なメールのいずれかに分類し、正常なメールを、メールユーザ毎の分類済メールボックスに格納する。このため、メールユーザは、不要な広告型メールや迷惑メールをUMAで受信することを回避できる。なお、正常なメールには、広告型メールが含まれることがある。
この分類部１３の詳細については後述する。
【００４５】
図４に示すように、前記分類用ＩＰアドレスデータベース１３には、５種類のデータベースが含まれる。すなわち、正常メール送信者ＩＰアドレス共通データベース１３ａ、迷惑メール送信者ＩＰアドレス共通データベース１３ｂ、正常メール送信者ＩＰアドレス個人用データベース１３ｃ、迷惑メール送信者ＩＰアドレス個人用データベース１３ｄ、広告型メール送信者ＩＰアドレス個人用データベース１３ｅの５種類である。
【００４６】
正常メール送信者ＩＰアドレス共通データベース１３ａ及び正常メール送信者ＩＰアドレス個人用データベース１３ｃは、正常メールの送信元ＩＰアドレスを登録するためのものである。
【００４７】
これらの正常メールに関するデータベース１３ａ，１３ｃうち、共通データベース１３ａは、各メールユーザについて共通して利用されるデータベースである。例えば、優良な企業や公的団体からのメールは、多くのユーザにとって正常メールとして扱われるべきものであるため、そのような企業や公的団体の送信元サーバのＩＰアドレスが、予め共通データベース１３ａに登録されている。
【００４８】
一方、個人用データベース１３ｃは、メールユーザごとに設けられており、各ユーザ宛のメールのうち、正常メールと分類されたものであって、その送信元ＩＰアドレスが共通データベース１３ａに登録されていないメールの送信元ＩＰアドレスが登録される。
この個人用データベース１３ｃには、例えば、各ユーザが日常的にメールをやり取りする相手の送信元サーバのＩＰアドレスが登録されることになる。
【００４９】
迷惑メール送信者ＩＰアドレス共通データベース１３ｂ及び迷惑メール送信者ＩＰアドレス個人用データベース１３ｄは、迷惑メールの送信元ＩＰアドレスを登録するためのものである。
【００５０】
これらの迷惑メールに関するデータベース１３ｂ，１３ｄうち、共通データベース１３ｂは、各メールユーザについて共通して利用されるデータベースである。例えば、有害情報を含むメールやウィルスメールは、多くのユーザにとって迷惑メールとして扱われるべきものであるため、そのようなメールの送信元サーバのＩＰアドレスは、この共通データベース１３ｂに予め登録されている。
【００５１】
一方、個人用データベース１３ｄは、メールユーザごとに設けられており、各ユーザ宛のメールのうち、迷惑メールと分類されたものであって、その送信元ＩＰアドレスが共通データベース１３ｂに登録されていないメールの送信元ＩＰアドレスが登録される。
【００５２】
なお、個人用データベース１３ｃ，１３ｄに登録されているＩＰアドレスのうち、多くのユーザの個人用データベース１３ｃ，１３ｄに登録された結果、共通性が高まったと判断したＩＰアドレスについては、システム１が対応する共通データベース１３ａ，１３ｂに格納する。
【００５３】
上記の４つのデータベース１３ａ，１３ｂ，１３ｃ，１３ｄは、広告型メール以外の非広告型メールである正常メール及び／又は迷惑メールを送信した送信元サーバのＩＰアドレスを登録する「非広告型メール送信元ＩＰアドレスデータベース」である。
これに対し、広告型メール送信元個人用データベース１３ｅは、広告型メールを送信した送信元サーバのＩＰアドレスを登録する「広告型メール送信元ＩＰアドレスデータベース」である。
【００５４】
この広告型メール送信元個人用データベース１３ｅは、メールユーザごとに設けられており、メールユーザごとの広告型メール送信元ＩＰアドレスが登録される。
「広告型メール送信元ＩＰアドレスデータベース」としては、この広告型メール送信元個人用データベース１３ｅだけが設けられており、正常メールや迷惑メールのように、共通データベースは設けられていない。
したがって、広告型メールに分類されたメールの送信元ＩＰアドレスは、すべて、各ユーザの広告型メール送信元個人用データベース１３ｅに登録される。共通データベースを設けないことで、ユーザごとの広告型メールの受信状況が把握し易くなる。
【００５５】
広告型メール送信元個人用データベース１３ｅには、興味を失った商品等の広告メールや読まなくなったメールマガジンなど、過去においては正常メールとして分類されていたが、現在は受信の必要がなくなったメールや、無差別に送信されてきて受信したくない広型メールなどの送信元サーバのＩＰアドレスが登録される。なお、ユーザがメールを手入力で分類してデータベース１３に登録する場合、迷惑メールか広告型メールかはユーザの主観で行えば足りる。
【００５６】
［４．分類部の詳細］
図５は、分類部１２の機能ブロックを示している。この分類部１２は、転送されてきたメールを受信する受信部１２１、受信部１２１で受信したメールの送信元ＩＰアドレスを抽出するＩＰアドレス抽出部１２２、抽出したＩＰアドレスを元に分類用ＩＰアドレスデータベース１３での最近傍探索を行う最近傍探索部１２３、最近傍探索の結果から弁別度を算出する弁別度算出部１２４、弁別度に基づいて受信したメールを分類するメール分類部１２５、正常メールであると分類されたメールを格納する分類済メールボックス１２６、受信部１２１で受信したメールのうち指定ＩＰアドレスが送信元であるメールを検出する指定ＩＰアドレス検出部１２７を備えている。
【００５７】
［４．１  ＩＰアドレス抽出部］
ＩＰアドレス抽出部１２２は、受信部１２１で受信したメールのメールヘッダに付加されているＲｅｃｅｉｖｅｄ行のうち、そのメールの受信者であるユーザのＭＴＡＯＢであるとしてシステム１に登録されているＭＴＡが、Ｒｅｃｅｉｖｅｄ行の「ｂｙ」の後に記載されているＲｅｃｅｉｖｅｄ行を抽出する。さらに、ＩＰアドレス抽出部１２２は、その抽出したＲｅｃｅｉｖｅｄ行における「ｆｒｏｍ」の後のＩＰアドレスを、送信元ＩＰアドレスとして抽出する。
なお、各ユーザのＭＴＡＯＢは、システム１に予め登録されている。
【００５８】
［４．２  最近傍探索部］
最近傍探索部１２３は、ＮＮＩＰＦと同様の最近傍探索理論に基づいて、抽出アドレスの最近傍アドレスを探索する。
すなわち、本実施形態の最近傍探索部１２３は、ＩＰアドレス抽出部１２２で抽出されたＩＰアドレス（抽出ＩＰアドレス；未知のＩＰアドレス）の最近傍アドレスを、分類用ＩＰアドレスデータベースにおける各データベース１３ａ，１３ｂ，１３ｃ，１３ｄ，１３ｅそれぞれで探索する。
【００５９】
具体的には、最近傍探索部１２３は、正常メール送信者ＩＰアドレス共通データベース１３ａにおける最近傍アドレス（第１最近傍アドレス）、迷惑メール送信者ＩＰアドレス共通データベース１３ｂにおける最近傍アドレス（第２最近傍アドレス）、メールの受信者であるユーザについての正常メール送信者ＩＰアドレス個人用データベース１３ｃにおける最近傍アドレス（第３最近傍アドレス）、メールの受信者であるユーザについての迷惑メール送信者ＩＰアドレス個人用データベース１３ｄにおける最近傍アドレス（第４最近傍アドレス）、及びメールの受信者であるユーザについての広告型メール送信者ＩＰアドレス個人用データベース１３ｅにおける最近傍アドレス（第５最近傍アドレス）を探索し、５つの最近傍アドレスを取得する。
この探索方法の詳細については、後述する。
【００６０】
また、最近傍探索部１２３は、正常メールに関する第１最近傍アドレス及び第３最近傍アドレスのうち、抽出ＩＰアドレスにより近いアドレスを、「正常メールとしての最近傍アドレス」とするとともに、迷惑メールに関する第２最近傍アドレス及び第３最近傍アドレスのうち、抽出ＩＰアドレスにより近いアドレスを、「迷惑メールとしての最近傍アドレス」とする。
【００６１】
ここで、正常メールとしての最近傍アドレスを「ＮＮ（ＩＰ；ＧＩＰ）」と表し、
迷惑メールについての最近傍アドレスを「ＮＮ（ＩＰ；ＢＩＰ）」と表し、
広告メールとしての最近傍アドレス（第４最近傍アドレス）を「ＮＮ（ＩＰ；ＡＩＰ）」と表し、
抽出ＩＰアドレス（未知ＩＰアドレス；ＩＰ）と、正常メールとしての最近傍アドレスＮＮ（ＩＰ；ＧＩＰ）との距離を、ＤGIP（ＩＰ）＝ｄｉｓｔ（ＩＰ，ＮＮ（ＩＰ；ＧＩＰ））と表し、
抽出ＩＰアドレス（未知ＩＰアドレス；ＩＰ）と、迷惑メールとしての最近傍アドレスＮＮ（ＩＰ；ＢＩＰ）との距離を、ＤBIP（ＩＰ）＝ｄｉｓｔ（ＩＰ，ＮＮ（ＩＰ；ＢＩＰ））と表し、
抽出ＩＰアドレス（未知ＩＰアドレス；ＩＰ）と、広告型メールとしての最近傍アドレスＮＮ（ＩＰ；ＡＩＰ）との距離を、ＤAIP（ＩＰ）＝ｄｉｓｔ（ＩＰ，ＮＮ（ＩＰ；ＡＩＰ））と表す。
なお、距離の求め方については後述するが、最近傍探索部１２３は、抽出ＩＰアドレスと各最近傍アドレスとから、これらの距離ＤGIP，ＤBIP，ＤAIPそれぞれ求めて出力する。
【００６２】
［４．３  弁別度算出部］
前記弁別度算出部１２４は、前記距離ＤGIP，ＤBIP，ＤAIPに基づいて、抽出ＩＰアドレスの迷惑メールの送信元らしさを示す弁別度、及び広告型メールの送信元らしさ示す弁別度を算出する。
【００６３】
ここで、抽出ＩＰアドレス（ＩＰ）が、迷惑メールの送信元らしいかを示す弁別度は、次式で表される。
【数１】
2011022876.tif 000003
【００６４】
また、抽出ＩＰアドレス（ＩＰ）が、広告型メールの送信元らしいかを示す弁別度は、次式で表される。
【数２】
2011022876.tif 000004
【００６５】
これは、正常メールの事前確率Ｐ（Ｇｏｏｄ）、迷惑メールの事前確率Ｐ（Ｂａｄ）、広告型メールの事前確率Ｐ（Ａｄｖ）がともに１／３で、正規確率分布をそれぞれ、Ｐ（ＩＰ｜Ｇｏｏｄ）＝１／ＤGIP，Ｐ（ＩＰ｜Ｂａｄ）＝１／ＤBIP，Ｐ（ＩＰ｜Ａｄｖ）＝１／ＤAIPとした場合に、下記のように迷惑メール及び広告型メールの事後確率をＢａｙｅｓ則で計算した結果と一致する。
【数３】
2011022876.tif 000005
【数４】
2011022876.tif 000006
【００６６】
上記のＰ（Ｓｐａｍ｜ＩＰ）は、抽出ＩＰアドレスが迷惑メール送信元ＩＰアドレスである確率（迷惑メール弁別度）を示しており、０〜１の値をとる。弁別度算出部１２４は、上記のＰ（Ｓｐａｍ｜ＩＰ）の式に基づいて弁別度を算出する。この値が、１に近いほど、迷惑メール送信元ＩＰアドレスである確率が高いことを示している。
また、上記のＰ（Ａｄｖ｜ＩＰ）は、抽出ＩＰアドレスが広告型メール送信元ＩＰである確率（広告型メール弁別度）を示しており、０〜１の値をとる。弁別度算出部１２４は、上記のＰ（Ａｄｖ｜ＩＰ）の式に基づいて弁別度を算出する。この値が、１に近いほど、広告メール送信元ＩＰアドレスである確率が高いことを示している。
また、抽出ＩＰアドレスが正常メール送信元ＩＰアドレスである確率（正常メール弁別度）は、Ｐ（Ｇｏｏｄ｜ＩＰ）＝１−（Ｐ（Ｓｐａｍ｜ＩＰ）＋Ｐ（Ａｄｖ｜ＩＰ））で求められる。
【００６７】
［４．４  メール分類部］
前記メール分類部１２５は、上記の弁別度Ｐ（Ｓｐａｍ｜ＩＰ），Ｐ（Ａｄｖ｜ＩＰ），Ｐ（Ｇｏｏｄ｜ＩＰ）に基づいて、分類対象の受信メールを、迷惑メール、広告型メール、正常メールのいずれかに分類する。
【００６８】
メール分類部１２５は、３つの弁別度Ｐ（Ｓｐａｍ｜ＩＰ），Ｐ（Ａｄｖ｜ＩＰ），Ｐ（Ｇｏｏｄ｜ＩＰ）のうち、最も大きな値を持つ分類（迷惑メール、広告型メール、正常メール）を決定し、受信メールはその分類に振り分けられ、当該受信メールの送信元ＩＰアドレス（抽出ＩＰアドレス）は、対応するデータベース１３ａ〜１３ｅに登録される。また、正常メールについては、分類済メールボックス１２６に格納され、ＵＭＡがメールを取得可能となる。
なお、決定した分類が迷惑メール又は正常メールである場合、その抽出ＩＰアドレスが、共通データベース１３ａ，１３ｂに登録されていない場合に、個人用データベース１３ｃ，１３ｄに登録する。
【００６９】
また、決定した分類が広告型メールである場合、メール分類部１２５は、メールの受信者であるユーザのユーザデータをユーザデータベース１４から取得し、抽出ＩＰアドレスに前記ユーザデータを関連付けた上で、当該抽出ＩＰアドレスを、広告型メール送信者ＩＰアドレス個人用データベース１３ｅに登録する。なお、個人用データベース１３ｃ，１３ｄについても、抽出ＩＰアドレスとユーザデータとを関連づけて登録してもよい。
【００７０】
このように、本システム１では、広告型メールのフィルタリングが行えるとともに、ブロックされた広告型メールの送信元ＩＰアドレスとブロックしたユーザ（メールの宛先ユーザ）のユーザデータとを関連づけたデータ（データベース１３ｅ）が得られる。このデータは、広告型メールのメール配信方法の適切さの判断材料となる情報として利用される。
【００７１】
また、弁別度を用いたメールの分類の際には、閾値を用いても良い。例えば、迷惑メール弁別度又は広告型メール弁別度は、所定の閾値Ｔ１以上でなければ、迷惑メール又は広告型メールとみなさないものとして扱うことができる。また、閾値は、２個又は３個以上設けてもよく、閾値に応じて迷惑メールらしさや広告型メールらしさを判定してもよい。また、その判定結果は、ユーザに対して、分類された各メールの色分け表示などに用いることができる。
【００７２】
［４．５  指定ＩＰアドレス検出部］
前記指定ＩＰアドレス検出部１２７は、指定ＩＰアドレス記憶部１５に記憶されている指定ＩＰアドレスが送信元ＩＰアドレスとなっているメールの受信状況（全受信数）を検出するとともに、指定ＩＰアドレスが送信元ＩＰアドレスとなっているメールが正常メールに分類された数及び／又は広告型メールに分類された数を検出する。また、迷惑メールに分類された数も検出してもよい。
【００７３】
指定ＩＰアドレス記憶部１５には、例えば、広告型メールの広告主から指定されたＩＰアドレス（広告型メールの送信元ＩＰアドレス）が入力されて記憶されている。指定ＩＰアドレス検出部１２７は、分類用ＩＰアドレスデータベース１３及び／又は分類部１２５での分類結果に基づいて、その指定ＩＰアドレスを持つ広告型メールが本システム１を通過した件数や、本システムでブロックされた件数を検出することができる。
【００７４】
これらの検出結果は、通過率算出部１８において、広告メールの通過率及び／又はブロック率の算出に用いられる。通過率は、［指定ＩＰアドレスを持つメールが正常メールに分類された件数／指定ＩＰアドレスを持つメールの全件数］で算出でき、ブロック率は、［指定ＩＰアドレスを持つメールが広告型メールに分類された件数／指定ＩＰアドレスを持つメールの全件数］で算出できる。
この算出結果は、システム１から出力され、広告型メールの広告主へ提供される情報となる。また、算出結果には、通過又はブロックしたユーザのユーザデータも付加してもよい。このような通過率又はブロック率が得られることで、広告主としては、依頼している広告メール配信業者が、適切な送信元ＩＰアドレスを持っているか否かを検討することが可能となる。
【００７５】
［５．  分類用ＩＰアドレスデータベースの検索］
前記検索部１７では、ＩＰアドレスを検索キーにして、分類用ＩＰアドレスデータベース１３を検索し、検索キーのＩＰアドレスが、各データベース１３ａ〜１３ｅにおいて登録されているか否かを検索し、出力することができる。
また、検索部１７からＩＰアドレスを検索キーとして、広告型メール送信者ＩＰアドレス個人用データベース１３ｅを検索すると、当該データベース１３ｅにおいて、そのＩＰアドレスに関連づけて登録されているユーザデータを抽出することができる。
例えば、広告型メールの広告主が、広告型メールがどの程度、本システム１においてどのようなユーザに広告型メールとしてブロックされているかを知りたい場合、当該広告型メールの送信元ＩＰアドレスを検索キーとして入力して検索し、抽出されたユーザデータを解析すればよい。
【００７６】
［６．最近傍探索の詳細］
以下、前記最近傍探索部１２３による最近傍探索理論について説明する。
【００７７】
［６．１  ＩＰアドレス］
本実施形態で使用するＩＰアドレスは、現在多く使用されているＩＰｖ４プロトコルに基づく。ＩＰｖ４のＩＰは、通常０〜２５５の数字４組をドットで繋いだ記法で表記される。本実施形態においては、ＩＰアドレスの距離計算を行うときは、ＮＮＩＰＦと同様に、ＩＰアドレスを２５６進数と考え１０進数表記に変換したＩＰアドレス値により行う。ＩＰアドレスからＩＰアドレス値を求めるには、図６に示すように、ＩＰアドレスの左側を上位桁として、各桁に対して、上位側から順に、２５６3、２５６2、２５６1、２５６0の桁重みを乗じて、１０進数のＩＰアドレスを求める。ＩＰアドレス値による距離計算は、ＮＮＩＰＦ採用されており、上記ＩＰアドレス値による距離計算によって適切に分類が行えることが確認されている。
【００７８】
データベース１３ａ〜１３ｅでは、ＩＰアドレス及びこのＩＰアドレス値が保存される。また、ＩＰアドレスは、バイナリデータで保存される。 ＩＰアドレスをバイナリデータに変換すると、ＩＰアドレスの各オクテットが１バイトになるので１つのＩＰアドレスを４バイトで扱うことができる。
【００７９】
［６．２  データベース１３の構築方法］
本システム１では、メールから抽出された送信元ＩＰアドレスを最近傍探索によって分類する。このため、分類数に応じた既知ＩＰアドレスの集合が必要となる。すなわち、正常メール、迷惑メール、広告型メールの３つに分類するのであれば、ＩＰ既知の正常メール送信者のＩＰアドレスの集合（データベース１３ａ，１３ｃ）、既知の迷惑メール送信者のＩＰアドレスの集合（データベース１３ｂ，１３ｄ）、既知の広告型メール送信者のＩＰアドレスの集合（データベース１３ｅ）それぞれが必要であり、これらの集合の中から、メールから抽出された送信元ＩＰアドレスの最近傍アドレスを抽出することになる。
【００８０】
従来のＮＮＩＰＦでは、既知のＩＰアドレスの集合を記憶するために、数百〜数千のＩＰアドレスをディレクトリの階層構造を利用し、入力されたメールのＩＰアドレスに最も近いアドレス（最近傍アドレス）を探索する。このため、通常のファイルシステムではディスクスペースを大量に消費してしまうという問題点がある。この問題を回避するために、個々のデータベース１３ａ〜３ｅを単一ファイルに格納し、それを読み込みメモリ上で最近傍探索を行う方法も考えられる。しかし、本システム１はメールが到着するたびに起動されるため、数千ものデータをファイルから読み込んでいたのでは、効率が良くない。
【００８１】
このような問題点を解決するため、本実施形態では、コンピュータ１の補助記憶装置（ハードディスク等）に格納されたデータをメモリに展開せずに最近傍探索を行う方法を採用する。これはソートアルゴリズムが内部ソートと外部ソートに分類されることになぞらえると、外部最近傍探索とも呼べる内容である。この外部最近傍探索のために、本実施形態では、Ｂ木又はＢ＋木を用いる。これらはもともと、一致型（Exact Match）の探索を前提としたデータ構造であるが、本実施形態ではこれらを最近傍探索に用いる。
【００８２】
本実施形態では、５つのデータベース１３ａ〜１３ｅそれぞれに対応するファイルをコンピュータ１の補助記憶装置（ハードディスク等）に設ける。ファイル内には、Ｂ木又はＢ＋木構造で、ＩＰアドレス値（及びＩＰアドレス）が保存される。
ファイル内にＢ木又はＢ＋木を構築することにより、探索はファイル内の移動のみで行うことができ、すべてのデータをメモリにロードする必要がなく効率が良い。
以下、Ｂ木及びＢ＋木を用いてＩＰアドレス値（ＩＰアドレス）をファイルに格納することにより、ディスクスペースの消費を抑え、メモリにロードしないで最近傍探索する方法について述べる。
【００８３】
［６．２．１  Ｂ木を用いたＩＰアドレスの格納］
ここでは、Ｂ木の定義や追加、削除などの操作を紹介し、Ｂ木を用いてＩＰアドレスをファイルに格納する方法とＢ木の最近傍探索について述べる。
【００８４】
［６．２．１．１  Ｂ木］
Ｂ木とは、システムにおけるインデックスやファイルシステムに用いられる木構造で、多分木の平衡木（バランス木）の一種である。Ｂ木は、ノード内のキーの個数を決定する次数ｋの値を持つ。ｋ次のＢ木の場合、次のように定義される。
【００８５】
・根以外の節には、ｋ個以上２ｋ個以下のキーが格納される。それぞれのキー（ｍ個とする）をａ［１］，・・・・・・，ａ［ｍ］とする。
・根には１個以上2ｋ個以下のキーが格納される。
・葉以外の任意の節には、部分木へのポインタがｍ＋１個ある・ただし、ｍはその節に格納されているキーの個数である。これらのポインタをｐ［１］，・・・・・・・，ｐ［ｍ］とする。
・すべての葉は同一レベルにある。
・任意の節において、キー列ａ［１］，・・・・・・，ａ［ｍ］は整列している。また、キーａ［ｉ］(１≦ ｉ ≦ ｍ)はｐ［ｉ−１］の指す部分木内のどのキーよりも大きく、逆にｐ［ｉ］の指す部分木内のどのキーよりも小さい。
以上が、ｋ次のＢ木の定義である。
本実施形態では、キーとしてＩＰアドレス値が格納される。
【００８６】
また、キーの探索は、各節のキー列は整列しているので二分探索によって行う。Ｂ木の大きな特徴は、動的ファイル操作に対する緩衝効果である。キーの分割によってノードが分割されると、分割直後のノードは空きスペースが十分あるので,しばらくは分割のような大がかりな構造の手直しは起こらない。削除についても同様である。特に、追加と削除が混雑しているような状況では緩衝効果によりノードの分割も連結の動作もほとんど必要とならない。
【００８７】
［６．２．１．２  Ｂ木のキー（ＩＰアドレス値）の追加］
Ｂ木のキー（ＩＰアドレス値）の追加の操作を、図７（ａ）の２次のＢ木を例に示す。
【００８８】
（１）キー（ＩＰアドレス値）１０の追加
まず、図７（ａ）に示すＢ木において、キー１０を探索すると格納すべきノードが見つかる。図７（ｂ）に示すように、このノードにはキーが２個含まれており、一個追加しても条件を満たすので単純に追加すればよい。
【００８９】
（２）キー（ＩＰアドレス値）３０の追加
図７（ａ）に示すＢ木において、キー３０を探索すると、格納すべきノードが見つかる。図７（ｃ）に示すように、この節には上限の４個のキーが格納されている。この場合は、キー３０を仮に挿入した後、二つに分割し中央のキー（ここでは「３０」）を親節に上げる。
【００９０】
上記（１），（２）で示した通り、Ｂ木におけるキーの追加は単純追加または分割によって行われる。分割によって中央のキーが親節に送られるが、もし親節にも最大限数のキーが既に入っていた場合、親ノードが再び分割されて、さらにその親に中央キーが送られる、このような操作が繰り返し起こり、時には根自体が分割され木の高さが一つ増えることも起こる、B木の高さが大きくなるのはこのように分割操作が根にまで及んだときに起こる。
【００９１】
［６．２．１．３  Ｂ木のキー（ＩＰアドレス値）の削除］
Ｂ木からのキーの削除の操作を、図８（ａ）の２次のＢ木を例に示す。
【００９２】
（１）キー６２の削除
キー６２を探索すると、葉ノードが見つかる。この場合，キー６２を削除してもまだキーは２個あるので条件は維持される。したがって図８（ｂ）のように単純に削除される。
【００９３】
（２）キー８５の削除
キー８５の入ったノードを探索すると、葉ノードが見つかる。
キー８５を削除すると、残りはキー８０一つとなり、条件を満たさなくなる。図８（ｃ）に示すように、隣の兄弟ノードを調べると、すぐ左の兄弟ノードに三つキーが入っているので、親ノードのキー７７も参加させて不足ノードへ移動させる。このように隣の兄弟ノードからキーを譲ってもらうことをアンダーフローという。
【００９４】
（３）キー９０の削除
キー９０を探索すると葉ノードが見つかる。
この場合もノード内のキーが最低個数しか入っていない。さらに隣の兄弟ノードを見ても譲る余裕のあるノードがない。このような場合は、図８（ｄ）に示すように、隣のノードと合わせて一つのノードにまとめる。この操作を連結という。この例では親ノード自体も条件を満たさなくなるので親ノードの兄弟ノードとの連結が再び引き起こされる。このように連結は根へと向かって波及することがあり、その結果、根ノードが連結に参加するとＢ木の高さが一つ小さくなることが起こる。
【００９５】
（４）キー８８の削除
（１），（２），（３）の例はすべて葉ノードに含まれるキーの削除であった。しかし、今回のキー８８の削除は分岐ノード内のキーである。このような場合は、まずキー８８よりも大きい直後のキーを探索する。例ではキー９０がそれである。その９０を８８の格納場所に複写した後、葉ノードにある、キー９０を削除する。葉ノードのキー９０の削除は（３）で述べた通りである。
【００９６】
［６．２．１．４  Ｂ木の最近傍探索］
Ｂ木の最近傍探索を、図９の２次のＢ木を例に示す.
最近傍探索を行うキー（ＩＰアドレス値）を、８２とする。この場合、まず、ｒｏｏｔノードに移動する。ｒｏｏｔノード内で二分探索を行い、・・・・キーｎ＜ ８２＜キーｎ＋１・・・・となる位置を探す。図９では、６０＜８２の位置である。
【００９７】
キー１・・・・キーｎ＜８２＜キーｎ＋１・・・・の位置が見つかるとキーｎとキーｎ＋１との距離を計算する。距離は、キー同士の値の差（絶対値）として算出される。図９では、８２−６０＝２２がｒｏｏｔノード内のキーとの最短距離である。
次に、６０の右にあるポインタから子ノードへ移動する。子ノードでも、二分探索、距離計算を行う。図９で距離計算を行うと、８２−７７＝５, ８８−８２＝６より、このノード内のキーとの最短距離は５である。Ｂ木が深くなっている場合、これを葉ノードに移動するまで繰り返す。
【００９８】
葉ノード内で二分探索、距離計算を行い、最短距離の中で最も小さい値を、抽出アドレスと最近傍アドレスとの最短距離として、返し処理を終了する。図９では、葉ノードで二分探索を行うと,８０＜８２＜８５の位置が見つかり、距離計算を行うと８２−８０＝２，８５−８２＝３となるので、葉ノード内のキーとの最短距離は２である。最短距離の中で最も小さい値は２なので、キー８２（抽出ＩＰアドレスのアドレス値）の最近傍アドレスとの距離として２を返すとともに、最近傍アドレスとしてキー８０に対応するＩＰアドレスを返して、処理を終了する。
Ｂ木のキーはソートされて格納されているため、一回の探索で最近傍探索ができるため、高速で処理が行える。
【００９９】
［６．２．２  Ｂ＋木を用いたＩＰアドレスの格納］
以下、Ｂ木を拡張したＢ＋木の特性とキーの追加や削除の操作、 本実施形態のデータベース１３ａ〜１３ｅそれぞれにおいて、Ｂ＋木を採用した場合に、このＢ＋木を用いてIPアドレスをファイルに格納する方法、Ｂ＋木の最近傍探索について述べる。
【０１００】
［６．２．２．１  Ｂ＋木］
Ｂ＋木は、Ｂ木を拡張した平衡木で、インデックスページである根、節ノードと、データページである葉ノードに分かれる。
Ｂ＋木では葉にすべてのデータが入り、根から葉までの節には索引と分岐しか入らずインデックスの役割をもち、B木よりも格納効率が良い。Ｂ＋木のインデックスページはデータを挿入したり、削除したりする過程で構成される。基本的な定義は、前記Ｂ木と同じである。
【０１０１】
［６．２．２．２  Ｂ＋木のキーの追加］
Ｂ＋木の追加の操作を、図１０（ａ）の２次のＢ＋木を例に示す。
【０１０２】
（１）キー２８の追加
キー２８で探索すると格納すべき葉ノードがみつかる。
この葉ノードにはキーが２個はいっておりキーの個数が上限に達していないので、単純に追加する。追加後を図１０（ｂ）に示す。
【０１０３】
(2)キー７０の追加
キー７０を探索すると格納すべき葉ノードが見つかる。
しかしこの葉ノードには、上限の４個が入っている。この場合は仮にキー７０を追加した後、中央のキーを親ノードであるインデックスノードに上げ、葉ノードを分割する。
分割後を図１０（ｃ）に示す。
【０１０４】
もし、親ノードであるインデックスノードのキーの個数が上限だった場合は、中央のインデックスキーを親インデックスに上げて、インデックスノードが分割する。
キー９５を追加した図１０（ｄ）を以下に示す。
【０１０５】
［６．２．２．３  Ｂ＋木のキーの削除］
Ｂ木からのキーの削除の操作を図１１（ａ）の２次のＢ＋木を例に示す。
【０１０６】
（１）キー７０の削除
キー７０の入ったノードを探索すると、葉ノードがみつかる。
このノードには、６０，６５，７０が入っておりキー７０を削除しても２個残るので条件を満たす。したがって、単純に削除される。削除後を図１１（ｂ）に示す。
【０１０７】
（２）キー２５の削除
キー２５を探索すると、葉ノードがみつかる。この葉ノードは２５，２８，５０がはいておりキー２５を削除しても２個残るので条件を満たすので単純に削除できる。しかし、インデックスノードにも２５があるのでインデックスノードの２５を削除した後、２８をインデックスノードに追加する。キー２５削除後を図１１（ｃ）に示す。
【０１０８】
（３）キー60の削除
キー６０を探索すると、葉ノードがみつかる。この葉ノードにはキーが２つしかなくキー６０を削除すると、条件を満たさなくなるので兄弟ノードと結合する。
さらに、ｒｏｏｔインデックスノードに６０があるので、６０を削除してｒｏｏｔの子インデックスノードが結合してｒｏｏｔインデックスになる。キー６０削除後を図１１（ｄ）に示す。
【０１０９】
［６．２．２．４  Ｂ＋木の最近傍探索］
Ｂ＋木の最近傍探索を、図１２の２次のＢ＋木を例に示す。最近傍探索を行うキーを５７とする。まず、ｒｏｏｔノードに移動する。ｒｏｏｔノード内で二分探索を行い・・・・キーｎ＜５７＜キーｎ＋１・・・・となる位置を探す。図１２では、５０＜５７＜７５の位置である。
【０１１０】
キー１・・・・キーｎ＜５７＜キーｎ＋１・・・・の位置が見つかるとキーｎとキーｎ＋１との距離を計算する。図１２では、５７−５０＝７，７５−５７＝１８より、ｒｏｏｔノード内のキーとの最短距離は７である。
【０１１１】
次に、５０と７５の間のポインタから子ノードへ移動する。子ノードでも二分探索、距離計算を行う。Ｂ＋木が深くなっている場合は、これを葉ノードに移動するまで繰り返す。葉ノード内で二分探索、距離計算を行い、最短距離の中で最も小さい値を返し処理を終了する。図１２では葉ノードで二分探索を行うと５５＜５７＜６０の位置が見つかり、距離計算を行うと５７−５５＝２，６０−５７＝３となるので、葉ノード内のキーとの最短距離は２である。最短距離の中で最も小さい値である２と対応するＩＰアドレスを返し処理を終了する。
Ｂ＋木のキーもＢ木と同じくソートされて格納されているため、一回の探索で最近傍探索ができ、高速で処理が行える。
【０１１２】
［７．実験］
ここでは、前記Ｂ木及びＢ＋木を用いてＩＰアドレスをファイルに格納し、従来の格納方法（ディレクトリの階層構造を利用した格納方法）とのサイズと探索速度を比較した結果を述べる。
【０１１３】
［７．１  次数ｋを変化させてのファイルサイズや探索速度の比較］
Ｂ木、Ｂ＋木には、ノード内のキーの個数を決める次数ｋをもつ。このｋの値によってＢ木、Ｂ＋木のファイルサイズや探索時間がどのように違うかを比較した。
【０１１４】
使用するデータは、現在のＮＮＩＰＦで使用されているＩＰアドレス集合ＧＩＰ，ＢＩＰとする。ＧＩＰ，ＢＩＰのＩＰアドレスの個数を以下に示す。
ＧＩＰ：正常なメール送信者ＩＰアドレス集合  （ＩＰアドレスの個数：842個）
ＢＩＰ：迷惑メール送信者ＩＰアドレス集合    （ＩＰアドレスの個数：3037個）
【０１１５】
次数ｋを変化させたときのＢ木、Ｂ＋木のファイルサイズ、探索速度を表１〜表４に示し、結果をまとめたグラフを図１３〜図１６に示す。
【表１】
2011022876.tif 000007
【０１１６】
Ｂ木のＧＩＰについての表とグラフ（表１及び図１３）をみると、ｋが３２の時、ファイルサイズが小さくなり、ｋが８の時、exact mach timeが速くなることがわかる。
しかし、exact match timeの差は、ｋ＝８の時３３[ms]、ｋ＝３２の時３３．９[ms]とごく僅かなのでファイルサイズが一番小さくなるｋ＝３２をＧＩＰのＢ木で用いるのが好ましい。
【０１１７】
【表２】
2011022876.tif 000008
【０１１８】
Ｂ木のＢＩＰについての表とグラフ（表２及び図１４）をみると、ｋが３２の時ファイルサイズが小さくなり、ｋが８の時、exact mach timeが速くなることがわかる。
しかし、exact match timeの差は、ｋ＝８の時３３．８[ms]、ｋ＝３２の時３５［ms]とごく僅かなのでファイルサイズが一番小さくなるｋ＝３２をＢＩＰのＢ木で用いるのが好ましい。
【０１１９】
【表３】
2011022876.tif 000009
【０１２０】
Ｂ＋木のＧＩＰについての表とグラフ（表３及び図１５）をみると、ｋが３２の時、ファイルサイズが小さくなり、ｋが８の時、exact mach timeが速くなることがわかる。
しかし、exact match timeの差は、ｋ＝８の時１２．６[ms]、ｋ＝３２の時１４．０[ms]とごく僅かなのでファイルサイズが一番小さくなるｋ＝３２をＧＩＰのＢ＋木で用いるのが好ましい。
【０１２１】
【表４】
2011022876.tif 000010
【０１２２】
Ｂ＋木のＢＩＰについての表とグラフ（表４及び図１６）をみると、ｋが３２の時、ファイルサイズが小さくなり、ｋが８の時、exact mach timeが速くなることがわかる。
しかし、exact match timeの差は、ｋ＝８の時１３．３[ms]、ｋ＝３２の時１５．５[ms]とごく僅かなのでファイルサイズが一番小さくなるｋ＝３２をＢＩＰのＢ＋木で用いるのが好ましい。
【０１２３】
［７．２  従来手法とのサイズ、探索時間の比較］
７．１で求めた次数ｋ＝３２でのＢ木、Ｂ＋木と従来手法であるディレクトリの階層構造とのサイズ、探索速度の比較を行った。
従来手法とＢ木、Ｂ＋木のサイズの比較を以下の表５で示す。 また、サイズの比較を対数軸でとった結果を図１７に示す。
【表５】
2011022876.tif 000011
【０１２４】
表５及び図１７より、ディレクトリの階層構造での格納よりもサイズを小さくすることに成功した。また、Ｂ木よりもＢ＋木のファイルサイズが小さくなることがわかった。このことより、Ｂ木よりもＢ＋木の格納効率が良いことがわかる。
【０１２５】
次に,探索速度の時間の違いを示す。exact matchの速度比較を図１８及び図１９に示す。図１８及び図１９よりexact matchの速度は従来手法よりわずかにＢ木が速くなり、Ｂ＋木が一番速くなることがわかった。
従来手法よりＢ木、Ｂ＋木の速度が速くなったのは、従来手法ではディレクトリを４回開くのに対し、Ｂ木やＢ＋木ではファイルを一度開くだけで済むので速度が速くなったと考えられる。
Ｂ木よりもＢ＋木の速度が速くなったのは、Ｂ木よりもＢ＋木の節ノードの格納率が良いので、葉ノードまで探索する回数が減ったからだと考えられる。
【０１２６】
次に最近傍探索の速度の比較を、図２０に示す。最近傍探索の速度実験より、従来の手法より、Ｂ木およびＢ＋木の速度が速くなったことがわかった。
【０１２７】
［７．３  Ｂ木、Ｂ＋木のキーの追加や削除の操作の比較］
IPアドレスをＢ木やＢ＋木を用いてファイルに格納する際に、キーを追加や削除などの動作の速度の違いを比較した。その結果を図２１に示す。
本実験では、Ｂ木、Ｂ＋木ともに深い木にはならなかったので、あまり大掛かりな動作は起こらず、追加や削除の動作も高速に行えた。
【０１２８】
［８．付記］
なお、本明細書の実施形態として開示した事項は、例示であって、本発明を限定するものではなく、様々な変形が可能である。
【符号の説明】
【０１２９】
１  フィルタリングシステム
１１  インターフェース部
１２  分類部
１３  分類用ＩＰアドレスデータベース
１３ａ  正常メール送信者ＩＰアドレス共通データベース
１３ｂ  迷惑メール送信者ＩＰアドレス共通データベース
１３ｃ  正常メール送信者ＩＰアドレス個人用データベース
１３ｄ  迷惑メール送信者ＩＰアドレス共通データベース
１３ｅ  広告メール送信者ＩＰアドレス個人用データベース
１４  ユーザデータベース
１５  指定ＩＰアドレス記憶部
１６  通過データ記憶部
１７  検索部
１８  通過率算出部
【図１】
2011022876.tif 000012
【図２】
2011022876.tif 000013
【図３】
2011022876.tif 000014
【図４】
2011022876.tif 000015
【図５】
2011022876.tif 000016
【図６】
2011022876.tif 000017
【図７】
2011022876.tif 000018
【図８】
2011022876.tif 000019
【図９】
2011022876.tif 000020
【図１０】
2011022876.tif 000021
【図１１】
2011022876.tif 000022
【図１２】
2011022876.tif 000023
【図１３】
2011022876.tif 000024
【図１４】
2011022876.tif 000025
【図１５】
2011022876.tif 000026
【図１６】
2011022876.tif 000027
【図１７】
2011022876.tif 000028
【図１８】
2011022876.tif 000029
【図１９】
2011022876.tif 000030
【図２０】
2011022876.tif 000031
【図２１】
2011022876.tif 000032