TOP > 国内特許検索 > メールフィルタリングシステム、そのコンピュータプログラム、情報生成方法 > 明細書

明細書 :メールフィルタリングシステム、そのコンピュータプログラム、情報生成方法

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5366204号 (P5366204)
公開番号 特開2011-022876 (P2011-022876A)
登録日 平成25年9月20日(2013.9.20)
発行日 平成25年12月11日(2013.12.11)
公開日 平成23年2月3日(2011.2.3)
発明の名称または考案の名称 メールフィルタリングシステム、そのコンピュータプログラム、情報生成方法
国際特許分類 G06F  13/00        (2006.01)
H04L  12/58        (2006.01)
FI G06F 13/00 610Q
G06F 13/00 620
G06F 13/00 540P
H04L 12/58 100Z
請求項の数または発明の数 8
全頁数 30
出願番号 特願2009-168408 (P2009-168408)
出願日 平成21年7月17日(2009.7.17)
審査請求日 平成24年7月3日(2012.7.3)
特許権者または実用新案権者 【識別番号】504145283
【氏名又は名称】国立大学法人 和歌山大学
発明者または考案者 【氏名】和田 俊和
個別代理人の代理人 【識別番号】110000280、【氏名又は名称】特許業務法人サンクレスト国際特許事務所
審査官 【審査官】木村 雅也
参考文献・文献 特開2003-348161(JP,A)
特開2008-276760(JP,A)
山中 純,経路間の距離測度に基づいたスパムメールフィルタリング方式の提案,電子情報通信学会技術研究報告 Vol.107 No.530,日本,社団法人電子情報通信学会,2008年 2月28日,第107巻,第33頁-第38頁
和田俊和,NNIPF,[onlin],日本,2007年11月 1日
調査した分野 G06F 13/00
H04L 12/58
特許請求の範囲 【請求項1】
メール分類用のIPアドレス集合を登録するための分類用データベースと、
受信メールのメールヘッダに含まれるメール送信元のIPアドレスを抽出し、抽出されたIPアドレスに最も近似する最近傍アドレスを、最近傍探索によって前記分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類する分類部と、
を備えたメールフィルタリングシステムにおいて、
前記分類用データベースは、広告型メールの送信元のIPアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のIPアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記分類部は、前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行い、当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求め、受信メールから抽出された前記IPアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するよう構成され、
前記広告型メール送信元データベースに登録されたIPアドレス集合を、ユーザデータと関連づけて出力する出力手段と、
を備えていることを特徴とするメールフィルタリングシステム。
【請求項2】
前記分類用IPデータベースは、非広告型メールを送信した送信元サーバのIPアドレス集合を登録するための非広告型メール送信元データベースとして、前記広告型メール以外の迷惑メールを送信した送信元サーバのIPアドレス集合を登録するための迷惑メール送信元データベースと、正常なメールを送信した送信元サーバのIPアドレス集合を登録するための正常メール送信元データベースと、を含み、
前記分類部は、前記最近傍探索を前記広告型メール送信元データベース、前記迷惑メール送信元データベース及び正常メール送信元データベースそれぞれに対して行い、当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求めるよう構成されている
請求項1記載のメールフィルタリングシステム。
【請求項3】
メール分類用のIPアドレス集合を登録するための分類用データベースと、
受信メールのメールヘッダに含まれるメール送信元のIPアドレスを抽出し、抽出されたIPアドレスに最も近似する最近傍アドレスを、最近傍探索によって前記分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類する分類部と、
を備えたメールフィルタリングシステムにおいて、
前記分類用データベースは、広告型メールの送信元のIPアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のIPアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記分類部は、前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行い、当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求め、受信メールから抽出された前記IPアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するよう構成され、
前記広告型メール送信元データベースに登録されたIPアドレス集合を、広告型メールのメール配信方法の適切さの判断に利用可能な情報として出力する出力手段とを備え、
記広告メール送信元IPアドレスデータベースは、ユーザ毎にIPアドレス集合を分けて登録するよう構成されている
ールフィルタリングシステム。
【請求項4】
前記広告型メール送信元アドレスは、広告型メールに分類されたメールの送信元IPアドレスと当該メールの宛先であるユーザのユーザデータとを関連付けて保存する
請求項1~3のいずれか1項に記載のメールフィルタリングシステム。
【請求項5】
指定されたIPアドレスが送信元アドレスであるメールが、前記分類部において広告型メールに分類された件数及び/又は非広告型メールに分類された件数を集計する手段を更に備えている
請求項1~4のいずれか1項に記載のメールフィルタリングシステム。
【請求項6】
コンピュータを、請求項1~5のいずれか1項に記載のメールフィルタリングシステムとして機能させるためのコンピュータプログラム。
【請求項7】
受信メールのメールヘッダに含まれるメール送信元のIPアドレスを抽出し、抽出されたIPアドレスに最も近似する最近傍アドレスを、最近傍探索によって、メール分類用のIPアドレス集合を登録するための分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類するメールフィルタリングシステムにおいて、広告型メールのメール配信方法の適切さの判断に利用可能な情報を生成する情報生成方法であって、
前記分類用データベースは、広告型メールの送信元のIPアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のIPアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記情報生成方法は、
前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行うステップと、
当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求めるステップと、
受信メールから抽出された前記IPアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するステップと、
前記広告型メール送信元データベースに登録されたIPアドレスを、ユーザデータと関連づけて出力するステップと、
を含む情報生成方法。
【請求項8】
受信メールのメールヘッダに含まれるメール送信元のIPアドレスを抽出し、抽出されたIPアドレスに最も近似する最近傍アドレスを、最近傍探索によって、メール分類用のIPアドレス集合を登録するための分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類するメールフィルタリングシステムにおいて、広告型メールのメール配信方法の適切さの判断に利用可能な情報を生成する情報生成方法であって、
前記分類用データベースは、広告型メールの送信元のIPアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のIPアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記情報生成方法は、
前記広告メール送信元IPアドレスデータベースを、ユーザ毎にIPアドレス集合を分けて登録するステップと、
前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行うステップと、
当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求めるステップと、
受信メールから抽出された前記IPアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するステップと、
前記広告型メール送信元データベースに登録されたIPアドレス集合を、広告型メールのメール配信方法の適切さの判断に利用可能な情報として出力するステップと、
を含む情報生成方法。
発明の詳細な説明 【技術分野】
【0001】
本発明は、メールフィルタリングシステム、そのコンピュータプログラム、情報生成方法に関するものである。
【背景技術】
【0002】
近年、電子メールの利用を妨げる問題として迷惑メール(スパムメール)が挙げられる。不特定多数に大量に送信される迷惑メールは、メールトラフィックの増大やウィルスメールの拡散などを招き、経済的な損失まで引き起こしている。このため、迷惑メールを適切に検出できるメールフィルタリングシステムが求められている。
【0003】
メールフィルタリングシステムとしては、メールの内容となる本文・タイトルなどの文章(コンテンツ)を解析して迷惑メール(スパムメール)を検出するコンテンツ分析型のシステムが一般的である。
【0004】
ここで、迷惑メール(広義の迷惑メール)には、有害な情報やウイルスを含むなどしてほとんどの人々にとって迷惑であると感じられるメール(狭義の迷惑メール)と、一般の企業が宣伝広告のために送信するメールであって、その情報を必要としない人々には有益でないものの、その情報を必要とする人々には有益であるメール(広告用のメール、メールマガジンなど)と、が存在する。
【0005】
後者のメール(以下、「広告型メール」という)は、企業等の正常な宣伝広告活動の一環として行われているものであり、狭義の迷惑メールとは区別して考えることができるが、これまで、前者と後者のメールを区別してフィルタリングするという発想はなかった。
【0006】
ここで、本発明者は、NNIPF(Nearest Neighbor IP address based mail Filter)とよばれるメールフィルタリングシステムを開発・運用している(非特許文献1参照)。
このNNIPFでは、ユーザが、組織外部からメールを受け取るときに使用するMTA(Mail Transfer Agent)をシステムに予め登録されている。また、NNIPFでは、正常な送信者のIPアドレス集合と迷惑メールの送信者のIPアドレス集合を予め登録している。
【0007】
NNIPFは、ユーザがシステムに登録したMTA(MTAOB;MTA On Border)が外部からメールを受信したときに生成してメールヘッダに付加したReceived行から、メール送信元のIPアドレスを割り出す。
【0008】
そして、NNIPFは、割り出したIPアドレスに関する最近傍探索を、予め登録されている正常な送信者のIPアドレス集合及び迷惑メールの送信者のIPアドレス集合に対して行う。これにより、予め登録されている正常な送信者のIPアドレス集合のうち、割り出したIPアドレスに最も近い値を持つIPアドレス(最近傍アドレス)が検出されるとともに、予め登録されている迷惑メールの送信者のIPアドレス集合のうち、割り出したIPアドレスに最も近い値を持つIPアドレス(最近傍アドレス)が検出される。
【0009】
さらに、NNIPFは、割り出したIPアドレスと、正常な送信者の最近傍アドレス及び迷惑メール送信者の最近傍アドレスそれぞれとの距離(アドレス空間内での距離)を求め、これらの距離に基づいて、迷惑メールらしさを示す「弁別度」(0~1の値)を求める。この弁別度が0であれば、ほぼ確実に正常なメールであり、逆に1であれば、ほぼ確実に迷惑メールであると判断される。また、0から1の間の中間値は、1に近いほど、迷惑メールらしさが高いことを示す。
【0010】
ここで、NNIPFは、受信したメールの送信元IPアドレスが、ブラックリスト(迷惑メールIPアドレスのリスト)又はホワイトリスト(正常メールIPアドレスのリスト)と一致するか一致しないかという「ブラックリスト/ホワイトリスト」型の分類とは異なるものである。
【0011】
送信元IPアドレスを「ブラックリスト/ホワイトリスト」で確認する場合、送信元IPアドレスが、「ブラックリスト/ホワイトリスト」に含まれるアドレスと1ビットでも異なると、「一致しない」と判定してしまい、迷惑メールを確実に検出しようとすると、迷惑メールが発信される可能性のある全てのサーバのIPアドレス集合がブラックリストに登録されている必要があるが、これは運用上不可能である。
【0012】
これに対し、NNIPFは、正常な送信者の最近傍アドレス及び迷惑メール送信者の最近傍アドレスそれぞれとの距離を求め、これらの距離に基づいて、迷惑メールらしさを示す「弁別度」を求めるため、迷惑メール送信者や正常な送信者のIPアドレス全てが予め登録されていなくても、迷惑メールを識別することができる。
【0013】
しかも、NNIPFでは、正しく運用した場合、98%以上の精度で分類が行えることが確認されている。これは、迷惑メールは、過去に迷惑メールを送信したことのあるサーバのIPアドレスと似たアドレス値のIPアドレスのサーバから送信されることが多く、正常なメールは、以前から受信し続けている送信元サーバのIPアドレスと似たアドレス値のIPアドレスから送信されることが多いという事実に基づいている。
【0014】
このような傾向が現れる理由は、IPアドレスが、国別、組織別に系統立って割り当てられており、迷惑メール送信元のIPアドレス集合には、IPアドレスの全空間において偏りが見られるからである。例えば、ある著名な優良企業から迷惑メールが来ることはほとんど無く、一方で、外国の格安プロバイダに割り当てられているIPアドレスから迷惑メールが来る可能性は、著名な優良企業からよりも高い。
この傾向は、IPアドレスの割り当てルールが変更にならない限り普遍であるため、迷惑メールを送信するサーバのIPアドレスは、決して均一に分布することはなく、統計的に有意な偏りを持ち続けるため、継続的に分類することが可能である。
【先行技術文献】
【0015】

