Indexing complex networks for fast attributed kNN queries

DOI 機関リポジトリ 機関リポジトリ (HANDLE) PDF Web Site 被引用文献1件 参考文献38件 オープンアクセス

この論文をさがす

説明

<jats:title>Abstract</jats:title><jats:p>The <jats:italic>k</jats:italic> nearest neighbor (<jats:italic>k</jats:italic>NN) query is an essential graph data-management tool used for finding relevant data entities suited to a user-specified query node. Graph indexing methods have the potential to achieve a quick <jats:italic>k</jats:italic>NN search response and thus are promising approaches. However, they struggle to handle large-scale attributed complex networks. This is because constructing indices and querying <jats:italic>k</jats:italic>NN nodes in large-scale networks are computationally expensive, and they are not designed to handle node attributes included in the networks. In this paper, we propose a novel graph indexing algorithm, namely <jats:italic>CT</jats:italic> index, for fast <jats:italic>k</jats:italic>NN queries on large complex networks. To overcome the aforementioned limitations, our algorithm generates two types of indices based on the topological properties of complex networks. In addition, we further propose <jats:italic>BAG</jats:italic> index along with CT index so that our algorithm enables to explore <jats:italic>k</jats:italic>NN nodes based on the attribute similarity. Our extensive experiments on real-world graphs show that our algorithm achieves up to 18,074 times faster indexing and 146 times faster <jats:italic>k</jats:italic>NN query than other state-of-the-art methods.</jats:p>

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (38)*注記

もっと見る

関連プロジェクト

もっと見る

詳細情報 詳細情報について

問題の指摘

ページトップへ