論文
DBSJ Letters Vol.2, No.4――――――――――――――――――――――――――――――――――――

モバイルユーザによる協調ブラウジ
ングのためのコンテンツ分割方式
A Content Partitioning Method forCollaborative Browsing by Mobile Users

前川 卓也♥原 隆浩♠

上向 俊晃♦
西尾 章治郎♠Takuya MAEKAWA Toshiaki UEMUKAI
Takahiro HARA Shojiro NISHIO

本論文では，1 つのモバイル端末だけでは閲覧できないリッチなコンテンツを，複数のモバイル端末に分割して閲覧する協調ブラウジングを想定し，協調ブラウジングを実現するためのコンテンツ分割方式を提案する．提案方式では，木構造形式で記述したコンテンツを完全グラフに変換した上でグラフ分割問題に帰着させる．このとき，端末の持つ機能やユーザの要望などを考慮した柔軟な分割を行う．
In this paper, we assume that mobile users
collaboratively browse a rich content, which one mobile
terminal cannot show by itself, by using multiple mobileterminals. We propose a content partitioning method forcollaborative browsing. The proposed method converts atree-structured content into a complete graph and adapts
a graph partitioning problem to the graph. In doing so,functions of mobile terminals and users’ requests aretaken into account.

1. はじめに
近年，計算機の小型化と無線通信技術の発展にともない，携帯電話をはじめモバイル端末の高機能化が急速に進んでおり，ユーザはモバイル端末を用いていつでもどこでもネッ
トワークにアクセスし，情報を得ることができる．しかし，依然として，モバイル端末はディスプレイサイズや計算能力などの機能的制限があるため，単一のモバイル端末を用いてリッチなコンテンツを快適に閲覧することは困難である．そこで，貧弱な機能しかもたないモバイル端末であっても，自身のモバイル端末と身の回りにある複数の端末とを組み合わせて利用することで，リッチなコンテンツを閲覧することができるものと考えられる．本論文では，このように，複数の端末を用いて1つのコンテンツを閲覧することを協調ブラウジングと呼ぶ．協調ブラウジングは，1つのコンテンツを複数のコンテンツに分割し，各端末に配布することにより実♥学生会員 大阪大学大学院情報科学研究科博士前期課程
t_maekawa@ist.osaka-u.ac.jp♦
大阪大学大学院工学研究科博士後期課程
uemukai@ise.eng.osaka-u.ac.jp♠
正会員 大阪大学大学院情報科学研究科{hara, nishio}@ist.osaka-u.ac.jp

1

現する．しかし，あるユーザが協調ブラウジングを行いたいときに，ユーザの身の回りある端末の数や性能などが一定であるとは限らない． そこで本論文では，協調ブラウジングにおいて，1つのコンテンツを任意の数の端末で協調して閲覧するためのコンテンツ分割方式を提案する．提案方式では，分割の対象とするコンテンツのメタデータを木構造で記述する．さらに，この木を完全グラフに変換することによりグラフ分割問題に帰着させ，さまざまな条件に応じてコンテンツを分割する．
本研究と同様にモバイル端末を用いて情報閲覧するための研究として，1つのモバイル端末には表示不可能なコンテンツから表示可能なコンテンツを作成する研究[1]や，あらかじめ設定してあるディスプレイやプリンタなどの機器を利用してリッチなサービスを提供する研究[4]がある．しかし，
本研究では，1つのリッチなコンテンツを簡素化せずに，複数の端末に分割することで提供する．また，端末の数や性能などに応じて動的に分割したコンテンツを提供できる．
以下では，2章で協調ブラウジングについて述べ，3章では，それを実現するためのコンテンツ分割方式について述べる．
最後に4章で結論と今後の課題を述べる．

2. 協調ブラウジング
本論文で想定する協調ブラウジングでは，ユーザは，他のユーザが所持するモバイル端末を用いて，1つの非力な端末では閲覧できないリッチなコンテンツを閲覧する．ここで，協調ブラウジングで閲覧するコンテンツは複数のオブジェクトから構成され，利用するモバイル端末数などに応じてオブジェクト集合に分割される．各端末には1つのオブジェクト集合からなるコンテンツが配布される．協調ブラウジングの応用例としては，下記のようなものがあげられる．
z
協調WWWブラウジング
リンク数やコンテンツ量が多く，1つのモバイル端末では閲覧するのに困難なWWWページを，複数のモバイル端末に分配する．例えば，PDAには画像などを多く含む情報量の多いコンテンツが割り当てられ，携帯電話には情報量の少ないコンテンツが割り当てられる．ユーザ
は各自のモバイル端末に割り当てられたWWWページを用いて情報を検索する．あるユーザがリンクを選択した際，そのリンク先のページをそれらのモバイル端末に分配し端末を協調させることにより，目的の情報を見つける．
z
協調ゲーム
1つのゲームにおいて，画面やタスクを分割し，複数のモバイル端末を用いて協調してゲームを行う．例えば，迷路のアプリケーションにおいて，1つのモバイル端末には表示しきれない迷路を各端末に分配する．ユーザは，各自のモバイル端末に割り当てられた迷路を担当し，1つの駒を端末間でリレーすることにより，駒を全体の迷路のスタートからゴールまで導く．
ここで，協調ブラウジングでは，協調して利用する端末の数，性能は一定ではなく，また，貧弱な処理しかできない携
帯電話などの端末も含まれるため，以下のような条件を考慮してコンテンツを分割する必要がある．
z
端末の数(コンテンツの分割数)想定環境ではコンテンツの閲覧を行うときに利用できる端末の数が一定でない．

日本データベース学会 Letters Vol.2, No.4

論文
DBSJ Letters Vol.2, No.4――――――――――――――――――――――――――――――――――――zz

zzz

端末に割り当て可能なコンテンツの量
端末によっては利用可能なメモリやストレージの容量が制限される．
端末の性能
端末によっては画面の大きさや処理能力などが制限される．そのため，コンテンツを複数の端末に分配するとき，各端末の性能比に応じてコンテンツの分配割合を決定する必要がある．
端末の機能
例えば，動画などのコンテンツは，その再生機能をもつ端末に割り当てる必要がある．
分割したコンテンツの関連性分割されたコンテンツを構成するオブジェクト集合は，関連性のあるオブジェクトから構成されている方が利用しやすい．
ユーザの要求ユーザによっては，特定のコンテンツ(オブジェクト)を自身の端末に割り当てたい場合や割り当てたくない場合がある．このような割り当て要求や，非割り当て要求を考慮して分割する必要がある．

3. コンテンツ分割方式
提案するコンテンツ分割方式は，木構造でメタデータを記述したコンテンツに対して分割を行う．本章では，想定するコンテンツおよびその分割方式について述べる．

3.1

コンテンツとメタデータ

本節では，協調ブラウジングで利用する木構造型コンテンツについて述べる．

3.1.1

コンテンツの構造

コンテンツ構造の概念図を図 1 に示す．図において，葉ノード(オブジェクトノード)は，コンテンツを構成する最小単位であるオブジェクトもしくはオブジェクト集合を表す．一方，葉ノード以外のノード(分類ノード)は，オブジェクトノードを階層的にグループ化するものであり，コンテンツの分割に利用する．例えば，オブジェクトノードは，1 つの画像ファイルである場合や，互いに関連性のある画像や文字列などのオブジェクト集合である場合が考えられる．図 1 では，各オブジェクトノードを 3 つの分類ノードによりグループ化し，階層的な木構造を構成している．
ここで，関連性のあるオブジェクト同士のグループ化を実現するために，コンテンツ構造の各枝に重みを与え，2 つのオブジェクトノードを結ぶパスの重みが小さいほど，その関連性が大きいと定義する．例えば，図 1 において，ノード Aと B のパスの距離は 2，ノード A と D のパスの距離は 4 となるため，ノード A はノード D よりノード B との関連性が大きい．

3.1.2

メタデータの記述

前節のように定義したコンテンツ構造に対して，メタデータを XML 形式で記述する．図 2 は，図 1 に示す構造を持つコンテンツに対するメタデータの記述例である．以下に，記述に用いる各タグについて説明する．
[node タグ]
コンテンツ構造のノードを表し，入れ子構造にすることにより，階層的なコンテンツ構造を表現する．また，type 属性
は，ノードが分類ノード(''grouping'')かオブジェクトノード(''object'')かを表し，name 属性は，ノードの名前を表す．ノ2root
1G1

11G2G3
分類ノード

1A1B

112

CDE

オブジェクトノード1F

