Full Text:   <1863>

CLC number: TP393.9

On-line Access: 

Received: 2003-07-16

Revision Accepted: 2004-01-19

Crosschecked: 0000-00-00

Cited: 12

Clicked: 4238

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2004 Vol.5 No.11 P.1405~1412


Using Greedy algorithm: DBSCAN revisited II

Author(s):  YUE Shi-hong, LI Ping, GUO Ji-dong, ZHOU Shui-geng

Affiliation(s):  Institute of Industrial Process Control, Zhejiang University, Hangzhou 310027, China; more

Corresponding email(s):   Shyue@iipc.zju.edu.cn

Key Words:  DBSCAN algorithm, Greedy algorithm, Density-skewed cluster

Share this article to: More

YUE Shi-hong, LI Ping, GUO Ji-dong, ZHOU Shui-geng. Using Greedy algorithm: DBSCAN revisited II[J]. Journal of Zhejiang University Science A, 2004, 5(11): 1405~1412.

@article{title="Using Greedy algorithm: DBSCAN revisited II",
author="YUE Shi-hong, LI Ping, GUO Ji-dong, ZHOU Shui-geng",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Using Greedy algorithm: DBSCAN revisited II
%A YUE Shi-hong
%A LI Ping
%A GUO Ji-dong
%A ZHOU Shui-geng
%J Journal of Zhejiang University SCIENCE A
%V 5
%N 11
%P 1405~1412
%@ 1869-1951
%D 2004
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2004.1405

T1 - Using Greedy algorithm: DBSCAN revisited II
A1 - YUE Shi-hong
A1 - LI Ping
A1 - GUO Ji-dong
A1 - ZHOU Shui-geng
J0 - Journal of Zhejiang University Science A
VL - 5
IS - 11
SP - 1405
EP - 1412
%@ 1869-1951
Y1 - 2004
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2004.1405

The density-based clustering algorithm presented is different from the classical Density-Based Spatial Clustering of Applications with Noise (DBSCAN) (Ester et al., 1996), and has the following advantages: first, greedy algorithm substitutes for R*-tree (Bechmann et al., 1990) in DBSCAN to index the clustering space so that the clustering time cost is decreased to great extent and I/O memory load is reduced as well; second, the merging condition to approach to arbitrary-shaped clusters is designed carefully so that a single threshold can distinguish correctly all clusters in a large spatial dataset though some density-skewed clusters live in it. Finally, authors investigate a robotic navigation and test two artificial datasets by the proposed algorithm to verify its effectiveness and efficiency.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Bechmann, N., Kriegel, H.P., Schneider, R., Seeger, B., 1990. The R*-tree: An Efficient and Robust Access Method For Points and Rectangles. Proc. ACM SIGMOD Int. Conf. Alt. City, NJ, p.322-331.

[2] Dash, M., Liu, H., Xu, X., 2001. ‘1+1>2’: Merging Distance and Density Based Clustering. 7th Int. Conf. DASFAA’ 01, HK, p.118-202.

[3] Ester, M., Kriegel, H.P., Sander, H., Xu, X., 1996. A Density-Based Algorithm for Discovering Clusters in Large Spatial Datasets with Noise. Proc. 2nd Int. Conf. KDDD. Portland, Oregon, p.1232-1239.

[4] Halkidi, M., Batistakis, Y., Vazirgiannis, M., 2002. Clustering validity checking methods: Part II. SIGMOD Record, 31(4):51-62.

[5] Han, J., 2001. Data Mining. Morgan Kaufmann Publishers, USA, p.242-266.

[6] Krishnapuram, R., Keller, J.M., 1993. A possibilistic approach to clustering. IEEE Trans. Fuzzy Syst., 1(2):98-106.

[7] Krishnapuram, R., Keller, J.M., 1998. An unified views: fuzzy robust clustering. IEEE Trans. Fuzzy Syst., 5(2):270-293.

[8] Lozano, S., Dobado, D., Larraneta, J., 2002. Modified fuzzy c-means algorithm for cellular manufacturing. Fuzzy Sets Syst., 126:23-32.

[9] Nakamura, E., Kehtarnavaz, N., 1998. Determining number of clusters and prototype locations via multi-scale clustering. Pattern Recognition Letters, 19(3):1265-1283.

[10] Skieyca, S., 1990. Minimum Vertex Cover, Implementing Discrete Mathematics: Combinatory and Graph Theory Wit Mathematic. Addison-Wesley, MA, p.234-245.

[11] Thshihiro, F., 2000. Approximation algorithms for submodular set cover with applications. IEICE Trans. Inf. & Syst., 18(3):156-166.

[12] Yue, S.H., Li, P., Zhou, S.G., Gu, Y.K., 2004. Using statistics: DBSCAN revisited I. http://www.cise.zju.edu.cn/iipc/shyue.

Open peer comments: Debate/Discuss/Question/Opinion



2015-03-24 02:45:47

Please send me this paper

Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE