論文翻訳: Lower Bounds for External Memory Dictionaries

2024年11月6日 2003年の論文 #BTree #BεTree

Gerth Stølting Brodal∗,†

Abstract Rolf Fagerberg∗

Abstract

Abstract
1 Introduction
2 Lower Bounds
3 上限
References
翻訳抄

1 Introduction

2 Lower Bounds

2.1 Any number of I/Os per update

2.2 Few I/Os per $B$ updates

2.3 Many I/Os per $B$ updates

3 上限

ここでは外部メモリ辞書のさまざまな上限について説明する。これらの構成の主な目的は定理 1 の下限が広い範囲のパラメータに対して漸近的に厳密であることを示すことである。

3.1 B-Tree

外部メモリに辞書を保持するための一般的なソリューションは B-Tree [8] を使用することである。B-Tree では各葉が $O(B)$ 個の要素を格納し、内部ノード (ルートを除く) が次数 $\Theta(B)$ を持ち、すべての葉の深さが等しい多方向ツリーである。各内部ノードは $O(1)$ 個のブロックに格納され、子へのポインタとクエリーを導くための適切な検索キーで構成される。B-Tree の次数境界は、高さが $O(\log_B N)$ であり、クエリーと更新が $O(\log_B N)$ I/O で実行できることを意味する [8]。

B-Tree 最上位の $O(M)$ 要素を内部メモリに保持することで、更新とクエリーを $O\left(\log_B \frac{N}{M}\right)$ I/O で実行できる。最上位の $O(M)$ 要素はレベル $0,1,\ldots,\ell$ に格納されるが、レベル $0,1,\ldots,\ell-1$ はすべて内部メモリに配置できる。レベル $\ell-1$ には $\Omega(M)$ 個のノードが含まれている。つまり、レベル $\ell+1$ をルートとする少なくとも 1 つの部分ツリーのサイズは $O\left(\frac{N}{M}\right)$ 、高さは $O\left(\log_B \frac{N}{M}\right)$ である。したがって B-Tree の高さは $\ell+O\left(\log_B \frac{N}{M}\right)$ となり、クエリーの I/O 回数は $O\left(1 + \log_B \frac{N}{M}\right)$ となる。補題 1 によりこのクエリー時間は最適である。

3.2 バッファツリー

Arge のバッファツリー [2] は各内部ノードが次数 $\Theta(M/B)$ を持ち、各葉が $O(M)$ 要素を格納する B-Tree の変種である。さらに、各内部ノードは $O(M)$ のバッファを持ち、そのバッファにはそのノードをルートとする部分ツリーに伝播される遅延操作が格納される。バッファツリーの詳細は [2] を参照。

バッファツリーはオフラインのクエリーと更新を効率的に実行するように設計されている。Arge が主張するように、オンライン設定で使用すると、バッファツリーは $O({\rm Sort}(N))$ 回の I/O で $N$ 個の更新をサポートする。クエリーを実行するときに 1 つのルートから葉への経路 (root-to-leaf path) に沿ったすべてのバッファを調べる必要があるため、オンラインクエリーは $O\left(\frac{M}{B} \log_{M/B} \frac{N}{M}\right)$ 回の I/O でサポートできる。更新の I/O 境界は B-Tree より大幅に優れており $B \cdot \log_B \frac{M}{B}$ 倍であるが、オンラインクエリーは $\frac{M}{B} / \log_B \frac{M}{B}$ 倍で遅くなる。

3.3 Truncated バッファツリー

以下では補題 2 に対応する上限を達成する構成の概要を示す。この構成は基本的にバッファツリーの切り詰められたバージョンである。 $N$ 回の挿入で $O(\delta\cdot N/B)$ 回の I/O が発生すると仮定する。バッファツリーのすべてのレベル $O(\log_{M/B}\frac{N}{M})$ を維持する代わりに最上位の $\delta$ レベルのみを維持する。つまり、すべてのノードの次数は $O(M/B)$ で、バッファのサイズは $O(M)$ である。バッファツリーのレベル $\delta+1$ , $\delta+2$ , $\ldots$ を維持する代わりに、レベル $\delta$ の各ノードにバケットを関連付ける。レベル $\delta$ のノードでバッファオーバーフローが発生するたびにバッファの内容がソートされバケットに移動される。バケットには $O(N/(\frac{M}{B})^\delta)$ 個の要素が格納される。バケットがオーバーフローするたびに、最適な外部メモリ選択アルゴリズム [9, 18] を適用してバケットを線形数の I/O で分割し、バッファツリーの葉分割と同様にツリーの最上位レベルに新しいバケットを挿入する。 $N$ 回の挿入を実行するには $O(\delta\cdot N/B)$ 回の I/O が必要であり、クエリーには $O(\delta\cdot M/B)$ 回の I/O に加えてバケットのスキャンに必要な I/O が必要となる。

