GBD木の検索性能の改良方法　－大きな図形を扱うための手法の提案－

IPSJ 3 Citations 5 References

Bibliographic Information

Other Title
  • A Method for Improving Retrieval Performance of a GBD Tree 窶髏€ A Proposal of a Method for Handling Large Graphic Elements
  • 情報検索

Search this article

Abstract

GBD木では 大きな図形が混在する場合 兄弟同士のノードの外接長方形の重なりが多くなるため 検索性能が低下する.この問題を解決するために 本輪文では 図形の外接長方形を一定の大きさ(D_max)ごとに分割してサブ外接長方形を生成し 図形の外接長方形の代わりに これらのサブ外接長方形を用いてGBD木を形成する方法を提案している.このとき サブ外接長方形は実際に図形の一部を包含するもののみを登録する.この方法によれば 大きな図形の外接長方形は実質的に小さくなる.また サブ外接長方形ごとに近くの図形とグノレープ化され 各ノードの外接長方形が小さくなり 兄弟同士の重なりが少なくなるため 検索性能が向上する.長い線分が混在するデータについての数値実験によると 適切なD_maxを用いることにより 提案方式では原方式に比べて検索時のCPUタイムとタッチノード数は低減されるが 挿入時のCPUタイムと木構造データを格納するのに要するメモリ量は増加することが分かった.削除時のCPUタイムには大きな差異はない.このような利点と欠点を考慮すると 提案した方法は実用上 長い線分が混在するデータを扱う場合で 検索性能を重視する場合に有用であると考えられる.

Journal

  • 情報処理学会論文誌

    情報処理学会論文誌 33 (10), 1254-1262, 1992-10-15

    Information Processing Society of Japan (IPSJ)

Citations (3)*help

See more

References(5)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top