大规模图中可扩展的可达性查询高效处理方法研究

发布时间：2017-09-29 05:00

  本文关键词：大规模图中可扩展的可达性查询高效处理方法研究

  更多相关文章： 可达性查询 遍历树 图划分 大规模图数据处理

【摘要】：随着复杂多元社交信息网络的广泛应用,关联数据对于人们周围的现实世界和社交网络而言具有越来越重要的地位。如Facebook拥有十亿多的用户。图,作为一种通用化的数据结构,对于表达复杂的结构化和半结构化数据,例如wikipedia,twitter,free-base等社交网络数据,具有重要意义。其中一个重要应用是,如何在一个给定的大规模图中高效地查询两个给定结点之间是否存在路径,即可达性查询处理。然而随着图数据的持续爆炸式增长,传统方法由于存储和时间局限性,很大程度上限制了它们在大规模图数据中的应用。因此,如何保证在拥有紧凑存储结构的前提下,以更高效的时间解决大规模图数据可达性问题,依然具有极大挑战性。基于遍历树图划分和连续重编码的索引策略Interval-Index,提出了一种拥有紧凑存储结构且能保证高效查询效率的大规模图索引。Interval-Index索引技术通过图划分提高了图处理的局部性和并行性,并在划分基础上对大规模图数据的存储结构进行设计,确保索引结构具有较高压缩比。为了提高数据访问的顺序性,方便建立高效索引,Interval-Index对每一个遍历树分区进行连续重编码。同时重编码策略使得后续基于变长字节的邻接表压缩具有更高的压缩效率。利用基于遍历树生成图的索引结构,可以通过二分查找实现对结点快速定位,提高了查询处理速率。此外,Interval-Index采用mmap虚拟内存技术实现对数据的按需调入,提高了内存利用率和数据载入效率。通过对多种真实图和合成图在可达性查询处理上的存储性能和速度性能方面的测试。Interval-Index方法在存储空间上比Feline至少降低了23%,在查询处理时间上比Feline至降低了20%。实验表明,随着数据集大小的增长,Interval-Index在存储空间和查询处理时间上都大致呈亚线性增长;相对而言,Feline的扩展性则较差,尤其是在查询处理时间方面相当逊色于Interval-Index。
【关键词】：可达性查询 遍历树 图划分 大规模图数据处理
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-9
• 1 绪论9-20
• 1.1 问题提出9-10
• 1.2 国内外研究现状10-18
• 1.3 研究内容18-19
• 1.4 文章框架结构19-20
• 2 大规模图数据可达性索引Interval-Index总体设计20-27
• 2.1 相关定义20-23
• 2.2 Interval-Index整体设计思路23-25
• 2.3 Interval-Index处理流程25-26
• 2.4 本章小结26-27
• 3 基于遍历树划分的可达性索引Interval-Index27-44
• 3.1 基于遍历树的图划分27-35
• 3.2 重编码遍历树35-37
• 3.3 Interval-Index索引构建37-40
• 3.4 邻接表压缩存储40-42
• 3.5 结点的快速定位42
• 3.6 本章小结42-44
• 4 实验与分析44-52
• 4.1 测试环境44
• 4.2 测试数据集与测试方法44-46
• 4.3 性能测试46-49
• 4.4 扩展性能测试49-50
• 4.5 分析与总结50
• 4.6 本章小结50-52
• 5 总结与展望52-54
• 致谢54-56
• 参考文献56-60
• 附录1 攻读学位期间被录用的期刊论文60-61
• 附录2 攻读学位期间申请的软件著作版权61

【相似文献】

中国期刊全文数据库 前10条

1 林宗振;;关于均匀钱币投掷过程的可达性[J];暨南理医学报(理科专版);1985年03期

2 许世蒙,张玉忠;有交易费的折算资产优化性质和可达性[J];控制理论与应用;2002年01期

3 李平华,陆玉麒;可达性研究的回顾与展望[J];地理科学进展;2005年03期

4 贾鹏;刘瑞菊;杨忠振;;基于陆域和空域运输系统的空港可达性评价方法研究[J];经济地理;2013年06期

5 姜海宁;谭石柳;;轨道交通建设对金华城镇可达性格局的影响[J];浙江师范大学学报(自然科学版);2014年02期

6 刘俊;陆玉麒;;江苏省公路交通网络可达性评价研究[J];南京师大学报(自然科学版);2008年03期

7 刘志林;王茂军;;北京市职住空间错位对居民通勤行为的影响分析——基于就业可达性与通勤时间的讨论[J];地理学报;2011年04期

8 蒋晓威;曹卫东;罗健;朱胜清;唐云云;;安徽省公路网络可达性空间格局及其演化[J];地理科学进展;2012年12期

9 刘俊;陆玉麒;孟德友;;基于不同指标的公路交通网络可达性评价——以江苏省为例[J];工业技术经济;2009年02期

10 袁立科;张宗益;;创新系统的区域可达性研究[J];科研管理;2007年01期

中国重要会议论文全文数据库 前10条

1 苗梅;Gerhard Weber;;推广可达性[A];第四届和谐人机环境联合学术会议论文集[C];2008年

2 吕斌;张纯;陈天鸣;;城市低收入群体的就业可达性变化研究:以北京为例[A];多元与包容——2012中国城市规划年会论文集(13.城市规划管理)[C];2012年

3 裴玉龙;盖春英;;公路网络可达性研究[A];科技、工程与经济社会协调发展——中国科协第五届青年学术年会论文集[C];2004年

4 尹海伟;徐建刚;祁毅;;上海公园空间可达性与公平性分析[A];中国地理学会2007年学术年会论文摘要集[C];2007年

5 张莉;陆玉麒;赵元正;;基于可达性的长江三角洲城市一日交流圈的动态变化研究[A];地理学核心问题与主线——中国地理学会2011年学术年会暨中国科学院新疆生态与地理研究所建所五十年庆典论文摘要集[C];2011年

6 孟德友;范况生;高超;;铁路客运提速前后省际可达性及空间格局分析[A];中国地理学会百年庆典学术论文摘要集[C];2009年

7 刘志林;王茂军;;北京市职住空间错位对居民通勤行为的影响分析——基于就业可达性与通勤时间的讨论[A];中国地理学会百年庆典学术论文摘要集[C];2009年

8 张宇;张英杰;张晓东;郑猛;;北京市区位可达性对房价影响分析[A];规划创新：2010中国城市规划年会论文集[C];2010年

9 朱琛;孙姗珊;;城市不同居住区位群体就业可达性差异研究——以上海市为例[A];城市时代，，协同规划——2013中国城市规划年会论文集（07-居住区规划与房地产）[C];2013年

10 杨育军;;可达性评价方法的比较:一种基于GIS的实证方法[A];中国地理信息系统协会第八届年会论文集[C];2004年

中国硕士学位论文全文数据库 前10条

1 丁振;既有路网下基于中小城市的快速通道网布局研究[D];西南交通大学;2015年

2 彭\~\~;基于区间标记索引的可达性查询设计及其在外包数据库中的应用[D];哈尔滨工业大学;2014年

3 薛鹏;图数据上可达性查询关键技术研究[D];东北大学;2014年

4 李建新;基于可达性的南昌市区域空间效应研究[D];江西师范大学;2015年

5 刘红;基于老年人游憩特征的长沙市公园可达性研究[D];湖南师范大学;2015年

6 王于楠;基于公路可达性的青海省人口时空格局演变研究[D];青海师范大学;2016年

7 李U

本文编号：940065