检索结果-南通市图书馆

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

图数据隐私保护可达性查询算法研究

计算机工程 2015年第2期41卷 167-172页

作者：尹树祥靳婷复旦大学计算机科学技术学院智能信息处理重点实验室上海200433

数据库领域越来越多的数据通过图的结构进行存储,随着图数据规模的快速增长和云计算的兴起,数据拥有者希望将数据外包给具有强大计算能力的服务商为其客户提供查询服务。为解决数据库中的可达性查询问题,提出一种隐私保护的可达性索引... 详细信息

数据库领域越来越多的数据通过图的结构进行存储,随着图数据规模的快速增长和云计算的兴起,数据拥有者希望将数据外包给具有强大计算能力的服务商为其客户提供查询服务。为解决数据库中的可达性查询问题,提出一种隐私保护的可达性索引和查询方法。对原始的2-hop索引构建方法进行优化,设计max ISCover启发式方法,给出根据人工节点添加算法建立pp-2-hop索引的unify IS和unify LS算法,并在此基础上,给出基于密文域的优化可达性查询方法。实验结果表明,基于max ISCover优化方法和unify IS算法建立的索引大小相比于基于原始2-hop索引的方法减小1个-2个数量级。

关键词：图数据可达性查询 2-hop索引隐私保护人工节点查询服务

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

时态二部图上k步可达查询算法研究

时态二部图上k步可达查询算法研究

作者：段佳俊东华大学

学位级别：硕士

给定时态二部图,可达性查询用于回答图中两点间是否存在满足条件的路径。时态二部图上的可达查询问题是图数据管理领域中一个基础研究问题。针对时态二部图上的可达查询处理,研究者提出了基于时间区间的可达查询处理算法,用于回答在给... 详细信息

给定时态二部图,可达性查询用于回答图中两点间是否存在满足条件的路径。时态二部图上的可达查询问题是图数据管理领域中一个基础研究问题。针对时态二部图上的可达查询处理,研究者提出了基于时间区间的可达查询处理算法,用于回答在给定时间区间内两点间是否存在可达路径。该方法存在的问题体现在两方面:(1)不能回答路径长度是否满足k步约束;(2)存在假阴性(false negative)的问题。本文针对以上问题进行研究,提出了相应的查询算法,解决了已有方法存在的问题。具体研究内容如下:首先,针对不能回答时态图上长度约束的可达查询问题,提出针对时间区间和路径长度约束的可达查询索引TBPK及相应的查询算法。TBPK索引基于2-hop思想,维护了每个点到其他可达顶点对应路径的时间区间及长度信息。查询处理时只需扫描两个查询点对应的索引标签即可得到结果,避免了昂贵的图遍历操作,可有效提高查询处理效率。提出了TBPK索引的构建算法,该算法使用特定的剪枝策略,可以在快速构建索引的同时降低索引规模。其次,分析并总结了现有方法存在假阴性问题的本质原因,并提出基于图转化的解决方案。该方案由两步组成。第一步,构建针对原始时态二部图的转化图。转化后的图保留了时态二部图上可达路径的时间区间,同时避免了时态二部图上进行查询时因无法重复访问造成的假阴性问题。第二步,在转化图的基础上,提出在线查询算法以及基于GTRK索引的查询算法。针对GTRK索引的构建问题,提出了高效索引构建算法,该算法基于贪心思想,避免了冗余索引项的产生,减少了索引构建的时间。针对时态二部图的更新问题,给出了高效的索引更新策略。最后,在16个数据集进行了相关的实验验证。实验结果从索引规模,可达比例,更新时间,索引构建时间,边减少比例,查询时间等6个角度,对本文提出方法的有效性和高效性进行了验证。

关键词：时态二部图图转化算法 k可达查询算法 2-hop索引

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于权值约束的k步可达性查询算法研究

基于权值约束的k步可达性查询算法研究

作者：余升东华大学

学位级别：硕士

可达性查询是数据图上的基本操作之一,旨在回答图中两个顶点是否存在一条路径,在生物网络、通信网络、社交网络等领域应用广泛。实际中,用户更关注可达性查询是否满足特定的约束条件,例如,两点之间的路径长度或者路径中边上的权值约束... 详细信息

