Indexing complex networks for fast attributed kNN queries
Indexing complex networks for fast attributed kNN queries
复制标题
DOI：
10.1007/s13278-022-00904-w
复制
发表时间：
2022-07
影响因子：
2.8
通讯作者：
Suomi Kobayashi;Shohei Matsugu;Hiroaki Shiokawa
中科院分区：
文献类型：
--
作者：
Suomi Kobayashi;Shohei Matsugu;Hiroaki Shiokawa
kNN查询是一种重要的图数据管理工具，用于查找适合用户指定查询节点的相关数据实体。图索引方法具有实现快速kNN搜索响应的潜力，因此是有前途的方法。然而，他们很难处理大规模的复杂网络。这是因为在大规模网络中构建索引和查询kNN节点在计算上是昂贵的，并且它们不是为了处理网络中包含的节点属性而设计的。在本文中，我们提出了一种新的图索引算法，namelyCTindex，快速kNN查询大型复杂网络。为了克服上述限制，我们的算法生成两种类型的指数的基础上复杂网络的拓扑特性。此外，我们还提出了BAG索引沿着CT索引，使得我们的算法能够基于属性相似性来探索kNN节点。我们对真实世界图的广泛实验表明，我们的算法比其他最先进的方法快18，074倍的索引速度和146倍的kNN查询速度。
Theknearest neighbor (kNN) 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 quickkNN search response and thus are promising approaches. However, they struggle to handle large-scale attributed complex networks. This is because constructing indices and queryingkNN 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, namelyCTindex, for fastkNN 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 proposeBAGindex along with CT index so that our algorithm enables to explorekNN 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 fasterkNN query than other state-of-the-art methods.