Graph structure is interesting. Since the birth of computer science, researchers and engineers have been modeling numerous fundamental and useful applications on graphs. In recent years when we are stepping into the big data era, graphs are massive, attached with various useful information, and evolute very rapidly. It is extremely challenging to process efficient and effective queries on modern networks. Indexing is a practical approach in database. We focus on indexing path-related queries in massive graphs in this study, to support efficient and effective query processing solutions.

Specifically, we start with the problem of point-to-point distance querying for massive scale-free graphs. It is a fundamental graph operator, serving as a basic building block for many applicati...[ Read more ]

Graph structure is interesting. Since the birth of computer science, researchers and engineers have been modeling numerous fundamental and useful applications on graphs. In recent years when we are stepping into the big data era, graphs are massive, attached with various useful information, and evolute very rapidly. It is extremely challenging to process efficient and effective queries on modern networks. Indexing is a practical approach in database. We focus on indexing path-related queries in massive graphs in this study, to support efficient and effective query processing solutions.

Specifically, we start with the problem of point-to-point distance querying for massive scale-free graphs. It is a fundamental graph operator, serving as a basic building block for many applications, including social network analysis, knowledge graph mining and product recommendation. Given a directed or undirected graph, we propose to build an index for answering these queries based on a novel hop-doubling labeling technique. We show that our method is much more efficient and effective compared to the state-of-the-art techniques, in terms of both querying time and indexing costs.

Then, we incorporate the hop-doubling labeling technique with a novel keyword indexing scheme to solve the top-k nearest keyword search problem in large graphs. The previous algorithms only give approximate results. We show that with the efficient graph indexing scheme, it is possible to query exact results very efficiently.

In the end, we study indexing a randomized query in massive graphs. Specifically, we improve SimRank querying with a randomized indexing scheme to support efficient, accurate and dynamic querying.