Minimal Spanning Tree Construction with MetricMatrix

Masahiro ISHIKAWA; Kazutaka FURUSE; Hanxiong CHEN; Nobuo OHBO

Minimal Spanning Tree Construction with MetricMatrix

Masahiro ISHIKAWA, Kazutaka FURUSE, Hanxiong CHEN, Nobuo OHBO

Full Text Views

0

Cite this

Summary :

Clustering is one of the most important topics in the field of knowledge discovery from databases. Especially, hierarchical clustering is useful since it gives a hierarchical view of a whole database and can be used to guide users in browsing a huge database. In many cases, clustering can be modeled as a graph partitioning problem. When an appropriate distance function between database objects is given, a database can be viewed as an edge-weighted complete graph, where vertices are database objects and weights of edges are distances between them. Then a process of MST (Minimal Spanning Tree) construction can be viewed as a process of a single-linkage agglomerative clustering process for database objects. In this paper, we propose an efficient MST construction method for a large complete metric graph, which is derived from a database with a metric distance function defined on it. Our method utilizes a metric index to reduce the number of distance calculations. The basic idea is to exclude those edges less probable to be a part of an MST by using the metric postulate. For this purpose, we introduce a new metric index named MetricMatrix. Experimental results show that our method can drastically reduce the number of distance calculations needed for MST construction in comparison with the classical method.

Publication: IEICE TRANSACTIONS on Information Vol.E85-D No.2 pp.362-372

Publication Date: 2002/02/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Databases

Cite this

Copy

Masahiro ISHIKAWA, Kazutaka FURUSE, Hanxiong CHEN, Nobuo OHBO, "Minimal Spanning Tree Construction with MetricMatrix" in IEICE TRANSACTIONS on Information, vol. E85-D, no. 2, pp. 362-372, February 2002, doi: .
Abstract: Clustering is one of the most important topics in the field of knowledge discovery from databases. Especially, hierarchical clustering is useful since it gives a hierarchical view of a whole database and can be used to guide users in browsing a huge database. In many cases, clustering can be modeled as a graph partitioning problem. When an appropriate distance function between database objects is given, a database can be viewed as an edge-weighted complete graph, where vertices are database objects and weights of edges are distances between them. Then a process of MST (Minimal Spanning Tree) construction can be viewed as a process of a single-linkage agglomerative clustering process for database objects. In this paper, we propose an efficient MST construction method for a large complete metric graph, which is derived from a database with a metric distance function defined on it. Our method utilizes a metric index to reduce the number of distance calculations. The basic idea is to exclude those edges less probable to be a part of an MST by using the metric postulate. For this purpose, we introduce a new metric index named MetricMatrix. Experimental results show that our method can drastically reduce the number of distance calculations needed for MST construction in comparison with the classical method.
URL: https://global.ieice.org/en_transactions/information/10.1587/e85-d_2_362/_p

Copy

@ARTICLE{e85-d_2_362,
author={Masahiro ISHIKAWA, Kazutaka FURUSE, Hanxiong CHEN, Nobuo OHBO, },
journal={IEICE TRANSACTIONS on Information},
title={Minimal Spanning Tree Construction with MetricMatrix},
year={2002},
volume={E85-D},
number={2},
pages={362-372},
abstract={Clustering is one of the most important topics in the field of knowledge discovery from databases. Especially, hierarchical clustering is useful since it gives a hierarchical view of a whole database and can be used to guide users in browsing a huge database. In many cases, clustering can be modeled as a graph partitioning problem. When an appropriate distance function between database objects is given, a database can be viewed as an edge-weighted complete graph, where vertices are database objects and weights of edges are distances between them. Then a process of MST (Minimal Spanning Tree) construction can be viewed as a process of a single-linkage agglomerative clustering process for database objects. In this paper, we propose an efficient MST construction method for a large complete metric graph, which is derived from a database with a metric distance function defined on it. Our method utilizes a metric index to reduce the number of distance calculations. The basic idea is to exclude those edges less probable to be a part of an MST by using the metric postulate. For this purpose, we introduce a new metric index named MetricMatrix. Experimental results show that our method can drastically reduce the number of distance calculations needed for MST construction in comparison with the classical method.},
keywords={},
doi={},
ISSN={},
month={February},}

Copy

TY - JOUR
TI - Minimal Spanning Tree Construction with MetricMatrix
T2 - IEICE TRANSACTIONS on Information
SP - 362
EP - 372
AU - Masahiro ISHIKAWA
AU - Kazutaka FURUSE
AU - Hanxiong CHEN
AU - Nobuo OHBO
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E85-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2002
AB - Clustering is one of the most important topics in the field of knowledge discovery from databases. Especially, hierarchical clustering is useful since it gives a hierarchical view of a whole database and can be used to guide users in browsing a huge database. In many cases, clustering can be modeled as a graph partitioning problem. When an appropriate distance function between database objects is given, a database can be viewed as an edge-weighted complete graph, where vertices are database objects and weights of edges are distances between them. Then a process of MST (Minimal Spanning Tree) construction can be viewed as a process of a single-linkage agglomerative clustering process for database objects. In this paper, we propose an efficient MST construction method for a large complete metric graph, which is derived from a database with a metric distance function defined on it. Our method utilizes a metric index to reduce the number of distance calculations. The basic idea is to exclude those edges less probable to be a part of an MST by using the metric postulate. For this purpose, we introduce a new metric index named MetricMatrix. Experimental results show that our method can drastically reduce the number of distance calculations needed for MST construction in comparison with the classical method.
ER -