Abstract
A new clustering problem is to perform clustering on objects in spatial
network. In real life, the euclidean distance cannot represent the
shortest distance of two objects whose locations are constainted. The
network model captures these constaints and the actual distance between
two objects is defined as their shortest distance in the network. Then, we
can perform clustering and to discover interesting properties about the
network and the objects.
Previous graph partitioning/clustering algorithms cannot be applied
directly transformed. The transformed network can be much more complex
and these algoriths are infeasible for large network. Also, most of them
are main memory algorithms and they cannot be applied for large problem
instances.
Finding the shortest distance of two points in a large network can be
expensive. As this operation is frequent in clustering, we focus on how to
reduce or amortize the effort for computing shortest distances. First, a
disk based representation for storing the network and the model will be
proposed. Then, two scalable clustering algorithms for objects in spatial
network will be discussed. One of them is based on k-medoids and the other
is a density based algorithm. Some preliminary experimental results will
be presented. We will also discuss how this model can be used for solving
some other related problems.