【非特許文献1】和田俊和,NNIPF,[onlin],2007年,[平成21年7月13日検索],インターネット<http://vrl.sys.wakayama-u.ac.jp/~twada/NNIPF.html>
【発明の概要】
【発明が解決しようとする課題】
【0016】
さて、企業等の正常な宣伝広告活動の一環として行われる広告型メールにおいては、テレビ放送における視聴率のように、メール配信の効果を測定するなどメール配信方法の適切さを検討可能であることが望まれる。
【0017】
この点に関し、本発明者は、広告型メールにおけるメール配信方法の適切さを、メールフィルタリングシステムにおける広告型メールの通過/ブロックに基づいて判断できるようにする、という着想を得た。
【0018】
例えば、広告型メールは、広告型メールを宣伝広告主のサーバからではなく、広告型メールの送信を請け負う専門業者のサーバから送信されることが多い。したがって、宣伝広告主からすると、どの専門業者を選択すべきか、という選択基準として、例えば、宣伝広告主が望むユーザにメールが届きやすいか否かという点が重要となる。
つまり、広告型メールでの宣伝広告を望む企業からすると、自社の広告型メールが、メールフィルタリングシステムでブロックされずに、できるだけ通過することが望ましい。
【0019】
しかし、従来のフィルタリングシステムでは、広告型メールに着目してこれを区別してフィルタリングするという発想が従来なかったのは、上述の通りであり、ブロックされたメールが広告メールであるか否かを判定することができなかった。
また、前記NNIPFにおいても、広告型メールに着目してフィルタリングをすることは行われていなかった。
【0020】
しかも、従来の一般的なコンテンツ分析型のメールフィルタリングシステムでは、広告型メールの文章(コンテンツ)が正常なメールの文章と区別し難いことが多いため、広告型メールだけを適切に抽出することができない。同じ理由から,コンテンツ分析型で、広告型メールを(広義の)迷惑メールとして検出しようとすると、正常なメールまでも迷惑メールとして検出されるおそれが高くなる。
さらに、広告型メールが受信されるべきものなのか、それとも受信拒否されるべきものかは、各ユーザの選好によるところが大きいため、コンテンツの内容だけから、正常に受信すべき広告型メールと受信拒否すべき広告型メールとを適切に区別することが困難である。
【0021】
このため、従来の一般的なコンテンツ分析型のメールフィルタリングシステムは、広告型メールのメール配信方法の適切さの判断には利用することが困難である。
【0022】
本発明は、上記問題に鑑み、広告型メールのメール配信方法の適切さの判断材料となる情報を生成できるメールフィルタリングシステム等を提供することを目的とする。
【課題を解決するための手段】
【0023】
本発明者は、広告型メールの送信元IPアドレス(例えば、広告型メール配信業者のIPアドレス)には、狭義の迷惑メールや正常メールのアドレスとは識別可能な偏りがあることを見出した。つまり、前記NNIPのように、メール送信元IPアドレスを元に最近傍探索を行って弁別度を求める方式では、過去に広告型メールを送信したサーバのIPアドレス集合を予め登録しておけば、新たに受信したメールのフィルタリングの際に広告型メールを識別して、広告型メールらしさの弁別度を求めることが可能であり、これを利用して、広告型メールのメール配信方法の適切さの判断に利用可能な情報を生成できるという着想を得て、本発明を完成した。
【0024】
(1)本発明は、
メール分類用のIPアドレス集合を登録するための分類用データベースと、
受信メールのメールヘッダに含まれるメール送信元のIPアドレスを抽出し、抽出されたIPアドレスに最も近似する最近傍アドレスを、最近傍探索によって前記分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類する分類部と、
を備えたメールフィルタリングシステムにおいて、
前記分類用データベースは、広告型メールの送信元のIPアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のIPアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記分類部は、前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行い、当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求め、受信メールから抽出された前記IPアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するよう構成され、
前記広告型メール送信元データベースに登録されたIPアドレス集合を、ユーザデータと関連づけて出力する出力手段と、
を備えていることを特徴とするメールフィルタリングシステムである。
【0025】
(2)前記分類用IPデータベースは、非広告型メールを送信した送信元サーバのIPアドレス集合を登録するための非広告型メール送信元データベースとして、前記広告型メール以外の迷惑メールを送信した送信元サーバのIPアドレス集合を登録するための迷惑メール送信元データベースと、正常なメールを送信した送信元サーバのIPアドレス集合を登録するための正常メール送信元データベースと、を含み、
前記分類部は、前記最近傍探索を前記広告型メール送信元データベース、前記迷惑メール送信元データベース及び正常メール送信元データベースそれぞれに対して行い、当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求めるよう構成されているのが好ましい。
【0026】
(3)メール分類用のIPアドレス集合を登録するための分類用データベースと、
受信メールのメールヘッダに含まれるメール送信元のIPアドレスを抽出し、抽出されたIPアドレスに最も近似する最近傍アドレスを、最近傍探索によって前記分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類する分類部と、
を備えたメールフィルタリングシステムにおいて、
前記分類用データベースは、広告型メールの送信元のIPアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のIPアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記分類部は、前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行い、当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求め、受信メールから抽出された前記IPアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するよう構成され、
前記広告型メール送信元データベースに登録されたIPアドレス集合を、広告型メールのメール配信方法の適切さの判断に利用可能な情報として出力する出力手段とを備え、
前記広告メール送信元IPアドレスデータベースは、ユーザ毎にIPアドレス集合を分けて登録するよう構成されているのが好ましい。
【0027】
(4)前記広告型メール送信元アドレスは、広告型メールに分類されたメールの送信元IPアドレスと当該メールの宛先であるユーザのユーザデータとを関連付けて保存するのが好ましい。
【0028】
(5)指定されたIPアドレスが送信元アドレスであるメールが、前記分類部において広告型メールに分類された件数及び/又は非広告型メールに分類された件数を集計する手段を更に備えているのが好ましい。
【0029】
(6)他の観点からみた本発明は、コンピュータを、上記(1)~(4)のいずれか1項に記載のメールフィルタリングシステムとして機能させるためのコンピュータプログラムである。
【0030】
(7)さらに他の観点からみた本発明は、受信メールのメールヘッダに含まれるメール送信元のIPアドレスを抽出し、抽出されたIPアドレスに最も近似する最近傍アドレスを、最近傍探索によって、メール分類用のIPアドレス集合を登録するための分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類するメールフィルタリングシステムにおいて、広告型メールのメール配信方法の適切さの判断に利用可能な情報を生成する情報生成方法であって、
前記分類用データベースは、広告型メールの送信元のIPアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のIPアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記情報生成方法は、
前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行うステップと、
当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求めるステップと、
受信メールから抽出された前記IPアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するステップと、
前記広告型メール送信元データベースに登録されたIPアドレスを、ユーザデータと関連づけて出力するステップと、
を含む情報生成方法である。
(8)さらに他の観点からみた本発明は、受信メールのメールヘッダに含まれるメール送信元のIPアドレスを抽出し、抽出されたIPアドレスに最も近似する最近傍アドレスを、最近傍探索によって、メール分類用のIPアドレス集合を登録するための分類用データベースから求めて、前記最近傍アドレスから受信したメールを分類するための弁別度を算出し、当該弁別度に基づいて前記受信メールを分類するメールフィルタリングシステムにおいて、広告型メールのメール配信方法の適切さの判断に利用可能な情報を生成する情報生成方法であって、
前記分類用データベースは、広告型メールの送信元のIPアドレス集合を登録するための広告型メール送信元データベースと、非広告型メールの送信元のIPアドレス集合を登録するための非広告型メール送信元データベースと、を含み、
前記情報生成方法は、
前記広告メール送信元IPアドレスデータベースを、ユーザ毎にIPアドレス集合を分けて登録するステップと、
前記最近傍探索を前記広告型メール送信元データベース及び非広告型メール送信元データベースそれぞれに対して行うステップと、
当該最近傍探索によって得られた前記最近傍アドレスから広告型メールらしさを示す弁別度を求めるステップと、
受信メールから抽出された前記IPアドレスを当該弁別度に応じて前記広告型メール送信元データベース及び非広告型メール送信元データベースのいずれかに分類して登録するステップと、
前記広告型メール送信元データベースに登録されたIPアドレス集合を、広告型メールのメール配信方法の適切さの判断に利用可能な情報として出力するステップと、
を含む情報生成方法である。
【発明の効果】
【0031】
本発明によれば、メールフィルタリングシステムから、広告型メールのメール配信方法の適切さの判断材料となる情報を出力することができる。
【図面の簡単な説明】
【0032】
【図1】MTAOBの概念のメールフィルタリングシステムの配置を示す図である。
【図2】メールフィルタリングシステムの入出力機能を示す概略図である。
【図3】メールフィルタリングシステムの内部機能を示す概略図である。
【図4】分類用IPアドレスデータベースの構成図である。
【図5】分類部の構成図である。
【図6】IPアドレスからIPアドレス値への変換の説明図である。
【図7】B木の追加操作を示す図である。
【図8】B木の削除操作を示す図である。
【図9】B木の最近傍探索を示す図である。
【図10】B+木の追加操作を示す図である。
【図11】B+木の削除操作を示す図である。
【図12】B+木の最近傍探索を示す図である。
【図13】B木のGIPのファイルサイズと探索速度を示すグラフである。
【図14】B木のBIPのファイルサイズと探索速度を示すグラフである。
【図15】B+木のGIPのファイルサイズと探索速度を示すグラフである。
【図16】B+木のBIPのファイルサイズと探索速度を示すグラフである。
【図17】サイズ比較の対数グラフである。
【図18】GIPのexact match平均速度のグラフである。
【図19】BIPのexact match平均速度のグラフである。
【図20】最近傍探索平均速度のグラフである。
【図21】追加・削除の動作の平均速度のグラフである。
【発明を実施するための形態】
【0033】
以下、本発明の好ましい実施形態について添付図面を参照しながら説明する。

