计算机科学

计算机科学 ›› 2019, Vol. 46 ›› Issue (10): 186-194.doi: 10.11896/jsjkx.19100530C

• 软件与数据库技术 • 上一篇    下一篇

面向局域检索的时变图数据存储与查询模型

赵萍1, 寿黎但1,2, 陈珂1,2, 陈刚1,2, 吴晓凡3   

  1. (浙江大学计算机科学与技术学院 杭州310027)1
    (浙江省大数据智能计算重点实验室(浙江大学) 杭州310027)2
    (网易(杭州)网络有限公司 杭州310051)3
  • 收稿日期:2018-07-15 修回日期:2018-09-25 出版日期:2019-10-15 发布日期:2019-10-21
  • 通讯作者: 陈珂(1977-),女,博士,副教授,硕士生导师,CCF会员,主要研究领域为时空数据库、数据挖掘以及数据隐私保护等,E-mail:chenk@zju.edu.cn。
  • 作者简介:赵萍(1992-),女,硕士,主要研究领域为查询处理、数据库优化等;寿黎但(1974-),男,博士,教授,博士生导师,CCF会员,主要研究领域为空间数据库、数据挖掘、数据可视化等;陈刚(1973-),男,博士,教授,博士生导师,主要研究领域为大数据管理;吴晓凡(1984-),男,博士,主要研究领域为大数据智能计算。
  • 基金资助:
    本文受国家重点研发计划项目(2017YFB1201001),国家自然科学基金项目(61672455),浙江省自然科学基金(LY18F020005)资助。

Storage and Query Model for Localized Search on Temporal Graph Data

ZHAO Ping1, SHOU Li-dan1,2, CHEN Ke1,2, CHEN Gang1,2, WU Xiao-fan3   

  1. (College of Computer Science and Technology,Zhejiang University,Hangzhou 310027,China)1
    (Key Laboratory of Big Data Intelligent Computing of Zhejiang Province (Zhejiang University),Hangzhou 310027,China)2
    (Netease (Hangzhou) Network Co.,Ltd,Hangzhou 310051,China)3
  • Received:2018-07-15 Revised:2018-09-25 Online:2019-10-15 Published:2019-10-21

PDF (PC)

792

摘要： 时变图数据是实体间相互关联、实体属性和实体间关系会发生频繁变化的图结构数据,适用于电子商务的商品与用户关系表示、包含时间维度的知识图谱构建、企业组织架构管理等场景。针对建立时变图数据通用存储检索方案的挑战,文中提出了一种面向局域检索的模型方案,基于图数据库高效的关系检索能力以及分布式键值数据库在存储与查询方面的优势,实现了通用的可提供丰富表达能力的图数据历史存储检索系统。实验证明,所提方案在历史属性存储上具备显著的优势。

关键词: 版本控制, 时变数据, 数据查询, 图数据库

Abstract: The temporal graph data is a graph structure data in which the entities are related to each other,and the entity attributes and the relationships between the entities frequently change.This model is applicable to product and user relationships representation in e-commerce,knowledge graphs that contains the history,and corporate organizational structure management.Aiming at the challenge of establishing a general storage scheme for time-varying graph data,this paper proposed a local-domain query based scheme for storing and retrieving time-varying graph data,which is based on the advantage of graph traversal on graph databases and the advantages of distributed key-value databases,achieving universal expression and provide rich expressions for storing graph data.Experiment results show that the system has significant advantages in the storage of historical attributes.

Key words: Data query, Graph database, Time-varying data, Version control

中图分类号: 

  • TP311.132.2
