文件名称:
2014-博士论文-Subgraph search for dynamic graphs
开发工具:
文件大小: 4mb
下载次数: 0
上传时间: 2015-07-28
详细说明： Subgraph search is the problem of searching a data graph for the occurrences of another graph, typically referred to as the query or pattern graph. This thesis is dedicated to studying a specific class of subgraph search, named subgraph isomorphism for dynamic graphs,i.e., graphs that are evolving over time. Subgraph isomorphism is a well studied NP-complete problem in computer science. It requires finding a bijective mapping between the vertices in the query graph and the data graph so that if two vertices are neighbors in the query graph, their mapped counterparts are neighbors in the data graph as well. Our research on dynamic graphs is motivated by large-scale graph data sources such as social media and cyber-security where applications continuously produce prodigious amounts of data. This thesis makes three major contributions. We begin with proposing a new subgraph isomorphism algorithm for dynamic graphs and a novel data structure, namely the Subgraph Join-Tree (SJ-Tree) to support the algorithm. Next, we demonstrate how the statistics of the graph stream can be leveraged to produce the best-performing SJ-Tree for a given query graph. We propose a metric for estimating the selectivity of a graph query and demonstrate its use to reason about the relative performance of different query execution strategies. Our observations are supported by experiments on multiple real-world data sources drawn from online news, social media and network traffic. Our experiments demonstrate speedups by 10-100 times over existing approaches. Finally, we propose a new algorithm and supporting data structures to implement the aforementioned dynamic graph search algorithm on a distributed system. As a secondary contribution, we demonstrate how the novel ideas from the graph search paradigm can be applied to discover patterns in dynamic graphs. The thesis concludes with presentation of real-world use cases from three different application domains. ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
