基本信息来源于合作网站,原文需代理用户跳转至来源网站获取       
摘要:
Answering reachability queries is one of the fundamental graph operations.Existing approaches either accelerate index construction by constructing an index that covers only partial reachability relationship,which may result in performing cost traversing operation when answering a query;or accelerate query answering by constructing an index covering the complete reachability relationship,which may be inefficient due to comparing the complete node labels.We propose a novel labeling scheme,which covers the complete reachability relationship,to accelerate reachability queries processing.The idea is to decompose the given directed acyclic graph(DAG)G into two subgraphs,G1 and G2.For G1,we propose to use topological labels consisting of two integers to answer all reachability queries.For G2,we construct 2-hop labels as existing methods do to answer queries that cannot be answered by topological labels.The benefits of our method lie in two aspects.On one hand,our method does not need to perform the cost traversing operation when answering queries.On the other hand,our method can quickly answer most queries in constant time without comparing the whole node labels.We confirm the efficiency of our approaches by extensive experimental studies using 20 real datasets.
内容分析
关键词云
关键词热度
相关文献总数  
(/次)
(/年)
文献信息
篇名 An Optimized Labeling Scheme for Reachability Queries
来源期刊 计算机、材料和连续体(英文) 学科 数学
关键词 DAG COMPUTING DETECTION REACHABILITY QUERIES PROCESSING
年,卷(期) 2018,(5) 所属期刊栏目
研究方向 页码范围 267-283
页数 17页 分类号 O15
字数 语种
DOI
五维指标
传播情况
(/次)
(/年)
引文网络
引文网络
二级参考文献  (0)
共引文献  (0)
参考文献  (0)
节点文献
引证文献  (0)
同被引文献  (0)
二级引证文献  (0)
2018(0)
  • 参考文献(0)
  • 二级参考文献(0)
  • 引证文献(0)
  • 二级引证文献(0)
研究主题发展历程
节点文献
DAG
COMPUTING
DETECTION
REACHABILITY
QUERIES
PROCESSING
研究起点
研究来源
研究分支
研究去脉
引文网络交叉学科
相关学者/机构
期刊影响力
计算机、材料和连续体(英文)
月刊
1546-2218
江苏省南京市浦口区东大路2号东大科技园A
出版文献量(篇)
346
总下载数(次)
4
总被引数(次)
0
论文1v1指导