特許
J-GLOBAL ID：201103008136558859

多次元空間データ構造および多次元空間データの更新および探索方法と前記多次元空間データ構造を記録した記録媒体および前記方法を実施するプログラムを記録した記録媒体

発明者：
櫻井 保志

櫻井 保志 について

, 
吉川 正俊

吉川 正俊 について

, 
植村 俊亮

植村 俊亮 について


出願人/特許権者：
日本電信電話株式会社

日本電信電話株式会社 について


代理人 (2件)： 三好 秀和 ,  三好 保男
公報種別：特許公報
出願番号（国際出願番号）：特願平11-001345
公開番号（公開出願番号）：特開2000-200342
特許番号：特許第3542732号
出願日： 1999年01月06日
公開日（公表日）： 2000年07月18日
請求項（抜粋）：
【請求項1】ディスクに格納される複数の幾何学的オブジェクトを多次元空間上で表現される多次元ベクトルとして表す多次元空間データのデータ構造であって、前記多次元空間データは、前記多次元空間内の幾何学的オブジェクトが所定のエントリ数分それぞれ包含された複数のリーフノードを該多次元空間内の端点の絶対座標値によりそれぞれ表現される複数の最小範囲矩形により梱包して該複数のリーフノードを該複数の最小範囲矩形に対して連接させ、該複数の最小範囲矩形をさらに新たな最小矩形範囲により梱包して該複数の最小範囲矩形を該新たな最小範囲矩形に対して連接させることにより、前記新たな最小範囲矩形を含む複数の最小範囲矩形を複数のノンリーフノードとし前記複数のリーフノードと共に階層化して構成された木構造における、前記複数のリーフノードそれぞれの前記多次元空間内の絶対値座標と、前記木構造における前記複数のノンリーフノードに対応する複数の最小矩形範囲の端点の絶対値座標とから表現された実部分と、前記木構造における前記複数のノンリーフノードそれぞれに対応する複数の最小範囲矩形に対する相対的位置に基づく複数の仮想範囲矩形を木状に階層化した場合における前記複数の仮想範囲矩形により求められた複数の部分空間符号により表現された仮想部分とを備え、前記仮想部分は、前記各ノンリーフノードに連接される複数のノンリーフノードを複数の子ノードとし、連接元の各ノンリーフノードを各親ノードとした際に、該各親ノードに連接される子ノードの数であるエントリ数と、前記各親ノードに連接される複数の子ノードに対応する複数の仮想範囲矩形の始点および終点それぞれの前記多次元空間内の位置情報により求められた部分空間符号と、前記各親ノードに連接する複数の子ノードそれぞれの前記ディスク上の格納位置を表すノードポインタとから構成されており、前記多次元空間の次元数をnとし、前記各親ノードの最小範囲矩形の対角を成す2つの端点a、a ́、および各親ノードに連接される各子ノードの最小範囲矩形の対角を成す2つの端点b、b ́とし、a、a ́、b、b ́は、それぞれ下式(1)、(2)、(3)、(4):a=[φ1 ,φ2 ,...,φn ] ・・・(1)a′=[φ1 ′,φ2 ′,...,φn ′] ・・・(2)b=[ψ1 ,ψ2 ,...,ψn ] ・・・(3)b′=[ψ1 ′,ψ2 ′,...,ψn ′] ・・・(4)但し、φi ≦φi ′;i∈{1,2,...,n}をそれぞれ満足する場合における前記各子ノードの各仮想範囲矩形の始点および終点それぞれの前記多次元空間内の位置情報をV=v,v ́とし、v、v ́は、それぞれ下式(5)、(6):v=[r1 ,r2 ,...,rn ] ・・・(5)v′=[r1 ′,r2 ′,...,rn ′] ・・・(6)但し、ri ≦ri ′、かつ;;数1::i=1,2,・・・,nを満足するものとし、ηiとηi ́(ηi≦ηi ́)を下式(9)および(10):;;数2::を満足するi次元座標上の部分区間を表すq元符号とし、F2(ηi,l)を符号長lとするηiの2進表現として下式(11):;;数3::を満足するものとした場合、前記各子ノードに対応する各仮想範囲矩形の始点および終点それぞれの位置情報により求められる前記多次元空間内の部分空間符号は、前記各子ノードの各仮想範囲矩形の位置情報Vを圧縮する2進符号S=(s,s ́)として、下式(12)および(13):s=[F2 (η1 ,l),F2 (η2 ,l),...,F2 (ηn ,l)] ・・・(12)s′=[F2 (η1 ′,l),F2 (η2 ′,l),...,F2 (ηn ′,l)] ・・・(13)を満足するように設定されており、前記複数の子ノードに対応する複数の仮想範囲矩形の始点および終点それぞれの位置情報により求められる前記多次元空間内の部分空間符号は、前記複数の子ノードの始点および終点それぞれに対して設定された1次元目からn次元目までの次元毎の部分空間符号として構成され、前記複数の子ノードそれぞれの前記ディスク上の格納位置を表すノードポインタは、該複数の子ノードそれぞれの前記ディスク上の格納位置をノード毎に表すページアドレスおよびバイト変位により構成されたことを特徴とする多次元空間データ構造。
IPC (2件)：
G06T 1/00 ,  G06F 17/30
FI (3件)：
G06T 1/00 200 E ,  G06F 17/30 170 B ,  G06F 17/30 419 A
引用特許：
出願人引用 (4件)
全件表示

前のページに戻る

TOP

BOTTOM