http://swrc.ontoware.org/ontology#TechnicalReport
A report on Top-k keyword search algorithms with redundancy elimination on graph databases
en
グラフ・モデル
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
Meirong Wang
Liru Zhang
Tadashi Ohmori
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).
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).
AN10112482
研究報告データベースシステム（DBS）
2010-DBS-151
28
1-8
2010-11-05