| 講演名 | 2003/7/10 超平面アレンジメントに基づく多次元空間幾何アルゴリズムの実装と評価(アルゴリズム・索引)(「夏のデータベースワークショップ(DBWS2003)」一般) 金子 邦彦, 牧之内 顕文, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本研究では,新しい空間データモデルとして,HA-face complexモデルを提案する.HA-face complexモデルでは,超平面アレンジメントのフェイスの複体として,空間物の位置と形を表現する.超平面アレンジメントのフェイスとは,ある次元の空間を複数の超平面で区切ったときにできる区画のことである.このモデルは,次元に特化しない空間データモデルであって,本質的に,任意の次元の空間データの表現に用いることができる.本研究では,HA-face complexモデル上で動く幾何計算(和や差や積などの集合論演算子や,交わる,離れている,含む,等しい,接するなどの位相関係述語)の効率よいアルゴリズムであるlocalized divide-and-conquerと,2ステップリファインメントの提案も行う.実験によって,これらアルゴリズムの効果の確認も行っている. |
| 抄録(英) | This paper preserits a kernel system for spatial database systems named Hawk's Eye. We implemented a new spatial data model named HA-face complex on Hawk's Eye. The model represents the spatial position and region of spatial objects of various dimensions in 2-, 3- or 4- dimensional space uniformly. A spatial object represented by the model is a finite set of hyperplane arrangement faces, each of which is a region in a hyperplane arrangement induced by hyperplanes in 2-, 3- or 4- dimensional space. We propose a new algorithm named localized divide-and-conquer to evaluate geometric operations and spatial relationships of two spatial objects represented by the model. The model is implemented on an object database system. Our experimental tests show that the localized divide-and-conquer is faster than other algorithms using an arrangement construction algorithm incremental or divide-and-conquer. |
| キーワード(和) | 空間データモデル / 空間データ処理 / 計算幾何学 / 超平面アレンジメント |
| キーワード(英) | spatial data model / spatial query processing / computational geometry / hyperplane arrangement |
| 資料番号 | DE2003-36 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DE |
|---|---|
| 開催期間 | 2003/7/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Data Engineering (DE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 超平面アレンジメントに基づく多次元空間幾何アルゴリズムの実装と評価(アルゴリズム・索引)(「夏のデータベースワークショップ(DBWS2003)」一般) |
| サブタイトル（和） | |
| タイトル（英） | HA-face Complex Spatial Data Model for Uniform Representation of Data and Algorithms |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 空間データモデル / spatial data model |
| キーワード(2)（和/英） | 空間データ処理 / spatial query processing |
| キーワード(3)（和/英） | 計算幾何学 / computational geometry |
| キーワード(4)（和/英） | 超平面アレンジメント / hyperplane arrangement |
| 第 1 著者 氏名（和/英） | 金子 邦彦 / Kunihiko KANEKO |
| 第 1 著者 所属（和/英） | 九州大学 大学院 システム情報科学研究院 Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 第 2 著者 氏名（和/英） | 牧之内 顕文 / Akifumi MAKINOUCHI |
| 第 2 著者 所属（和/英） | 九州大学 大学院 システム情報科学研究院 Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 発表年月日 | 2003/7/10 |
| 資料番号 | DE2003-36 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 191 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |