WEKO3
アイテム
有向グラフ上の最短経路問題に対する効率的な索引付け
http://hdl.handle.net/10228/6020
http://hdl.handle.net/10228/6020f04f498d-b15b-4d53-9824-e32f3171fbd1
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
DBSJ7_211.pdf (184.5 kB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2017-02-09 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | 有向グラフ上の最短経路問題に対する効率的な索引付け | |||||||||||||
| 言語 | ja | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Scalable Indexing for Reachability Problem on Directed Graphs | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | jpn | |||||||||||||
| 著者 |
原口, 新平
× 原口, 新平× 中村, 有作× 坂本, 比呂志
WEKO
17609
|
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | 本研究では，有向グラフ上の任意の2ノード間の距離を高速に計算できる規模耐性の高い索引構造を提案する．本研究で提案する手法は，有向グラフ上の最短距離計算として，ノード間の距離計算の結果をあらかじめ隣接行列に格納しておく方法がある．しかしながら，この方法では時間計算量と領域計算量の両方のコストが高く，大規模なグラフ構造に適用する事は困難である．そこで本研究では，一般の有向グラフに適用可能な距離計算のためのラベル付けを提案し，その有効性を実験により検証する．特に, XMLデータにおいて，前処理に必要な主記憶量，計算時間および索引サイズを示す． | |||||||||||||
| 言語 | ja | |||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | We propose an efficient algorithm which reports the length of a shortest path between any two nodes of a directed graph in constant time. In usual method, we can obtain the constant time response for any query in this problem by using an adjacent matrix for the graph. However, this method requires huge memory space and it is difficult to apply it to lage database. So we introduce more practical method for this problem and evaluated the efficency by experiments. | |||||||||||||
| 言語 | en | |||||||||||||
| 書誌情報 |
ja : 日本データベース学会論文誌 巻 7, 号 1, p. 211-214, 発行日 2008-06 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | 日本データベース学会 | |||||||||||||
| 言語 | ja | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||
| 収録物識別子 | 1883-4205 | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | 日本データベース学会 | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | VoR | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
| 連携ID | ||||||||||||||
| 値 | 631 | |||||||||||||
