行う分散多次元センサデータ管理シス テム
4.7 多次元の 1 次元化 :Z-order
本節では，T-Ringにおいて基本的な，多次元データを1次元値に変更する処理を行うZ-order について述べる．この処理を行うクラスはZorder.javaである．このクラスのインスタンスを生成 するには，コンストラクタの引数として多次元データの各値（doubleの値）のListを必要とする．
そして，getZorder()という関数を呼び出すと，まず，Listで渡された値の要素数から，何次元の
データであるかを解析する．そして，各次元の値をバイナリの値（byteの配列）に変更する．次 に，各配列の要素数を調べる．要素数の最も多い配列に要素数を合わせるために，他の配列に最も 多い配列の要素数と同値になるまで0を埋める．最後に，各次元における配列の先頭を順に並べ，
すべての次元の値が並べ終わったら，配列の次の要素について同様の作業を行う．これを要素数分 繰り返す．これにより，最終的に完成したbyteの配列を関数の結果として返す．これについての
図解が図4.4である．Z-orderのプログラムとその使用例は以下に掲載する．
Listing 4.1 Z-order
p u b l i c c l a s s Z o r d e r i m p l e m e n t s Z o r d e r I n t e r f a c e {
p r i v a t e A r r a y L i s t < Long > p o s i t i o n s = new A r r a y L i s t < Long >() ;
p r i v a t e A r r a y L i s t < A r r a y L i s t < Byte > > b i n a r y P o s i t i o n s = new A r r a y L i s t < A r r a y L i s t < Byte > >() ; p u b l i c Z o r d e r ( A r r a y L i s t < Long > p o s i t i o n s ) {
t h i s . p o s i t i o n s = p o s i t i o n s ; }
p u b l i c b y t e [] g e t Z o r d e r () { c o n v e r t P o s i t i o n s T o B i n a r y () ; int l e n g t h = a d j u s t P o s i t i o n s () ;
A r r a y L i s t < Byte > r e t u r n A r r a y = new A r r a y L i s t < Byte >() ; for ( int i = 0; i < l e n g t h ; i ++) {
for ( int j = 0; j < t h i s . p o s i t i o n s . s i z e () ; j ++) {
r e t u r n A r r a y . add (( b y t e ) ( t h i s . b i n a r y P o s i t i o n s . get ( j ) . get ( i ) ) ) ; }
b y t e [] t m p B y t e A r r a y = new b y t e [ a d j u s t P o s i t i o n s ()
* t h i s . p o s i t i o n s . s i z e () ];
for ( int i = 0; i < t m p B y t e A r r a y . l e n g t h ; i ++) { t m p B y t e A r r a y [ i ] = r e t u r n A r r a y . get ( i ) ;
}
r e t u r n t m p B y t e A r r a y ; }
p r i v a t e v o i d c o n v e r t P o s i t i o n s T o B i n a r y () {
for ( int i = 0; i < t h i s . p o s i t i o n s . s i z e () ; i ++) {
t h i s . b i n a r y P o s i t i o n s . add ( c o n v e r t T o B i n a r y ( t h i s . p o s i t i o n s . get ( i ) ) ) ; }
}
p r i v a t e int a d j u s t P o s i t i o n s () {
int max = t h i s . b i n a r y P o s i t i o n s . get (0) . s i z e () ;
for ( int i = 0; i < t h i s . b i n a r y P o s i t i o n s . s i z e () ; i ++) { if ( max < t h i s . b i n a r y P o s i t i o n s . get ( i ) . s i z e () ) {
max = t h i s . b i n a r y P o s i t i o n s . get ( i ) . s i z e () ; }
}
int gap ;
for ( int i = 0; i < t h i s . b i n a r y P o s i t i o n s . s i z e () ; i ++) { gap = max - t h i s . b i n a r y P o s i t i o n s . get ( i ) . s i z e () ; for ( int j = 0; j < gap ; j ++) {
t h i s . b i n a r y P o s i t i o n s . get ( i ) . add (( b y t e ) 0) ; }
}
r e t u r n max ; }
p r i v a t e A r r a y L i s t < Byte > c o n v e r t T o B i n a r y ( l o n g d ) { A r r a y L i s t < Byte > b y t e A r r a y = new A r r a y L i s t < Byte >() ; w h i l e ( d >= 2) {
b y t e A r r a y . add (( b y t e ) ( d % 2) ) ; d /= 2;
}
b y t e A r r a y . add (( b y t e ) d ) ; r e t u r n b y t e A r r a y ;
}
p u b l i c v o i d d e b u g () { g e t Z o r d e r () ;
S y s t e m . out . p r i n t l n ( " n u m b e r of d i m e n s i o n s : " + t h i s . p o s i t i o n s . s i z e () ) ; for ( int i = 0; i < t h i s . p o s i t i o n s . s i z e () ; i ++) {
S y s t e m . out . p r i n t l n ( " p o s i t i o n of d i m e n s i o n " + i + " : "
+ t h i s . p o s i t i o n s . get ( i ) ) ; }
for ( int i = 0; i < t h i s . p o s i t i o n s . s i z e () ; i ++) {
S y s t e m . out . p r i n t l n ( " c o n v e r t e d p o s i t i o n of d i m e n s i o n " + i + " : "
+ t h i s . b i n a r y P o s i t i o n s . get ( i ) ) ; }
S y s t e m . out . p r i n t l n ( " max b i n a r y l e n g t h : " + a d j u s t P o s i t i o n s () ) ; S y s t e m . out . p r i n t ( " z o r d e r : [ " ) ;
for ( int i = 0; i < g e t Z o r d e r () . l e n g t h ; i ++) { S y s t e m . out . p r i n t ( g e t Z o r d e r () [ i ]+ " , " ) ;
}
S y s t e m . out . p r i n t l n ( " ] " ) ; }
}
Listing 4.2 Z-order使用例
p u b l i c c l a s s Z o r d e r T e s t {
p u b l i c s t a t i c v o i d m a i n ( S t r i n g [] a r g v ) {
A r r a y L i s t < Long > p o s i t i o n s = new A r r a y L i s t < Long >() ; p o s i t i o n s . add (( l o n g ) 10) ;
p o s i t i o n s . add (( l o n g ) 5) ; p o s i t i o n s . add (( l o n g ) 20) ;
Z o r d e r I n t e r f a c e z o r d e r = new Z o r d e r ( p o s i t i o n s ) ; z o r d e r . g e t Z o r d e r () ;
z o r d e r . d e b u g () ;
}
}
Listing 4.3 実行結果
p o s i t i o n of d i m e n s i o n 0 :10 p o s i t i o n of d i m e n s i o n 1 :5 p o s i t i o n of d i m e n s i o n 2 :20
c o n v e r t e d p o s i t i o n of d i m e n s i o n 0 : [0 , 1 , 0 , 1 , 0]
c o n v e r t e d p o s i t i o n of d i m e n s i o n 1 : [1 , 0 , 1 , 0 , 0]
c o n v e r t e d p o s i t i o n of d i m e n s i o n 2 : [0 , 0 , 1 , 0 , 1]
max b i n a r y l e n g t h : 5
z o r d e r : [0 ,1 ,0 ,1 ,0 ,0 ,0 ,1 ,1 ,1 ,0 ,0 ,0 ,0 ,1]
[0, 1, 0, 1, 0]
positions[0]
10
[1, 0, 1, 0, 0]
positions[1]
5
[0, 0, 1, 0, 1]
positions[2]
20
[0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1]
図4.4 Z-order図解
4.8 まとめ
本章では，まず，保存ピアの計算量を削減し，Synapseよりもデータ管理の時間的密度が高いア ルゴリズムを提案することを述べた．次に，T-Ringにおいて時間という属性をDHTにおける保 存ピアの決定における一つ要素としてではなく，保存ピアの変更を行うための要素として扱うこと を述べた．そして，時間的密度，計算コストの観点から集中管理，Synapse，T-Ringの3つの手 法の比較を行った．また，センサデータの時間的特殊性に着目した多次元センサデータ分散管理シ ステムであるT-Ringの詳細な設計概念，設計実装について述べた．T-RingはP2Pのトポロジと して，代表的なアルゴリズムであるChordに準拠した1Dトーラスを用いている．保存ピアの参 加や離脱なども同様にChordに準拠している．また，多次元データを扱うにあたり，Z-orderによ り 次元化に言及した．時間的特殊性については， と という つの時間概念を導入し，
保存ピア変更の基準とした．また，ユーザがT-Ringシステムを用いて，データ取得のクエリを送 る際の，形式を定義した．