【手続補正書】
【提出日】平成20年9月29日(2008.9.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ネットワーク上に配置され、他の装置と共有するデータを検索するデータ検索装置であって、
前記ネットワーク上の仮想的な位置を示す識別子であり該識別子に含まれる構成子の並びにより一意の順位を表す論理識別子が当該論理識別子によって示される位置に配置されるデータ検索装置毎に一意に付与され、
前記データ検索装置は、検索対象となる各データ検索装置の論理識別子の集合である論理識別子範囲を指定した検索要求を受け取ると、前記論理識別子範囲が含む各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで前記論理識別子範囲を１または複数の論理識別子範囲に分割する分割手段と、
前記分割手段によって分割された各論理識別子範囲を検索対象として指定した検索要求を、該検索要求の転送先条件が成立する装置に転送する検索要求転送手段とを備えるデータ検索装置。
【請求項２】
前記論理識別子は該論理識別子に含まれる構成子の並びにより一意の数値を表し、
前記分割手段は、前記論理識別子範囲が含む各論理識別子に含まれる先頭の構成子が同一であるように各論理識別子を分別することで該論理識別子範囲を１または複数の論理識別子範囲に分割し、分割された１または複数の論理識別子範囲毎に該論理識別子範囲が含む各論理識別子を、それぞれ前記先頭の構成子を取り出すようにビットシフトするビットシフト範囲分割処理を実行する請求項１記載のデータ検索装置。
【請求項３】
前記分割手段は、
前記論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子に含まれる先頭の構成子を比較し、
両先頭の構成子が同一である場合に、前記論理識別子範囲が含む各論理識別子を、それぞれ前記先頭の構成子を取り出すようにビットシフトし、
両先頭の構成子が異なる場合に、前記ビットシフト範囲分割処理を実行する請求項２記載のデータ検索装置。
【請求項４】
前記データ検索装置は、
該データ検索装置の論理識別子が表す数値が前記ネットワークに配置されているデータ検索装置の論理識別子の中で最大値を表す場合には、最小値を表す論理識別子のデータ検索装置であり、該データ検索装置の論理識別子が表す数値よりも大きい数値を表す論理識別子の他のデータ検索装置が存在する場合には、該他のデータ検索装置の論理識別子の中で最小値を表す論理識別子の他のデータ検索装置である、論理的近接装置とあらかじめ通信可能に接続され、
前記データ検索装置は、
該データ検索装置の論理識別子と前記受け取った検索要求で指定される論理識別子範囲とに基づいて一の仮想的な位置を示す論理識別子を生成する検索実行手段と、
前記論理識別子範囲が含む各論理識別子が、該データ検索装置の論理識別子が表す数値と前記論理的近接装置の論理識別子が表す数値とで示される範囲に含まれる数値を表す論理識別子の集合である特定範囲に含まれるか否かによって前記論理識別子範囲を分割する範囲分割手段とを備え、
前記分割手段は、
前記範囲分割手段によって分割された各論理識別子範囲のうち前記特定範囲が含まない論理識別子を含む論理識別子範囲に対して前記ビットシフト範囲分割処理を実行し、
前記検索要求転送手段は、
前記分割手段によって分割された各論理識別子範囲を検索対象として指定するとともに前記一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項２または請求項３記載のデータ検索装置。
【請求項５】
前記分割手段は、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が前記特定範囲に含まれる場合に、前記特定範囲が含まない各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで、前記各論理識別子を含む論理識別子範囲を分割する請求項４記載のデータ検索装置。
【請求項６】
前記分割手段は、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が前記特定範囲に含まれない場合、前記検索要求を前記検索要求転送手段に送り、
前記検索要求転送手段は、
前記受け取った検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項４または請求項５記載のデータ検索装置。
【請求項７】
前記検索実行手段は、前記一の仮想的な位置を示す論理識別子に含まれる後尾の構成子が、前記受け取った検索要求で指定される論理識別子範囲に含まれる各論理識別子の特定の位置の構成子となるように前記一の仮想的な位置を示す論理識別子を生成する請求項４記載のデータ検索装置。
【請求項８】
前記データ検索装置は、
前記分割手段によって分割された論理識別子範囲毎に、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子と該論理識別子範囲に含まれる各論理識別子の先頭の構成子とから一の仮想的な位置を示す論理識別子を算出する先頭ビット取得手段を備え、
前記検索要求転送手段は、
前記分割手段によって分割された各論理識別子範囲を検索対象として指定するとともに前記先頭ビット取得手段が算出した一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項５記載のデータ検索装置。
【請求項９】
前記検索実行手段は、該データ検索装置の論理識別子と前記受け取った検索要求で指定される論理識別子範囲とに基づいて、一の仮想的な位置を示す論理識別子を、前記論理識別子範囲に含まれる論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である境界論理識別子毎にそれぞれ対応付けて生成し、前記各一の仮想的な位置を示す論理識別子がそれぞれ表す数値で示される範囲に含まれる数値を表す論理識別子の集合である仮想論理識別子範囲を前記論理識別子範囲と対応付け、
前記分割手段は、
前記論理識別子範囲が含む各論理識別子が、前記特定範囲に含まれるか否かによって該各論理識別子を分別することで前記論理識別子範囲を分割し、分割前の論理識別子範囲の各境界論理識別子と、該各境界論理識別子にそれぞれ対応付けられている前記一の仮想的な位置を示す論理識別子とに基づいて前記仮想論理識別子範囲を分割して、分割された各論理識別子範囲にそれぞれ対応付ける第１分割手段と、
前記第１分割手段によって分割された各論理識別子範囲のうち、前記特定範囲に含まれない論理識別子を含む論理識別子範囲に対応付けられている仮想論理識別子範囲が含む各論理識別子が、前記特定範囲に含まれるか否かによって前記仮想論理識別子範囲を分割し、分割された各仮想論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である仮想境界論理識別子と、前記論理識別子範囲の各境界論理識別子とに基づいて前記論理識別子範囲を分割して、分割された各仮想論理識別子範囲にそれぞれ対応付ける第２分割手段と、
前記第２分割手段によって分割された各仮想論理識別子範囲のうち、前記特定範囲が含む論理識別子を含む仮想論理識別子範囲の各境界仮想論理識別子と、当該各境界仮想論理識別子にそれぞれ対応付けられている境界論理識別子と、をそれぞれ先頭の構成子を取り出すようにビットシフトする範囲左ビットシフト手段と、を含み、
前記検索要求転送手段は、
前記分割手段によって分割された各論理識別子範囲を検索対象として指定するとともに前記各論理識別子範囲にそれぞれ対応付けられている仮想論理識別子範囲を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項４記載のデータ検索装置。
【請求項１０】
ネットワーク上に配置された複数の端末を備え、各端末間で共有するデータを検索するデータ検索システムであって、
前記ネットワーク上の仮想的な位置を示す識別子であり該識別子に含まれる構成子の並びにより一意の順位を表す論理識別子が当該論理識別子によって示される位置に配置される端末毎に一意に付与され、
前記各端末は、検索対象となる各端末の論理識別子の集合である論理識別子範囲を指定した検索要求を受け取ると、前記論理識別子範囲が含む各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで前記論理識別子範囲を１または複数の論理識別子範囲に分割する分割手段と、
前記分割手段によって分割された各論理識別子範囲を検索対象として指定した検索要求を、該検索要求の転送先条件が成立する装置に転送する検索要求転送手段とを備えるデータ検索システム。
【請求項１１】
ネットワーク上の仮想的な位置を示す識別子であり該識別子に含まれる構成子の並びにより一意の順位を表す論理識別子が当該論理識別子によって示される位置に配置されるデータ検索装置毎に一意に付与され、
前記データ検索装置は、検索対象となる各データ検索装置の論理識別子の集合である論理識別子範囲を指定した検索要求を受け取ると、前記論理識別子範囲が含む各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで前記論理識別子範囲を１または複数の論理識別子範囲に分割する分割ステップと、
前記分割ステップによって分割された各論理識別子範囲を検索対象として指定した検索要求を、該検索要求の転送先条件が成立する装置に転送する検索要求転送ステップとを実行するデータ検索方法。
【請求項１２】
前記論理識別子は該論理識別子に含まれる構成子の並びにより一意の数値を表し、
前記分割ステップは、前記論理識別子範囲が含む各論理識別子に含まれる先頭の構成子が同一であるように各論理識別子を分別することで該論理識別子範囲を１または複数の論理識別子範囲に分割し、分割された１または複数の論理識別子範囲毎に該論理識別子範囲が含む各論理識別子を、それぞれ前記先頭の構成子を取り出すようにビットシフトするビットシフト範囲分割処理を実行する請求項１１記載のデータ検索方法。
【請求項１３】
前記分割ステップは、
前記論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子に含まれる先頭の構成子を比較し、
両先頭の構成子が同一である場合に、前記論理識別子範囲が含む各論理識別子を、それぞれ前記先頭の構成子を取り出すようにビットシフトし、
両先頭の構成子が異なる場合に、前記ビットシフト範囲分割処理を実行する請求項１２記載のデータ検索方法。
【請求項１４】
前記データ検索装置は、
該データ検索装置の論理識別子が表す数値が前記ネットワークに配置されているデータ検索装置の論理識別子の中で最大値を表す場合には、最小値を表す論理識別子のデータ検索装置であり、該データ検索装置の論理識別子が表す数値よりも大きい数値を表す論理識別子の他のデータ検索装置が存在する場合には、該他のデータ検索装置の論理識別子の中で最小値を表す論理識別子の他のデータ検索装置である、論理的近接装置とあらかじめ通信可能に接続され、
前記データ検索装置は、
該データ検索装置の論理識別子と前記受け取った検索要求で指定される論理識別子範囲とに基づいて一の仮想的な位置を示す論理識別子を生成する検索実行ステップと、
前記論理識別子範囲が含む各論理識別子が、該データ検索装置の論理識別子が表す数値と前記論理的近接装置の論理識別子が表す数値とで示される範囲に含まれる数値を表す論理識別子の集合である特定範囲に含まれるか否かによって前記論理識別子範囲を分割する範囲分割ステップとを実行し、
前記分割ステップは、
前記範囲分割ステップによって分割された各論理識別子範囲のうち前記特定範囲が含まない論理識別子を含む論理識別子範囲に対して前記ビットシフト範囲分割処理を実行し、
前記検索要求転送ステップは、
前記分割ステップによって分割された各論理識別子範囲を検索対象として指定するとともに前記一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項１２または請求項１３記載のデータ検索方法。
【請求項１５】
前記分割ステップは、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が前記特定範囲に含まれる場合に、前記特定範囲が含まない各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで、前記各論理識別子を含む論理識別子範囲を分割する請求項１４記載のデータ検索方法。
【請求項１６】
前記分割ステップは、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が前記特定範囲に含まれない場合、前記検索要求を前記検索要求転送ステップに送り、
前記検索要求転送ステップは、
前記受け取った検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項１４または請求項１５記載のデータ検索方法。
【請求項１７】
前記検索実行ステップは、前記一の仮想的な位置を示す論理識別子に含まれる後尾の構成子が、前記受け取った検索要求で指定される論理識別子範囲に含まれる各論理識別子の特定の位置の構成子となるように前記一の仮想的な位置を示す論理識別子を生成する請求項１４記載のデータ検索方法。
【請求項１８】
前記データ検索装置は、
前記分割ステップによって分割された論理識別子範囲毎に、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子と該論理識別子範囲に含まれる各論理識別子の先頭の構成子とから一の仮想的な位置を示す論理識別子を算出する先頭ビット取得ステップを実行し、
前記検索要求転送ステップは、
前記分割ステップによって分割された各論理識別子範囲を検索対象として指定するとともに前記先頭ビット取得ステップが算出した一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項１５記載のデータ検索方法。
【請求項１９】
前記検索実行ステップは、該データ検索装置の論理識別子と前記受け取った検索要求で指定される論理識別子範囲とに基づいて、一の仮想的な位置を示す論理識別子を、前記論理識別子範囲に含まれる論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である境界論理識別子毎にそれぞれ対応付けて生成し、前記各一の仮想的な位置を示す論理識別子がそれぞれ表す数値で示される範囲に含まれる数値を表す論理識別子の集合である仮想論理識別子範囲を前記論理識別子範囲と対応付け、
前記分割ステップは、
前記論理識別子範囲が含む各論理識別子が、前記特定範囲に含まれるか否かによって該各論理識別子を分別することで前記論理識別子範囲を分割し、分割前の論理識別子範囲の各境界論理識別子と、該各境界論理識別子にそれぞれ対応付けられている前記一の仮想的な位置を示す論理識別子とに基づいて前記仮想論理識別子範囲を分割して、分割された各論理識別子範囲にそれぞれ対応付ける第１分割ステップと、
前記第１分割ステップによって分割された各論理識別子範囲のうち、前記特定範囲に含まれない論理識別子を含む論理識別子範囲に対応付けられている仮想論理識別子範囲が含む各論理識別子が、前記特定範囲に含まれるか否かによって前記仮想論理識別子範囲を分割し、分割された各仮想論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である仮想境界論理識別子と、前記論理識別子範囲の各境界論理識別子とに基づいて前記論理識別子範囲を分割して、分割された各仮想論理識別子範囲にそれぞれ対応付ける第２分割ステップと、
前記第２分割ステップによって分割された各仮想論理識別子範囲のうち、前記特定範囲が含む論理識別子を含む仮想論理識別子範囲の各境界仮想論理識別子と、当該各境界仮想論理識別子にそれぞれ対応付けられている境界論理識別子と、をそれぞれ先頭の構成子を取り出すようにビットシフトする範囲左ビットシフトステップと、を実行し、
前記検索要求転送ステップは、
前記分割ステップによって分割された各論理識別子範囲を検索対象として指定するとともに前記各論理識別子範囲にそれぞれ対応付けられている仮想論理識別子範囲を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項１４記載のデータ検索方法。
【請求項２０】
ネットワーク上に配置されたデータ検索装置が他の装置と共有するデータを検索するためのデータ検索用プログラムであって、
前記ネットワーク上の仮想的な位置を示す識別子であり該識別子に含まれる構成子の並びにより一意の順位を表す論理識別子が当該論理識別子によって示される位置に配置される前記データ検索装置毎に一意に付与され、
検索対象となる各データ検索装置の論理識別子の集合である論理識別子範囲を指定した検索要求を受け取ると、前記論理識別子範囲が含む各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで前記論理識別子範囲を１または複数の論理識別子範囲に分割する分割処理と、
前記分割処理によって分割された各論理識別子範囲を検索対象として指定した検索要求を、該検索要求の転送先条件が成立する装置に転送する検索要求転送処理とを前記データ検索装置に実行させるデータ検索用プログラム。
【請求項２１】
前記論理識別子は該論理識別子に含まれる構成子の並びにより一意の数値を表し、
前記分割処理は、前記論理識別子範囲が含む各論理識別子に含まれる先頭の構成子が同一であるように各論理識別子を分別することで該論理識別子範囲を１または複数の論理識別子範囲に分割し、分割された１または複数の論理識別子範囲毎に該論理識別子範囲が含む各論理識別子を、それぞれ前記先頭の構成子を取り出すようにビットシフトするビットシフト範囲分割処理を実行する請求項２０記載のデータ検索用プログラム。
【請求項２２】
前記分割処理は、
前記論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子に含まれる先頭の構成子を比較し、
両先頭の構成子が同一である場合に、前記論理識別子範囲が含む各論理識別子を、それぞれ前記先頭の構成子を取り出すようにビットシフトし、
両先頭の構成子が異なる場合に、前記ビットシフト範囲分割処理を実行する請求項２１記載のデータ検索用プログラム。
【請求項２３】
前記データ検索装置は、
該データ検索装置の論理識別子が表す数値が前記ネットワークに配置されているデータ検索装置の論理識別子の中で最大値を表す場合には、最小値を表す論理識別子のデータ検索装置であり、該データ検索装置の論理識別子が表す数値よりも大きい数値を表す論理識別子の他のデータ検索装置が存在する場合には、該他のデータ検索装置の論理識別子の中で最小値を表す論理識別子の他のデータ検索装置である、論理的近接装置とあらかじめ通信可能に接続され、
該データ検索装置の論理識別子と前記受け取った検索要求で指定される論理識別子範囲とに基づいて一の仮想的な位置を示す論理識別子を生成する検索実行処理と、
前記論理識別子範囲が含む各論理識別子が、該データ検索装置の論理識別子が表す数値と前記論理的近接装置の論理識別子が表す数値とで示される範囲に含まれる数値を表す論理識別子の集合である特定範囲に含まれるか否かによって前記論理識別子範囲を分割する範囲分割処理とを実行し、
前記分割処理は、
前記範囲分割処理によって分割された各論理識別子範囲のうち前記特定範囲が含まない論理識別子を含む論理識別子範囲に対して前記ビットシフト範囲分割処理を実行し、
前記検索要求転送処理は、
前記分割処理によって分割された各論理識別子範囲を検索対象として指定するとともに前記一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項２１または請求項２２記載のデータ検索用プログラム。
【請求項２４】
前記分割処理は、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が前記特定範囲に含まれる場合に、前記特定範囲が含まない各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで、前記各論理識別子を含む論理識別子範囲を分割する請求項２３記載のデータ検索用プログラム。
【請求項２５】
前記分割処理は、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が前記特定範囲に含まれない場合、前記検索要求を前記検索要求転送処理に送り、
前記検索要求転送処理は、
前記受け取った検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項２３または請求項２４記載のデータ検索用プログラム。
【請求項２６】
前記検索実行処理は、前記一の仮想的な位置を示す論理識別子に含まれる後尾の構成子が、前記受け取った検索要求で指定される論理識別子範囲に含まれる各論理識別子の特定の位置の構成子となるように前記一の仮想的な位置を示す論理識別子を生成する請求項２３記載のデータ検索用プログラム。
【請求項２７】
前記データ検索装置は、
前記分割処理によって分割された論理識別子範囲毎に、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子と該論理識別子範囲に含まれる各論理識別子の先頭の構成子とから一の仮想的な位置を示す論理識別子を算出する先頭ビット取得処理を実行し、
前記検索要求転送処理は、
前記分割処理によって分割された各論理識別子範囲を検索対象として指定するとともに前記先頭ビット取得処理が算出した一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項２４記載のデータ検索用プログラム。
【請求項２８】
前記検索実行処理は、該データ検索装置の論理識別子と前記受け取った検索要求で指定される論理識別子範囲とに基づいて、一の仮想的な位置を示す論理識別子を、前記論理識別子範囲に含まれる論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である境界論理識別子毎にそれぞれ対応付けて生成し、前記各一の仮想的な位置を示す論理識別子がそれぞれ表す数値で示される範囲に含まれる数値を表す論理識別子の集合である仮想論理識別子範囲を前記論理識別子範囲と対応付け、
前記分割処理は、
前記論理識別子範囲が含む各論理識別子が、前記特定範囲に含まれるか否かによって該各論理識別子を分別することで前記論理識別子範囲を分割し、分割前の論理識別子範囲の各境界論理識別子と、該各境界論理識別子にそれぞれ対応付けられている前記一の仮想的な位置を示す論理識別子とに基づいて前記仮想論理識別子範囲を分割して、分割された各論理識別子範囲にそれぞれ対応付ける第１分割処理と、
前記第１分割処理によって分割された各論理識別子範囲のうち、前記特定範囲に含まれない論理識別子を含む論理識別子範囲に対応付けられている仮想論理識別子範囲が含む各論理識別子が、前記特定範囲に含まれるか否かによって前記仮想論理識別子範囲を分割し、分割された各仮想論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である仮想境界論理識別子と、前記論理識別子範囲の各境界論理識別子とに基づいて前記論理識別子範囲を分割して、分割された各仮想論理識別子範囲にそれぞれ対応付ける第２分割処理と、
前記第２分割処理によって分割された各仮想論理識別子範囲のうち、前記特定範囲が含む論理識別子を含む仮想論理識別子範囲の各境界仮想論理識別子と、当該各境界仮想論理識別子にそれぞれ対応付けられている境界論理識別子と、をそれぞれ先頭の構成子を取り出すようにビットシフトする範囲左ビットシフト処理と、を実行し、
前記検索要求転送処理は、
前記分割処理によって分割された各論理識別子範囲を検索対象として指定するとともに前記各論理識別子範囲にそれぞれ対応付けられている仮想論理識別子範囲を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する請求項２３記載のデータ検索用プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
Ｋｏｏｒｄｅでは、このようなｄｅ  Ｂｒｕｉｊｎグラフを一方向リンクを利用してルーティングを行う。例えば、３ビットの論理識別子がｘｙｚのノードから３ビットの論理識別子がａｂｃのノードにメッセージを転送するときは、論理識別子がｘｙｚ→ｙｚａ→ｚａｂ→ａｂｃのノードへ順にメッセージがルーティングされる。すなわち、終点の論理識別子と始点の論理識別子をつなげたｘｙｚａｂｃを順に左にシフトさせたノードにメッセージが転送される。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
（２）第２の従来技術について：
第１の従来技術はオーバレイネットワークに関係なく、ｄｅ  Ｂｒｕｉｊｎグラフを用いた理論上のアルゴリズムについての説明であったが、実際には、Ｃｈｏｒｄのハッシュ空間では各ノードは間隔を持って存在しているため（すなわち、論理識別子空間１６（２の４乗）である場合に、論理識別子０〜１５の全てにノードが存在するわけではないため）、全ての論理識別子を持つノードが定義されたｄｅ  Ｂｒｕｉｊｎグラフは適用できない。そこで、Ｋｏｏｒｄｅではｄｅ  Ｂｒｕｉｊｎ上のＩＤをＣｈｏｒｄハッシュ空間上の仮想ＩＤとし、一つのノードがある区間のＩＤを担当させている。このようにオーバレイネットワークにＫｏｏｒｄｅを実装した場合の構成についても、非特許文献１に記載されている。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
図１９に示すように、第２の従来技術におけるデータ検索システムは、ネットワーク３００上でのアドレスを有する複数のピア３１０，３２０，３３０から構成される。なお、ピア３１０，３２０，３３０は、それぞれ第１の従来技術におけるノードに相当する。これらのピア３１０，３２０，３３０はそれぞれ異なる論理識別子を有する。さらに、各ピア３１０，３２０，３３０は、ピア論理識別子格納部３１８と、ローカルデータ格納部３１１と、ルーティングテーブル３１２と、メッセージ転送手段３１３と、通信手段３１４と、左ビットシフト手段３１５と、先頭ビット取得手段３１６と、登録・検索実行手段３１７とを備えている。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
仮想ノードｉが上記の範囲に含まれる場合は（ステップＳ４０３のＹｅｓ）、ピアｍの先頭ビット取得手段３１６は、キーシフトｋｓｈｉｆｔの先頭ビットｂと、当該仮想ノードｉを用いて、２ｉ＋ｂ  ｍｏｄ  Ｎの計算を行い、計算結果の論理識別子を仮想ノードｉとする（ステップＳ４０４）。ここで、Ｎは論理識別子空間のサイズある。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００４３
【補正方法】変更
【補正の内容】
【００４３】
以上の目的を達成するため、本発明のデータ検索装置は、ネットワーク上に配置され、他の装置と共有するデータを検索するデータ検索装置であって、ネットワーク上の仮想的な位置を示す識別子であり該識別子に含まれる構成子の並びにより一意の順位を表す論理識別子が当該論理識別子によって示される位置に配置されるデータ検索装置毎に一意に付与され、データ検索装置は、検索対象となる各データ検索装置の論理識別子の集合である論理識別子範囲を指定した検索要求を受け取ると、論理識別子範囲が含む各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで論理識別子範囲を１または複数の論理識別子範囲に分割する分割手段と、分割手段によって分割された各論理識別子範囲を検索対象として指定した検索要求を、該検索要求の転送先条件が成立する装置に転送する検索要求転送手段とを備える。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００４４
【補正方法】変更
【補正の内容】
【００４４】
論理識別子は該論理識別子に含まれる構成子の並びにより一意の数値を表し、分割手段は、論理識別子範囲が含む各論理識別子に含まれる先頭の構成子が同一であるように各論理識別子を分別することで該論理識別子範囲を１または複数の論理識別子範囲に分割し、分割された１または複数の論理識別子範囲毎に該論理識別子範囲が含む各論理識別子を、それぞれ先頭の構成子を取り出すようにビットシフトするビットシフト範囲分割処理を実行するように構成されていてもよい。このような構成によれば、確実にネットワーク上におけるデータの範囲検索を実現することができる。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００４５
【補正方法】変更
【補正の内容】
【００４５】
分割手段は、論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子に含まれる先頭の構成子を比較し、両先頭の構成子が同一である場合に、論理識別子範囲が含む各論理識別子を、それぞれ先頭の構成子を取り出すようにビットシフトし、両先頭の構成子が異なる場合に、ビットシフト範囲分割処理を実行するように構成されていてもよい。このような構成によれば、論理識別子範囲を先頭の構成子が同一であるような複数の論理識別子範囲に確実に分割することができる。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００４６
【補正方法】変更
【補正の内容】
【００４６】
データ検索装置は、該データ検索装置の論理識別子が表す数値がネットワークに配置されているデータ検索装置の論理識別子の中で最大値を表す場合には、最小値を表す論理識別子のデータ検索装置であり、該データ検索装置の論理識別子が表す数値よりも大きい数値を表す論理識別子の他のデータ検索装置が存在する場合には、該他のデータ検索装置の論理識別子の中で最小値を表す論理識別子の他のデータ検索装置である、論理的近接装置とあらかじめ通信可能に接続され、データ検索装置は、該データ検索装置の論理識別子と受け取った検索要求で指定される論理識別子範囲とに基づいて一の仮想的な位置を示す論理識別子を生成する検索実行手段と、論理識別子範囲が含む各論理識別子が、該データ検索装置の論理識別子が表す数値と論理的近接装置の論理識別子が表す数値とで示される範囲に含まれる数値を表す論理識別子の集合である特定範囲に含まれるか否かによって論理識別子範囲を分割する範囲分割手段とを備え、分割手段は、範囲分割手段によって分割された各論理識別子範囲のうち特定範囲が含まない論理識別子を含む論理識別子範囲に対してビットシフト範囲分割処理を実行し、検索要求転送手段は、分割手段によって分割された各論理識別子範囲を検索対象として指定するとともに一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送するように構成されていてもよい。このような構成によれば、定数次数と対数ホップ数を実現しつつオーバレイネットワーク上でのデータの範囲検索を確実に実行することができる。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
分割手段は、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が特定範囲に含まれる場合に、特定範囲が含まない各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで、各論理識別子を含む論理識別子範囲を分割するように構成されていてもよい。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００４８
【補正方法】変更
【補正の内容】
【００４８】
分割手段は、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が特定範囲に含まれない場合、検索要求を検索要求転送手段に送り、検索要求転送手段は、受け取った検索要求を、該検索要求の転送先条件が成立する装置に転送するように構成されていてもよい。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００４９
【補正方法】変更
【補正の内容】
【００４９】
検索実行手段は、一の仮想的な位置を示す論理識別子に含まれる後尾の構成子が、受け取った検索要求で指定される論理識別子範囲に含まれる各論理識別子の特定の位置の構成子となるように一の仮想的な位置を示す論理識別子を生成するように構成されていてもよい。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００５０
【補正方法】変更
【補正の内容】
【００５０】
データ検索装置は、分割手段によって分割された論理識別子範囲毎に、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子と該論理識別子範囲に含まれる各論理識別子の先頭の構成子とから一の仮想的な位置を示す論理識別子を算出する先頭ビット取得手段を備え、検索要求転送手段は、分割手段によって分割された各論理識別子範囲を検索対象として指定するとともに先頭ビット取得手段が算出した一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送するように構成されていてもよい。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
検索実行手段は、該データ検索装置の論理識別子と受け取った検索要求で指定される論理識別子範囲とに基づいて、一の仮想的な位置を示す論理識別子を、論理識別子範囲に含まれる論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である境界論理識別子毎にそれぞれ対応付けて生成し、各一の仮想的な位置を示す論理識別子がそれぞれ表す数値で示される範囲に含まれる数値を表す論理識別子の集合である仮想論理識別子範囲を論理識別子範囲と対応付け、分割手段は、論理識別子範囲が含む各論理識別子が、特定範囲に含まれるか否かによって該各論理識別子を分別することで論理識別子範囲を分割し、分割前の論理識別子範囲の各境界論理識別子と、該各境界論理識別子にそれぞれ対応付けられている一の仮想的な位置を示す論理識別子とに基づいて仮想論理識別子範囲を分割して、分割された各論理識別子範囲にそれぞれ対応付ける第１分割手段と、第１分割手段によって分割された各論理識別子範囲のうち、特定範囲に含まれない論理識別子を含む論理識別子範囲に対応付けられている仮想論理識別子範囲が含む各論理識別子が、特定範囲に含まれるか否かによって仮想論理識別子範囲を分割し、分割された各仮想論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である仮想境界論理識別子と、論理識別子範囲の各境界論理識別子とに基づいて論理識別子範囲を分割して、分割された各仮想論理識別子範囲にそれぞれ対応付ける第２分割手段と、第２分割手段によって分割された各仮想論理識別子範囲のうち、特定範囲が含む論理識別子を含む仮想論理識別子範囲の各境界仮想論理識別子と、当該各境界仮想論理識別子にそれぞれ対応付けられている境界論理識別子と、をそれぞれ先頭の構成子を取り出すようにビットシフトする範囲左ビットシフト手段と、を含み、検索要求転送手段は、分割手段によって分割された各論理識別子範囲を検索対象として指定するとともに各論理識別子範囲にそれぞれ対応付けられている仮想論理識別子範囲を含む検索要求を、該検索要求の転送先条件が成立する装置に転送するように構成されていてもよい。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００５２
【補正方法】変更
【補正の内容】
【００５２】
本発明のデータ検索システムは、ネットワーク上に配置された複数の端末を備え、各端末間で共有するデータを検索するデータ検索システムであって、ネットワーク上の仮想的な位置を示す識別子であり該識別子に含まれる構成子の並びにより一意の順位を表す論理識別子が当該論理識別子によって示される位置に配置される端末毎に一意に付与され、各端末は、検索対象となる各端末の論理識別子の集合である論理識別子範囲を指定した検索要求を受け取ると、論理識別子範囲が含む各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで論理識別子範囲を１または複数の論理識別子範囲に分割する分割手段と、分割手段によって分割された各論理識別子範囲を検索対象として指定した検索要求を、該検索要求の転送先条件が成立する装置に転送する検索要求転送手段とを備える。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００５３
【補正方法】変更
【補正の内容】
【００５３】
本発明のデータ検索方法は、ネットワーク上の仮想的な位置を示す識別子であり該識別子に含まれる構成子の並びにより一意の順位を表す論理識別子が当該論理識別子によって示される位置に配置されるデータ検索装置毎に一意に付与され、データ検索装置は、検索対象となる各データ検索装置の論理識別子の集合である論理識別子範囲を指定した検索要求を受け取ると、論理識別子範囲が含む各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで論理識別子範囲を１または複数の論理識別子範囲に分割する分割ステップと、分割ステップによって分割された各論理識別子範囲を検索対象として指定した検索要求を、該検索要求の転送先条件が成立する装置に転送する検索要求転送ステップとを実行する。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】００５４
【補正方法】変更
【補正の内容】
【００５４】
論理識別子は該論理識別子に含まれる構成子の並びにより一意の数値を表し、分割ステップは、論理識別子範囲が含む各論理識別子に含まれる先頭の構成子が同一であるように各論理識別子を分別することで該論理識別子範囲を１または複数の論理識別子範囲に分割し、分割された１または複数の論理識別子範囲毎に該論理識別子範囲が含む各論理識別子を、それぞれ先頭の構成子を取り出すようにビットシフトするビットシフト範囲分割処理を実行する。
分割ステップは、論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子に含まれる先頭の構成子を比較し、両先頭の構成子が同一である場合に、論理識別子範囲が含む各論理識別子を、それぞれ先頭の構成子を取り出すようにビットシフトし、両先頭の構成子が異なる場合に、ビットシフト範囲分割処理を実行する。
データ検索装置は、該データ検索装置の論理識別子が表す数値がネットワークに配置されているデータ検索装置の論理識別子の中で最大値を表す場合には、最小値を表す論理識別子のデータ検索装置であり、該データ検索装置の論理識別子が表す数値よりも大きい数値を表す論理識別子の他のデータ検索装置が存在する場合には、該他のデータ検索装置の論理識別子の中で最小値を表す論理識別子の他のデータ検索装置である、論理的近接装置とあらかじめ通信可能に接続され、データ検索装置は、該データ検索装置の論理識別子と受け取った検索要求で指定される論理識別子範囲とに基づいて一の仮想的な位置を示す論理識別子を生成する検索実行ステップと、論理識別子範囲が含む各論理識別子が、該データ検索装置の論理識別子が表す数値と論理的近接装置の論理識別子が表す数値とで示される範囲に含まれる数値を表す論理識別子の集合である特定範囲に含まれるか否かによって論理識別子範囲を分割する範囲分割ステップとを実行し、分割ステップは、範囲分割ステップによって分割された各論理識別子範囲のうち特定範囲が含まない論理識別子を含む論理識別子範囲に対してビットシフト範囲分割処理を実行し、検索要求転送ステップは、分割ステップによって分割された各論理識別子範囲を検索対象として指定するとともに一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】００５５
【補正方法】変更
【補正の内容】
【００５５】
分割ステップは、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が特定範囲に含まれる場合に、特定範囲が含まない各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで、各論理識別子を含む論理識別子範囲を分割する。
分割ステップは、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が特定範囲に含まれない場合、検索要求を検索要求転送ステップに送り、検索要求転送ステップは、受け取った検索要求を、該検索要求の転送先条件が成立する装置に転送する。
検索実行ステップは、一の仮想的な位置を示す論理識別子に含まれる後尾の構成子が、受け取った検索要求で指定される論理識別子範囲に含まれる各論理識別子の特定の位置の構成子となるように一の仮想的な位置を示す論理識別子を生成する。
データ検索装置は、分割ステップによって分割された論理識別子範囲毎に、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子と該論理識別子範囲に含まれる各論理識別子の先頭の構成子とから一の仮想的な位置を示す論理識別子を算出する先頭ビット取得ステップを実行し、検索要求転送ステップは、分割ステップによって分割された各論理識別子範囲を検索対象として指定するとともに先頭ビット取得ステップが算出した一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する。
検索実行ステップは、該データ検索装置の論理識別子と受け取った検索要求で指定される論理識別子範囲とに基づいて、一の仮想的な位置を示す論理識別子を、論理識別子範囲に含まれる論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である境界論理識別子毎にそれぞれ対応付けて生成し、各一の仮想的な位置を示す論理識別子がそれぞれ表す数値で示される範囲に含まれる数値を表す論理識別子の集合である仮想論理識別子範囲を論理識別子範囲と対応付け、分割ステップは、論理識別子範囲が含む各論理識別子が、特定範囲に含まれるか否かによって該各論理識別子を分別することで論理識別子範囲を分割し、分割前の論理識別子範囲の各境界論理識別子と、該各境界論理識別子にそれぞれ対応付けられている一の仮想的な位置を示す論理識別子とに基づいて仮想論理識別子範囲を分割して、分割された各論理識別子範囲にそれぞれ対応付ける第１分割ステップと、第１分割ステップによって分割された各論理識別子範囲のうち、特定範囲に含まれない論理識別子を含む論理識別子範囲に対応付けられている仮想論理識別子範囲が含む各論理識別子が、特定範囲に含まれるか否かによって仮想論理識別子範囲を分割し、分割された各仮想論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である仮想境界論理識別子と、論理識別子範囲の各境界論理識別子とに基づいて論理識別子範囲を分割して、分割された各仮想論理識別子範囲にそれぞれ対応付ける第２分割ステップと、第２分割ステップによって分割された各仮想論理識別子範囲のうち、特定範囲が含む論理識別子を含む仮想論理識別子範囲の各境界仮想論理識別子と、当該各境界仮想論理識別子にそれぞれ対応付けられている境界論理識別子と、をそれぞれ先頭の構成子を取り出すようにビットシフトする範囲左ビットシフトステップと、を実行し、検索要求転送ステップは、分割ステップによって分割された各論理識別子範囲を検索対象として指定するとともに各論理識別子範囲にそれぞれ対応付けられている仮想論理識別子範囲を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する。
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
本発明のデータ検索用プログラムは、ネットワーク上に配置されたデータ検索装置が他の装置と共有するデータを検索するためのデータ検索用プログラムであって、ネットワーク上の仮想的な位置を示す識別子であり該識別子に含まれる構成子の並びにより一意の順位を表す論理識別子が当該論理識別子によって示される位置に配置されるデータ検索装置毎に一意に付与され、検索対象となる各データ検索装置の論理識別子の集合である論理識別子範囲を指定した検索要求を受け取ると、論理識別子範囲が含む各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで論理識別子範囲を１または複数の論理識別子範囲に分割する分割処理と、分割処理によって分割された各論理識別子範囲を検索対象として指定した検索要求を、該検索要求の転送先条件が成立する装置に転送する検索要求転送処理とをデータ検索装置に実行させる。
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】００５７
【補正方法】変更
【補正の内容】
【００５７】
論理識別子は該論理識別子に含まれる構成子の並びにより一意の数値を表し、分割処理は、論理識別子範囲が含む各論理識別子に含まれる先頭の構成子が同一であるように各論理識別子を分別することで該論理識別子範囲を１または複数の論理識別子範囲に分割し、分割された１または複数の論理識別子範囲毎に該論理識別子範囲が含む各論理識別子を、それぞれ先頭の構成子を取り出すようにビットシフトするビットシフト範囲分割処理を実行する。
分割処理は、論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子に含まれる先頭の構成子を比較し、両先頭の構成子が同一である場合に、論理識別子範囲が含む各論理識別子を、それぞれ先頭の構成子を取り出すようにビットシフトし、両先頭の構成子が異なる場合に、ビットシフト範囲分割処理を実行する。
データ検索装置は、該データ検索装置の論理識別子が表す数値がネットワークに配置されているデータ検索装置の論理識別子の中で最大値を表す場合には、最小値を表す論理識別子のデータ検索装置であり、該データ検索装置の論理識別子が表す数値よりも大きい数値を表す論理識別子の他のデータ検索装置が存在する場合には、該他のデータ検索装置の論理識別子の中で最小値を表す論理識別子の他のデータ検索装置である、論理的近接装置とあらかじめ通信可能に接続され、該データ検索装置の論理識別子と受け取った検索要求で指定される論理識別子範囲とに基づいて一の仮想的な位置を示す論理識別子を生成する検索実行処理と、論理識別子範囲が含む各論理識別子が、該データ検索装置の論理識別子が表す数値と論理的近接装置の論理識別子が表す数値とで示される範囲に含まれる数値を表す論理識別子の集合である特定範囲に含まれるか否かによって論理識別子範囲を分割する範囲分割処理とを実行し、分割処理は、範囲分割処理によって分割された各論理識別子範囲のうち特定範囲が含まない論理識別子を含む論理識別子範囲に対してビットシフト範囲分割処理を実行し、検索要求転送処理は、分割処理によって分割された各論理識別子範囲を検索対象として指定するとともに一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する。
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】００５８
【補正方法】変更
【補正の内容】
【００５８】
分割処理は、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が特定範囲に含まれる場合に、特定範囲が含まない各論理識別子に含まれる特定の位置の構成子毎に各論理識別子を分別することで、各論理識別子を含む論理識別子範囲を分割する。
分割処理は、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子が特定範囲に含まれない場合、検索要求を検索要求転送処理に送り、検索要求転送処理は、受け取った検索要求を、該検索要求の転送先条件が成立する装置に転送する。
検索実行処理は、一の仮想的な位置を示す論理識別子に含まれる後尾の構成子が、受け取った検索要求で指定される論理識別子範囲に含まれる各論理識別子の特定の位置の構成子となるように一の仮想的な位置を示す論理識別子を生成する。
データ検索装置は、分割処理によって分割された論理識別子範囲毎に、他のデータ検索装置から転送されてきた検索要求に含まれる一の仮想的な位置を示す論理識別子と該論理識別子範囲に含まれる各論理識別子の先頭の構成子とから一の仮想的な位置を示す論理識別子を算出する先頭ビット取得処理を実行し、検索要求転送処理は、分割処理によって分割された各論理識別子範囲を検索対象として指定するとともに先頭ビット取得処理が算出した一の仮想的な位置を示す論理識別子を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する。
検索実行処理は、該データ検索装置の論理識別子と受け取った検索要求で指定される論理識別子範囲とに基づいて、一の仮想的な位置を示す論理識別子を、論理識別子範囲に含まれる論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である境界論理識別子毎にそれぞれ対応付けて生成し、各一の仮想的な位置を示す論理識別子がそれぞれ表す数値で示される範囲に含まれる数値を表す論理識別子の集合である仮想論理識別子範囲を論理識別子範囲と対応付け、分割処理は、論理識別子範囲が含む各論理識別子が、特定範囲に含まれるか否かによって該各論理識別子を分別することで論理識別子範囲を分割し、分割前の論理識別子範囲の各境界論理識別子と、該各境界論理識別子にそれぞれ対応付けられている一の仮想的な位置を示す論理識別子とに基づいて仮想論理識別子範囲を分割して、分割された各論理識別子範囲にそれぞれ対応付ける第１分割処理と、第１分割処理によって分割された各論理識別子範囲のうち、特定範囲に含まれない論理識別子を含む論理識別子範囲に対応付けられている仮想論理識別子範囲が含む各論理識別子が、特定範囲に含まれるか否かによって仮想論理識別子範囲を分割し、分割された各仮想論理識別子範囲が含む各論理識別子のうち最大値と最小値とをそれぞれ表す論理識別子である仮想境界論理識別子と、論理識別子範囲の各境界論理識別子とに基づいて論理識別子範囲を分割して、分割された各仮想論理識別子範囲にそれぞれ対応付ける第２分割処理と、第２分割処理によって分割された各仮想論理識別子範囲のうち、特定範囲が含む論理識別子を含む仮想論理識別子範囲の各境界仮想論理識別子と、当該各境界仮想論理識別子にそれぞれ対応付けられている境界論理識別子と、をそれぞれ先頭の構成子を取り出すようにビットシフトする範囲左ビットシフト処理と、を実行し、検索要求転送処理は、分割処理によって分割された各論理識別子範囲を検索対象として指定するとともに各論理識別子範囲にそれぞれ対応付けられている仮想論理識別子範囲を含む検索要求を、該検索要求の転送先条件が成立する装置に転送する。
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】０１１１
【補正方法】変更
【補正の内容】
【０１１１】
ここで、１側最小論理識別子は「１０１０」（１０進数表記で「１０」）となる。すなわち、図５の１２０４に記載の論理識別子範囲は以前に２回ビットシフトされている。２回のビットシフトで取り出された（はじき出された）値はそれぞれ「１」と「０」である（図５の１２０２で「１」が取り出され、図５の１２０４で「０」が取り出されている）。このことから、ビットシフトされる前の１側の論理識別子範囲の値は「１０１＊」（「＊」は「０」または「１」）となる。従って、１側最小論理識別子は「１０１０」となる。
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】０１１２
【補正方法】変更
【補正の内容】
【０１１２】
また、０側最大論理識別子は「１００１」（１０進数表記で「９」）となる。すなわち、図５の１２０４に記載の論理識別子範囲は以前に２回ビットシフトされている。２回のビットシフトで取り出された（はじき出された）値はそれぞれ「１」と「０」である（図５の１２０２で「１」が取り出され、図５の１２０４で「０」が取り出されている）。このことから、ビットシフトされる前の０側の論理識別子範囲の値は「１００＊」（「＊」は「０」または「１」）となる。従って、０側最大論理識別子は「１００１」となる。
【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】０１２１
【補正方法】変更
【補正の内容】
【０１２１】
実施の形態２．
上記の実施の形態１はオーバレイネットワークに関係なく、ｄｅ  Ｂｒｕｉｊｎグラフを用いた理論上の範囲検索のアルゴリズムについての説明であったが、実際には、Ｃｈｏｒｄのハッシュ空間では各ノードは間隔を持って存在しているため（すなわち、例えば論理識別子空間１６（２の４乗）である場合に、論理識別子０〜１５の全てにノードが存在するわけではないため）、全ての論理識別子を持つノードが定義されたｄｅ  Ｂｒｕｉｊｎグラフは適用できない。そこで、この実施の形態２ではｄｅ  Ｂｒｕｉｊｎ上の論理識別子（ＩＤ）をＣｈｏｒｄハッシュ空間上の仮想ＩＤとし、一つのノードがある区間のＩＤを担当させている。
【手続補正２５】
【補正対象書類名】明細書
【補正対象項目名】０１２９
【補正方法】変更
【補正の内容】
【０１２９】
範囲分割手段８１５は、与えられた論理識別子範囲を、ルーティングテーブル８１２に格納されたピアの論理識別子を境界値として分割する。この場合、例えば、論理識別子範囲にピアの論理識別子が含まれる場合には、最小論理識別子とピアの論理識別子とから決定される論理識別子範囲と、ピアの論理識別子と最大論理識別子とから決定される論理識別子範囲とに分割される。このとき、シフト後最大論理識別子やシフト後最小論理識別子範囲も同時に分割する。
【手続補正２６】
【補正対象書類名】明細書
【補正対象項目名】０１４２
【補正方法】変更
【補正の内容】
【０１４２】
メッセージ転送手段８１３は、論理識別子範囲ＬｏｗＲａｎｇｅｓがＮｕｌｌであるか否か判定する（ステップＳ９０２）。論理識別子範囲ＬｏｗＲａｎｇｅｓがＮｕｌｌでない場合には（ステップＳ９０２のＮｏ）、メッセージ転送手段８１３は、ローカルデータ格納部８１１において、論理識別子範囲ＬｏｗＲａｎｇｅｓに含まれるシフト前の論理識別子をもとに、これと対応するデータ（論理識別子範囲ＬｏｗＲａｎｇｅに対応する検索式に合致するデータ）を検索する（ステップＳ９０３）。そして、検索した検索結果を検索実行者に渡す。
【手続補正２７】
【補正対象書類名】明細書
【補正対象項目名】０１５３
【補正方法】変更
【補正の内容】
【０１５３】
図１０に示す論理識別子範囲１４０１は、左ビットシフト範囲分割（図３に示した処理）により、［８，１１］である論理識別子範囲１４０２と［７，７］である論理識別子範囲１４０３に分割される。前者の論理識別子範囲［８，１１］のシフト前先頭ビットは１であり、後者の論理識別子範囲［７，７］のシフト前先頭ビットは０である。さらにピア１３１６にて左ビットシフト範囲分割をすることも可能であるが、後者の論理識別子範囲［７，７］をさらに左ビットシフト範囲分割すると、上記条件である論理識別子１１１０と論理識別子１１１１の下位から２ビット目に０（シフト前先頭ビット）であるものは存在しないので、さらなる左ビットシフト範囲分割は行わない。一方、前者の論理識別子範囲［８，１１］はさらにピア１３１６にて左ビットシフト分割を行うことが可能である。
【手続補正２８】
【補正対象書類名】明細書
【補正対象項目名】０１７５
【補正方法】変更
【補正の内容】
【０１７５】
実施の形態３．
上記の実施の形態２は、ｄｅ  Ｂｒｕｉｊｎ上の論理識別子（ＩＤ）をＣｈｏｒｄハッシュ空間上の仮想ＩＤとし、論理識別子範囲の先頭ビットの違いにより、新たな仮想ＩＤを生成しつつ論理識別子範囲を分割していた。しかし、この場合、大きなハッシュ空間（ＩＤ空間）を用いる場合には、ビット数が多くなり、管理する仮想ＩＤの数も多くなる。そこで、この実施の形態３では、複数の仮想ＩＤを集合として、すなわち仮想範囲（仮想論理識別子範囲）として管理することにより、ピアが扱うデータ量を削減する。
【手続補正２９】
【補正対象書類名】明細書
【補正対象項目名】０１９２
【補正方法】変更
【補正の内容】
【０１９２】
次いで、メッセージ転送手段２０１３は、未発見検索範囲集合ＮｏｔＦｏｕｎｄＲａｎｇｅｓ内の未発見検索範囲ＮｏｔＦｏｕｎｄＲａｎｇｅを、ピアｍとピアｓの論理識別子の範囲（ｍ、ｓ］とともに範囲分割手段Ａ２０１６に渡し、各未発見検索範囲ＮｏｔＦｏｕｎｄＲａｎｇｅに対して、ステップＳ１６０６の処理を繰り返し実行させる（ステップＳ１６０５）。
【手続補正３０】
【補正対象書類名】明細書
【補正対象項目名】０１９３
【補正方法】変更
【補正の内容】
【０１９３】
範囲分割手段Ａ２０１６は、未発見検索範囲ＮｏｔＦｏｕｎｄＲａｎｇｅを、ピアｍとピアｓの論理識別子の範囲（ｍ，ｓ］で、仮想範囲をもとに範囲内検索範囲ｉｎＲａｎｇｅと範囲外検索範囲ｏｕｔＲａｎｇｅに分割する（ステップＳ１６０６）。そして、範囲分割手段Ａ２０１６は、範囲内検索範囲ｉｎＲａｎｇｅと範囲外検索範囲ｏｕｔＲａｎｇｅをメッセージ転送手段２０１３に返す。
【手続補正３１】
【補正対象書類名】明細書
【補正対象項目名】０２００
【補正方法】変更
【補正の内容】
【０２００】
次に、範囲分割手段Ｂ２０１７が実行する処理（ステップＳ１６０３）について説明する。図１３は、この実施の形態３の範囲分割手段Ｂが実行する処理を示すフローチャートである。なお、検索範囲ｑＲａｎｇｅは、仮想検索範囲ｉＲａｎｇｅと論理識別子範囲ｋＲａｎｇｅとシフト回数ｃとから構成されている。
【手続補正３２】
【補正対象書類名】明細書
【補正対象項目名】０２０３
【補正方法】変更
【補正の内容】
【０２０３】
範囲分割手段Ｂ２０１７は、仮想範囲ｅａｃｈＫｅｙＲａｎｇｅの上限値の先頭から（全ビット長−シフト回数ｃ）ビットを上位に、論理識別子範囲ｋＲａｎｇｅの上限値を（全ビット長−シフト回数ｃ）回右ビットシフトしたビット列を下位に持つビット列を新たな仮想論理識別子範囲の上限値（最大仮想論理識別子）ＮｅｗＩｍｇＲａｎｇｅＭａｘとする（ステップＳ１８０４）。
【手続補正３３】
【補正対象書類名】明細書
【補正対象項目名】０２０４
【補正方法】変更
【補正の内容】
【０２０４】
また、範囲分割手段Ｂ２０１７は、仮想範囲ｅａｃｈＫｅｙＲａｎｇｅの下限値の先頭から（全ビット長−シフト回数ｃ）ビットを上位に、論理識別子範囲ｋＲａｎｇｅの上限値を（全ビット長−シフト回数ｃ）回右ビットシフトしたビット列を下位に持つビット列を新たな仮想論理識別子範囲の下限値（最小仮想論理識別子）ＮｅｗＩｍｇＲａｎｇｅＭｉｎとする（ステップＳ１８０５）。
【手続補正３４】
【補正対象書類名】明細書
【補正対象項目名】０２０８
【補正方法】変更
【補正の内容】
【０２０８】
次に、範囲分割手段Ａ２０１６が実行する処理（ステップＳ１６０６）について説明する。図１４は、この実施の形態３の範囲分割手段Ａが実行する処理を示すフローチャートである。なお、検索範囲ｑＲａｎｇｅは、仮想検索範囲ｉＲａｎｇｅと論理識別子範囲ｋＲａｎｇｅとシフト回数ｃとから構成されている。
【手続補正３５】
【補正対象書類名】明細書
【補正対象項目名】０２１７
【補正方法】変更
【補正の内容】
【０２１７】
まず、検索範囲左ビットシフト手段２０１５は、シフト回数ｃを増やす（ステップＳ２１０１）。次いで、検索範囲左ビットシフト手段２０１５は、仮想範囲ｉＲａｎｇｅの上限値ｉＭａｘ（最大仮想論理識別子）に、それを左ビットシフトし下位ビットに、論理識別子範囲ｋＲａｎｇｅの上限値ｋＭａｘ（最大論理識別子）の先頭からｃビット目を加えたビット列を与える（ステップＳ２１０２）。次に、検索範囲左ビットシフト手段２０１５は、仮想範囲ｉＲａｎｇｅの下限値ｉＭｉｎ（最小仮想論理識別子）に、それを左ビットシフトし下位ビットに、論理識別子範囲ｋＲａｎｇｅの下限値ｋＭｉｎ（最小論理識別子）の先頭からｃビット目を加えたビット列を与える（ステップＳ２１０３）。そして、処理後の値をメッセージ転送手段２０１３に返す。
【手続補正３６】
【補正対象書類名】明細書
【補正対象項目名】０２２５
【補正方法】変更
【補正の内容】
【０２２５】
次に、ピア１９１５は、検索範囲１９２３、検索範囲１９２４を含む検索範囲集合を探すピア１９１５は、ピア１９１５の論理識別子１０より大きくサクセサ（ピアｓ）の論理識別子１３以下の範囲（１０，１３］で、論理識別子範囲をもとに範囲分割を行う（ステップＳ１６０３）。検索範囲１９２３の論理識別子範囲は［８，１１］であるため、範囲内検索範囲集合としてその論理識別子範囲に［１１，１１］を含む検索範囲１９２５が格納され、範囲外検索範囲集合としてその論理識別子範囲に［８，１０］を含む検索範囲１９２６と論理識別子範囲が［７，７］である検索範囲１９２４が格納される。検索範囲１９２５は発見検索範囲集合に格納され、検索範囲１９２６および検索範囲１９２４は未発見検索範囲集合に格納される（ステップＳ１６０４）。
【手続補正３７】
【補正対象書類名】図面
【補正対象項目名】図１５
【補正方法】変更
【補正の内容】
【図１５】
2008262507.tif 000001
【手続補正３８】
【補正対象書類名】図面
【補正対象項目名】図２０
【補正方法】変更
【補正の内容】
【図２０】
2008262507.tif 000002