WEKO3
アイテム
A report on Top-k keyword search algorithms with redundancy elimination on graph databases
https://ipsj.ixsq.nii.ac.jp/records/70815
https://ipsj.ixsq.nii.ac.jp/records/70815526d3985-4adb-473c-be1b-e17ef1e309b4
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-DBS10151028.pdf (852.3 kB)
|
Copyright (c) 2010 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2010-11-05 | |||||||
| タイトル | ||||||||
| タイトル | A report on Top-k keyword search algorithms with redundancy elimination on graph databases | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A report on Top-k keyword search algorithms with redundancy elimination on graph databases | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | グラフ・モデル | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| Graduate School of Information Systems, The University of Electro-Communications | ||||||||
| 著者所属 | ||||||||
| Graduate School of Information Systems, The University of Electro-Communications | ||||||||
| 著者所属 | ||||||||
| Graduate School of Information Systems, The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Systems, The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Systems, The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Systems, The University of Electro-Communications | ||||||||
| 著者名 |
Meirong, Wang
× Meirong, Wang
|
|||||||
| 著者名(英) |
Meirong, Wang
× Meirong, Wang
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In recent database studies, a new trend for managing vast amounts of heterogeneous data is to represent all data as a graph database and to provide a ranked keyword search algorithm in that graph. Many previous studies [1][2][3][4][5][6] discussed new searching algorithms for finding better sub-graph in a graph database, in such a way to detect appropriate sub-graph in a ranked order under given keywords. In this paper, by modifying an existing graph-database search algorithm DPBF [1] in a straightforward strategy, we propose such an algorithm that can find exact top-k with eliminating redundant answers, in an exact ranked order in O((2l+1mk+3lnk・logk)log(2lnk)) run time (l: the number of keywords; k: top-k; n: the number of nodes in the graph database; m: the number of edges in the graph database) with the space complexity of O(2l+1nk). | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In recent database studies, a new trend for managing vast amounts of heterogeneous data is to represent all data as a graph database and to provide a ranked keyword search algorithm in that graph. Many previous studies [1][2][3][4][5][6] discussed new searching algorithms for finding better sub-graph in a graph database, in such a way to detect appropriate sub-graph in a ranked order under given keywords. In this paper, by modifying an existing graph-database search algorithm DPBF [1] in a straightforward strategy, we propose such an algorithm that can find exact top-k with eliminating redundant answers, in an exact ranked order in O((2l+1mk+3lnk・logk)log(2lnk)) run time (l: the number of keywords; k: top-k; n: the number of nodes in the graph database; m: the number of edges in the graph database) with the space complexity of O(2l+1nk). | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10112482 | |||||||
| 書誌情報 |
研究報告データベースシステム（DBS） 巻 2010-DBS-151, 号 28, p. 1-8, 発行日 2010-11-05 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
