A report on Top-k keyword search algorithms with redundancy elimination on graph databases

概要

論文の詳細を見る
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).
2010-11-05