[1]ARENAS M,GUTIERREZ C,PÉREZ J.Foundations of RDF databases//Reasoning Web International Summer School.Berlin:Springer,2009:158-204.
[2]BERNERS-LEE T,HENDLER J,LASSILA O.The Semantic Web.Scientific American,2001,284(5):28-37.
[3]W3C.SPARQL query language for RDF[EB/OL].https://www.w3.org/TR/rdf-sparql-query/.
[4]BOLLACKER K,EVANS C,PARITOSH P,et al.Freebase:a Collaboratively Created Graph Database for Structuring Human Knowledge//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data.New York:ACM,2008:1247-1250.
[5]MAX V,GROZA T.SemVersion:An RDF-based ontology versioning system[C]//Proceedings of the IADIS International Conference WWW/Internet.2006.
[6]TICHY,WALTER F.RCS－a system for version control[J].Software:Practice and Experience,1985,15(7):637-654.
[7]CLAUDIUS H,BROCCO M,WÖRNDL W.Scalable Semantic Version Control for Linked Data Management[C]//LDQ@ ESWC.2015.
[8]YANNIS T,THEOHARIS Y,ANDREOU D.European Seman-tic Web Conference[M].Berlin:Springer,2008.
[9]IM D H,ZONG N,KIM E H,et al.A Hypergraph-based Storage Policy for RDF Version Management System//Procee-dings of the 6th International Conference on Ubiquitous Information Management and Communication.New York:ACM,2012:74-78.
[10]BARRASA J.RDF Triple Stores vs.Labeled Property Graphs:What’s the Difference”[R].Neo4j,2017.
[11]RENZO A,GUTIERREZ C.Survey of graph database models[J].ACM Computing Surveys (CSUR),2008,40(1):1.
[12]MILLER J J.Graph Database Applications and Concepts with Neo4j//Proceedings of the Southern Association for Information Systems Conference.Atlanta:AIS,2013, 2324(S36):141-147.
[13]IAN R,WEBBER J,EIFREM E.Graph databases [M].O’Reilly Media,Inc.,2013.
[14]MIAO Y S,et al.Immortalgraph:A system for storage and analysis of temporal graphs[J].ACM Transactions on Storage (TOS),2015,11(3):14.
[15]HUANG H X,et al.Tgraph:a temporal graph data management system[C]//Proceedings of the 25th ACM International on Conference on Information and Knowledge Management.ACM,2016.
[16]UDAYAN K,DESHPANDE A.Efficient snapshot retrieval over historical graph data[C]//2013 IEEE 29th International Conference on Data Engineering (ICDE).IEEE,2013.
[17]Neo Technology.Time-Based Versioned Graphs [EB/OL].iansrobinson.com/2014/05/13/time-based-versioned-graphs.
[18]Neo Technology.GraphGist:Network versions[EB/OL].neo4j.com/graphgist/network-versions.
[19]XU J,ZHANG Q Z,ZHAO X,et al.Survey on Dynamic Graph Pattern Matching Technologies.Journal of Software,2018,29(3):663-688.(in Chinese)
许嘉,张千桢,赵翔,等.动态图模式匹配技术综述.软件学报,2018,29(3):663-688.
[20]VIJITBENJARONK W D,LEE J,SUZUMURA T, et al. Sca-lable Time-Versioning Support for Property Graph Databases//2017 IEEE International Conference on Big Data.New York:IEEE,2017:1580-1589.
[21]SALIM J,VANSTEENBERGHE V.An empirical comparison of graph databases[C]//2013 International Conference on Social Computing (SocialCom).IEEE,2013.
[22]FLORIAN H,PEINL R.Performance of graph query languages:comparison of cypher,gremlin and native access in Neo4j[C]//Proceedings of the Joint EDBT/ICDT 2013 Workshops.ACM,2013.
[23]CLINTON G,TONG Z.Elasticsearch:The Definitive Guide:A Distributed Real-Time Search and Analytics Engine [M].O’Reilly Media,Inc.,2015.
[24]CARLSON,JOSIAH L.Redis in action[M].Manning Publications Co.,2013.
[25] ANTIREZ.Streams:a new general purpose data structure in Redis[EB/OL].http://antirez.com/news/114.
[26]RODRIGUEZ,MARKO A.The gremlin graph traversal ma-chine and language (invited talk)[C]//Proceedings of the 15th Symposium on Database Programming Languages.ACM,2015.
[27]MARCUS P,LEHNER W,RUDOLF M.Extending graph tra-versals with application logic [P].U.S.Patent Application No.14/820,357.
[28]LESKOVEC J,ADAMIC L A,HUBERMAN B A.The dyna-mics of viral marketing[J].ACM Transactions on the Web (TWEB),2007,1(1):5.
[1] 梁静茹, 鄂海红, 宋美娜.
基于属性图模型的领域知识图谱构建方法
Method of Domain Knowledge Graph Construction Based on Property Graph Model
计算机科学, 2022, 49(2): 174-181. https://doi.org/10.11896/jsjkx.210500076
[2] 黄梅根, 刘川, 杜欢, 刘佳乐.
基于知识图谱的认知诊断模型及其在教辅中的应用研究
Research on Cognitive Diagnosis Model Based on Knowledge Graph and Its Application in Teaching Assistant
计算机科学, 2021, 48(6A): 644-648. https://doi.org/10.11896/jsjkx.200700163
[3] 鄂海红, 韩鹏昊, 宋美娜.
关系型数据库向图数据库的转换方法
Conversion Method from Relational Database to Graph Database
计算机科学, 2021, 48(10): 140-144. https://doi.org/10.11896/jsjkx.201100073
[4] 秦东明, 喻剑, 张波, 赵勤.
基于分布式无共享架构的海量数据并行查询平台
Massive Data Parallel Query Platform Based on Distributed Shared-nothing Architecture
计算机科学, 2019, 46(4): 44-49. https://doi.org/10.11896/j.issn.1002-137X.2019.04.007
[5] 梁俊斌, 马方强, 蒋婵.
动态无线传感网中数据查询技术的研究进展
Research Progress on Data Query Technology in Dynamic Wireless Sensor Networks
计算机科学, 2019, 46(11): 41-48. https://doi.org/10.11896/jsjkx.181202258
[6] 张宇霞.
Mozilla项目缺陷修复追踪关系研究
Study on Bug-fixed Traceability of Mozilla Project
计算机科学, 2017, 44(4): 21-23. https://doi.org/10.11896/j.issn.1002-137X.2017.04.005
[7] 姜人和,郑晓梅,朱晓倩,潘敏学,张天.
一种基于UML关系的Java代码库构造方法
Method of Java Code Repository Construction Based on UML Relationship
计算机科学, 2017, 44(11): 69-79. https://doi.org/10.11896/j.issn.1002-137X.2017.11.011
[8] 邓晓军,欧阳旻,李玉龙.
基于虚拟环的无线传感网节能数据存储与查询机制
Energy-efficient Wireless Sensor Network Data Storage and Query Mechanism Based on Virtual Ring
计算机科学, 2015, 42(8): 132-135.
[9] 武彤，赵雪，赵洵.
动态更新实物化视图以提高OLAP查询效率
Dynamically Update Materialized View in Order to Improve the Efficiency of OLAP Queries
计算机科学, 2012, 39(Z6): 315-317.
[10] 石高涛 赵增华.
移动多Sink传感器网络数据查询和收集技术研究现状

计算机科学, 2009, 36(5): 12-15.
[11] .
EIR：具有超级结点的非结构化P2P中多维数据搜索框架研究

计算机科学, 2007, 34(5): 59-61.
[12] 姚佳丽 张坤龙 王珊.
基于P2P的数据索引与查询

计算机科学, 2005, 32(3): 69-72.
[13] 刘柏嵩 高济.
本体演化管理研究

计算机科学, 2004, 31(5): 9-12.
[14] 王新军 洪晓光 王海洋 马绍汉.
利用领域知识改进数据仓库中知识发现查询的效率

计算机科学, 2004, 31(2): 123-125.
[15] 曹付元 梁吉业.
基于SQL语言的粗糙数据查询

计算机科学, 2004, 31(2): 66-68.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发