-
题名图数据隐私保护可达性查询算法研究
被引量：2
- 1
-
-
作者
尹树祥
靳婷
-
机构
复旦大学计算机科学技术学院智能信息处理重点实验室
-
出处
《计算机工程》
CAS
CSCD
北大核心
2015年第2期167-172,共6页
-
文摘
数据库领域越来越多的数据通过图的结构进行存储,随着图数据规模的快速增长和云计算的兴起,数据拥有者希望将数据外包给具有强大计算能力的服务商为其客户提供查询服务。为解决数据库中的可达性查询问题,提出一种隐私保护的可达性索引和查询方法。对原始的2-hop索引构建方法进行优化,设计max ISCover启发式方法,给出根据人工节点添加算法建立pp-2-hop索引的unify IS和unify LS算法,并在此基础上,给出基于密文域的优化可达性查询方法。实验结果表明,基于max ISCover优化方法和unify IS算法建立的索引大小相比于基于原始2-hop索引的方法减小1个-2个数量级。
-
关键词
图数据
可达性查询
2-hop索引
隐私保护
人工节点
查询服务
-
Keywords
graph data
reachability query
2-hop index
privacy protection
artificial node
query service
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名标签约束图上的k步可达性查询
- 2
-
-
作者
杜明
邢瑞萍
周军锋
谭玉婷
-
机构
东华大学计算机科学与技术学院
-
出处
《计算机科学》
CSCD
北大核心
2022年第12期283-292,共10页
-
基金
上海市自然科学基金(20ZR1402700)
国家自然科学基金(61472339,61572421,61272124)。
-
文摘
标签约束图上的k步可达性查询问题,回答了在一个标签约束图上两点之间是否存在一条长度不大于k的路径并且这条路径上的标签都在用户给定的标签集中的问题。标签约束图上的k步可达性查询问题在现实中有着广泛的应用,然而现有算法无法直接回答这个问题。因此,首先提出LK2H算法。LK2H算法主要包括构建索引和查询两个步骤。第一步是给图上的所有顶点构建一组包含k和标签信息的2-Hop索引,第二步是基于构建好的索引进行查询。在查询时,为了尽可能地为用户返回更多的信息,LK2H算法优化了一类不可达查询的返回结果:当用户无法明确所有的标签类型,不能给出完整的标签约束,进而导致查询结果为不可达时,将完整的标签集返回给用户。其次,提出优化算法LK2H+。LK2H+算法通过构建部分顶点的2-Hop索引进一步缩减索引大小和索引的构建时间,并基于构建好的索引进行查询。查询时,需要对顶点按照是否构建了索引进行分类讨论。最后,基于15个真实数据集进行测试。实验结果表明,LK2H算法和LK2H+算法都可以高效地解决标签约束图上的k步可达性查询问题。
-
关键词
标签约束图
k步可达性查询
2-hop索引
顶点覆盖
图论
-
Keywords
Label-constrained graph
k-step reachability query
2-hop index
Vertex cover
Graph theory
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名一种基于悬挂顶点关联索引的最短路径查询算法
被引量：7
- 3
-
-
作者
陈伟
楼志斌
杨清章
-
机构
河北环境工程学院信息工程系
上海科学院
燕山大学信息科学与工程学院
-
出处
《燕山大学学报》
CAS
北大核心
2018年第3期265-271,共7页
-
基金
国家自然科学基金资助项目(61472339
61572421)
河北省高等学校科学技术研究重点项目(ZD2018048)
-
文摘
最短路径查询是图数据查询中的热点问题。针对现有的"索引+查询"方法存在的查询效率低下且扩展性差等问题,本文提出了悬挂顶点关联索引策略,即先对度为1的顶点构建顶点关联索引,再对其他顶点构建2-hop标签索引,并依此提出了相应的最短路径查询算法。本文提出的索引策略降低了索引规模,减少了构建索引时间,使得最短路径查询算法的效率和扩展性得到了改善。最后,通过对11个真实的数据集进行实验,从索引构建时间、索引规模大小、查询时间等方面验证了本文方法的高效性。
-
关键词
图
最短路径查询
悬挂顶点
顶点关联索引
2-hop标签索引
-
Keywords
graph
shortest path query
pendant vertex
vertex-related index
2-hop label index
-
分类号
TP392
[自动化与计算机技术—计算机应用技术]
-
-
题名基于顶点关联索引的最短路径查询算法研究
被引量：1
- 4
-
-
作者
余靖
杨清章
-
机构
燕山大学信息科学与工程学院
河北省计算机虚拟技术与系统集成重点实验室
河北省软件工程重点实验室
-
出处
《高技术通讯》
北大核心
2017年第11期899-906,共8页
-
基金
国家自然科学基金(61572421)资助项目
-
文摘
研究了图查询中的最短路径查询问题,针对现有的查询算法存在构建索引时间长和索引规模庞大所导致的低效性和扩展性问题,在索引构建方面提出了顶点关联索引策略。对度数为1的顶点构建顶点关联索引,对其他顶点构建2-hop标签索引,通过减少冗余数据存储和图的遍历次数,降低索引规模以减少构建索引时间。基于所提出的查询策略,给出了基于顶点关联关系和2-hop标签的最短路径查询算法。
-
关键词
图模型
最短路径查询
顶点关联索引
2-hop标签索引
-
Keywords
graphical model, shortest path query, vertex-related index, 2-hop label index
-
分类号
TP311.13
[自动化与计算机技术—计算机软件与理论]
-
