PathSim
PathSim
复制标题
DOI：
10.14778/3402707.3402736
复制
发表时间：
2011-08
影响因子：
2.5
通讯作者：
Yizhou Sun;Jiawei Han;Xifeng Yan;Philip S. Yu;Tianyi Wu
中科院分区：
文献类型：
--
作者：
Yizhou Sun;Jiawei Han;Xifeng Yan;Philip S. Yu;Tianyi Wu
相似度搜索是数据库和Web搜索引擎中的基本操作。随着文献网络、社交媒体网络等由多类型、相互关联的对象组成的大型异构信息网络的出现，研究此类网络中的相似度搜索具有重要意义。直观地说，如果两个对象在网络中有多条路径相连，那么它们就是相似的。然而，大多数现有的相似性度量都是针对同构网络定义的。没有考虑路径背后不同的语义含义。因此，它们不能直接应用于异构网络。本文研究了异构网络中相同类型对象之间的相似性搜索。此外，通过考虑网络中不同的链接路径，可以推导出不同的相似语义。因此，我们引入了基于元路径相似性的概念，其中元路径是由不同对象类型之间定义的一系列关系组成的路径（即元级别的结构路径）。无论用户是想在给定足够的领域知识的情况下明确指定路径组合，还是通过实验试验选择最佳路径，或者只是提供训练样例来学习它，元路径都构成了基于网络的相似度搜索引擎的公共基础。特别是，在元路径框架下，我们定义了一种名为PathSim的新颖相似度度量，它能够在网络中找到对等对象（例如，找到相似领域和相似声誉的作者），与基于随机行走的相似度度量相比，它在许多情况下更有意义。为了支持PathSim查询的快速在线查询处理，我们开发了一个有效的解决方案，该解决方案部分实现短元路径，然后将它们在线连接以计算top-k结果。在真实数据集上的实验证明了我们提出的范式的有效性和效率。
Similarity search is a primitive operation in database and Web search engines. With the advent of large-scale heterogeneous information networks that consist of multi-typed, interconnected objects, such as the bibliographic networks and social media networks, it is important to study similarity search in such networks. Intuitively, two objects are similar if they are linked by many paths in the network. However, most existing similarity measures are defined for homogeneous networks. Different semantic meanings behind paths are not taken into consideration. Thus they cannot be directly applied to heterogeneous networks. In this paper, we study similarity search that is defined among the same type of objects in heterogeneous networks. Moreover, by considering different linkage paths in a network, one could derive various similarity semantics. Therefore, we introduce the concept of meta path-based similarity, where a meta path is a path consisting of a sequence of relations defined between different object types (i.e., structural paths at the meta level). No matter whether a user would like to explicitly specify a path combination given sufficient domain knowledge, or choose the best path by experimental trials, or simply provide training examples to learn it, meta path forms a common base for a network-based similarity search engine. In particular, under the meta path framework we define a novel similarity measure called PathSim that is able to find peer objects in the network (e.g., find authors in the similar field and with similar reputation), which turns out to be more meaningful in many scenarios compared with random-walk based similarity measures. In order to support fast online query processing for PathSim queries, we develop an efficient solution that partially materializes short meta paths and then concatenates them online to compute top-k results. Experiments on real data sets demonstrate the effectiveness and efficiency of our proposed paradigm.