(57)【要約】      （修正有）【課題】所定のクエリ区間又はポイントと重複する全ての区間を発見するために区間のセットを表現及び探索する時間及び空間的に効率的なシステムを提供する。【解決手段】システムは、ハッシュされるべき区間のセットを示すデータを取得する。局所性保持ハッシュに基づいて各区間を部分区間のセットに分割する。各部分区間に関連付けられたハッシュコードを取得する。区間ハッシュテーブルに挿入する。システムは、各区間の最低順序要素のための低ハッシュコード及び最高順序要素のための高ハッシュコードを取得する。ハッシュコードのセットを形成する。セット内の各ハッシュコードにのみに関連付けられた最大区間を取得する。最大区間は、各ハッシュコードにのみに関連付けられた任意のより大きな区間によって包含されない。取得された最大区間並びに各区間の最低順序要素及び最高順序要素に基づいて、各ハッシュコードに関連付けられた各部分区間を特定する。【選択図】図５
2017220226.tif 000002
【特許請求の範囲】
【請求項１】
区間をハッシュするコンピュータ実装方法であって、
プロセッサのセットを備えるコンピュータシステムにより、ハッシュされるべき区間のセットを示すデータ構造を取得することであって、各区間が密な連続的に順序付けられた要素を含むことと、
前記コンピュータシステムにより、近傍要素を近傍ハッシュコードにマッピングする局所性保持ハッシュに基づいて前記各区間を部分区間のセットに分割することと、
前記局所性保持ハッシュを介して、各部分区間に関連付けられたハッシュコードを取得することと、
前記取得されたハッシュコードに対応する位置において前記各部分区間を区間ハッシュテーブルに挿入することと
を備える、方法。
【請求項２】
前記各区間を分割することが、
前記局所性保持ハッシュを介して、前記各区間の最低順序要素のための低ハッシュコード及び最高順序要素のための高ハッシュコードを取得することと、
前記低ハッシュコード、前記低及び高ハッシュコードに対する中間のハッシュコード、及び前記高ハッシュコードを含むハッシュコードのセットを形成することと、
前記ハッシュコードのセット内の各ハッシュコードにのみに関連付けられた最大区間を取得することであって、前記最大区間が前記各ハッシュコードにのみに関連付けられた任意のより大きな区間によって包含されないことと、
前記取得された最大区間並びに前記各区間の前記最低順序要素及び最高順序要素に基づいて、前記各ハッシュコードに関連付けられた各部分区間を特定することと
をさらに備える、請求項１に記載の方法。
【請求項３】
前記区間ハッシュテーブルを探索することをさらに備えることが、
探索区間を含む探索クエリを受信することと、
前記局所性保持ハッシュに基づいて、前記探索区間を探索部分区間のセットに分割することと、
前記局所性保持ハッシュを介して、各探索部分区間に関連付けられた探索ハッシュコードを取得することと、
第２の区間の最低及び最高順序要素を前記各部分区間の最低及び最高順序要素と比較することに基づいて、前記各探索部分区間と重複する前記ハッシュコードに関連付けられた前記区間についてのハッシュテーブルを探索することと
を備える、請求項１に記載の方法。
【請求項４】
前記区間ハッシュテーブルが、前記探索ハッシュコードに関連付けられた区間の前記取得されたセットが不連続であるように、不連続区間ハッシュテーブルであり、
前記各探索部分区間が、前記各探索部分区間の最低及び最高順序要素が前記探索要素と等しくなるように、単一の探索要素を含み、
各区間が前記探索要素と重複するかどうかを判定することが、バイナリ探索を使用することをさらに備える、
請求項３に記載の方法。
【請求項５】
コンピュータによって実行されたときに前記コンピュータに区間をハッシュする方法を実行させる命令を記憶する持続性コンピュータ可読記憶媒体において、前記方法が、
プロセッサのセットを備えるコンピュータシステムにより、ハッシュされるべき区間のセットを示すデータ構造を取得することであって、各区間が密な連続的に順序付けられた要素を含むことと、
前記コンピュータシステムにより、近傍要素を近傍ハッシュコードにマッピングする局所性保持ハッシュに基づいて前記各区間を部分区間のセットに分割することと、
前記局所性保持ハッシュを介して、各部分区間に関連付けられたハッシュコードを取得することと、
前記取得されたハッシュコードに対応する位置において前記各部分区間を区間ハッシュテーブルに挿入することと、
前記区間ハッシュテーブルを持続性記憶媒体に記憶することと
を備える、持続性コンピュータ可読記憶媒体。
【請求項６】
前記各区間を分割することが、
前記局所性保持ハッシュを介して、前記各区間の最低順序要素のための低ハッシュコード及び最高順序要素のための高ハッシュコードを取得することと、
前記低ハッシュコード、前記低及び高ハッシュコードに対する中間のハッシュコード、及び前記高ハッシュコードを含むハッシュコードのセットを形成することと、
前記ハッシュコードのセット内の各ハッシュコードにのみに関連付けられた最大区間を取得することであって、前記最大区間が前記各ハッシュコードにのみに関連付けられた任意のより大きな区間によって包含されないことと、
前記取得された最大区間並びに前記各区間の前記最低順序要素及び最高順序要素に基づいて、前記各ハッシュコードに関連付けられた各部分区間を特定することと
をさらに備える、請求項５に記載の持続性コンピュータ可読記憶媒体。
【請求項７】
前記方法が、前記区間ハッシュテーブルを探索することをさらに備え、
探索区間を含む探索クエリを受信することと、
前記局所性保持ハッシュに基づいて、前記探索区間を探索部分区間のセットに分割することと、
前記局所性保持ハッシュを介して、各探索部分区間に関連付けられた探索ハッシュコードを取得することと、
第２の区間の最低及び最高順序要素を前記各部分区間の最低及び最高順序要素と比較することに基づいて、前記各探索部分区間と重複する前記ハッシュコードに関連付けられた前記区間についてのハッシュテーブルを探索することと
を備える、請求項５に記載の持続性コンピュータ可読記憶媒体。
【請求項８】
前記各探索部分区間と重複する区間を探索することが片側バイナリ探索を使用することをさらに備え、
各区間の各最低順序要素に基づいて順序付けられた前記探索ハッシュコードに関連付けられた区間のセットを取得することと、
前記各探索部分区間が前記取得された区間のセットにおける中間区間と重複することができないと判定することに応答して、前記中間区間の片側に順序付けられたセットにおける区間を破棄することと
を備える、請求項７に記載の持続性コンピュータ可読記憶媒体。
【請求項９】
区間をハッシュするコンピュータシステムであって、
複数のプロセッサのセットと、
前記プロセッサのセットに接続され、前記プロセッサのセットによって実行されたときに前記プロセッサのセットに区間をハッシュする方法を実行させる命令を記憶する持続性コンピュータ可読記憶媒体とを備え、前記方法が、
プロセッサのセットを備えるコンピュータシステムにより、ハッシュされるべき区間のセットを示すデータ構造を取得することであって、各区間が密な連続的に順序付けられた要素を含むことと、
前記コンピュータシステムにより、近傍要素を近傍ハッシュコードにマッピングする局所性保持ハッシュに基づいて前記各区間を部分区間のセットに分割することと、
前記局所性保持ハッシュを介して、各部分区間に関連付けられたハッシュコードを取得することと、
前記取得されたハッシュコードに対応する位置において前記各部分区間を区間ハッシュテーブルに挿入することと、
前記区間ハッシュテーブルを持続性記憶媒体に記憶することと
を備える、コンピュータシステム。
【請求項１０】
前記各区間を分割することが、
前記局所性保持ハッシュを介して、前記各区間の最低順序要素のための低ハッシュコード及び最高順序要素のための高ハッシュコードを取得することと、
前記低ハッシュコード、前記低及び高ハッシュコードに対する中間のハッシュコード、及び前記高ハッシュコードを含むハッシュコードのセットを形成することと、
前記ハッシュコードのセット内の各ハッシュコードにのみに関連付けられた最大区間を取得することであって、前記最大区間が前記各ハッシュコードにのみに関連付けられた任意のより大きな区間によって包含されないことと、
前記取得された最大区間並びに前記各区間の前記最低順序要素及び最高順序要素に基づいて、前記各ハッシュコードに関連付けられた各部分区間を特定することと
をさらに備える、請求項９に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は区間探索に関する。より具体的には、本開示は、所定のクエリ区間又はポイントと重複する全ての区間を発見するために区間のセットを表示及び探索する方法及びシステムに関する。
【背景技術】
【０００２】
区間は、密で順序付けられた要素の中断のないセットである。密な要素は、実数のように真に連続的とすることができ、又は、単にＩＰアドレス若しくはＵＲＬなどの密で順序付けられた要素とすることができる。区間は中断されず、したがって、範囲内の全ての密で順序付けられた要素を含む。
【０００３】
所定のクエリ区間又はポイントと重複する全ての区間を発見するために区間のセットを探索するという問題は、インターネット及びパケットルーティング、クラスレスドメイン間ルーティング（ＣＩＤＲ）、ジオＩＰ探索、地理情報システム、メモリ管理、ガベージコレクション、永続的オブジェクト指向データベース及びウェブサーバアクセス制御を含む多くのアプリケーションを有する。例えば、ジオＩＰ探索アプリケーションは、カスタマーケアにおいて、（推薦及びカスタマイズのために）自己のＩＰアドレスに基づいて顧客の地理位置情報を発見するために使用されることができる。
【０００４】
区間探索に対する従来のアプローチは、区間クエリを効率的に答えるために設計された特殊種類のバイナリ探索ツリー（通常は赤黒ツリーとして実装される）である区間ツリーと称されるデータ構造に基づいている。区間ツリーは、Ｏ（ｎ）空間を使用して、Ｏ（ｎ  ｌｏｇｎ）時間で構築されることができる。ここで、ｎは区間数である。それは、Ｏ（ｌｏｇｎ＋ｋ）時間で探索されることができる。ここで、ｋは、出力における区間数である。
【０００５】
区間ツリーは、現在の最先端技術であるが、それらのＯ（ｌｏｇｎ＋ｋ）探索時間は、大抵の場合に区間クエリを高速化するために特別なハードウェアを使用しなければならないパケットルーティングなどの多くの用途についての実時間要件を満たさない可能性がある。区間ツリーは、左右の枝間において要素を分割しなければならず、バランスの考慮、要素が記憶される順序についての記憶場所の可能な依存性をもたらす。したがって、配列内のバイナリ探索は、ツリー内のバイナリ探索よりも通常は時間がかかり、全ての枝において完全にバランスがとれないことがある。記憶装置に関して、区間ツリーのポインタを多用すると、特にポインタが３２ビットマシンのもののサイズの２倍である６４ビットマシンにおいて空間オーバーヘッドを大幅に増加させることがある。最後に、区間探索は、本質的にバイナリ探索ツリー内でポインタを追うことであり、悪いメモリ参照の局所性を生み出し、それゆえに、ＲＡＭよりもはるかに高速なＬ１及びＬ２キャッシュなどの最新のプロセッサのメモリ階層の恩恵を受けないことがある。
【発明の概要】
【課題を解決するための手段】
【０００６】
本発明の１つの実施形態は、区間ハッシュ及び探索のためのシステム及び方法を提供する。動作中において、システムは、ハッシュされるべき区間のセットを示すデータを取得する。システムは、近傍要素を近傍ハッシュコードにマッピングする局所性保持ハッシュに基づいて各区間を部分区間のセットに分割する。そして、システムは、局所性保持ハッシュを介して、各部分区間に関連付けられたハッシュコードを取得する。そして、システムは、ハッシュコードに対応する位置において各部分区間を区間ハッシュテーブルに挿入する。そして、システムは、区間ハッシュテーブルを持続性記憶媒体に記憶する。
【０００７】
この実施形態の変形例において、システムは、局所性保持ハッシュを介して、各区間の最低順序要素のための低ハッシュコード及び最高順序要素のための高ハッシュコードを取得することができる。システムは、低ハッシュコード、低及び高ハッシュコードに対する中間のハッシュコード若しくはコード、及び高ハッシュコードを含むハッシュコードのセットを形成することができる。システムは、ハッシュコードのセット内の各ハッシュコードにのみに関連付けられた最大区間を取得することができ、最大区間は、各ハッシュコードにのみに関連付けられた任意のより大きな区間によって包含されない。システムは、取得された最大区間並びに各区間の最低順序要素及び最高順序要素に基づいて、各ハッシュコードに関連付けられた各部分区間を特定することができる。
【０００８】
この実施形態の変形例において、システムは、探索区間を含む探索クエリを受信することができる。システムは、局所性保持ハッシュに基づいて、探索区間を探索部分区間のセットに分割することができる。システムは、局所性保持ハッシュを介して、各探索部分区間に関連付けられた探索ハッシュコードを取得することができる。システムは、第２の区間の最低及び最高順序要素を各部分区間の最低及び最高順序要素と比較することに基づいて、各探索部分区間と重複するハッシュコードに関連付けられた区間についてのハッシュテーブルを探索することができる。
【０００９】
この実施形態の変形例において、区間ハッシュテーブルは、探索ハッシュコードに関連付けられた区間の取得されたセットが不連続であるように、不連続区間ハッシュテーブルとすることができる。各探索部分区間は、各探索部分区間の最低及び最高順序要素が探索要素と等しくなるように、単一の探索要素を含むことができる。各区間が探索要素と重複するかどうかを判定することは、バイナリ探索を使用することをさらに備えることができる。
【００１０】
この実施形態の変形例において、システムは、区間ハッシュテーブルに基づいてクラスレスドメイン間ルーティング（ＣＩＤＲ）ブロック探索を実行することができる。
【００１１】
この実施形態の変形例において、システムは、片側バイナリ探索を実行することができる。システムは、各区間の各最低順序要素に基づいて順序付けられた探索ハッシュコードに関連付けられた区間のセットを取得することができる。各探索部分区間が取得された区間のセットにおける中間区間と重複することができないと判定したことに応答して、システムは、中間区間の片側において順序付けられた順序付きセットの区間を破棄することができる。
【００１２】
この実施形態の変形例において、区間ハッシュテーブルは、探索ハッシュコードに関連付けられた区間の取得されたセットが不連続であるように、不連続区間ハッシュテーブルとすることができる。片側バイナリ探索は、入れ子にされたバイナリ探索を使用することをさらに備えることができる。各探索部分区間が中間区間に重複することができると判定することに応答して、システムは、内側片側探索を実行することができる。
【００１３】
この実施形態の変形例において、区間ハッシュテーブルは、単一の最低順序又は最高順序要素を記憶することによって各区間を表す連続区間ハッシュテーブルとすることができる。２つの各区間が空き空間によって分離されていることに応答して、システムは、２つの各区間の中間の空き空間を表すために連続区間ハッシュテーブルにダミー区間を記憶することができる。
【図面の簡単な説明】
【００１４】
【図１Ａ】図１Ａは、区間の例を示している。
【図１Ｂ】図１Ｂは、区間を離散的な部分区間に分割する例を示している。
【図１Ｃ】図１Ｃは、局所性保持ハッシュに基づいて区間を離散的な部分区間に分割する例を示している。
【図２】図２は、本発明の実施形態にかかる区間ハッシュテーブルを利用する区間探索システムの例示的なアーキテクチャを示すブロック図を表している。
【図３】図３は、本発明の実施形態にかかる区間ハッシュの方法を示すブロック図を表している。
【図４】図４は、本発明の実施形態にかかる区間離散化のための方法を示すブロック図を表している。
【図５】図５は、本発明の実施形態にかかる区間探索のための方法を示すブロック図を表している。
【図６】図６は、本発明の実施形態にかかる片側バイナリ探索による区間探索のための方法を示すブロック図を表している。
【図７Ａ】図７Ａは、重複区間の例を示している。
【図７Ｂ】図７Ｂは、連続区間の例を示している。
【図８】図８は、実験結果に基づく本発明のランタイム及びメモリ性能を示している。
【図９】図９は、本発明の実施形態にかかる区間探索及びハッシュのための例示的な装置を示すブロック図を表している。
【図１０】図１０は、本発明の実施形態にかかる区間探索及びハッシュのための例示的なコンピュータシステムを示すブロック図を表している。
【発明を実施するための形態】
【００１５】
図面において、同様の参照符号は同じ図要素を指している。
【００１６】
以下の説明は、当業者が実施形態を作製して使用するのを可能とするように提示され、特定の用途及びその要件の文脈において提供される。開示された実施形態に対する様々な変更は、当業者にとって容易に明らかであり、本願明細書において定義される一般的な原理は、本開示の精神及び範囲から逸脱することなく他の実施形態及び用途に適用されることができる。それゆえに、本発明は、示された実施形態に限定されるものではなく、本願明細書において開示される原理及び特徴と一致する最も広い範囲が与えられるべきである。
【００１７】
概要
本発明の実施形態は、区間ハッシュテーブル内のハッシュ区間によって所定の区間又はポイントと重複する全ての区間を発見するために区間のセットを探索するという問題を解決する。本願明細書に開示された方法及びシステムは、可能な方法で漸近的に最適なポイント探索を含む、時間及び空間効率的な方法で重複区間を発見することができる。本発明はまた、（なおも双方の基準に関して十分に性能を発揮しながら）時間−空間トレードオフのスペクトルを提供し、幅広いアプリケーション及び装置に対して効果的にする。例えば、本システムは、数十ナノ秒以内に高性能のジオＩＰ探索を可能とする。動作中において、システムは、ハッシュされるべき区間のセットを示すデータを取得する。システムは、局所性保持ハッシュに基づいて、各区間を部分区間のセットに分割する。そして、システムは、各部分区間に関連付けられたハッシュコードを取得し、ハッシュコードに対応する位置において区間ハッシュテーブルに各部分区間を挿入する。システムは、さらに、区間ハッシュテーブルを探索することができる。
【００１８】
システムは、区間及びポイントを照会及び探索するためのコンピューティング技術及びコンピュータ能力を向上させる。本願明細書において開示されるシステム及び方法は、従来の技術と比較してランタイムを大幅に改善することができ、いくつかの場合において、より空間効率もまたよい。本願明細書に開示されるような区間ハッシュテーブルはまた、時間−空間トレードオフのスペクトルを提供し、様々なリアルタイム及び記憶要件を有する異なるアプリケーションにおいて同じ実装を使用するのを可能とする。本発明は、インターネット及びパケットルーティング、クラスレスドメイン間ルーティング（ＣＩＤＲ）、ジオ−ＩＰ探索、ＩＰ−メディアン−インカム探索、地理情報システム、メモリ管理、ガベージコレクション、永続的オブジェクト指向データベース及びウェブサーバアクセス制御を含む、多くのアプリケーションを有する。
【００１９】
図１Ａは、区間の例を示している。示されるように、区間は、要素の連続体１００における連続サブセット又はセグメントである。連続体１００は、実数のセットのように真に連続的なセットとすることができ、又は、ＩＰアドレス若しくはＵＲＬのセットなどの密に順序付けされた要素とすることができる。有限の精度において、実数のセットを表す浮動小数点数などの連続的なセットのコンピュータ化表現はまた、真に連続的ではなく密であり且つ順序付けられることができることに留意されたい。区間は中断されないため、範囲内の全ての密な順序付き要素を含む。例えば、区間１０２及び１０４は、連続体１００のサブセットである。図１Ａに示されるように、区間１０２は、最低順序要素又は終点１０６及び最高順序要素１０８を有し、したがって、１０６と１０８との間の連続体１００内の全ての要素を含む。本発明のいくつかの実施形態において、システムは、区間の２つの終点によって並びに区間ＩＤ又はインデックスフィールドによって区間ハッシュテーブル内の区間、又は他のデータ構造を表している。
【００２０】
図１Ｂは、連続体１１０における区間を離散的な部分区間に分割する例を示している。本発明の実施形態において、システムは、区間を効率的に記憶及び探索するために区間を「量子化する」又は「離散化する」。このことによって、連続体１１０における粒度が導入される。例えば、境界１１２、１１４及び１１６は、連続体１１０内の離散領域を画定する。本発明の実施形態において、区間の量子化された部分区間は、区間によって占有される離散領域に基づいて選択される。
【００２１】
区間は、複数の離散的な部分区間に及ぶことができ、離散領域の境界と一致しない終点を有することができることに留意されたい。例えば、図１Ｂに示されるように、区間１２０は、下側終点１２２及び上側終点１２４を有する。区間が完全に離散領域を包含する場合、対応する量子化された部分区間は、この離散領域に等しい。しかしながら、区間終点が離散領域の内側にある場合、いくつかの実施形態において、対応する量子化された部分区間は、元の区間の終点において終了する。例えば、区間１２０は、以下の３つの離散的な部分領域に分割される：外側の２つの離散的な部分領域は、終点１２２及び１２４において終了し、中間の離散的な部分領域は、離散領域全体を占有する。同様に、区間１１８は、２つの離散的な部分領域に分割される。
【００２２】
それらを量子化することに基づいて区間を探索する場合、離散化の品質とコストとの間において妥協する最適な粒度を発見することが重要であり得る。本発明の実施形態において、システムは、区間を離散化する局所性保持ハッシュ関数を使用することによってこの問題を解決することができる。
【００２３】
図１Ｃは、局所性保持ハッシュに基づいて区間を離散的な部分区間に分割する例を示している。局所性保持ハッシュは、「近く」の区間を同じ又は隣接するハッシュコードにマッピングする。これは、それらをインデックス付けするために使用されるハッシュ−テーブルスロット内の区間の近接性を保持する。システムはまた、所定のハッシュコードにマッピングされる全ての可能な区間の最大区間を返す局所性保持ハッシュ関数の逆数を利用することもできる。最大区間は、区間の包含に関して定義される。すなわち、最大区間は、所定のハッシュコードへの他の区間のマッピングの部分区間ではない。
【００２４】
図１Ｃは、いくつかの実施形態にかかる、図１Ｂにおける離散領域が選択されることができる方法を示している。示されるように、連続体１１０における各離散領域は、単一のハッシュコードへの最大区間マッピングである。したがって、いくつかの実施形態において、１１８及び１２０などの離散化区間は、各区間に関連付けられたハッシュコードのセットを特定することと、各区間を単一のハッシュコードにマッピングする離散的な部分区間に分割することとを含む。例えば、区間１２０は、３つのハッシュコードに関連付けられており、したがって、３つの離散的な部分区間に分割される。
【００２５】
システムアーキテクチャ
図２は、本発明の実施形態にかかる、区間ハッシュ及び探索方法を利用する区間ハッシュシステム２００の例示的なアーキテクチャを示すブロック図を表している。区間ハッシュシステム２００は、実施形態にしたがって、複数のプロセッサと並列に、区間のセットを分割して重複する区間を探索することができる。標準的なシステムにおいて、システム２００は、重複する区間を探索するためにかなりの計算コスト及び空間を必要とする。しかしながら、本願明細書において開示される方法を使用して、システム２００は、ユーザがより少ない時間及び空間において重複する区間を探索するのを可能とする。
【００２６】
区間ハッシュシステム２００は、サーバ２０６に接続された記憶装置２０４にインストールされた区間ハッシュテーブルモジュール２０２を含むことができる。本発明の様々な実施形態は、任意数のサーバ及び記憶装置を含むことができることに留意されたい。様々な実装において、区間ハッシュテーブルモジュール２０２は、区間ハッシュシステム２００の区間離散化モジュール又は他の要素を含むことができ、本願明細書に記載された技術を実行することができる。システム２００は、区間を記述するデータを受信し、そのようなデータを記憶装置２０４に記憶することができる。システム２００は、区間ハッシュテーブルモジュール２０２についてのコード及び記憶装置２０４からの区間２０８についてのデータを読み出すことができる。システム２００は、区間のセットを分割することができ、割り当てられた区間において動作するプロセッサ２１０Ａ−２１０Ｈなどのプロセッサにそれらを割り当てることができる。
【００２７】
区間ハッシュの方法
図３は、本発明の実施形態にかかる区間ハッシュの方法を示すフローチャート３００を表している。動作中において、システムは、ハッシュされるべき区間のセットを示すデータを取得する（動作３０２）。そして、システムは、局所性保持ハッシュ関数に基づいて、個々の区間を離散的な部分区間のセットに離散化することができる（動作３０４）。局所性保持ハッシュは、「近くの」区間を同じ又は隣接するハッシュコードにマッピングする。
【００２８】
局所性保持ハッシュ関数を作成する１つの方法は、局所性を保持する抽象化を使用することである。抽象化は、問題を符号化するために必要な変数のサブセットのみが考慮される抽象的空間に問題を投影する緩和である。例えば、１３．１．１０１．１３１のＩＰアドレスは、カルテット符号化においてオクテットのいくつかを無視することによって１３．＊．＊．＊（又は＊．＊．＊．１３１）として抽象化されることができる。通常は同じ問題について抽象化を実行する複数の方法があり、いくつかの抽象化は、他の抽象化よりも局所性が保持される。
【００２９】
上記ＩＰアドレスの例において、２つの１３．＊．＊．＊のＩＰアドレスが、２つの別個のサブネット上にある可能性がある２つの＊．＊．＊．１３１のアドレスよりも、同じサブネット上にある可能性が高いため、抽象化１３．＊．＊．＊は抽象化＊．＊．＊．１３１よりも優れている。それゆえに、前者は、後者よりも局所性を保持している。追加のオクテットを考慮することにより、１３．＊．＊．＊抽象化をさらに洗練することができる。例えば、１３．１．＊．＊及び１３．１．１０１．＊は、双方とも、元の単一オクテット抽象化よりも局所性を保持している。３つの局所性保持抽象化のうち、１３．１．１０１．＊は最も洗練され、それは、２５６３の合計サイズを有する最大の抽象的空間を有するのに対して、１３．＊．＊．＊抽象化は、３つのうちの最小の２５６のサイズの抽象的空間を有して最も洗練されていない。この例は、空間トレードオフに対する基本的局所性をもたらす。局所性を保持するための抽象化の能力が増すにつれて、空間要件も増す。仮に、全ての変数（例えば、我々のＩＰアドレスの例においては４つのオクテット全て）を考慮することによってアイデンティティ抽象化を使用することができ、局所性の１００％を保持するように保証された損失がない抽象化を作成するが、残念なことに、そのような「理想的な」抽象化は、通常、実用的にはあまりにも非効率的な空間である（例えば、ＩＰｖ４アドレス空間についての２５６４個のスロットのハッシュテーブルを必要とする）。それゆえに、局所性を保持することとメモリを維持することとのバランスをとらなければならない。本願明細書に開示された区間ハッシュテーブルは、これら２つの相反する目的の間で効果的なバランスを提供するデータ構造である。
【００３０】
そして、システムは、局所性保持ハッシュ関数を介して、各離散的な部分区間に関連付けられたハッシュコードを取得することができる（動作３０６）。そして、システムは、各部分区間をハッシュコードに対応する位置において区間ハッシュテーブルに挿入することができる（動作３０８）。
【００３１】
従来のハッシュテーブルは、ハッシュ衝突を解決するために連鎖又は開放アドレッシングのいずれかを使用することができるが、本発明の実施形態において、システムは、区間の局所性を保持するために連鎖を使用する。さらにまた、本発明の実施形態において、区間ハッシュテーブル内のハッシュテーブルスロットの数は、局所性保持ハッシュ関数によって生成される可能なハッシュコードの数（例えば、抽象的空間のサイズ）と等しくなければならない。それゆえに、２つが区間ハッシュテーブルにおいて同じであるため、ハッシュコードを対応するハッシュテーブルスロットに変換するためにモジュラス演算を実行する必要はない。本発明の実施形態において、ハッシュコード及びハッシュテーブルスロットは、交換可能な概念として使用される。
【００３２】
そして、システムは、より多くの離散的な部分区間がハッシュされたままであるかどうかを判定することができる（動作３１０）。より離散した部分区間がハッシュされたままであると判定したことに応答して、システムは、ハッシュ動作３０６から開始してハッシュ処理を繰り返すことができる。
【００３３】
それ以上の離散的な部分区間がハッシュされることがないと判定することに応答して、システムは、より多くの区間が離散化されたままであるかどうかを判定することができる（動作３１２）。より多くの区間が離散化されたままであると判定することに応答して、システムは、離散化動作３０４から開始して離散化プロセスを繰り返すことができる。
【００３４】
離散化されるべき区間がそれ以上残っていないと判定したことに応答して、システムは、離散化された区間を返すことができる。
【００３５】
区間を離散化する方法
図４は、本発明の実施形態にかかる区間離散化のための方法４００を示すブロック図を表している。方法４００は、図１Ｃが図１Ｂの詳細を提供するのと同様に、方法３００において各区間を離散化するステップ３０４の詳細を提供することに留意されたい。区間の離散化はまた、本願明細書においては区間を分割又は量子化することとしても称される。動作中において、システムは、離散化されるべき区間を示すデータを取得する（動作４０２）。あるいは、ステップ４０２において、システムは、方法３００から離散化されるべき区間を受信することができる。システムは、局所性保持ハッシュ関数を介して、区間の最低順序要素についての低ハッシュコード及び高次順序要素についての高ハッシュコードを取得することができる（動作４０４）。
【００３６】
そして、システムは、低ハッシュコード、低及び高ハッシュコードに対する任意の中間のハッシュコード、及び高ハッシュコードを含むハッシュコードのセットを形成することができる（動作４０６）。いくつかの場合において、低及び高ハッシュコードは等しくてもよく、その場合、ハッシュコードのセットは、１つのハッシュコードしか含まないことに留意されたい。低及び高ハッシュコードが隣接している場合、ハッシュコードのセットは、いかなる中間コードも含まない。
【００３７】
そして、システムは、各ハッシュコードのみに関連付けられた任意の区間によって包含されることができない１つの各ハッシュコードに排他的に関連付けられた最大区間を取得することができる（動作４０８）。第１の区間は、第２の区間が第１の区間の部分区間である場合には第２の区間を包含するものとして定義され、又は、第２の区間の終点が第１の区間に属する場合には等価的に定義される。
【００３８】
先に説明したように、量子化された部分区間は、元の区間が離散領域を包含しているかどうかに応じて、元の区間の終点又は離散領域の境界において終了することができる。したがって、システムは、次に、各ハッシュコードが低ハッシュコードを超えるかどうかを判定することができる（動作４１０）。各ハッシュコードが低ハッシュコード以下であると判定することに応答して、システムは、離散化された部分区間を区間の最低順序要素において開始するように設定することができる（動作４１２）。各ハッシュコードが低ハッシュコードを超えていると判定したことに応答して、システムは、離散化された部分区間を最大区間の最低順序要素において開始するように設定することができる（動作４１４）。
【００３９】
そして、システムは、各ハッシュコードが高ハッシュコードよりも小さいかどうかを判定することができる（動作４１６）。各ハッシュコードが高ハッシュコード以上であると判定したことに応答して、システムは、離散化された部分区間を区間の最高順序要素において終了するように設定することができる（動作４１８）。各ハッシュコードが高ハッシュコードよりも小さいと判定することに応答して、システムは、離散化された部分区間を最大区間の最高順序要素において終了するように設定することができる（動作４２０）。
【００４０】
最後に、システムは、ハッシュコードのセットに追加のハッシュコードが残存しているかどうかを判定することができる（動作４２２）。追加のハッシュコードがあると判定するのに応答して、システムは、動作４０８から開始して離散化プロセスを繰り返し、次の各ハッシュコードについての最大区間を取得する。セット内にそれ以上のハッシュコードが残存していないと判定したことに応答して、システムは、離散化部分区間を返すことができる。
【００４１】
区間探索
図５は、本発明の実施形態にかかる、所定の区間と重複するハッシュテーブル内の区間を探索する方法５００を示すブロック図を表している。動作中において、システムは、探索区間を含む探索クエリを受信する（動作５０２）。そして、システムは、例えば方法４００によって探索区間を離散化探索部分区間のセットに離散化することができる（動作５０４）。そして、システムは、上述したように、局所性保持ハッシュ関数を介して、各離散化探索部分区間に関連付けられた探索ハッシュコードを取得することができる（動作５０６）。そして、システムは、取得された探索ハッシュコードに関連付けられたハッシュテーブル内の区間のセットを特定することができる（動作５０８）。
【００４２】
そして、システムは、各区間の最低及び最高順序要素を探索部分要素の最低及び最高順序要素と比較することに基づいて、特定された区間のセットにおける各区間が各探索部分区間に重複するかどうかを判定することができる（動作５１０）。各区間が探索部分区間と重複していると判定したことに応答して、システムは、発見された重複区間のセットに各区間を追加することができる（動作５１２）。
【００４３】
そして、システムは、探索ハッシュコードに関連付けられたハッシュテーブル内の区間のセットにより多くの区間が残存しているかどうかを判定することができる（動作５１４）。より多くの区間が残存していると判定したことに応答して、システムは、比較動作５１０から開始して比較プロセスを繰り返すことができる。区間がそれ以上残存していないと判定したことに応答して、システムは、より多くの離散化部分区間を探索するかどうか判定することができる（動作５１６）。より離散的な部分区間が残存していると判定することに応答して、システムは、ハッシュ動作５０６から開始して探索プロセスを繰り返すことができる。それ以上の区間が残存していないと判定することに応答して、システムは、発見した重複する区間を返すことができる。
【００４４】
片側バイナリ探索
図６は、本発明の実施形態にかかる、片側バイナリ探索に基づく区間探索の方法６００を示すブロック図を表している。方法６００は、方法５００のステップ５１０の詳細、すなわち、一般的な場合において、各区間が各探索部分区間と重複するかどうかを判定するために要素を比較することを提供することに留意されたい。片側バイナリ探索は、最初に各探索部分区間が取得された区間セット内の中間区間と重複することが可能であるかどうかを判定するために重複に必要な条件を検査することを含む。この必要条件は、方法６００においてより詳細に説明され、本開示においてさらに後に説明される。そして、この重複が不可能であると判定したことに応答して、システムは、中間区間の片側において順序付けられた順序付きセットの区間を破棄することができる。いくつかの実施形態において使用される片側バイナリ探索は、条件が満たされた場合にのみ順序付きセットが二等分されることから、標準的なバイナリ探索とは異なる。
【００４５】
動作中において、システムは、探索ハッシュコードに関連付けられた区間のセットを取得する（動作６０２）。あるいは、ステップ６０２において、システムは、方法５００から区間のセットを受信することができる。いくつかの実施形態において、取得されたセットは、各区間の各最低順序要素に基づいて順序付けられることができる。
【００４６】
そして、システムは、順序付けられた区間のセット内の中間区間を選択することができる（動作６０４）。いくつかの実施形態において、システムは、順序付けられたセット内の最低及び最高順序区間に関連付けられた区間ＩＤ又はインデックスを平均化することによって中間区間を選択することができる。そして、システムは、中間区間がおそらく探索部分区間に重複するように必要な条件を満たすかどうかを判定することができる。いくつかの実施形態において、システムは、探索部分区間の高側終点を中間区間の低側終点と比較することによってそれを行う（動作６０６）。探索部分区間の高側終点と中間区間の低側終点とを比較することにより、システムは、中間区間よりも下位に順序付けられた区間が探索部分区間と重複することができるかどうかを同時に判定することに留意されたい。他の実施形態において、代わりに、システムは、探索部分区間の低側終点を中間区間の高側終点と比較することができ、中間区間の上位に順序付けられた区間についての情報も提供する。
【００４７】
探索部分区間の高側終点が中間区間の低側終点を超えている（すなわち、中間区間又はそれよりも短区間での重複が可能である）と判定することに応答して、システムは、中間区間の下位の区間を直線的にプローブすることができる。いくつかの実施形態において、システムは、各区間の高側終点を探索部分区間の低側終点と比較することにより、中間区間以下に順序付けられた各区間をプローブすることができる（動作６０８）。動作６０６及び６０８は、以下に記載されるように、重複するために必要且つ十分な条件をともに表すことに留意されたい。それゆえに、中間区間の片側区間が探索部分区間と重複する可能性があると判定されると、これらの区間のうちのどれが重複するかを判定するために線形プロービングが使用されることができる。そして、システムは、より多くの区間が中間区間の下位をプローブするために残存しているかどうかを判定することができる（動作６１０）。プローブする区間が残存していると判定されたことに応答して、システムは、プロービング動作６０８からプロービングプロセスを繰り返すことができる。プローブする区間がないと判定することに応答して、システムは、動作６１４に進むことができる。
【００４８】
ステップ６０６において、探索部分区間の高側終点が中間区間の低側終点よりも小さい（すなわち、中間区間又はその下位の区間においては重複することが不可能である）と判定することに応答して、システムは、区間の順序付けられたセットを二等分することができる。いくつかの実施形態において、システムは、中間区間及びそれより上位の区間を破棄することによってこれを行うことができる（動作６１２）。そして、システムは、順序付きセット内で探索する区間が残存しているかどうかを判定することができる（動作６１４）。探索する区間が残存していると判定することに応答して、システムは、動作６０４において新たな中間区間を選択することから開始して探索プロセスを繰り返すことができる。探索する区間が残存していると判定することに応答して、システムは、特定された区間を返すことができる。
【００４９】
不連続なハッシュテーブル探索及び不連続なポイント探索
いくつかの実施形態において、特別な場合のために方法６００に変形を加えることができる。例えば、ステップ６０２において取得された探索ハッシュコードに関連付けられた区間のセットが不連続である場合、区間ハッシュテーブルは、不連続区間ハッシュテーブルと称されることができる。この場合、区間の順序付けは、各セットの終点が区間を順序付けるために使用されることに依存せず、そのため、順序付けは、各セットのいずれかの終点に基づくことができる。例えば、ステップ６０２におけるように、各区間の低側終点に基づいて区間を順序付けることは、各区間の高側終点に基づいているかのように同じ順序付けを生成する。
【００５０】
不連続区間ハッシュテーブル探索の一般的な場合のために、いくつかの実施形態において、システムは、単一片側バイナリ探索よりもむしろ、入れ子にされたバイナリ探索を行うことができる。入れ子にされたバイナリ探索は、２つの片側バイナリ探索を含むことができる。これは、不連続区間が互いに重複することができないためであり、したがって、最大でも１つは探索部分区間の各終点に重複することができる。それゆえに、線形プロービングは、不連続区間が部分区間の内側に重複するかを判定するためにのみ必要とされることができる。
【００５１】
いくつかの実施形態において、各探索部分区間が中間区間に重複することができるとの判定６０６における判定に続いて、システムは、内側片側バイナリ探索を実行することができる。内側片側バイナリ探索は、内側中間区間が各探索部分区間と重複するかどうかを判定するために（以下においてさらに記載される）第２の十分条件を評価することを含むことができる。内側中間区間及び探索部分区間が重複すると判定することに応答して、システムは、探索部分区間と重複する内側最小と内側最大との間の全ての区間を特定するために線形プロービングを実行することができる。内側中間区間及び探索部分区間が重複しないと判定することに応答して、システムは、内側バイナリ探索領域を二等分することができる。例えば、外側探索が区間のセットの上半分を枝刈りすることを含むいくつかの実施形態において、内側探索において、システムは、内側配列の下側半分、すなわち、内側最小から内側中間区間までを枝刈りすることができる。いくつかの実施形態において、外側探索は、代わりに、区間のセットの下側半分を枝刈りすることを含むことができ、内側探索は、その後、内側配列の上側半分を枝刈りすることを含むことができる。
【００５２】
いくつかの実施形態において、ポイント探索のための特殊化、すなわち探索区間が単一要素である場合もまたあってもよい。そのような場合、システムは、方法６００と同様に区間探索を実行することができるが、等しい低側及び高側終点を有する単一の探索部分区間を指定することができるのみである。すなわち、探索部分区間は、探索されるポイントに等しくすることができる。さらにまた、探索ハッシュコードは、局所性保持ハッシュ関数によってこのポイントに関連付けられたハッシュコードとすることができる。
【００５３】
いくつかの実施形態において、また、不連続区間ハッシュテーブル内のポイント探索のために特殊化があってもよい。いくつかの実施形態において、不連続区間ハッシュテーブル内のポイント探索は、片側バイナリ探索よりもむしろ、標準的な（すなわち、両側）バイナリ探索を含むことができる。不連続ポイント探索の場合、不連続区間が厳密に順序付けされ、最大でも１つのそのような区間が探索されるポイントと重複することができることから、標準的なバイナリ探索を使用するための条件は満たされている。それゆえに、動作中において、システムは、探索ハッシュコードに関連付けられた不連続な区間の順序付きセットを取得することができ、順序付けは、区間の終点のいずれかにしたがうことができる。そして、システムは、区間のセット内の中間区間のインデックスを取得することができる。そして、システムは、中間区間の低側終点が探索ポイントを超えているかどうかを判定することによって中間区間が探索ポイントに重複することができるかどうかを判定することができる。重複が不可能である（例えば、中間区間の低側終点が探索ポイントを超えている）と判定することに応答して、システムは、中間区間及びその上位の全ての区間を破棄することによって区間のセットの上側半分を枝刈りすることができる。そして、システムは、探索を継続することができる。
【００５４】
重複が可能であると判定することに応答して、システムは、中間区間が中間区間の高側終点を超えているか又は探索ポイントに等しいかどうかを判定することによって探索ポイントに重複するかどうかを判定することができる。中間区間が探索ポイントと重複しない（例えば、中間区間の高側終点が探索ポイント未満である）と判定することに応答して、システムは、中間区間及びその下位の全ての区間を破棄することによって区間のセットの下側半分を枝刈りすることができる。そして、システムは、探索を継続することができる。中間区間が探索ポイントに重複すると判定することに応答して、システムは、発見した重複区間として中間区間を特定し、中間区間のインデックスを返すことができる。
【００５５】
重複及び連続区間
図７Ａは、重複区間７０２及び７０４の例を示している。方法６００におけるように、区間がその低側及び高側終点要素によって定義されることができることから、それらの低側及び高側終点要素を比較することによって区間７０２及び７０４が重複すると判定することが可能である。すなわち、区間の低側終点は、その高側終点を超えることはなく、区間は、常に２つの端部に対して全ての中間要素を含んでいる。区間は、それらの２つの終点によって定義されることができることから、ともに必要十分な重複のための２つの条件がある。
【００５６】
方法６００と同様に、これらの条件のうちの１つだけを指定すると、重複のために必要な条件を提供し、重複が可能であるかどうかを検査するために使用されることができる。例えば、図７Ａに示されるように、区間７０２は、それぞれ、低側及び高側終点７０６及び７０８を有し、７０４は、それぞれ、低側及び高側終点７１０及び７１２を有する。第１の区間７０２の高側終点７０８が第２の区間７０４の低側終点７１０を超えているか又は等しい場合、重複が可能である。
【００５７】
しかしながら、第１の区間の全体が第２の区間の全体を超えた場合には、２つの区間が依然として重複しない可能性がある。したがって、重複するために、第１の区間７０２の低側終点７０６はまた、第２の区間７０４の高側終点７１２以下でなければならない。
【００５８】
図７Ｂは、連続区間７１４、７１６及び７１８の例を示している。示されるように、連続区間は、それらの間に空き空間を有していないが、代わりに単一の境界ポイントにおいて重複する。例えば、区間７１４及び７１６は、境界要素７２０を共有し、区間７１６及び７１８は、境界要素７２２を共有する。
【００５９】
いくつかの実施形態において、連続区間は、一般的な区間よりも効率的に記憶又は処理されることができる。いくつかの実施形態において、システムは、各区間の低側終点を記憶するのみであり、その高側終点は、次の区間の低側終点によって暗示される。完全に連続区間のセットについて、そのような記憶方法は、低側及び高側終点の記憶に比べて５０％だけメモリ要件を低減することができる。
【００６０】
区間の大部分（全てではない）が連続している場合を処理するために、区間ハッシュテーブルは、連続性を回復するために最も近い非連続区間の間にダミー区間を挿入することができる。例えば、７１４及び７１８などの第１及び第２の区間が連続していない場合、システムは、連続性を回復するために第１及び第２の区間の間の７１６などのダミー区間を追加することができる。ダミー区間を追加すると、若干の記憶装置のオーバーヘッドを追加することがあるが、区間の大部分が依然として連続している場合、全体的なメモリ要件は、依然として完全な区間を記憶するのに比べて削減することができる。ダミー区間は、それが元の区間のいずれでもないことを示すために（例えば、０又は−１の区間ＩＤによって）適切に注釈付けされなければならない。
【００６１】
性能、実験結果及び用途
本発明は、インターネット及びパケットルーティング、クラスレスドメイン間ルーティング（ＣＩＤＲ）、ジオ−ＩＰ探索、ＩＰ−メディアン−インカム探索、地理情報システム、メモリ管理、ガベージコレクション、永続的オブジェクト指向データベース及びウェブサーバアクセス制御を含む多くのアプリケーションを有する。例えば、ジオ−ＩＰ探索は、（推薦及びカスタマイズのために）自己のＩＰアドレスに基づいて顧客の地理的位置を発見するためにカスタマーケアに使用されることができる。
【００６２】
図８は、本発明の例示的なランタイム性能及びメモリ使用量を示している。この図は、約３００万ブロックのデータベース内のクラスレスドメイン間ルーティング（ＣＩＤＲ）ブロック探索についての１つのスレッドのみによる方法６００と同様の区間探索方法を使用して本発明によって取得された実験結果に基づくものである。ＣＩＤＲにおいて、ＩＰパケットは、共通の接頭辞を有するＩＰアドレスの連続ブロックを表すその対応するＣＩＤＲブロックに基づいてルーティングされる。図に示されるように、いくつかの実施形態において、システムは、依然として双方の基準に関して良好に実行しながら、より優れた計算速度と引き換えにより低いメモリ要件をトレードオフすることができる。
【００６３】
図８に示されるように、２５又は２６個のハッシュビットが使用される場合、単一のスレッドのみによって１５ナノ秒の最速探索時間が達成され、以前の技術を超える有意な改善である。過去においては、そのような速度は、ネットワークルータにおいてみられるように、大抵の場合、特殊なハードウェアを使用することによって達成された。２６個のハッシュビットを超えて、キャッシュミスの副作用は、ハッシュの利点を追い越し、減少よりもむしろ増加する探索時間を生じさせる。メモリ要件は、ハッシュビットの数が２４を超えるのにともない、より迅速に成長し始める。２４個の接頭辞ビットを有するＣＩＤＲブロックが検査データ内の全てのＣＩＤＲブロックの４０％を占め、これらのブロックについての量子化区間数が２４個を超えて使用されるさらなるハッシュビット数のそれぞれについて２倍になることから、これは理解される。
【００６４】
本願明細書に開示された区間ハッシュテーブルは、合理的なメモリ設置面積を維持しながら、区間ツリーに比べて大幅にランタイムを向上させることができる。所定の場合において、区間ハッシュテーブルはまた、区間ツリーよりも多くの空間効率とすることができ、より多くの区間が記憶されて探索されるのを可能とする。より重要なことに、区間ハッシュテーブルは、区間ツリー、又は、リンクされたリスト若しくは（ソートされた）区間の配列などの他のデータ構造によって容易に達成されることができない時間−空間トレードオフのスペクトルを提供する。これは、様々な実時間及び記憶装置要件を有する異なるアプリケーションにおいて同じ区間ハッシュテーブルの実装を使用するのを可能とする。
【００６５】
通常のハッシュテーブルは、バイナリ探索ツリーの相手方にわたって最悪の場合の複雑性の利点を享受しないことが知られている。同じことは、最悪の場合に時間的複雑性を低減しない区間ハッシュテーブルについても同様である。しかしながら、平均的な場合の複雑性は、典型的にはハッシュテーブルに有利になる。区間ハッシュテーブルについて、平均的な場合の複雑性は、元の非量子化区間の総数のみならず、量子化区間数にも依存する。ｑをクエリ区間についての量子化区間数とし、ｒを各非量子化区間についての量子化区間の平均数とし、ｍをｑ及びｒの最小とする。区間に重複することができるハッシュテーブルにおける区間クエリについての平均複雑性は、Ｏ（ｋ  ｍ＋ｑ）である。ここで、ｋは、発見した区間数である。ｋに加えて、ｋ個の重複区間のそれぞれは、ｑ＞ｒである場合には平均でｒ倍だけ又はｑ≦ｒである場合には最大でもｑ倍だけ繰り返し発見されることができることから、平均的な複雑性は、ｑ及びｒによって影響を受ける。Ｏ（ｋ  ｍ＋ｑ）の同一の平均的な場合の複雑性は、不連続区間ハッシュテーブルに適用される。しかしながら、ポイントクエリについて、探索は、常に単一のハッシュコード（すなわち、ｑ＝１）に限定されることから、区間量子化は、いかなる複雑性の不利益を招かない。すなわち、ｑ及びｒは、双方とも、ポイント探索の複雑性に影響を与えない。不連続区間ハッシュテーブルについて、単一の重複区間のみが発見されることができるという余分な利点があり、それゆえにポイント探索についての平均的な場合複雑性は、Ｏ（１）であり、一定時間の動作である。表１は、これらの４つの場合について平均的な場合の時間的複雑性をまとめている。
【００６６】
【表１】
2017220226.tif 000003
【００６７】
区間ツリーの平均的な場合の時間的複雑性がＯ（ｌｏｇ  ｎ＋ｋ）であることを思い出すと、ｎは区間数である。区間ハッシュテーブルは、大きいｎについて保持することができるｋ  ｍ＋ｑ＜ｌｏｇ  ｎ＋ｋである限り、区間ツリーにわたって複雑性の利点を享受する。ポイント探索の平均的な場合の複雑性の利点は、それがｎ、ｑ又はｒに依存しないことから、より一層重要である。
【００６８】
漸近最適性：クエリ結果を印刷するために少なくともＯ（ｋ）時間かかることから、ポイント探索区間ハッシュテーブルの平均的複雑性が漸近的に最適であることを示すことは容易である。発明者の知る限り、これは、これまで漸近的に最適なポイントベースの区間探索を実行するデータ構造のみである。
【００６９】
空間的複雑性：区間ハッシュテーブルの空間的複雑性は、ｑ≧１であることから、区間ツリーのＯ（ｎ）空間的複雑性よりも高いことがあるＯ（ｎ  ｑ’）である。しかしながら、区間ハッシュテーブルが区間ツリーよりも少ないメモリを必要とする場合がある。例えば、６４ビットシステムにおいて、ポインタは、８バイトの記憶装置を必要とする。低側及び高側終点が３２ビット整数又は浮動小数点数において符号化された場合、区間は、区間ツリーに記憶するために２４バイトを必要とする。区間ハッシュテーブルは、ポインタを使用する必要がないため、量子化区間は、元の非量子化区間を記憶するために記憶装置の１２バイト及び８バイトをとることができる。（ハッシュテーブルインデックス配列を除く）総メモリ要件は、同一の６４ビットシステムにおいて１２ｒ＋８バイトであり、また、ｒ＜１．３３である限り、区間ハッシュテーブルは、区間ツリーよりも多くの空間的効率があることができる。
【００７０】
例えば、上記ＣＩＤＲ実験において、２，９７８，５６７個のＣＩＤＲブロックが存在し、そのため、各ＣＩＤＲブロックが３２ビット整数を使用して最小及び最大のＩＰｖ４アドレスの対として符号化される場合、ＣＩＤＲブロックだけを記憶するために２，９７８，５６７×８＝２３，８２８，５３６バイトをとるであろう。区間量子化の空間的オーバーヘッドに追加すると、（ハッシュテーブルインデックス配列及び元の非量子化区間を含む）総メモリ要件は、使用されるハッシュビット数が少ない場合（例えば、８又は９）、ＣＩＤＲブロックのサイズの約２倍である。比較のため、区間ツリーは、同じ区間を記憶するために３２ビットマシンでは２，９７８，５６７×１６＝４７，６５７，０７２バイトを必要とし、又は、６４ビットマシンでは２，９７８，５６７×２４＝７１，４８５，６０８バイトを必要とするであろう。換言すれば、区間ハッシュテーブルは、せいぜい２０個のハッシュビットが使用される場合、６４ビットマシンでは区間ツリーよりも多くの空間的効率がある。
【００７１】
例示的な装置
図９は、いくつかの実施形態にかかる、区間探索及びハッシュを容易とする例示的な装置９００を示すブロック図を表している。装置９００は、有線又は無線通信チャネルを介して互いに通信することができる複数のモジュールを備えることができる。装置９００は、１つ以上の集積回路を使用して実現されることができ、図９に示されるものよりも少ない又は多いモジュールを含むことができる。さらに、装置９００は、コンピュータシステムに内蔵されることができ、又は、他のコンピュータシステム及び／又は装置と通信することができる別個の装置として実現されることができる。具体的には、装置９００は、区間データ構造受信モジュール９０２と、区間離散化モジュール９０４と、部分区間ハッシュモジュール９０６と、区間探索モジュール９０８と、部分区間記憶モジュール９１０とを備えることができる。装置９００はまた、図９には示されていない追加のモジュールを含むことができることに留意されたい。
【００７２】
いくつかの実施形態において、区間データ構造受信モジュール９０２は、区間の表現を含むデータを受信することができる。区間離散化モジュール９０４は、区間を離散化部分区間に分割することができる。部分区間ハッシュモジュール９０６は、部分区間についてのハッシュコード値を取得するために局所性保持ハッシュ関数を使用することができる。区間探索モジュール９０８は、所定のクエリ区間又はポイントと重複する区間について区間ハッシュテーブルを探索することができる。部分区間記憶モジュール９１０は、区間ハッシュテーブルのデータ構造内の部分区間を記憶することができる。図２に示された区間ハッシュテーブルモジュール２０２は、図９に示された様々なモジュールの任意の及び全ての機能を提供してもよいことに留意されたい。
【００７３】
例示的なシステム
図１０は、いくつかの実施形態にかかる例示的な区間探索及びハッシュコンピュータシステム１０００を示している。いくつかの実施形態において、コンピュータシステム１０００は、サーバとすることができる。いくつかの実施形態において、システム１０００は、プロセッサ１００２と、メモリ１００４と、記憶装置１００６とを含む。いくつかの実施形態において、１００２は、プロセッサのセットを含むことができる。記憶装置１００６は、本発明の実施形態にかかる区間探索及びハッシュを利用することができるアプリケーション１０１４及び１０１６などの多数のアプリケーションと、オペレーティングシステム１０２２とを記憶することができる。記憶装置１００６はまた、区間データ構造受信モジュール９０２と、区間離散化モジュール９０４と、部分区間ハッシュモジュール９０６と、区間探索モジュール９０８と、部分区間記憶モジュール９１０とを含むことができる区間ハッシュシステム１００８を記憶する。システム１０００及び／又は区間データ構造受信モジュール９０２は、区間データを含む区間データ１０３０を受信又は生成することができ、区間ハッシュシステム１００８に対してアクセス可能なメモリ部に区間データをコピーすることができる。動作中において、区間ハッシュシステム１００８などの１つ以上のアプリケーションは、記憶装置１００６からメモリ１００４にロードされ、その後、プロセッサセット１００２によって実行される。プログラムの実行中において、プロセッサセット１００２は、上述した機能を実行する。システム１０００は、ディスプレイ１０１０、キーボード１０１８及びポインティングデバイス１０２０に結合されることができる。
【００７４】
いくつかの実施形態において、区間データ構造受信モジュール９０２は、区間の表現を含むデータを受信することができる。区間離散化モジュール９０４は、区間を離散化部分区間に分割することができる。部分区間ハッシュモジュール９０６は、部分区間についてのハッシュコード値を取得するために局所性保持ハッシュ関数を使用することができる。区間探索モジュール９０８は、所定のクエリ区間又はポイントと重複する区間についての区間ハッシュテーブルを探索することができる。部分区間記憶モジュール９１０は、区間ハッシュテーブルデータ構造における部分区間を記憶することができる。図２に示された区間ハッシュテーブルモジュール２０２は、図１０に示された様々なモジュールの任意の及び全ての機能を提供してもよいことに留意されたい。
【００７５】
この詳細な説明に記載されたデータ構造及びコードは、典型的には、コンピュータシステムによって使用するためのコード及び／又はデータを記憶することができる任意の装置又は媒体とすることができるコンピュータ可読記憶媒体上に記憶される。コンピュータ可読記憶媒体は、限定されるものではないが、揮発性メモリ、不揮発性メモリ、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、ＤＶＤ（ディジタル多用途ディスク又はディジタルビデオディスク）などの磁気及び光記憶装置、又は、現在知られているか又は今後開発されるコンピュータ可読媒体を記憶することができる他の媒体を含む。
【００７６】
詳細な説明のセクションに記載された方法及びプロセスは、上述したようにコンピュータ可読記憶媒体に記憶することができるコード及び／又はデータとして具現化されることができる。コンピュータシステムがコンピュータ可読記憶媒体に記憶されたコード及び／又はデータを読み取って実行すると、コンピュータシステムは、コンピュータ可読記憶媒体内に記憶されたデータ構造及びコードとして具現化される方法及びプロセスを行う。
【００７７】
さらにまた、本願明細書に記載される方法及びプロセスは、ハードウェアモジュール又は装置に含まれることができる。これらのモジュール又は装置は、限定されるものではないが、特定用途向け集積回路（ＡＳＩＣ）チップ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定の時間に特定のソフトウェアモジュール又はコードの一部を実行する専用又は共有プロセッサ、及び／又は、現在知られているか又は後に開発される他のプログラマブル論理デバイスを含むことができる。ハードウェアモジュール又は装置が起動される場合、それらは、それらの内部に含まれる方法及びプロセスを実行する。
【図１Ａ】
2017220226.tif 000004
【図１Ｂ】
2017220226.tif 000005
【図１Ｃ】
2017220226.tif 000006
【図２】
2017220226.tif 000007
【図３】
2017220226.tif 000008
【図４】
2017220226.tif 000009
【図５】
2017220226.tif 000010
【図６】
2017220226.tif 000011
【図７Ａ】
2017220226.tif 000012
【図７Ｂ】
2017220226.tif 000013
【図８】
2017220226.tif 000014
【図９】
2017220226.tif 000015
【図１０】
2017220226.tif 000016