【手続補正書】
【提出日】令和3年3月9日(2021.3.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
シャード・データベースのシャード・テーブルにレコードを記憶するためのコンピュータ実装方法であって、前記シャード・データベースは、複数のデータベース・シャードを含み、前記データベース・シャードのそれぞれは、前記シャード・テーブルのレコードの部分集合を記憶するように構成され、特定のシャーディング・キーと関連するレコードが当該データベース・シャードに記憶されていることがあり得るかどうかに関する指示を提供するように構成されたそれぞれのブルーム・フィルタと関連し、前記コンピュータ実装方法が、
記憶される前記レコードのためのシャーディング・キーであって、前記レコードの１つまたは複数のフィールドに基づくシャーディング・キーを、取得することと、
複数の前記それぞれのブルーム・フィルタのそれぞれのために、当該ブルーム・フィルタによって用いられる１つまたは複数のハッシュ関数を前記シャーディング・キーに適用することによって、当該ブルーム・フィルタと共に用いるための前記シャーディング・キーのそれぞれの表現を生成することと、
前記複数のブルーム・フィルタのそれぞれの現在値と当該ブルーム・フィルタと共に用いるための前記シャーディング・キーの前記それぞれの表現との間のハミング距離を計算することと、
前記計算されたハミング距離に基づき、データベース・シャードを選択することと、
前記レコードを前記選択されたデータベース・シャードに記憶することと
を含む、コンピュータ実装方法。
【請求項２】
前記それぞれのブルーム・フィルタのそれぞれが、同じビット数と同じハッシュ関数とを用いる、請求項１に記載のコンピュータ実装方法。
【請求項３】
前記それぞれのブルーム・フィルタのそれぞれが、カウンティング・フィルタである、請求項１に記載のコンピュータ実装方法。
【請求項４】
データベース・シャードを選択することが、前記計算されたハミング距離が前記計算されたハミング距離の中の最小値であるそれぞれのブルーム・フィルタと関連するデータベース・シャードを選択することを含む、請求項１に記載のコンピュータ実装方法。
【請求項５】
前記計算されたハミング距離が前記計算されたハミング距離の中の最小値であるそれぞれのブルーム・フィルタと関連するデータベース・シャードを選択することが、前記計算されたハミング距離が最小値であるそれぞれのブルーム・フィルタと関連するデータベース・シャードの中から前記データベース・シャードをランダムに選択することを含む、請求項４に記載のコンピュータ実装方法。
【請求項６】
前記シャード・データベースが、それぞれのデータベース・シャードが新たなレコードを記憶するために利用可能であるかまたは利用不可能であるかに関する指示をさらに含み、前記シャーディング・キーのそれぞれの表現が生成される前記複数のブルーム・フィルタが、使用不可能であると示されているデータベース・シャードと関連するどのブルーム・フィルタも含まない、請求項１に記載のコンピュータ実装方法。
【請求項７】
前記シャーディング・キーの表現がそのために生成される前記複数のブルーム・フィルタが、使用可能であると指示されている全部のデータベース・シャードと関連する前記それぞれのブルーム・フィルタを含む、請求項６に記載のコンピュータ実装方法。
【請求項８】
前記シャード・データベースが、前記データベース・シャードのそれぞれの中に挿入されたレコードのそれぞれの個数をカウントするためのそれぞれの挿入カウンタをさらに含み、前記コンピュータ実装方法が、
前記選択されたデータベース・シャードのための前記挿入カウンタをインクリメントすることをさらに含む、請求項１に記載のコンピュータ実装方法。
【請求項９】
前記選択されたデータベース・シャードの中に挿入されたレコードの前記個数が所定の閾値を超えるかどうかを判断することと、
前記選択されたデータベース・シャードの中に挿入されたレコードの前記個数が所定の閾値を超えるかどうかを判断することに応答して、前記選択されたデータベース・シャードに、新たなレコードを記憶するためには利用不可能であるとのマークを付することと
をさらに含む、請求項８に記載のコンピュータ実装方法。
【請求項１０】
新たなデータベース・シャードと、関連するブルーム・フィルタとを前記シャード・データベースに追加することをさらに含む、請求項１に記載のコンピュータ実装方法。
【請求項１１】
シャード・データベースのシャード・テーブルからレコードを検索するためのコンピュータ実装方法であって、前記シャード・データベースは、複数のデータベース・シャードを含み、前記データベース・シャードのそれぞれは、前記シャード・テーブルのレコードの部分集合を記憶するように構成され、特定のシャーディング・キーと関連するレコードが当該データベース・シャードに記憶されていることがあり得るかどうかに関する指示を提供するように構成されたそれぞれのブルーム・フィルタと関連し、前記コンピュータ実装方法が、
検索される前記レコードのためのシャーディング・キーであって、前記レコードの１つまたは複数のフィールドに基づくシャーディング・キーを、取得することと、
前記データベース・シャードのそれぞれと関連する前記それぞれのブルーム・フィルタのそれぞれのために、当該ブルーム・フィルタによって用いられる１つまたは複数のハッシュ関数を前記シャーディング・キーに適用することによって、当該ブルーム・フィルタと共に用いるための前記シャーディング・キーのそれぞれの表現を生成することと、
前記それぞれのブルーム・フィルタのうちのどれが、前記シャーディング・キーのそれらのそれぞれの表現とマッチするかを識別することと、
前記レコードを見つけるために、前記識別されたブルーム・フィルタと関連する前記データベース・シャードをサーチすることと、
前記レコードを提供することと
を含む、コンピュータ実装方法。
【請求項１２】
前記それぞれのブルーム・フィルタのそれぞれが、同じビット数と同じハッシュ関数とを用いる、請求項１１に記載のコンピュータ実装方法。
【請求項１３】
シャード・データベースを記憶するためのシステムであって、前記シャード・データベースは、複数のデータベース・シャードを含み、前記データベース・シャードのそれぞれは、シャード・テーブルのレコードの部分集合を記憶するように構成され、特定のシャーディング・キーと関連するレコードが当該データベース・シャードに記憶されていることがあり得るかどうかに関する指示を提供するように構成されたそれぞれのブルーム・フィルタと関連し、前記システムが、
それぞれが、前記複数のデータベース・シャードのうちの１つまたは複数を記憶するように構成されている、複数の計算システムと、
コントローラであって、
検索されるレコードのためのシャーディング・キーであって、前記レコードの１つまたは複数のフィールドに基づくシャーディング・キーを、取得し、
前記データベース・シャードのそれぞれと関連する前記それぞれのブルーム・フィルタのそれぞれのために、当該ブルーム・フィルタによって用いられる１つまたは複数のハッシュ関数を前記シャーディング・キーに適用することにより、当該ブルーム・フィルタと共に用いるための前記シャーディング・キーのそれぞれの表現を生成し、
前記それぞれのブルーム・フィルタのうちのどれが、前記シャーディング・キーのそれらのそれぞれの表現とマッチするかを識別し、
前記レコードを見つけるため、前記識別されたブルーム・フィルタと関連する前記データベース・シャードをサーチし、
前記レコードを提供することにより、
前記シャード・データベースの前記シャード・テーブルから前記レコードを検索するように構成されている、前記コントローラと
を備える、システム。
【請求項１４】
前記それぞれのブルーム・フィルタのそれぞれが、同じビット数と同じハッシュ関数とを用いる、請求項１３に記載のシステム。
【請求項１５】
前記それぞれのブルーム・フィルタのそれぞれが、カウンティング・フィルタである、請求項１３に記載のシステム。
【請求項１６】
前記コントローラが、さらに、
記憶されるレコードのためのシャーディング・キーであって、前記レコードの１つまたは複数のフィールドに基づくシャーディング・キーを、取得し、
複数の前記それぞれのブルーム・フィルタのそれぞれのために、当該ブルーム・フィルタによって用いられる１つまたは複数のハッシュ関数を前記シャーディング・キーに適用することにより、当該ブルーム・フィルタと共に用いるための前記シャーディング・キーのそれぞれの表現を生成し、
前記複数のブルーム・フィルタのそれぞれの現在値と当該ブルーム・フィルタと共に用いるための前記シャーディング・キーの前記それぞれの表現との間のハミング距離を計算し、
前記計算されたハミング距離に基づき、データベース・シャードを選択し、
前記レコードを前記選択されたデータベース・シャードに記憶することによって、
前記シャード・データベースの前記シャード・テーブルに前記レコードを記憶するように構成されている、請求項１３に記載のシステム。
【請求項１７】
データベース・シャードを選択することが、前記計算されたハミング距離が前記計算されたハミング距離の中の最小値であるそれぞれのブルーム・フィルタと関連するデータベース・シャードを選択することを含む、請求項１６に記載のシステム。
【請求項１８】
前記シャード・データベースが、それぞれのデータベース・シャードが新たなレコードを記憶するために利用可能であるかまたは利用不可能であるかに関する指示をさらに含み、前記シャーディング・キーのそれぞれの表現が生成される前記複数のブルーム・フィルタが、前記レコードを記憶するとき、使用不可能であると示されているデータベース・シャードと関連するどのブルーム・フィルタも含まない、請求項１６に記載のシステム。
【請求項１９】
前記シャード・データベースが、前記データベース・シャードのそれぞれに挿入されたレコードのそれぞれの個数をカウントするためのそれぞれの挿入カウンタをさらに含み、前記コントローラが、さらに、前記レコードが記憶されると前記選択されたデータベース・シャードのための前記挿入カウンタをインクリメントするように構成されている、請求項１６に記載のシステム。
【請求項２０】
前記コントローラが、さらに、
前記選択されたデータベース・シャードに挿入されたレコードの前記個数が所定の閾値を超えるかどうかを判断し、
前記選択されたデータベース・シャードに挿入されたレコードの前記個数が前記所定の閾値を実際に超えるとの判断に応答して、前記選択されたデータベース・シャードに、新たなレコードを記憶するために利用不可能であるとのマークを付す
ように構成されている、請求項１９に記載のシステム。
【請求項２１】
前記コントローラが、さらに、
前記シャード・データベースに、新たなデータベース・シャードと、関連するブルーム・フィルタとを追加するように構成されている、請求項１６に記載のシステム。
【請求項２２】
前記シャード・データベースが、前記データベース・シャードのそれぞれから削除されたレコードのそれぞれの個数をカウントするそれぞれの削除カウンタをさらに含む、請求項１６に記載のシステム。
【請求項２３】
前記コントローラが、さらに、
特定のデータベース・シャードから削除されたレコードの前記個数が当該データベース・シャードのためのそれぞれの所定の閾値を超えるかどうかを判断し、前記特定のデータベース・シャードから削除されたレコードの前記個数が当該データベース・シャードのための前記それぞれの所定の閾値を超えるとの判断に応答して、当該データベース・シャードに現に記憶されているレコードに基づき、当該データベース・シャードのための前記ブルーム・フィルタを再構築するように構成されている、請求項２２に記載のシステム。
【請求項２４】
コンピュータ・プログラムであって、請求項１ないし１２のいずれか１項に記載の方法の各ステップをコンピュータに実行させるための、コンピュータ・プログラム。
【請求項２５】
請求項２４に記載のコンピュータ・プログラムを記録した、コンピュータ可読記録媒体。
【請求項２６】
シャード・データベースのシャード・テーブルにレコードを記憶するためのシステムであって、前記シャード・データベースは、複数のデータベース・シャードを含み、前記データベース・シャードのそれぞれは、前記シャード・テーブルのレコードの部分集合を記憶するように構成され、特定のシャーディング・キーと関連するレコードが当該データベース・シャードに記憶されていることがあり得るかどうかに関する指示を提供するように構成されたそれぞれのブルーム・フィルタと関連し、前記システムが、
記憶される前記レコードのためのシャーディング・キーであって、前記レコードの１つまたは複数のフィールドに基づくシャーディング・キーを、取得し、
複数の前記それぞれのブルーム・フィルタのそれぞれのために、当該ブルーム・フィルタによって用いられる１つまたは複数のハッシュ関数を前記シャーディング・キーに適用することによって、当該ブルーム・フィルタと共に用いるための前記シャーディング・キーのそれぞれの表現を生成し、
前記複数のブルーム・フィルタのそれぞれの現在値と当該ブルーム・フィルタと共に用いるための前記シャーディング・キーの前記それぞれの表現との間のハミング距離を計算し、
前記計算されたハミング距離に基づき、データベース・シャードを選択し、および
前記レコードを前記選択されたデータベース・シャードに記憶するように、構成可能である、システム。
【請求項２７】
シャード・データベースのシャード・テーブルからレコードを検索するためのシステムであって、前記シャード・データベースは、複数のデータベース・シャードを含み、前記データベース・シャードのそれぞれは、前記シャード・テーブルのレコードの部分集合を記憶するように構成され、特定のシャーディング・キーと関連するレコードが当該データベース・シャードに記憶されていることがあり得るかどうかに関する指示を提供するように構成されたそれぞれのブルーム・フィルタと関連し、前記システムが、
検索される前記レコードのためのシャーディング・キーであって、前記レコードの１つまたは複数のフィールドに基づくシャーディング・キーを、取得し、
前記データベース・シャードのそれぞれと関連する前記それぞれのブルーム・フィルタのそれぞれのために、当該ブルーム・フィルタによって用いられる１つまたは複数のハッシュ関数を前記シャーディング・キーに適用することによって、当該ブルーム・フィルタと共に用いるための前記シャーディング・キーのそれぞれの表現を生成し、
前記それぞれのブルーム・フィルタのうちのどれが、前記シャーディング・キーのそれらのそれぞれの表現とマッチするかを識別し、
前記レコードを見つけるために、前記識別されたブルーム・フィルタと関連する前記データベース・シャードをサーチし、
前記レコードを提供するように構成可能である、システム。