可达性查询是数据图上的基本操作之一,旨在回答图中两个顶点是否存在一条路径,在生物网络、通信网络、社交网络等领域应用广泛。实际中,用户更关注可达性查询是否满足特定的约束条件,例如,两点之间的路径长度或者路径中边上的权值约束。已有方法对这两种约束独立进行研究,无法处理两种约束同时存在的情况。对此,本文研究同时支持权值约束和路径长度约束的可达性查询处理算法。具体研究内容如下:首先,本文定义了权值约束的k步可达性查询问题:在图中查找两个查询点之间是否存在一条满足长度及权值区间约束的可达路径。在此基础上,提出基于2-hop思想的高效索引构建方法WKRI。该索引为图中每个顶点预先生成包含长度及权值区间的可达路径信息索引标签,基于该信息可实现高效查询处理。WKRI方法在索引构建过程中提供顶点选择策略及两种有效的剪枝策略,减少无效遍历,加快索引构建时间,使构建得到的为不包含冗余路径信息的最小索引。其次,为了进一步减小索引规模并提升查询效率,提出基于最小点覆盖的索引优化方法WKRI+。WKRI+方法首先求得图的最小点覆盖,对最小点覆盖中的顶点进行剪枝处理,然后构建得到两种索引WTH及WTH*。其中,WTH索引提供最快的查询效率,WTH*索引提供最小的索引规模。最后,以索引构建时间、索引规模及查询响应时间三个维度作为评价标准,并改变权值集规模大小,在15个真实数据集进行实验。实验结果验证了在回答权值约束的k步可达性查询时,本文所提出的解决方案具有可行性与高效性。

关键词：加权无向图权值约束的k步可达性查询 2-hop索引最小点覆盖

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

大规模属性网络中的可达性问题研究

大规模属性网络中的可达性问题研究

作者：傅仙明浙江工商大学

学位级别：硕士

现实世界中,实体与实体之间的各种联系都可以用相应复杂网络来建模和表示,例如用户之间的交互关系可以建模为社交网络,蛋白质之间的相互作用可以建模为蛋白质网络,基因之间的调控关系可以建模为生物网络。随着科技的进步和社会的发展,... 详细信息

现实世界中,实体与实体之间的各种联系都可以用相应复杂网络来建模和表示,例如用户之间的交互关系可以建模为社交网络,蛋白质之间的相互作用可以建模为蛋白质网络,基因之间的调控关系可以建模为生物网络。随着科技的进步和社会的发展,事物间的联系变得更加紧密,相应的网络规模也不断扩大。为了对这些网络进行研究,我们通常会将网络抽象为数据结构中的图结构。其中,网络中的实体对应图中的节点,实体之间的联系对应图中节点之间的边。作为图分析中的一个基本问题,可达性查询已经被广泛应用于多个计算机科学领域。在现实情况中,实体之间的联系往往是多重的,即实体之间的联系（即图结构中的边）会包含多种属性,这种网络也被称为多属性网络。而现有的针对可达性查询的工作只考虑了图中边只有一种属性或者没有属性的情况。因此,目前的可达性模型并不适用于在具有多属性边的属性图上进行可达性查询。此外,属性网络中关于可达性查询的研究大多是基于给定的约束条件来确定节点间的可达性。然而许多实际应用的目标是找到使两个节点可达的最小属性集合,而不是判断指定约束条件下的可达性。因此,本文首先提出了两种针对多属性图的可达性模型,即必要属性约束可达性模型和存在属性约束可达性模型,并针对两个可达性模型提出了相应的可达性查询问题。随后,为了加快可达性查询的速度,本文基于2-hop cover的思想针对两个可达模型提出了相应的索引算法,并根据索引的性质提出了基于节点度的优化策略和基于属性数量的优化策略以加快索引的构建。之后,本文提出了属性网络中的最小可达属性集合问题,并设计了基于热点的算法和自底向上的算法对问题进行求解。对于多属性网络中的可达性问题和属性网络中的最小可达属性集合问题,我们分别在多个真实的数据集上进行了实验的对比,根据不同类型查询的响应时间和不同节点度分布查询的响应时间对本文所提出算法的高效性进行验证,根据不同属性数量下查询的响应时间和不同节点数量下查询的响应时间对本文所提出算法的可扩展性进行验证。

关键词：属性网络可达性查询 2-hop索引

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

大图上基于权值约束的可达性查询

大图上基于权值约束的可达性查询

作者：成梦佳东华大学

学位级别：硕士

可达性查询用于研究图中给定源点和终点之间是否存在一条可达路径,基于权值约束的可达性查询是可达性查询的其中一种,用于回答给定两个查询的顶点之间是否存在一条路径,并且其每条边上的权值都满足给定的约束条件。相较于传统的可达性查... 详细信息

