Exploring story similarities using graph edit distance algorithms
Date
2013
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
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.