【0034】
[1.最近傍探索型フィルタリングシステムの概要と用語の定義]
図1及び図2は、実施形態に係るメールフィルタリングシステム(フィルタリング用サーバ)1の運用形態を例示している。図1に示すように、メールユーザが使用するメール送受信ソフトウエアおよびそれが動作するコンピュータを、「UMA」(User Mail Agent)という。また、ある組織(メールサーバを有する企業・大学などの団体、インターネットサービスプロバイダなど)Sに、複数のMTA(Mail Transfer Agent)が設置されている場合に、UMAに対して通常のメール受信のための受信メールボックスを提供するMTAを、「Base MTA」という。また、メールユーザが、組織S外部からメールを受け取る際に、当該組織S内のMTAであって、外部サーバからメールを受信するMTAをMTAOB(MTA On the Border)という。

【0035】
本実施形態では、Base MTAは、メールを受信すると、実施形態に係るフィルタリングシステム(フィルタリング用サーバ))1にメールを転送するよう設定されている。図2に示すように、本フィルタリングシステム1は、転送されてきたメールを分類し、正常なメールは、メールユーザごとの分類済メールボックスに格納される。メールユーザは、フィルタリングシステム1を利用してメールを受信する場合、Base MTAではなく、フィルタリングシステム1の分類済みメールボックスからメールを取得する。つまり、フィルタリングシステム1において、正常でないメール(迷惑メール・広告型メール)は、ブロックされ、正常なメールは通過する。

