1次元データ構造の範囲検索への適用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/26 09:37 UTC 版)
「Z階数曲線」の記事における「1次元データ構造の範囲検索への適用」の解説
局所性を良好に保ちながら効率的な範囲検索を行いたいようなアルゴリズムでは、データ構造内で遭遇した点から、次の多次元の探索範囲にあるZ値への計算が必要である: この例では、照会したい範囲（ x = 2,...,3, y = 2,...,6 ）を点で囲まれる矩形で表した。このうちで最大のz値は MAX は 45 である。この例においては、照会対象をz値に基いて探索するうちに F = 19 に遭遇するため、 F と MAX の間のz値の範囲（斜線の領域）について探索が必要となる。探索を高速化として、照会したい範囲の未照会の範囲で最小のz値 BIGMIN （この例では 36 ）を計算し、 BIGMIN と MAX の間の区間（太字の範囲）のみを探索する事で、斜線領域の多くを飛ばせる。もし、逆向きに探索する場合は BIGMIN と同様に、照会範囲内で F よりも小さな最大の Z値 LITMAX を計算する。この BIGMIN 問題は Tropf と Herzog に提起され解決されている。 この手法は UB木 の "GetNextZ-address" でも用いられる。この手法は元の1次元のデータ構造に依存せずデータを容易かつ自由に構造化可能なため、B木のような既知の手法を用いて動的データへ対応できる。（これはR木が特別な配慮を要する事と対照的である。） （元のデータ構造に従って）階層的にこの手法を適用すれば、増加方向、減少方向の何れであれ、非常に効率的な多次元の範囲検索を適用でき、最近傍探索の基礎として商用あるいは技術的にも重要である。Z階数を応用した多次元の商用データベースシステムがいくつか製品化されている（オラクルデータベース 1995, en:Transbase 2000 ）。 今は昔となる 1966 に、G.M.Morton が地理学的データベースの静的な2次元のファイル群についてZ階数を提案した。面のデータ単位には1つまたは幾つかの二次的な、Z値に基づいた枠を含んでいた。高確率で隣接フレーム間の参照を僅かな走査ステップで可能であった。
※この「1次元データ構造の範囲検索への適用」の解説は、「Z階数曲線」の解説の一部です。
「1次元データ構造の範囲検索への適用」を含む「Z階数曲線」の記事については、「Z階数曲線」の概要を参照ください。
- 1次元データ構造の範囲検索への適用のページへのリンク
