Show simple item record

dc.contributor.authorZhu, Haohan
dc.date.accessioned2016-07-14T17:14:58Z
dc.date.available2016-07-14T17:14:58Z
dc.date.issued2016
dc.identifier.urihttps://hdl.handle.net/2144/17056
dc.description.abstractGraphs that evolve over time are called temporal graphs. They can be used to describe and represent real-world networks, including transportation networks, social networks, and communication networks, with higher fidelity and accuracy. However, research is still limited on how to manage large scale temporal graphs and execute queries over these graphs efficiently and effectively. This thesis investigates the problems of temporal graph data management related to node and edge sequence queries. In temporal graphs, nodes and edges can evolve over time. Therefore, sequence queries on nodes and edges can be key components in managing temporal graphs. In this thesis, the node sequence query decomposes into two parts: graph node similarity and subsequence matching. For node similarity, this thesis proposes a modified tree edit distance that is metric and polynomially computable and has a natural, intuitive interpretation. Note that the proposed node similarity works even for inter-graph nodes and therefore can be used for graph de-anonymization, network transfer learning, and cross-network mining, among other tasks. The subsequence matching query proposed in this thesis is a framework that can be adopted to index generic sequence and time-series data, including trajectory data and even DNA sequences for subsequence retrieval. For edge sequence queries, this thesis proposes an efficient storage and optimized indexing technique that allows for efficient retrieval of temporal subgraphs that satisfy certain temporal predicates. For this problem, this thesis develops a lightweight data management engine prototype that can support time-sensitive temporal graph analytics efficiently even on a single PC.en_US
dc.language.isoen_USen_US
dc.subjectComputer scienceen_US
dc.subjectGraph databaseen_US
dc.subjectIndexing and queryingen_US
dc.subjectSimilarity learningen_US
dc.subjectTime-series analysisen_US
dc.titleSequence queries on temporal graphsen_US
dc.typeThesis/Dissertation
dc.date.updated2016-06-21T19:35:31Z
etd.degree.nameDoctor of Philosophyen_US
etd.degree.leveldoctoralen_US
etd.degree.disciplineComputer Scienceen_US
etd.degree.grantorBoston Universityen_US


This item appears in the following Collection(s)

Show simple item record