フラクショナルカスケーディング

コンピュータサイエンスにおいて、分数カスケーディングとは、一連の関連データ構造内で同じ値を探すバイナリ検索のシーケンスを高速化する手法です。シーケンス内の最初のバイナリ検索には、バイナリ検索の標準どおり対数的な時間がかかりますが、シーケンス内の後続の検索はより高速になります。1986年にChazelleとGuibasの 2 つの論文 (Chazelle & Guibas 1986a、Chazelle & Guibas 1986b) で導入された分数カスケーディングのオリジナル バージョンは、Lueker (1978) と Willard (1978) の範囲検索データ構造に由来するカスケーディングの考え方と、Chazelle (1983) に由来する分数サンプリングの考え方を組み合わせたものです。その後の著者らは、一連の個別の挿入および削除イベントによってデータが変更されてもデータ構造を維持できる、より複雑な形式の分数カスケーディングを導入しました。

分数カスケーディングの簡単な例として、次の問題を考えてみましょう。入力として、すべてのリストの合計の長さが であるような数値の順序付きリストのコレクションが与えられ、各リストでクエリ値のバイナリ検索を実行できるようにそれらを処理する必要があります。たとえば、およびの場合、 ${\displaystyle k}$${\displaystyle L_{i}}$${\displaystyle \sum _{i}|L_{i}|}$${\displaystyle n}$${\displaystyle q}$${\displaystyle k}$${\displaystyle k=4}$${\displaystyle n=17}$

${\displaystyle L_{1}}$= 24、64、65、80、93

${\displaystyle L_{2}}$= 23、25、26

${\displaystyle L_{3}}$= 13、44、62、66

${\displaystyle L_{4}}$= 11、35、46、79、81

この検索問題に対する最も簡単な解決方法は、各リストを別々に保存することです。その場合、必要なスペースは ですが、クエリの実行時間は です。これは、各リストで別々のバイナリ検索を実行する必要があるためです。この構造をクエリする場合の最悪のケースは、各リストのサイズが等しい場合です。そのため、クエリに含まれる各バイナリ検索には時間がかかります。 ${\displaystyle O(n)}$${\displaystyle O{\bigl (}k\log(n/k){\bigr )}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle n/k}$${\displaystyle k}$${\displaystyle O{\bigl (}\log(n/k){\bigr )}}$

2 つ目の解決法では、より多くのスペースを消費しますが、クエリを高速化できます。すべてのリストを 1 つの大きなリスト にマージし、各小さなリスト で検索した結果のリストを各項目に関連付けます。このマージされたリストの要素を と記述すると、 は数値で、、、、は、元の入力リストのそれぞれと同じ大きさの次の要素の位置 (最初の数値の位置は 0) です(そのような要素が存在しない場合は、リストの末尾の後の位置)。 ${\displaystyle k}$${\displaystyle L}$${\displaystyle x}$${\displaystyle L}$${\displaystyle x}$${\displaystyle L_{i}}$${\displaystyle x[a,b,c,d]}$${\displaystyle x}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle d}$${\displaystyle x}$

${\displaystyle L}$= 11 [0,0,0,0]、13 [0,0,0,1]、23 [0,0,1,1]、24 [0,1,1,1]、25 [1,1] 、1,1]、26 [1,2,1,1]、

35 [1,3,1,1]、44 [1,3,1,2]、46 [1,3,2,2]、62 [1,3,2,3]、64 [1,3, 3,3]、65 [2,3,3,3]、

66 [3,3,3,3]、79 [3,3,4,3]、80 [3,3,4,4]、81 [4,3,4,4]、93 [4,3, 4,5]

この統合ソリューションでは、 の時間内にクエリを実行できます。つまり、 で を検索し、この検索で​​見つかった項目に格納されている結果を報告します。たとえば、 の場合、でを検索すると項目 62[1,3,2,3] が見つかり、そこから結果、 (の末尾を過ぎていることを示すフラグ値)、、およびが返されます。ただし、このソリューションでは、空間計算量の面で大きなペナルティが発生します。の各項目に検索結果 のリストを格納する必要があるため、空間が使用されます。${\displaystyle O(k+\log n)}$${\displaystyle q}$${\displaystyle L}$${\displaystyle x}$${\displaystyle q=50}$${\displaystyle q}$${\displaystyle L}$${\displaystyle L_{1}[1]=64}$${\displaystyle L_{2}[3]}$${\displaystyle q}$${\displaystyle L_{2}}$${\displaystyle L_{3}[2]=62}$${\displaystyle L_{4}[3]=79}$${\displaystyle O(kn)}$${\displaystyle n}$${\displaystyle L}$${\displaystyle k}$