図 1 コンテンツ構造の概念図
Fig.1 Basic Concept of the Content Structure<?xml version="1.0"?><node type="grouping"><node type="grouping" name="section1"><node type="object" name="subsection1" weight="3"><locator>./section1/subsection1.html</locator></node><node type="object" name="subsection2"><locator>./section1/subsection2.html</locator><function>3</function></node><node type="object" name="subsection3"><locator>./section1/subsection3.html</locator></node></node><node type="grouping" name="section2"><node type="object" name="subsection1"><locator>./section2/subsection1.html</locator></node><node type="object" name="subsection2"
edge_weight="2"><locator>./section2/subsection2.html</locator></node></node><node type="grouping" name="menu"><node type="object" name="table of contents"><locator>./toc/toc.html</locator></node></node></node>

図 2 メタデータの記述例
Fig.2 Example of Metadata Describing
ードがオブジェクトノード(type=''object'')の場合，weight属性でそのオブジェクト量を設定する．edge_weight 属性は，ノードとその親ノードとの間を結ぶ枝の重みを表す．
[locator タグ]
ノードがオブジェクトノード(type=''object'')の場合，そのnode タグ内に定義する．その node タグが表すオブジェクトのファイル名などを記述する．
[function タグ]
ノードがオブジェクトノード(type=''object'')の場合，そのnode タグ内に定義する．オブジェクトの実行に必要な機能を数字として記述する．

3.2

コンテンツ分割方式

本節では，前節で述べた木構造型コンテンツに対して適用する分割方式について述べる．この分割方式では，メタデー
タの木を完全グラフに変換し，そのグラフを分割することによりコンテンツの分割を実現する．ここで，グラフ分割問題を解くためのアルゴリズムとしては，KL アルゴリズム[3]や，ネットワーク分割問題を解くための FM アルゴリズム[2]が日本データベース学会 Letters Vol.2, No.4

論文
DBSJ Letters Vol.2, No.4――――――――――――――――――――――――――――――――――――
root

4
G12A

G2

32

B

C

G3DE

F

図 3 コンテンツ分割の例
Fig.3 Example of Content Partitioning
ある．これらのアルゴリズムは，2 分割だけでなく，それ以上のグループにグラフを分割するアルゴリズムに簡単に拡張できる．例えば，FM アルゴリズムに基づくネットワーク
4 分割アルゴリズム[5]や，FM アルゴリズムに基づく複数分割アルゴリズム[6]がある．本論文で提案するコンテンツ分割方式では，FM アルゴリズムを拡張する．

3.2.1

図 4 コンテンツ分割アルゴリズム
Fig.4 Content Partitioning Algorithm

コンテンツ分割の定義

コンテンツの分割は，3.1 節で述べたメタデータの木をもとに作成した完全グラフを対象に行う．完全グラフのノードはメタデータのオブジェクトノードのみから成り，ノード間の枝の重さは，メタデータの木構造におけるノード間のパスの重さに対応する．この変換により，完全グラフにおけるすべてのノード間の枝の重みは，それぞれのノードの関連性を表す．このような完全グラフを用いた簡単なコンテンツ分割結果の例を図 3 に示す．この例では，分割数が 2 で，分割後の 2 つのコンテンツの量が等しく，さらに，関連のあるオブジェクト(集合)同士が同じ分割コンテンツになるようにグループ化されている．オブジェクトノード同士を接続している
実曲線は，完全グラフの枝を表しており，同じ分割コンテンツにグループ化されているオブジェクトノード同士を連結している．このように，完全グラフの枝から，接続するオブジェクトノード同士がグループを構成するようにカットする枝を選択し，コンテンツの分割を行う．
ここで，提案するコンテンツ分割方式では，2 章で述べた条件を考慮することから，分割の目的が一般のグラフ分割問題とは異なる．そのため，グラフ分割を評価する際の新たな指標が必要になる．そこで，分割結果の有効性を評価するための評価関数を導入する．評価関数 f は以下の式で表し，評価値が小さいほど条件を満たした分割であることを示す．