【0036】
また、本フィルタリングシステム1は、メールを分類した結果に基づいて、広告型メールのメール配信方法の適切さの判断に利用可能な情報を出力する。

【0037】
なお、本実施形態のフィルタリングシステム1は、Base MTAと同じサーバに搭載されていてもよい。また、フィルタリングシステムの各機能は、同一サーバに搭載されている必要はなく、分散していてもよい。

【0038】
[2.メールの送信元IPアドレスについて]
各MTAは、メールを受信して転送する度に、メールヘッダに、図1に示すようなReceived行を付加する。Received行には、「From」の後に、当該MTAへメールを送信したサーバのIPアドレスが記載され、「by」の後に、当該MTAのIPアドレスが記載される。

【0039】
メールは、複数のMTAを転送されてくるため、一つのメールのメールヘッダには、複数のReceived行が付加されているのが一般的であるが、複数のReceived行のうち、組織Sの外部サーバからメールを受信するMTAOBが「by」の後に記載されているReceived行をみれば、そのReceived行の「From」の後のIPアドレスが、メール送信元のIPアドレスであることがわかる。MTAOBが「by」の後に記載されているReceived行は、ユーザの属する組織SのMTAOBが付加したものであるため、送信元IPアドレスの偽装は困難であり、送信元の正しいIPアドレスが得られる。

【0040】
本フィルタリングシステム1は、メールヘッダに含まれる送信元IPアドレスを用いて、メールの分類を行う。

【0041】
[3.メールフィルタリングシステムの構成]
図3は、本メールフィルタリングシステム(以下、単に「システム」という)1の機能ブロックを示している。なお、本システム1は、サーバ(コンピュータ)1にメールフィルタリング用コンピュータプログラムをインストールして構成されており、以下に説明するシステム1の機能は、当該プログラムがサーバ(コンピュータ)1によって実行されることで発揮されるものである。

【0042】
本システム1は、メールユーザが各種設定などの入力を行うためのインターフェース部11、メールを分類する分類部12、分類のためのIPアドレスが登録された分類用IPアドレスデータベース13、メールユーザの情報(年齢、性別、地域、職業など)が登録されたユーザデータベース14、指定IPアドレスを記憶するための指定IPアドレス記憶部15、及び通過率データ記憶部16、デーベース13を検索するための検索部17、及び指定IPアドレスを送信元とするメールのフィルタ通過率算出部18を備えている。

【0043】
前記インターフェース部11は、Webサーバとしての機能を有しており、ユーザは、(UMAが搭載された)ユーザコンピュータから、Webブラウザ機能によって、必要な情報の閲覧や入力を行うことができる。インターフェース部11では、分類部12に転送された各メールの分類状況をユーザに対して表示させたり、分類未確定のメールについて正常メールであるか非正常メール(受信したくない広告型メール又は迷惑メール)であるかの区別の入力をユーザから受け付けたり、システム1が誤って分類したメールやシステムが分類不能と判断したメールについて、ユーザが手動入力で適切に分類(広告型メール、迷惑メール、正常なメールのいずれか)するためのユーザからの入力を受け付けたりすることができる。

【0044】
前記分類部12では、当該分類部12に転送されてきたメールを、自動的に、広告型メール、迷惑メール、正常なメールのいずれかに分類し、正常なメールを、メールユーザ毎の分類済メールボックスに格納する。このため、メールユーザは、不要な広告型メールや迷惑メールをUMAで受信することを回避できる。なお、正常なメールには、広告型メールが含まれることがある。
この分類部13の詳細については後述する。

【0045】
図4に示すように、前記分類用IPアドレスデータベース13には、5種類のデータベースが含まれる。すなわち、正常メール送信者IPアドレス共通データベース13a、迷惑メール送信者IPアドレス共通データベース13b、正常メール送信者IPアドレス個人用データベース13c、迷惑メール送信者IPアドレス個人用データベース13d、広告型メール送信者IPアドレス個人用データベース13eの5種類である。

【0046】
正常メール送信者IPアドレス共通データベース13a及び正常メール送信者IPアドレス個人用データベース13cは、正常メールの送信元IPアドレスを登録するためのものである。

【0047】
これらの正常メールに関するデータベース13a,13cうち、共通データベース13aは、各メールユーザについて共通して利用されるデータベースである。例えば、優良な企業や公的団体からのメールは、多くのユーザにとって正常メールとして扱われるべきものであるため、そのような企業や公的団体の送信元サーバのIPアドレスが、予め共通データベース13aに登録されている。

【0048】
一方、個人用データベース13cは、メールユーザごとに設けられており、各ユーザ宛のメールのうち、正常メールと分類されたものであって、その送信元IPアドレスが共通データベース13aに登録されていないメールの送信元IPアドレスが登録される。
この個人用データベース13cには、例えば、各ユーザが日常的にメールをやり取りする相手の送信元サーバのIPアドレスが登録されることになる。

【0049】
迷惑メール送信者IPアドレス共通データベース13b及び迷惑メール送信者IPアドレス個人用データベース13dは、迷惑メールの送信元IPアドレスを登録するためのものである。

【0050】
これらの迷惑メールに関するデータベース13b,13dうち、共通データベース13bは、各メールユーザについて共通して利用されるデータベースである。例えば、有害情報を含むメールやウィルスメールは、多くのユーザにとって迷惑メールとして扱われるべきものであるため、そのようなメールの送信元サーバのIPアドレスは、この共通データベース13bに予め登録されている。

【0051】
一方、個人用データベース13dは、メールユーザごとに設けられており、各ユーザ宛のメールのうち、迷惑メールと分類されたものであって、その送信元IPアドレスが共通データベース13bに登録されていないメールの送信元IPアドレスが登録される。

【0052】
なお、個人用データベース13c,13dに登録されているIPアドレスのうち、多くのユーザの個人用データベース13c,13dに登録された結果、共通性が高まったと判断したIPアドレスについては、システム1が対応する共通データベース13a,13bに格納する。

【0053】
上記の4つのデータベース13a,13b,13c,13dは、広告型メール以外の非広告型メールである正常メール及び/又は迷惑メールを送信した送信元サーバのIPアドレスを登録する「非広告型メール送信元IPアドレスデータベース」である。
これに対し、広告型メール送信元個人用データベース13eは、広告型メールを送信した送信元サーバのIPアドレスを登録する「広告型メール送信元IPアドレスデータベース」である。

【0054】
この広告型メール送信元個人用データベース13eは、メールユーザごとに設けられており、メールユーザごとの広告型メール送信元IPアドレスが登録される。
「広告型メール送信元IPアドレスデータベース」としては、この広告型メール送信元個人用データベース13eだけが設けられており、正常メールや迷惑メールのように、共通データベースは設けられていない。
したがって、広告型メールに分類されたメールの送信元IPアドレスは、すべて、各ユーザの広告型メール送信元個人用データベース13eに登録される。共通データベースを設けないことで、ユーザごとの広告型メールの受信状況が把握し易くなる。