分数カスケーディングにより、同じ検索問題を、時間と空間の境界が両方の長所、つまりクエリ時間と空間を満たすように解決できます。分数カスケーディング ソリューションは、新しいリストのシーケンス を保存することです。このシーケンスの最終的なリスト はに等しくなります。以前の各リストは、 の2 つおきの項目とマージすることによって形成されます。このマージされたリストの各項目を使用して、 でを検索した結果の位置と、でを検索した結果の位置の 2 つの数値を保存します。上記のデータの場合、次のリストが作成されます。 ${\displaystyle O(k+\log n)}$${\displaystyle O(n)}$${\displaystyle M_{i}}$${\displaystyle M_{k}}$${\displaystyle L_{k}}$${\displaystyle M_{i}}$${\displaystyle L_{i}}$${\displaystyle M_{i+1}}$${\displaystyle x}$${\displaystyle x}$${\displaystyle L_{i}}$${\displaystyle x}$${\displaystyle M_{i+1}}$

${\displaystyle M_{1}}$= 24 [0, 1]、25 [1, 1]、35 [1, 3]、64 [1, 5]、65 [2, 5]、79 [3, 5]、80 [3, 6]、93 [4、6]

${\displaystyle M_{2}}$= 23 [0, 1]、25 [1, 1]、26 [2, 1]、35 [3, 1]、62 [3, 3]、79 [3, 5]

${\displaystyle M_{3}}$= 13 [0, 1]、35 [1, 1]、44 [1, 2]、62 [2, 3]、66 [3, 3]、79 [4, 3]

${\displaystyle M_{4}}$= 11 [0, 0]、35 [1, 0]、46 [2, 0]、79 [3, 0]、81 [4, 0]

この構造で のクエリを実行するとします。まず、で の標準的なバイナリ検索を実行し、値64 [1,5] を見つけます。 64[1,5] の「1」は、での検索でが返されることを示しています。 64 [1,5]の「5」は、のおおよその位置が5 の位置であることを示しています。より正確には、でのバイナリ検索では、位置 5 の値 79[3,5] か、1 つ前の 62[3,3] のいずれかが返されます。 を62 と比較して、それが小さいことを観察することにより、 での正しい検索結果は 62[3,3] であると判定します。 62[3,3] の最初の「3」は、での検索でが返されることを示しています。これは、リスト の末尾を超えていることを示すフラグ値です。 62[3,3] の 2 番目の「3」は、のおおよその位置が位置 3 であることを示しています。より正確には、をバイナリ検索すると、位置 3 の値 62[2,3] か、1 つ前の値 44[1,2] が返されます。 を小さい方の値 44 と比較すると、 での正しい検索結果は62[2,3] であることがわかります。 62[2,3] の「2」は、の検索でが返されることを示し、 62[2,3] の「3」は、で検索した結果が位置 3 の 79[3,0] か、位置 2 の 46[2,0] であることを示しています。 46 と比較すると、正しい結果は 79[3,0] であり、での検索結果はであることがわかります。このように、単一のリストでバイナリ検索を実行し、その後に各後続のリストで単一の比較を実行することで 、4 つのリストのそれぞれで を見つけました。${\displaystyle q=50}$${\displaystyle q}$${\displaystyle M_{1}}$${\displaystyle q}$${\displaystyle L_{1}}$${\displaystyle L_{1}[1]=64}$${\displaystyle q}$${\displaystyle M_{2}}$${\displaystyle q}$${\displaystyle M_{2}}$${\displaystyle q}$${\displaystyle M_{2}}$${\displaystyle q}$${\displaystyle L_{2}}$${\displaystyle L_{2}[3]}$${\displaystyle q}$${\displaystyle L_{2}}$${\displaystyle q}$${\displaystyle M_{3}}$${\displaystyle q}$${\displaystyle M_{3}}$${\displaystyle q}$${\displaystyle M_{3}}$${\displaystyle q}$${\displaystyle L_{3}}$${\displaystyle L_{3}[2]=62}$${\displaystyle q}$${\displaystyle M_{4}}$${\displaystyle q}$${\displaystyle q}$${\displaystyle L_{4}}$${\displaystyle L_{4}[3]=79}$${\displaystyle q}$${\displaystyle M_{1}}$

より一般的には、このタイプのデータ構造では、でののバイナリ検索を実行し、その結果の値からでの の位置を決定することによってクエリを実行します。次に、各 について、でのの既知の位置を使用して、 でのその位置を見つけます。 でのの位置に関連付けられた値は、でのバイナリ検索の正しい結果であるか、その正しい結果から 1 ステップ離れた での位置を指します。したがって、から へのステップには1 回の比較のみが必要です。したがって、クエリの合計時間は次のとおりです。${\displaystyle q}$${\displaystyle M_{1}}$${\displaystyle q}$${\displaystyle L_{1}}$${\displaystyle i>1}$${\displaystyle q}$${\displaystyle M_{i}}$${\displaystyle M_{i+1}}$${\displaystyle q}$${\displaystyle M_{i}}$${\displaystyle M_{i+1}}$${\displaystyle q}$${\displaystyle M_{i+1}}$${\displaystyle i}$${\displaystyle i+1}$${\displaystyle O(k+\log n)}$

