Exploring story similarities using graph edit distance algorithms

Paul, Sritama
Journal Title
Journal ISSN
Volume Title
University of Delaware
In computer science, particularly in the fields of interactive storytelling and game authoring, stories are represented as a sequence of goals and actions taken by various characters. Graph data structures are often used to represent these, where the nodes are goals and actions, and the edges represent time and order. Existing story authoring tools allow authors to create stories by adding goals, actions, and characters and thereby create the story. However, existing authoring tools do not provide much help to the author in the form of feedback on the story they are creating. It is therefore difficult for storytellers, particularly novice storytellers, to create their story. One way to aid storytellers, is to have the story authoring tool suggest continuations and details based on some knowledge that the tool has. In our work, we create a knowledge base that exists of all the stories that the tool has collected. The idea is that we can use these existing stories to suggest appropriate feedback to the storyteller. This relies on the assumption that the group of storytellers collectively has knowledge that can be useful to a new storyteller. We know that this is often the case within certain domains such as the military or police force, where many stories or experiences have commonalities. As the stories are represented as graphs, we will use graph similarity algorithms to compute the similarity between the story being authored and the existing stories in the knowledge base. In this thesis, we explore how several different graph similarity algorithms perform with regard to determining story similarity.