In many real-world applications, the underlying data can be modeled as graphs. Querying graph data involves four main building blocks: the query semantics, the query parameters, the underlying graph data, and the output. When handling graph queries, changes can be made on the input parameters, the input graph, or the output. For example, modern graphs are dynamically changing, and bring challenges to the efficiency of querying algorithms. Also, query rewriting techniques are developed to modify query parameters, so that the output matches the user’s intent.

In this thesis, we study how to handle and utilize such changes in order to improve the efficiency and effectiveness of three complex graph queries. Specifically, we first study the problem of community search on dynamic heterogeneou...[ Read more ]

In many real-world applications, the underlying data can be modeled as graphs. Querying graph data involves four main building blocks: the query semantics, the query parameters, the underlying graph data, and the output. When handling graph queries, changes can be made on the input parameters, the input graph, or the output. For example, modern graphs are dynamically changing, and bring challenges to the efficiency of querying algorithms. Also, query rewriting techniques are developed to modify query parameters, so that the output matches the user’s intent.

In this thesis, we study how to handle and utilize such changes in order to improve the efficiency and effectiveness of three complex graph queries. Specifically, we first study the problem of community search on dynamic heterogeneous information networks (HINs), where the input graph is dynamically changing, and an efficient algorithm should be able to quickly update the output after the graph changes. Then we consider the problem of SPARQL query rewriting, in which one is allowed to modify the input SPARQL query, which is a kind of query parameters, so that the actual output is close to the user’s intention. Finally, we study the problem of publishing graphs under node differential privacy, where one should randomly modify the output graph, so the information of any single node cannot be inferred from the output graph with high confidence.