この例では、分数カスケード リストには合計 25 個の要素があり、元の入力の 2 倍未満です。一般に、このデータ構造の のサイズは最大で で あり、帰納法で簡単に証明できます。したがって、データ構造の合計サイズは最大で であり 、同じ入力リストからの合計サイズへの寄与を互いに 再グループ化することでわかります。${\displaystyle M_{i}}$$${\displaystyle |L_{i}|+{\frac {1}{2}}|L_{i+1}|+{\frac {1}{4}}|L_{i+2}|+\cdots +{\frac {1}{2^{j}}}|L_{i+j}|+\cdots ,}$$$${\displaystyle \sum |M_{i}|=\sum |L_{i}|\left(1+{\frac {1}{2}}+{\frac {1}{4}}+\cdots \right)\leq 2n=O(n),}$$${\displaystyle L_{i}}$

一般に、フラクショナル カスケードは、各頂点に順序付きリストのラベルが付けられた有向グラフであるカタログ グラフから始まります。このデータ構造のクエリは、グラフ内のパスとクエリ値qで構成されます。データ構造は、パスの頂点に関連付けられた順序付きリストのそれぞれでqの位置を決定する必要があります。上記の単純な例では、カタログ グラフ自体が 4 つのノードのみを持つパスです。パスの前の部分の検索で見つかった結果に応じて、パス内の後の頂点をクエリの一部として動的に決定することができます。

この種のクエリを処理するために、各頂点が最大d 個の入力エッジと最大d 個の出力エッジを持ち、定数d が一定であるグラフの場合、各頂点に関連付けられたリストは、頂点の各出力隣接ノードからの項目の一部によって拡張されます。この部分は、すべてのリストが拡張される合計量が入力サイズに対して線形になるように、 1/ dより小さくなるように選択する必要があります。各拡張リストの各項目には、同じ頂点に格納されている拡張されていないリストと、各出力隣接リストにおけるその項目の位置が格納されます。上記の単純な例では、d = 1 であり、各リストに隣接項目の 1/2 の部分が追加されました。

このデータ構造のクエリは、クエリ パスの最初の頂点に関連付けられた拡張リストでの標準的なバイナリ検索と、パスの各連続頂点でのより単純な検索で構成されます。各隣接項目からリストを拡張するために 1/ r の割合の項目が使用される場合、各連続クエリ結果は、前のパス頂点からのクエリ結果に格納された位置から最大rステップ以内で見つかる可能性があり、したがって完全なバイナリ検索を実行することなく定数時間で見つかる可能性があります。

動的フラクショナルカスケーディングでは、カタロググラフの各ノードに格納されているリストは、リスト項目が挿入および削除される一連の更新によって動的に変更される可能性があります。これにより、データ構造にいくつかの問題が生じます。

まず、カタログ グラフのノードでアイテムが挿入または削除されると、そのアイテムはそのノードに関連付けられた拡張リスト内に配置され、カタログ グラフの他のノードに変更が伝播する可能性があります。拡張リストを配列に格納するのではなく、バイナリ検索ツリーとして格納する必要があります。これにより、拡張リストのバイナリ検索を可能にしながら、これらの変更を効率的に処理できます。

2 番目に、挿入または削除によって、カタログ グラフの隣接ノードに渡されるノードに関連付けられたリストのサブセットが変更されることがあります。動的設定では、何らかのdについて、このサブセットをリストのd番目の位置ごとに項目として選択することはもはや実現可能ではありません。これは、このサブセットが更新のたびに大幅に変更されるためです。むしろ、B ツリーに密接に関連する手法により、1/ dより小さいことが保証されるデータの一部を選択でき、選択された項目は完全なリスト内で一定数の位置だけ離れていることが保証され、ノードに関連付けられた拡張リストへの挿入または削除によって、1/ d未満の操作の一部で変更が他のノードに伝播されます。このようにして、ノード間のデータの分散は、クエリ アルゴリズムが高速であるために必要な特性を満たしながら、データの挿入または削除あたりのバイナリ検索ツリー操作の平均数が一定であることを保証します。

3 番目で最も重要な点は、静的な分数カスケード データ構造では、カタログ グラフの各ノードの拡張リストの各要素xについて、そのノードからの入力項目と隣接ノードに格納されている拡張リストの間でxを検索したときに取得される結果のインデックスが維持されることです。ただし、この情報は動的な設定で維持するにはコストがかかりすぎます。単一の値xを挿入または削除すると、他の無制限の数の値に格納されているインデックスが変更される可能性があります。代わりに、分数カスケードの動的バージョンでは、各ノードに対して複数のデータ構造が維持されます。

• ノードの拡張リスト内の項目を小さな整数にマッピングします。これにより、拡張リスト内の位置の順序は整数の比較順序と同等になり、これらの整数からリスト項目への逆マップが行われます。Dietz (1982) の順序維持技術により、この番号付けを効率的に維持できます。
• ノードの入力リストに関連付けられた数値を検索する、ファン・エムデ・ボアズ木などの整数検索データ構造。この構造と、項目から整数へのマッピングにより、拡張リストの各要素xについて、入力リストでx を検索したときに見つかる項目を効率的に見つけることができます。
• カタログ グラフ内の各隣接ノードに対して、隣接ノードから伝播されたデータのサブセットに関連付けられた数値を検索する同様の整数検索データ構造。この構造と、項目から整数へのマッピングにより、拡張リストの各要素xについて、隣接ノードに関連付けられた拡張リスト内のxの位置から一定数のステップ以内の位置を効率的に見つけることができます。

これらのデータ構造により、挿入または削除ごとに O(log n )の時間で動的分数カスケーディングを実行でき 、カタログ グラフ内の長さkのパスをたどるkバイナリ検索のシーケンスをO(log n  +  k  log log  n )の時間で実行できます 。

分数カスケーディングの典型的な応用には、計算幾何学における範囲検索データ構造が含まれます。たとえば、半平面範囲レポートの問題を考えてみましょう。つまり、 n個のポイントの固定セットをクエリ半平面と交差させ、交差点内のすべてのポイントをリストします。問題は、このタイプのクエリが交差点のサイズhに関して効率的に回答されるようにポイントを構造化することです。この目的に使用できる 1 つの構造は、入力ポイント セットの凸層です。これは、ポイント セットの凸包と、残りのポイントの再帰的に構築された凸層で構成される、ネストされた凸多角形のファミリです。単一の層内で、クエリ半平面内のポイントは、凸多角形のエッジ傾斜のソートされたシーケンス内で半平面境界線の傾斜のバイナリ検索を実行することによって見つけることができます。これにより、クエリ半平面内にあり、境界から最も遠いポリゴンの頂点が見つかり、次にポリゴンのエッジに沿って順番に検索して、クエリ半平面内の他のすべての頂点が見つかります。半平面範囲報告問題全体は、この検索手順を最も外側のレイヤーから開始して内側に進み、クエリ半空間から分離したレイヤーに到達するまで繰り返すことによって解決できます。分数カスケーディングにより、各レイヤーのポリゴンエッジ傾斜のシーケンス間の連続バイナリ検索が高速化され、この問題のデータ構造がスペース O( n ) とクエリ時間 O(log  n  +  h ) で実現されます。データ構造は、Chazelle (1985) のアルゴリズムによって時間 O( n  log  n ) で構築できます。この例のように、このアプリケーションではリストの線形シーケンス (凸レイヤーのネストされたシーケンス) でのバイナリ検索が行われるため、カタログ グラフは単なるパスになります。

幾何学的データ構造における分数カスケーディングのもう 1 つの応用は、単調な細分、つまり、垂直線が最大 2 点で任意の多角形と交差するような平面の多角形への分割における点の位置に関するものです。Edelsbrunner、Guibas、および Stolfi (1986) が示したように、この問題は、細分を横切って左から右に伸びる多角形パスのシーケンスを見つけ、クエリ ポイントより上にあるこれらのパスのうち最も低いパスをバイナリ検索することで解決できます。クエリ ポイントがパスの 1 つの上にあるか下にあるかをテストすること自体は、バイナリ検索問題として解決できます。つまり、パスの頂点の x 座標の中から点の x 座標を検索して、どのパス エッジがクエリ ポイントより上または下にあるかを判断します。したがって、各点の位置クエリは、パス間のバイナリ検索の外側のレイヤーとして解決でき、その各ステップ自体が頂点の x 座標間でバイナリ検索を実行します。分数カスケーディングを使用すると、内部バイナリ検索の時間を短縮し、  O( n )のスペースを持つデータ構造を使用してクエリあたりの合計時間を O(logn)に短縮できます。このアプリケーションでは、カタログ グラフは、外部バイナリ検索の可能な検索シーケンスを表すツリーです。

計算幾何学を超えて、Lakshman & Stiliadis (1998) と Buddhikot、Suri & Waldvogel (1999) は、インターネット ルーターの高速パケット フィルタリング用のデータ構造の設計に分数カスケーディングを適用しています。Gao ら (2004) は、センサー ネットワークでのデータ配布と取得のモデルとして分数カスケーディングを使用しています。