可达性查询用于研究图中给定源点和终点之间是否存在一条可达路径,基于权值约束的可达性查询是可达性查询的其中一种,用于回答给定两个查询的顶点之间是否存在一条路径,并且其每条边上的权值都满足给定的约束条件。相较于传统的可达性查询,权值约束的可达性查询在实际生活中更有意义,如基因蛋白质生物网络、通信网络、道路交通网络等,这些图的边上往往会记录包含特定信息的数据以描述顶点之间关联性的强弱程度,而这种关联的约束信息无法用传统可达查询来体现,只能通过基于权值约束的可达查询处理。现有的基于权值约束可达性查询的相关算法尽管查询响应时间较快,但是其构建的索引规模太大,无法在内存有限的情况下,处理规模较大的数据图。针对以上问题,本文提出三种高效索引来支持在有限内存的环境下高效处理大规模数据图上的权值约束可达查询。本文的研究内容如下:首先,提出一种基于加权图的2-hop索引及其构建算法。该算法基于顶点的度来确定顶点的处理顺序,然后基于该顺序来构建加权图的2-hop索引。该方法的基本思想是将加权图上的权值约束可达查询转换为基于顶点标签的集合交集操作。考虑到基于加权图来构建2-hop索引的时间和空间代价过高,进一步提出基于最小和最大生成树的2-hop索引方法。该方法首先构建原图的最小和最大生成树,然后按照度从大到小的顺序在生成树上构建索引,从而减小构建索引的时间和空间代价。其次,考虑到顶点的处理顺序会极大影响2-hop索引的规模和构建时间,提出优化的2-hop索引构建策略。和以上提出的2-hop索引方法不同,优化方法是在构建2-hop索引的过程中,根据顶点划分子图的变化情况来动态确定下一个最适合处理的顶点,以此来减小2-hop索引的规模和构建时间。具体来说,该方法在生成树的基础上,通过找树的中间结点作为hop点来构建2-hop索引。之后删除该点,可得到若干子树,对每棵子树重复以上操作。最后,基于多个真实数据集进行实验测试,以索引大小、索引构建时间和查询响应时间为指标,对本文提出的算法的高效性进行了验证。实验结果表明,基于大度顶点的优化策略和基于中间结点的优化策略都能够有效降低索引的规模大小,并且后者具有更好的查询效率。

关键词：加权图 2-hop索引权值约束可达性查询生成树中间结点

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图上可达性查询的隐私保护方法研究

图上可达性查询的隐私保护方法研究

作者：尹树祥复旦大学

学位级别：硕士

在数据库领域中,越来越多的数据通过图结构的方式进行存储,比如社交网络、生物信息学以及XML数据等。针对这些图数据的查询,很多时候需要更强大的计算机资源进行处理。为解决该问题,比较经济实用的方法是将这些数据外包给一个第三方的... 详细信息

在数据库领域中,越来越多的数据通过图结构的方式进行存储,比如社交网络、生物信息学以及XML数据等。针对这些图数据的查询,很多时候需要更强大的计算机资源进行处理。为解决该问题,比较经济实用的方法是将这些数据外包给一个第三方的服务提供商(Service Provider, SP),让它去为我们提供查询服务。然而,SP并不是一直可以值得信赖,它可能对外包到它上面的数据比较感兴趣,以获得商业利益。除此之外,数据拥有者(Data Owner)不希望他的数据被不信任的人获取,同时查询者也不希望他的查询内容被他人得知。可达性查询作为数据库领域一个最基础的问题,本文针对可达性查询过程中可能产生的隐私问题,提出了图数据上可达性查询的隐私保护方法。我们的隐私保护目标主要包括：客户端查询信息和图数据结构信息。针对我们提出的隐私保护目标,我们在基于传统的2-hop索引方法上,根据图数据不同的稀疏性质,提出了pp-2-hop和·ppm-2-hop两种索引方法。在这两种索引方法中,我们对原始的2-hop索引通过不同的添加人工代理中心点策略,使得对于任何的可达性查询,其查询结果大小一致,进而SP无法从相同大小的查询结果中获取关于查询的信息。同时,我们通过对索引进行加密,使得所有的可达性查询在密文域中进行,进一步阻止SP对索引内容进行推理。本文对两种索引算法分别在基于密文攻击和基于集合大小的攻击模式下进行安全性分析。最后,分别对两种索引算法在合成数据集和真实数据集上进行实验研究。

关键词：图数据可达性查询 2-hop索引隐私保护查询服务