バケットは (バッファオーバーフローごとに) $M$ 個の要素のソートされたシーケンスを反復的に追加することによって形成されるため、分数カスケーディング [12, 13] の考えを採用してバケット全体をスキャンしないようにすることができる。バケットは $S_1 \cup \cdots \cup S_k$ で構成されていると仮定する。ここで各 $S_i$ はバッファオーバーフローの結果としてソートされたシーケンス、つまり $|S_i| = M$ である。我々は $S_1,\dots,S_k$ のみを格納する代わりにわずかに大きい集合 $\bar{S}_1,\ldots,\bar{S}_k$ を格納する。ここで $\bar{S}_1 = S_1$ であり、 $i \ge 2$ の場合、 $\bar{S}_i$ は $\bar{S}_{i-1}$ の 2 番目の要素ごとにマージされた $S_i$ で構成される。帰納法により $\bar{S}_i \le 2M$ である。 $\bar{S}_i$ の各要素には、 $\bar{S}_{i-1}$ の位置、または $\bar{S}_{i-1}$ の前方または後方 (predecessor or successor) へのポインタを格納する。

バケット内の要素を検索するにはまず $O(M/B)$ 回の I/O を使って $\bar{S}_k$ の前方または後方を検索する。これで、保存されたポインタを使用して各セット $\bar{S}_i$ に対して $O(1)$ 回の I/O を費やすだけで $\bar{S}_{k-1},\bar{S}_{k-2},\ldots,\bar{S}_k$ 内での位置を見つけることができる。クエリーの合計時間は $O(\delta\cdot M/B + N/(M(M/B)^{\Omega(\delta)}))$ となり、これはある $c$ と $N \ge M(M/B)^{c\delta}$ に対しては $O(N/(M(M/B)^{\Omega(\delta)}))$ となる。

$S_{k+1}$ と $\bar{S}_k$ から新しいセット $\bar{S}_{k+1}$ を作成するには $O(M/B)$ 回の I/O を使用した線形スキャンで行うことができる。バケットを分割するには上述のバケット構造を再計算する必要がある。これは、選択によって作成された 2 つのリストをスキャンすることによって線形数の I/O で実行することができる。つまり $N$ 回の挿入でもまだ $O(\delta\cdot M/B)$ 回の I/O が実行される。

3.4 バッファ付き B-Tree

B-Tree にバッファを追加して次数を変化させることによって、B-Tree の漸近的なクエリー時間を犠牲にすることなく更新の償却 (amortized) I/O 境界を大幅に改善できる。

我々はパラメータ $\log N \lt \delta \le B \log N$ に対して $N$ 回の更新で $O(\delta\cdot \frac{N}{B})$ 回の I/O を実行できる場合について考える。我々が使用する構造は次数が $\Theta(\delta/\log N)$ の B-Tree、すなはち葉が $\Theta(B)$ 個の要素を格納し、(ルートを除く) 内部ノードが次数 $\Theta(\delta/\log N)$ を持つ木構造である。結果として得られる木構造の高さは $O\left(\log_{\delta/\log N} \frac{N}{B}\right)$ である。各ノードには、ノードの下の部分ツリーへの $O(B)$ 個の遅延更新を含む $O(1)$ ブロックに格納されるバッファがある。バッファツリーと同様に、バッファ内の遅延更新はバッファがオーバーフローした場合にのみ下位に伝播される。ノードのバッファがオーバーフローすると、 $\Omega((B\log N)/\delta)$ 個の要素をノードのバッファから子のバッファに移動できるような子が存在する。残りの要素はバッファ内に残る。これは、ツリー内のルートから葉への単一の経路に沿ってすべてのバッファがオーバーフローしていることを意味する。更新がリーフに到達するとツリーはバッファツリー [2] のように再バランスされる。