f = f1(c2 f2+c3 f3+c4 f4)
f1は，配布するコンテンツを端末上で実行できない度合を示す関数であり，実行できないオブジェクトと全オブジェクトの重みの比で表す．f2は，分配したコンテンツ量が指定した割合にどれだけ遠いかを示す関数であり，割り当てたオブジェクト量と割り当てを要求したオブジェクト量との端末ごとの適合度で表す．f3は，ユーザのコンテンツ割り当て要求にどれだけ応えていないかを示す関数であり，要求どおりに割り当てられなかったオブジェクト数とすべての要求数の比で表す．f4は，分割した際に同じグループに属するオブジェクトノード間の関連性を示す関数であり，端末ごとに割り当てるオブジェクトノードから構成した最小スパニング木の枝の総和と，完全グラフのすべての枝の重みの総和の比で表す．また，c2，c3，c4はそれぞれf2，f3，f4の重みを決定するための係数であり，この値によってそれぞれの関数の重要

3

Convert Tree into Complete Graph
Coordinate Graph
Create Initial k-way Partitioning
Compute f 'minf = f '/*k-way FM Algorithm*/
Do While minf updates
Unmark all nodes
Do While Unmarked nodes exist
Compute f in Unmarked nodes
Find noden and groupm that minimize f
Move noden into groupm and markend Do
Find groups that minimize f in the above loop and thisminimum f is set to tmpminf
If ( minf > tmpminf )minf = tmpminf
end Ifend Do

度を調整できる．

3.2.2

分割の手順

提案する分割方式では，まず，メタデータの木を完全グラフに変換した後，さまざまな条件を満たすよう完全グラフの調整を行い，初期のグラフ分割を行う．その後，複数分割に拡張した FM アルゴリズムを用いて，分割したグループ間でのオブジェクトノードの移動を行う．図 4 にアルゴリズムを示し，以下にその主要な点を説明する．
[Coordinate Graph]
グラフの調整では，実行に必要な機能をもつ端末が存在しないオブジェクトノードをグラフから削除する．
[Create Initial k-way Partitioning]
まず，調整後のグラフから最小スパニング木を求める．その最小スパニング木から，k-1 本の枝をカットすることにより，グラフをk個のグループに分割する．カットする枝は，ある端末からの割り当て要求と非割り当て要求をできるだ
け満たすもの，かつ，枝の重みが大きいものを優先的に選択する．そして，分割したkグループのコンテンツを各端末に割り当てる際の可能なすべての組み合わせの中から，最小の評価値fをもつ組み合わせを求め，これを初期分割における割り当てとする．さらに，端末i(0≦ i ≦ k-1)に割り当てるオブジェクトノードの集合groupiを出力する．
[k-way FM Algorithm]
初期分割によって求めたグループ間でノードの移動を行い，さらに適切な分割を求める．まず，ノードn (noden)が自身の属するグループ以外のグループgroupm (noden ∉ groupm)に移動したすべての場合の評価値fを，マークされていないすべてのノードについて求める．その中で最小のfを与えるノードの移動を選び，その移動を実行し，さらにそのノードをマークする．この手順をすべてのノードがマークされるまで繰り返す．この繰り返しの中で，最小の評価値を与えたグループ分けを暫定的な最適のグループ分けとする．次に，すべてのノードのマークを外した上で，そのグループ分けからさらにグループ間でのノードの移動による分割の最適化を繰り返す．この繰り返しは最小評価値の更新が行われなくなった時点で終了する．

日本データベース学会 Letters Vol.2, No.4

論文
DBSJ Letters Vol.2, No.4――――――――――――――――――――――――――――――――――――
慮したコンテンツ記述・分割に関する研究」，文部科学省科学技術振興調整費「モバイル環境向 P2P 型情報共有基盤の確立」，および文部科学省 21 世紀 COE プログラム「ネットワーク共生環境を築く情報技術の創出」の研究助成によるものである．ここに記して謝意を表す．

