Decision support queries on graph data : answering which-pair queries

Abstract

Decision support systems are computer aided tools that support the decision making process of an organization. By analyzing enormous volumes of data, decision support systems will provide insightful information to its users. The success of a decision support system relies heavily on both the accuracy of the information that it can provide and the time it requires to provide the information. Conventionally, decision support systems operate using numeric data. The prevalence of graph data has prompted decision support research to begin researching techniques for supporting graph data. Thus far, only graph summarizing and graph pattern mining has been addressed. However, these techniques do not allow for changes in the underlying graph data. When the underlying data is represented by graphs, what types of decision support queries will users ask? This work presents "which" queries, a class of decision support queries that are specific to graph data, and illustrate their potential applications. When an organization makes a decision resulting in a change to the underlying graph data, new edges may eventually be added to the organization's graph data model. The addition of a new edge to the graph will affect how the objects, modeled in the graph, relate to each other. Determining how the object relationships change is a crucial factor that the organization needs to consider. However, determining object relationships is an expensive operation. Furthermore, the solution space that an organization is considering can be considerably large when using graph data; thus, efficient algorithms to evaluate the fundamental "which" queries are also presented. This work will develop a decision support system that effectively and efficiently answers the fundamental "which" queries. First, a model for "which" queries will be developed. Then, algorithms for efficiently answering fundamental "which" queries will be presented, which have been experimentally shown to be orders of magnitude faster than basic solutions. The results of the experiments on five real graph data sets will be presented. Finally, discussion of how the proposed algorithms can be used to answer other types of "which" queries will be presented.