【0055】
広告型メール送信元個人用データベース13eには、興味を失った商品等の広告メールや読まなくなったメールマガジンなど、過去においては正常メールとして分類されていたが、現在は受信の必要がなくなったメールや、無差別に送信されてきて受信したくない広型メールなどの送信元サーバのIPアドレスが登録される。なお、ユーザがメールを手入力で分類してデータベース13に登録する場合、迷惑メールか広告型メールかはユーザの主観で行えば足りる。

【0056】
[4.分類部の詳細]
図5は、分類部12の機能ブロックを示している。この分類部12は、転送されてきたメールを受信する受信部121、受信部121で受信したメールの送信元IPアドレスを抽出するIPアドレス抽出部122、抽出したIPアドレスを元に分類用IPアドレスデータベース13での最近傍探索を行う最近傍探索部123、最近傍探索の結果から弁別度を算出する弁別度算出部124、弁別度に基づいて受信したメールを分類するメール分類部125、正常メールであると分類されたメールを格納する分類済メールボックス126、受信部121で受信したメールのうち指定IPアドレスが送信元であるメールを検出する指定IPアドレス検出部127を備えている。

【0057】
[4.1 IPアドレス抽出部]
IPアドレス抽出部122は、受信部121で受信したメールのメールヘッダに付加されているReceived行のうち、そのメールの受信者であるユーザのMTAOBであるとしてシステム1に登録されているMTAが、Received行の「by」の後に記載されているReceived行を抽出する。さらに、IPアドレス抽出部122は、その抽出したReceived行における「from」の後のIPアドレスを、送信元IPアドレスとして抽出する。
なお、各ユーザのMTAOBは、システム1に予め登録されている。

【0058】
[4.2 最近傍探索部]
最近傍探索部123は、NNIPFと同様の最近傍探索理論に基づいて、抽出アドレスの最近傍アドレスを探索する。
すなわち、本実施形態の最近傍探索部123は、IPアドレス抽出部122で抽出されたIPアドレス(抽出IPアドレス;未知のIPアドレス)の最近傍アドレスを、分類用IPアドレスデータベースにおける各データベース13a,13b,13c,13d,13eそれぞれで探索する。

【0059】
具体的には、最近傍探索部123は、正常メール送信者IPアドレス共通データベース13aにおける最近傍アドレス(第1最近傍アドレス)、迷惑メール送信者IPアドレス共通データベース13bにおける最近傍アドレス(第2最近傍アドレス)、メールの受信者であるユーザについての正常メール送信者IPアドレス個人用データベース13cにおける最近傍アドレス(第3最近傍アドレス)、メールの受信者であるユーザについての迷惑メール送信者IPアドレス個人用データベース13dにおける最近傍アドレス(第4最近傍アドレス)、及びメールの受信者であるユーザについての広告型メール送信者IPアドレス個人用データベース13eにおける最近傍アドレス(第5最近傍アドレス)を探索し、5つの最近傍アドレスを取得する。
この探索方法の詳細については、後述する。

【0060】
また、最近傍探索部123は、正常メールに関する第1最近傍アドレス及び第3最近傍アドレスのうち、抽出IPアドレスにより近いアドレスを、「正常メールとしての最近傍アドレス」とするとともに、迷惑メールに関する第2最近傍アドレス及び第3最近傍アドレスのうち、抽出IPアドレスにより近いアドレスを、「迷惑メールとしての最近傍アドレス」とする。

【0061】
ここで、正常メールとしての最近傍アドレスを「NN(IP;GIP)」と表し、
迷惑メールについての最近傍アドレスを「NN(IP;BIP)」と表し、
広告メールとしての最近傍アドレス(第4最近傍アドレス)を「NN(IP;AIP)」と表し、
抽出IPアドレス(未知IPアドレス;IP)と、正常メールとしての最近傍アドレスNN(IP;GIP)との距離を、DGIP(IP)=dist(IP,NN(IP;GIP))と表し、
抽出IPアドレス(未知IPアドレス;IP)と、迷惑メールとしての最近傍アドレスNN(IP;BIP)との距離を、DBIP(IP)=dist(IP,NN(IP;BIP))と表し、
抽出IPアドレス(未知IPアドレス;IP)と、広告型メールとしての最近傍アドレスNN(IP;AIP)との距離を、DAIP(IP)=dist(IP,NN(IP;AIP))と表す。
なお、距離の求め方については後述するが、最近傍探索部123は、抽出IPアドレスと各最近傍アドレスとから、これらの距離DGIP,DBIP,DAIPそれぞれ求めて出力する。

【0062】
[4.3 弁別度算出部]
前記弁別度算出部124は、前記距離DGIP,DBIP,DAIPに基づいて、抽出IPアドレスの迷惑メールの送信元らしさを示す弁別度、及び広告型メールの送信元らしさ示す弁別度を算出する。

【0063】
ここで、抽出IPアドレス(IP)が、迷惑メールの送信元らしいかを示す弁別度は、次式で表される。
【数1】
JP0005366204B2_000002t.gif

【0064】
また、抽出IPアドレス(IP)が、広告型メールの送信元らしいかを示す弁別度は、次式で表される。
【数2】
JP0005366204B2_000003t.gif

【0065】
これは、正常メールの事前確率P(Good)、迷惑メールの事前確率P(Bad)、広告型メールの事前確率P(Adv)がともに1/3で、正規確率分布をそれぞれ、P(IP|Good)=1/DGIP,P(IP|Bad)=1/DBIP,P(IP|Adv)=1/DAIPとした場合に、下記のように迷惑メール及び広告型メールの事後確率をBayes則で計算した結果と一致する。
【数3】
JP0005366204B2_000004t.gif
【数4】
JP0005366204B2_000005t.gif

【0066】
上記のP(Spam|IP)は、抽出IPアドレスが迷惑メール送信元IPアドレスである確率(迷惑メール弁別度)を示しており、0~1の値をとる。弁別度算出部124は、上記のP(Spam|IP)の式に基づいて弁別度を算出する。この値が、1に近いほど、迷惑メール送信元IPアドレスである確率が高いことを示している。
また、上記のP(Adv|IP)は、抽出IPアドレスが広告型メール送信元IPである確率(広告型メール弁別度)を示しており、0~1の値をとる。弁別度算出部124は、上記のP(Adv|IP)の式に基づいて弁別度を算出する。この値が、1に近いほど、広告メール送信元IPアドレスである確率が高いことを示している。
また、抽出IPアドレスが正常メール送信元IPアドレスである確率(正常メール弁別度)は、P(Good|IP)=1-(P(Spam|IP)+P(Adv|IP))で求められる。

【0067】
[4.4 メール分類部]
前記メール分類部125は、上記の弁別度P(Spam|IP),P(Adv|IP),P(Good|IP)に基づいて、分類対象の受信メールを、迷惑メール、広告型メール、正常メールのいずれかに分類する。

【0068】
メール分類部125は、3つの弁別度P(Spam|IP),P(Adv|IP),P(Good|IP)のうち、最も大きな値を持つ分類(迷惑メール、広告型メール、正常メール)を決定し、受信メールはその分類に振り分けられ、当該受信メールの送信元IPアドレス(抽出IPアドレス)は、対応するデータベース13a~13eに登録される。また、正常メールについては、分類済メールボックス126に格納され、UMAがメールを取得可能となる。
なお、決定した分類が迷惑メール又は正常メールである場合、その抽出IPアドレスが、共通データベース13a,13bに登録されていない場合に、個人用データベース13c,13dに登録する。

【0069】
また、決定した分類が広告型メールである場合、メール分類部125は、メールの受信者であるユーザのユーザデータをユーザデータベース14から取得し、抽出IPアドレスに前記ユーザデータを関連付けた上で、当該抽出IPアドレスを、広告型メール送信者IPアドレス個人用データベース13eに登録する。なお、個人用データベース13c,13dについても、抽出IPアドレスとユーザデータとを関連づけて登録してもよい。