[文献］
A

B

C

D

E

FG

H

I

J

図 5 ターゲットのメタデータ
Fig.5 Target Metadata
表 1 端末と分割の条件
Table 1 Condition of Terminals and Partitioning
容量2端末 0
端末 1
端末 2

割り当てる
コンテンツの比532割り当て
要求JA-

非割り当て要求H-

表 2 割り当て結果
Table 2 Results of Allocation
結果 1 (c2=c3=c4=1)

結果 2 (c2=c3=1,c4=3)

B,C,G,I,J
A,F,H
D,E

B,C,I,J
A,F,G,H
D,E

端末 0
端末 1
端末 2

3.2.3

分割方式の適用例

前節のアルゴリズムを用いて，図 5 に示す木構造メタデー
タを持つコンテンツを，3 つの端末に対して分割する例を示
す．すべてのオブジェクトノードおよび枝の重みは 1 で，深さ 1 の分類ノードは，その子ノードの位置関係を考慮する．
また，A から J のオブジェクトノードのうち，F は実行に特別な機能を必要とするオブジェクトであり，端末 1 のみがこれを実行できるものとする．その他の端末および分割の条件
を表 1 に示す．
c2=c3=c4=1 およびc2=c3=1,c4=3 のときの結果を表 2 に示す．
結果 1 で端末 0 に割り当てられていたオブジェクトGが，結果 2 では端末 1 に割り当てられている．これは，c4=3 とすることにより，オブジェクト同士の関連性に重点が置かれたためであり，Gと関連性の強いオブジェクトFとHと同じ端末に割り当てられている．

4. おわりに
本論文では，1 つの端末では閲覧できないリッチなコンテンツを，複数の端末を用いて閲覧する協調ブラウジングを実現するためのコンテンツ分割方式を提案した．提案方式を用いることにより，指定した条件を考慮した分割を行うことができる．しかし，分割した後のグループを端末に対して割り当てる際に，すべての組み合わせを考慮するため，端末数が多くなると計算量が多くなる．
今後は，協調ブラウジングを用いたアプリケーションの実装を行い，実際の利用環境において分割に必要な条件などを再検討する予定である．

[謝辞][1] Anderson, C.R., Domingos, P., and Weld, D.S.:
Personalizing web sites for mobile users, Proc. WWW'01,
pp. 565-575 (May 2001).
[2] Fiduccia, C.M. and Mattheyes, R.M.: A linear timeheuristic for improving network partitioning, Proc.
Design Automation Conf., pp. 175-181 (June 1982).
[3] Kernighan, B.W. and Lin, S.: An efficient heuristic
procedure for partitioning graphs, Bell System
Technical J., Vol. 49, No. 2, pp. 291-307 (Feb. 1970).
[4] Masuoka, R., Labrou, Y., Parsia, B., and Sirin, E.:
Ontology-enabled pervasive computing applications,
IEEE Intelligent Systems, Vol. 18, No. 5, pp. 68-72(Sep./Oct. 2003).
[5] Sanchis, L.A.: Multiple-way network partitioning,
IEEE Transactions on Computers, Vol. 38, No. 1, pp.
62-81 (Jan. 1989).
[6] Suaris, P.R. and Kedem, G.: Quadrisection: A new
approach to standard cell layout, Proc. Int’l Conf. on
Computer-Aided Design, pp. 474-477 (Nov. 1987).

前川 卓也

Takuya MAEKAWA

2003 年大阪大学大学院工学部情報システム工学科卒業．現在，同大学院情報科学研究科博士前期課程在学中．日本デー
タベース学会学生会員．

上向 俊晃

Toshiaki UEMUKAI

2000 年大阪大学工学部情報システム工学科卒業．2001 年同大学院工学研究科博士前期課程修了．現在，同大学院工学研
究科博士後期課程在学中．

原 隆浩

Takahiro HARA

1995 年大阪大学工学部情報システム工学科卒業．1997 年同大学院工学研究科博士前期課程修了．同年，同大学院工学研
究科博士後期課程中退後，同大学院工学研究科情報システム工学専攻助手，2002 年より同大学院情報科学研究科マルチメディア工学専攻助手となり，現在に至る．工学博士． IEEE，
電子情報通信学会，日本データベース学会の各会員．

西尾 章治郎Shojiro NISHIO

1975 年京都大学工学部数理工学科卒業．1980 年同大学院工学研究科博士後期課程修了．工学博士．京都大学工学部助手，大阪大学基礎工学部および情報処理教育センター助教授，大阪大学大学院工学研究科情報システム工学専攻教授を経て，2002 年より同大学院情報科学研究科マルチメディア工学専
攻教授となり，現在に至る．2000 年より大阪大学サイバーメディアセンター長，2003 年より大阪大学大学院情報科学研究科長を併任．この間，カナダ・ウォータールー大学，ビクトリア大学客員．データベース，マルチメディアシステムの研究に従事．現在，Data & Knowledge Engineering, Data
Mining and Knowledge Discovery などの論文誌編集委員．
情報処理学会フェローを含め，ACM，IEEE など 9 学会の会員．

本研究の一部は，平成 15 年度受託研究（独立行政法人通信総合研究所）「モバイル端末による協調ブラウジングを考4

日本データベース学会 Letters Vol.2, No.4