Computer Science ›› 2019, Vol. 46 ›› Issue (10): 186-194.doi: 10.11896/jsjkx.19100530C

• Software & Database Technology • Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] LIANG Jing-ru, E Hai-hong, Song Mei-na. Method of Domain Knowledge Graph Construction Based on Property Graph Model [J]. Computer Science, 2022, 49(2): 174-181.
[2] HUANG Mei-gen, LIU Chuan, DU Huan, LIU Jia-le. Research on Cognitive Diagnosis Model Based on Knowledge Graph and Its Application in Teaching Assistant [J]. Computer Science, 2021, 48(6A): 644-648.
[3] E Hai-hong, HAN Peng-hao, SONG Mei-na. Conversion Method from Relational Database to Graph Database [J]. Computer Science, 2021, 48(10): 140-144.
[4] QIN Dong-ming, YU Jian, ZHANG Bo, ZHAO Qin. Massive Data Parallel Query Platform Based on Distributed Shared-nothing Architecture [J]. Computer Science, 2019, 46(4): 44-49.
[5] LIANG Jun-bin, MA Fang-qiang, JIANG Chan. Research Progress on Data Query Technology in Dynamic Wireless Sensor Networks [J]. Computer Science, 2019, 46(11): 41-48.
[6] ZHANG Yu-xia. Study on Bug-fixed Traceability of Mozilla Project [J]. Computer Science, 2017, 44(4): 21-23.
[7] JIANG Ren-he, ZHENG Xiao-mei, ZHU Xiao-qian, PAN Min-xue and ZHANG Tian. Method of Java Code Repository Construction Based on UML Relationship [J]. Computer Science, 2017, 44(11): 69-79.
[8] DENG Xiao-jun, OU-YANG Min and LI Yu-long. Energy-efficient Wireless Sensor Network Data Storage and Query Mechanism Based on Virtual Ring [J]. Computer Science, 2015, 42(8): 132-135.
[9] CHEN Hai-yan. Design and Realization of Distributed Big Data Management System [J]. Computer Science, 2014, 41(Z11): 393-395.
[10] . Dynamically Update Materialized View in Order to Improve the Efficiency of OLAP Queries [J]. Computer Science, 2012, 39(Z6): 315-317.
[11] SHI Gao-tao ZHAO Zeng-hua (School of Computer Science and Technology, Tianjin University, Tianjin 300072, China). [J]. Computer Science, 2009, 36(5): 12-15.
[12] . [J]. Computer Science, 2007, 34(5): 59-61.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!