【0070】
このように、本システム1では、広告型メールのフィルタリングが行えるとともに、ブロックされた広告型メールの送信元IPアドレスとブロックしたユーザ(メールの宛先ユーザ)のユーザデータとを関連づけたデータ(データベース13e)が得られる。このデータは、広告型メールのメール配信方法の適切さの判断材料となる情報として利用される。

【0071】
また、弁別度を用いたメールの分類の際には、閾値を用いても良い。例えば、迷惑メール弁別度又は広告型メール弁別度は、所定の閾値T1以上でなければ、迷惑メール又は広告型メールとみなさないものとして扱うことができる。また、閾値は、2個又は3個以上設けてもよく、閾値に応じて迷惑メールらしさや広告型メールらしさを判定してもよい。また、その判定結果は、ユーザに対して、分類された各メールの色分け表示などに用いることができる。

【0072】
[4.5 指定IPアドレス検出部]
前記指定IPアドレス検出部127は、指定IPアドレス記憶部15に記憶されている指定IPアドレスが送信元IPアドレスとなっているメールの受信状況(全受信数)を検出するとともに、指定IPアドレスが送信元IPアドレスとなっているメールが正常メールに分類された数及び/又は広告型メールに分類された数を検出する。また、迷惑メールに分類された数も検出してもよい。

【0073】
指定IPアドレス記憶部15には、例えば、広告型メールの広告主から指定されたIPアドレス(広告型メールの送信元IPアドレス)が入力されて記憶されている。指定IPアドレス検出部127は、分類用IPアドレスデータベース13及び/又は分類部125での分類結果に基づいて、その指定IPアドレスを持つ広告型メールが本システム1を通過した件数や、本システムでブロックされた件数を検出することができる。

【0074】
これらの検出結果は、通過率算出部18において、広告メールの通過率及び/又はブロック率の算出に用いられる。通過率は、[指定IPアドレスを持つメールが正常メールに分類された件数/指定IPアドレスを持つメールの全件数]で算出でき、ブロック率は、[指定IPアドレスを持つメールが広告型メールに分類された件数/指定IPアドレスを持つメールの全件数]で算出できる。
この算出結果は、システム1から出力され、広告型メールの広告主へ提供される情報となる。また、算出結果には、通過又はブロックしたユーザのユーザデータも付加してもよい。このような通過率又はブロック率が得られることで、広告主としては、依頼している広告メール配信業者が、適切な送信元IPアドレスを持っているか否かを検討することが可能となる。

【0075】
[5. 分類用IPアドレスデータベースの検索]
前記検索部17では、IPアドレスを検索キーにして、分類用IPアドレスデータベース13を検索し、検索キーのIPアドレスが、各データベース13a~13eにおいて登録されているか否かを検索し、出力することができる。
また、検索部17からIPアドレスを検索キーとして、広告型メール送信者IPアドレス個人用データベース13eを検索すると、当該データベース13eにおいて、そのIPアドレスに関連づけて登録されているユーザデータを抽出することができる。
例えば、広告型メールの広告主が、広告型メールがどの程度、本システム1においてどのようなユーザに広告型メールとしてブロックされているかを知りたい場合、当該広告型メールの送信元IPアドレスを検索キーとして入力して検索し、抽出されたユーザデータを解析すればよい。

【0076】
[6.最近傍探索の詳細]
以下、前記最近傍探索部123による最近傍探索理論について説明する。

【0077】
[6.1 IPアドレス]
本実施形態で使用するIPアドレスは、現在多く使用されているIPv4プロトコルに基づく。IPv4のIPは、通常0~255の数字4組をドットで繋いだ記法で表記される。本実施形態においては、IPアドレスの距離計算を行うときは、NNIPFと同様に、IPアドレスを256進数と考え10進数表記に変換したIPアドレス値により行う。IPアドレスからIPアドレス値を求めるには、図6に示すように、IPアドレスの左側を上位桁として、各桁に対して、上位側から順に、2563、2562、2561、2560の桁重みを乗じて、10進数のIPアドレスを求める。IPアドレス値による距離計算は、NNIPF採用されており、上記IPアドレス値による距離計算によって適切に分類が行えることが確認されている。

【0078】
データベース13a~13eでは、IPアドレス及びこのIPアドレス値が保存される。また、IPアドレスは、バイナリデータで保存される。 IPアドレスをバイナリデータに変換すると、IPアドレスの各オクテットが1バイトになるので1つのIPアドレスを4バイトで扱うことができる。

【0079】
[6.2 データベース13の構築方法]
本システム1では、メールから抽出された送信元IPアドレスを最近傍探索によって分類する。このため、分類数に応じた既知IPアドレスの集合が必要となる。すなわち、正常メール、迷惑メール、広告型メールの3つに分類するのであれば、IP既知の正常メール送信者のIPアドレスの集合(データベース13a,13c)、既知の迷惑メール送信者のIPアドレスの集合(データベース13b,13d)、既知の広告型メール送信者のIPアドレスの集合(データベース13e)それぞれが必要であり、これらの集合の中から、メールから抽出された送信元IPアドレスの最近傍アドレスを抽出することになる。

【0080】
従来のNNIPFでは、既知のIPアドレスの集合を記憶するために、数百~数千のIPアドレスをディレクトリの階層構造を利用し、入力されたメールのIPアドレスに最も近いアドレス(最近傍アドレス)を探索する。このため、通常のファイルシステムではディスクスペースを大量に消費してしまうという問題点がある。この問題を回避するために、個々のデータベース13a~3eを単一ファイルに格納し、それを読み込みメモリ上で最近傍探索を行う方法も考えられる。しかし、本システム1はメールが到着するたびに起動されるため、数千ものデータをファイルから読み込んでいたのでは、効率が良くない。

【0081】
このような問題点を解決するため、本実施形態では、コンピュータ1の補助記憶装置(ハードディスク等)に格納されたデータをメモリに展開せずに最近傍探索を行う方法を採用する。これはソートアルゴリズムが内部ソートと外部ソートに分類されることになぞらえると、外部最近傍探索とも呼べる内容である。この外部最近傍探索のために、本実施形態では、B木又はB+木を用いる。これらはもともと、一致型(Exact Match)の探索を前提としたデータ構造であるが、本実施形態ではこれらを最近傍探索に用いる。

【0082】
本実施形態では、5つのデータベース13a~13eそれぞれに対応するファイルをコンピュータ1の補助記憶装置(ハードディスク等)に設ける。ファイル内には、B木又はB+木構造で、IPアドレス値(及びIPアドレス)が保存される。
ファイル内にB木又はB+木を構築することにより、探索はファイル内の移動のみで行うことができ、すべてのデータをメモリにロードする必要がなく効率が良い。
以下、B木及びB+木を用いてIPアドレス値(IPアドレス)をファイルに格納することにより、ディスクスペースの消費を抑え、メモリにロードしないで最近傍探索する方法について述べる。

【0083】
[6.2.1 B木を用いたIPアドレスの格納]
ここでは、B木の定義や追加、削除などの操作を紹介し、B木を用いてIPアドレスをファイルに格納する方法とB木の最近傍探索について述べる。

【0084】
[6.2.1.1 B木]
B木とは、システムにおけるインデックスやファイルシステムに用いられる木構造で、多分木の平衡木(バランス木)の一種である。B木は、ノード内のキーの個数を決定する次数kの値を持つ。k次のB木の場合、次のように定義される。