最上位の $O(M)$ 個の要素は、B-Tree のケースで上述したように内部メモリに格納できるため、結果として $O\left(\log_{\delta/\log N}\frac{N}{M}\right)$ 回の I/O のクエリーと $O(\delta\cdot \frac{N}{B})$ 回の I/O の $N$ 個の更新をサポートするツリーが得られる。更新の境界は、ツリーの最大 $O(\log N)$ レベルのそれぞれに最大 $O(N/((B\log N)/\delta))$ のバッファオーバーフローが発生することから生じる。つまりバッファオーバーフローを処理するために必要な I/O は最大 $O(\log N \cdot \delta N/(B\log N)) = O(\delta\cdot\frac{N}{B})$ 回になる (バッファツリーの場合と同様に、ツリーの再バランスに必要な I/O はバッファオーバーフローの処理コストに支配される)。 $\delta\ge\log^{1+\epsilon}N$ の場合、クエリーの境界は任意の定数 $\epsilon \gt 0$ に対して $O(\log_\delta\frac{N}{M})$ となる。

$\delta = B^\epsilon\log N$ の場合、結果として得られるツリーは次数 $O(B^\epsilon)$ 、高さ $O(\frac{1}{\epsilon}\log_B N)$ となる。したがってクエリーには $O(\frac{1}{\epsilon}\log_B\frac{N}{M})$ 回の I/O が必要となり、 $B$ 個の更新には償却 $O(\frac{B^\epsilon}{\epsilon}\log_B\frac{N}{M})$ 回の I/O が必要になる。これは標準の B-Tree のクエリー時間と定数倍の範囲内で一致するが、更新の境界は改善される。

References

A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116–1127, Sept. 1988.
L. Arge. The buffer tree: A new technique for optimal I/O-algorithms. In Proc. 4th Workshop on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes in Computer Science, pages 334–345. Springer Verlag, Berlin, 1995.
L. Arge. External memory data structures. In 9th European Symposium on Algorithms (ESA 2001), volume 2161 of Lecture Notes in Computer Science, pages 1–29. Springer Verlag, Berlin, 2001.
L. Arge, M. Knudsen, and K. Larsen. A general lower bound on the I/O-complexity of comparison-based algorithms. In Proc. 3rd Workshop on Algorithms and Data Structures (WADS), volume 709 of Lecture Notes in Computer Science, pages 83–94. Springer Verlag, Berlin, 1993.
L. Arge and P. B. Miltersen. On showing lower bounds for external-memory computational geometry problems. In J. Abello and J. S. Vitter, editors, External Memory Algorithms and Visualization, pages 139–160. American Mathematical Society Press, Providence, RI, 1999.
L. Arge and J. Pagter. I/O-space trade-offs. In Proc. 7th Scandinavian Workshop on Algorithm Theory, volume 1851 of Lecture Notes in Computer Science, pages 448–461. Springer Verlag, Berlin, 2000.
L. Arge, V. Samoladas, and J. S. Vitter. On two-dimensional indexability and optimal range search indexing. In Proceedings of the Eighteenth ACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems, pages 346–357. ACM Press, 1999.
R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173–189, 1972.
M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7:448–461, 1973.
A. Borodin, L. J. Guibas, N. A. Lynch, and A. C. Yao. Efficient searching using partial ordering. Information Processing Letters, 12:71–75, 1981.
G. S. Brodal, S. Chaudhuri, and J. Radhakrishnan. The randomized complexity of maintaining the minimum. Nordic Journal of Computing, Selected Papers of the 5th Scandinavian Workshop on Algorithm Theory (SWAT’96), 3(4):337–351, 1996.
B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133–162, 1986.
B. Chazelle and L. J. Guibas. Fractional cascading: II. applications. Algorithmica, 1:163–191, 1986.
D. Comer. The ubiquitous B-tree. ACM Computing Surveys, 11(2):121–137, 1979.
D. E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison Wesley Longman, USA, 2 edition, 1998.
V. Samoladas. On Indexing Large Databases for Advanced Data Models. PhD thesis, The University of Texas at Austin, 2001. Dept. of Computer Science.
V. Samoladas and D. P. Miranker. A lower bound theorem for indexing schemes and its application to multidimensional range queries. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 4451. ACM Press, 1998.
J. F. Sibeyn. External selection. In Proceedings of the 16th Symposium Theoretical Aspects of Computer Science (STACS), volume 1563 of Lecture Notes in Computer Science, pages 291–301. Springer-Verlag, 1999.
J. S. Vitter. External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys, 33(2):209–271, June 2001.

翻訳抄

検索操作においては従来の B-Tree の定数オーダーの性能を維持しながら、更新操作のスループットを大幅に改善する B^ε-Tree についての 2003 年の論文。

Brodal, G.S., Fagerberg, R.: Lower bounds for external memory dictionaries. In: 14th Annual ACM-SIAMSymposium on Discrete Algorithms (SODA). pp. 546–554 (2003)