The search functionality is under construction.

The search functionality is under construction.

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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

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 -