【0085】
・根以外の節には、k個以上2k個以下のキーが格納される。それぞれのキー(m個とする)をa[1],・・・・・・,a[m]とする。
・根には1個以上2k個以下のキーが格納される。
・葉以外の任意の節には、部分木へのポインタがm+1個ある・ただし、mはその節に格納されているキーの個数である。これらのポインタをp[1],・・・・・・・,p[m]とする。
・すべての葉は同一レベルにある。
・任意の節において、キー列a[1],・・・・・・,a[m]は整列している。また、キーa[i](1≦ i ≦ m)はp[i-1]の指す部分木内のどのキーよりも大きく、逆にp[i]の指す部分木内のどのキーよりも小さい。
以上が、k次のB木の定義である。
本実施形態では、キーとしてIPアドレス値が格納される。

【0086】
また、キーの探索は、各節のキー列は整列しているので二分探索によって行う。B木の大きな特徴は、動的ファイル操作に対する緩衝効果である。キーの分割によってノードが分割されると、分割直後のノードは空きスペースが十分あるので,しばらくは分割のような大がかりな構造の手直しは起こらない。削除についても同様である。特に、追加と削除が混雑しているような状況では緩衝効果によりノードの分割も連結の動作もほとんど必要とならない。

【0087】
[6.2.1.2 B木のキー(IPアドレス値)の追加]
B木のキー(IPアドレス値)の追加の操作を、図7(a)の2次のB木を例に示す。

【0088】
(1)キー(IPアドレス値)10の追加
まず、図7(a)に示すB木において、キー10を探索すると格納すべきノードが見つかる。図7(b)に示すように、このノードにはキーが2個含まれており、一個追加しても条件を満たすので単純に追加すればよい。

【0089】
(2)キー(IPアドレス値)30の追加
図7(a)に示すB木において、キー30を探索すると、格納すべきノードが見つかる。図7(c)に示すように、この節には上限の4個のキーが格納されている。この場合は、キー30を仮に挿入した後、二つに分割し中央のキー(ここでは「30」)を親節に上げる。

【0090】
上記(1),(2)で示した通り、B木におけるキーの追加は単純追加または分割によって行われる。分割によって中央のキーが親節に送られるが、もし親節にも最大限数のキーが既に入っていた場合、親ノードが再び分割されて、さらにその親に中央キーが送られる、このような操作が繰り返し起こり、時には根自体が分割され木の高さが一つ増えることも起こる、B木の高さが大きくなるのはこのように分割操作が根にまで及んだときに起こる。

【0091】
[6.2.1.3 B木のキー(IPアドレス値)の削除]
B木からのキーの削除の操作を、図8(a)の2次のB木を例に示す。

【0092】
(1)キー62の削除
キー62を探索すると、葉ノードが見つかる。この場合,キー62を削除してもまだキーは2個あるので条件は維持される。したがって図8(b)のように単純に削除される。

【0093】
(2)キー85の削除
キー85の入ったノードを探索すると、葉ノードが見つかる。
キー85を削除すると、残りはキー80一つとなり、条件を満たさなくなる。図8(c)に示すように、隣の兄弟ノードを調べると、すぐ左の兄弟ノードに三つキーが入っているので、親ノードのキー77も参加させて不足ノードへ移動させる。このように隣の兄弟ノードからキーを譲ってもらうことをアンダーフローという。

【0094】
(3)キー90の削除
キー90を探索すると葉ノードが見つかる。
この場合もノード内のキーが最低個数しか入っていない。さらに隣の兄弟ノードを見ても譲る余裕のあるノードがない。このような場合は、図8(d)に示すように、隣のノードと合わせて一つのノードにまとめる。この操作を連結という。この例では親ノード自体も条件を満たさなくなるので親ノードの兄弟ノードとの連結が再び引き起こされる。このように連結は根へと向かって波及することがあり、その結果、根ノードが連結に参加するとB木の高さが一つ小さくなることが起こる。

【0095】
(4)キー88の削除
(1),(2),(3)の例はすべて葉ノードに含まれるキーの削除であった。しかし、今回のキー88の削除は分岐ノード内のキーである。このような場合は、まずキー88よりも大きい直後のキーを探索する。例ではキー90がそれである。その90を88の格納場所に複写した後、葉ノードにある、キー90を削除する。葉ノードのキー90の削除は(3)で述べた通りである。

【0096】
[6.2.1.4 B木の最近傍探索]
B木の最近傍探索を、図9の2次のB木を例に示す.
最近傍探索を行うキー(IPアドレス値)を、82とする。この場合、まず、rootノードに移動する。rootノード内で二分探索を行い、・・・・キーn< 82<キーn+1・・・・となる位置を探す。図9では、60<82の位置である。

【0097】
キー1・・・・キーn<82<キーn+1・・・・の位置が見つかるとキーnとキーn+1との距離を計算する。距離は、キー同士の値の差(絶対値)として算出される。図9では、82-60=22がrootノード内のキーとの最短距離である。
次に、60の右にあるポインタから子ノードへ移動する。子ノードでも、二分探索、距離計算を行う。図9で距離計算を行うと、82-77=5, 88-82=6より、このノード内のキーとの最短距離は5である。B木が深くなっている場合、これを葉ノードに移動するまで繰り返す。

【0098】
葉ノード内で二分探索、距離計算を行い、最短距離の中で最も小さい値を、抽出アドレスと最近傍アドレスとの最短距離として、返し処理を終了する。図9では、葉ノードで二分探索を行うと,80<82<85の位置が見つかり、距離計算を行うと82-80=2,85-82=3となるので、葉ノード内のキーとの最短距離は2である。最短距離の中で最も小さい値は2なので、キー82(抽出IPアドレスのアドレス値)の最近傍アドレスとの距離として2を返すとともに、最近傍アドレスとしてキー80に対応するIPアドレスを返して、処理を終了する。
B木のキーはソートされて格納されているため、一回の探索で最近傍探索ができるため、高速で処理が行える。

【0099】
[6.2.2 B+木を用いたIPアドレスの格納]
以下、B木を拡張したB+木の特性とキーの追加や削除の操作、 本実施形態のデータベース13a~13eそれぞれにおいて、B+木を採用した場合に、このB+木を用いてIPアドレスをファイルに格納する方法、B+木の最近傍探索について述べる。

【0100】
[6.2.2.1 B+木]
B+木は、B木を拡張した平衡木で、インデックスページである根、節ノードと、データページである葉ノードに分かれる。
B+木では葉にすべてのデータが入り、根から葉までの節には索引と分岐しか入らずインデックスの役割をもち、B木よりも格納効率が良い。B+木のインデックスページはデータを挿入したり、削除したりする過程で構成される。基本的な定義は、前記B木と同じである。

【0101】
[6.2.2.2 B+木のキーの追加]
B+木の追加の操作を、図10(a)の2次のB+木を例に示す。

【0102】
(1)キー28の追加
キー28で探索すると格納すべき葉ノードがみつかる。
この葉ノードにはキーが2個はいっておりキーの個数が上限に達していないので、単純に追加する。追加後を図10(b)に示す。

【0103】
(2)キー70の追加
キー70を探索すると格納すべき葉ノードが見つかる。
しかしこの葉ノードには、上限の4個が入っている。この場合は仮にキー70を追加した後、中央のキーを親ノードであるインデックスノードに上げ、葉ノードを分割する。
分割後を図10(c)に示す。

【0104】
もし、親ノードであるインデックスノードのキーの個数が上限だった場合は、中央のインデックスキーを親インデックスに上げて、インデックスノードが分割する。
キー95を追加した図10(d)を以下に示す。

【0105】
[6.2.2.3 B+木のキーの削除]
B木からのキーの削除の操作を図11(a)の2次のB+木を例に示す。

【0106】
(1)キー70の削除
キー70の入ったノードを探索すると、葉ノードがみつかる。
このノードには、60,65,70が入っておりキー70を削除しても2個残るので条件を満たす。したがって、単純に削除される。削除後を図11(b)に示す。

【0107】
(2)キー25の削除
キー25を探索すると、葉ノードがみつかる。この葉ノードは25,28,50がはいておりキー25を削除しても2個残るので条件を満たすので単純に削除できる。しかし、インデックスノードにも25があるのでインデックスノードの25を削除した後、28をインデックスノードに追加する。キー25削除後を図11(c)に示す。

【0108】
(3)キー60の削除
キー60を探索すると、葉ノードがみつかる。この葉ノードにはキーが2つしかなくキー60を削除すると、条件を満たさなくなるので兄弟ノードと結合する。
さらに、rootインデックスノードに60があるので、60を削除してrootの子インデックスノードが結合してrootインデックスになる。キー60削除後を図11(d)に示す。

【0109】
[6.2.2.4 B+木の最近傍探索]
B+木の最近傍探索を、図12の2次のB+木を例に示す。最近傍探索を行うキーを57とする。まず、rootノードに移動する。rootノード内で二分探索を行い・・・・キーn<57<キーn+1・・・・となる位置を探す。図12では、50<57<75の位置である。

【0110】
キー1・・・・キーn<57<キーn+1・・・・の位置が見つかるとキーnとキーn+1との距離を計算する。図12では、57-50=7,75-57=18より、rootノード内のキーとの最短距離は7である。

【0111】
次に、50と75の間のポインタから子ノードへ移動する。子ノードでも二分探索、距離計算を行う。B+木が深くなっている場合は、これを葉ノードに移動するまで繰り返す。葉ノード内で二分探索、距離計算を行い、最短距離の中で最も小さい値を返し処理を終了する。図12では葉ノードで二分探索を行うと55<57<60の位置が見つかり、距離計算を行うと57-55=2,60-57=3となるので、葉ノード内のキーとの最短距離は2である。最短距離の中で最も小さい値である2と対応するIPアドレスを返し処理を終了する。
B+木のキーもB木と同じくソートされて格納されているため、一回の探索で最近傍探索ができ、高速で処理が行える。

【0112】
[7.実験]
ここでは、前記B木及びB+木を用いてIPアドレスをファイルに格納し、従来の格納方法(ディレクトリの階層構造を利用した格納方法)とのサイズと探索速度を比較した結果を述べる。

【0113】
[7.1 次数kを変化させてのファイルサイズや探索速度の比較]
B木、B+木には、ノード内のキーの個数を決める次数kをもつ。このkの値によってB木、B+木のファイルサイズや探索時間がどのように違うかを比較した。

【0114】
使用するデータは、現在のNNIPFで使用されているIPアドレス集合GIP,BIPとする。GIP,BIPのIPアドレスの個数を以下に示す。
GIP:正常なメール送信者IPアドレス集合 (IPアドレスの個数:842個)
BIP:迷惑メール送信者IPアドレス集合 (IPアドレスの個数:3037個)

【0115】
次数kを変化させたときのB木、B+木のファイルサイズ、探索速度を表1~表4に示し、結果をまとめたグラフを図13~図16に示す。
【表1】
JP0005366204B2_000006t.gif

【0116】
B木のGIPについての表とグラフ(表1及び図13)をみると、kが32の時、ファイルサイズが小さくなり、kが8の時、exact mach timeが速くなることがわかる。
しかし、exact match timeの差は、k=8の時33[ms]、k=32の時33.9[ms]とごく僅かなのでファイルサイズが一番小さくなるk=32をGIPのB木で用いるのが好ましい。

【0117】
【表2】
JP0005366204B2_000007t.gif

【0118】
B木のBIPについての表とグラフ(表2及び図14)をみると、kが32の時ファイルサイズが小さくなり、kが8の時、exact mach timeが速くなることがわかる。
しかし、exact match timeの差は、k=8の時33.8[ms]、k=32の時35[ms]とごく僅かなのでファイルサイズが一番小さくなるk=32をBIPのB木で用いるのが好ましい。

【0119】
【表3】
JP0005366204B2_000008t.gif

【0120】
B+木のGIPについての表とグラフ(表3及び図15)をみると、kが32の時、ファイルサイズが小さくなり、kが8の時、exact mach timeが速くなることがわかる。
しかし、exact match timeの差は、k=8の時12.6[ms]、k=32の時14.0[ms]とごく僅かなのでファイルサイズが一番小さくなるk=32をGIPのB+木で用いるのが好ましい。

【0121】
【表4】
JP0005366204B2_000009t.gif

【0122】
B+木のBIPについての表とグラフ(表4及び図16)をみると、kが32の時、ファイルサイズが小さくなり、kが8の時、exact mach timeが速くなることがわかる。
しかし、exact match timeの差は、k=8の時13.3[ms]、k=32の時15.5[ms]とごく僅かなのでファイルサイズが一番小さくなるk=32をBIPのB+木で用いるのが好ましい。

【0123】
[7.2 従来手法とのサイズ、探索時間の比較]
7.1で求めた次数k=32でのB木、B+木と従来手法であるディレクトリの階層構造とのサイズ、探索速度の比較を行った。
従来手法とB木、B+木のサイズの比較を以下の表5で示す。 また、サイズの比較を対数軸でとった結果を図17に示す。
【表5】
JP0005366204B2_000010t.gif

【0124】
表5及び図17より、ディレクトリの階層構造での格納よりもサイズを小さくすることに成功した。また、B木よりもB+木のファイルサイズが小さくなることがわかった。このことより、B木よりもB+木の格納効率が良いことがわかる。

【0125】
次に,探索速度の時間の違いを示す。exact matchの速度比較を図18及び図19に示す。図18及び図19よりexact matchの速度は従来手法よりわずかにB木が速くなり、B+木が一番速くなることがわかった。
従来手法よりB木、B+木の速度が速くなったのは、従来手法ではディレクトリを4回開くのに対し、B木やB+木ではファイルを一度開くだけで済むので速度が速くなったと考えられる。
B木よりもB+木の速度が速くなったのは、B木よりもB+木の節ノードの格納率が良いので、葉ノードまで探索する回数が減ったからだと考えられる。

【0126】
次に最近傍探索の速度の比較を、図20に示す。最近傍探索の速度実験より、従来の手法より、B木およびB+木の速度が速くなったことがわかった。

【0127】
[7.3 B木、B+木のキーの追加や削除の操作の比較]
IPアドレスをB木やB+木を用いてファイルに格納する際に、キーを追加や削除などの動作の速度の違いを比較した。その結果を図21に示す。
本実験では、B木、B+木ともに深い木にはならなかったので、あまり大掛かりな動作は起こらず、追加や削除の動作も高速に行えた。

【0128】
[8.付記]
なお、本明細書の実施形態として開示した事項は、例示であって、本発明を限定するものではなく、様々な変形が可能である。
【符号の説明】
【0129】
1 フィルタリングシステム
11 インターフェース部
12 分類部
13 分類用IPアドレスデータベース
13a 正常メール送信者IPアドレス共通データベース
13b 迷惑メール送信者IPアドレス共通データベース
13c 正常メール送信者IPアドレス個人用データベース
13d 迷惑メール送信者IPアドレス共通データベース
13e 広告メール送信者IPアドレス個人用データベース
14 ユーザデータベース
15 指定IPアドレス記憶部
16 通過データ記憶部
17 検索部
18 通過率算出部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19
【図21】
20