International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B2. Istanbul 2004 
In CAESA, we only need to go through the data set once in 
order to calculate the parameters associated with the grid cells 
at the bottom level, the overhead of CAESA is linearly 
proportional to the number of objects with a small constant 
factor. 
  
3.0 r- STING * 
2.5 | xe 
8 20 s : s 
$ 151 XUL 
B 101 a CAESA 
0.5 a A Lia se 0s le peril 
0.0 3 ln | | + 
0 2000 4000 6000 8000 
Number of cells at bottom layer 
Figure 7: Overhead comparison between STING and CAESA 
when user change her/his focus 
To obtain performance of CAESA, we implemented the house- 
price example discussed in Section 3.2. We generated 2400 data 
points(houses), the hierarchical structure has 6 layers in this test. 
Figure 2 shows the expected result, Figure 3 shows the result of 
our algorithm, and Figure 4 shows the result when user change 
her/his focus according to the last query. From the experimental 
result we can see apparently that our algorithm is valid and has 
a high performance. 
6. CONCLUSION 
In this paper, we proposed a scalable and visualization-oriented 
clustering algorithm for exploratory spatial analysis. It is of 
high performance and low computing cost, and it can run focus- 
changing clustering efficiently, can be adaptable to visualization 
situation, that is, choosing appropriate relative clustering 
granularity automatically according to current relative 
visualization resolution. We built a prototype to demonstrate the 
practicability of the proposed algorithm. Experimental results 
show our algorithm is effective and efficient. 
REFERENCES 
Agrawal R., Gehrke J., Gunopulos D. et al., 1998. Automatic 
subspace clustering of high dimensional data for data mining 
applications. In Proc. of the ACM SIGMOD, pp. 94-105. 
David Hand, Heikki Mannila and Padhraic Smyth, 2001. 
Principles of Data Mining. Massachusetts Institute of 
Technolology Press. 
Ester,M., Kriegel, H. P., Sander,J. et al., 1996. A density-based 
algorithm for discovering clusters in large spatial databases 
with noise. In Proc.of 2nd Int. Conf. Knowledge Discovery and 
Data Mining. pp. 226-231. 
Guha S., Rastogi R. and Shim K., 1998. CURE: an efficient 
clustering algorithm for large databases. In: Proc. of the ACM 
SIG MOD, pp. 73784. 
Halkidi, M., Batistakis, Y. and Vazirgiannis, M., 200]. 
Clustering algorithms and validity measures. In Proc of 13th 
Intl. Conf. on Scientific and Statistical Database Management, 
pp.3-22. 
Hinneburg, A., Keim, D. and Wawryniuk, M., 2003. Using 
projections to visually cluster high-dimensional data. /EEE 
Computational Science and Engineering], 5(2), pp. 14 — 25. 
Hu, B. and Marek-Sadowska, M., 2004. Fine Granularity 
Clustering-Based Placement. /EEE Transactions on Computer- 
Aided Design of Integrated Circuits and Systems. 23(4), pp. 527 
- S36. 
Jiawei Han, Micheline Kamber. Data Mining: Concepts and 
Techniques. Morgan Kaufmann Publishers, 2001. 
Matsushita, M. and Kato, T., 2001. Interactive visualization 
method for exploratory data analysis. In Proc. of 15th Intl. Conf. 
on Information Visualization, pp. 671—676. 
Memarsadeghi, N. and O'Leary, D.P., 2003. Classified 
information: the data clustering problem. /EEE Computational 
Science and Engineering. 5(5), pp. 54 — 60. 
Ng Ka Ka. E. and Ada Wai-chee Fu., 2002. Efficient algorithm 
for projected clustering. In Proc.of ICDE, pp. 273—273. 
Sheikholeslami G.. Chatterjee, S. and Zhang, A., 1998. 
WaveCluster: a multi-resolution clustering app roach for very 
large spatial databases. In Proc. of 24th VLDB, pp. 428 439. 
Tin Kam Ho., 2002. Exploratory analysis of point proximity in 
subspaces. In Proc. of 16th Intl. Conf. on Pattern Recognition. 
Vol. 2, pp. 196 — 199 
Wang Lian, Cheung, W.W., Mamoulis, N., et al., 2004. An 
efficient and scalable algorithm for clustering XML documents 
by structure. /EEE Transactions on Knowledge and Data 
Engineering, 16(1), pp. 82 — 96 
Wang, W., Yang, J. and Muntz, R., 1997. Sting: a statistical 
information grid approach to spatial data mining. In Proc. of 
VLDB, pp. 186-195. 
Wang, W., Yang, J. and Muntz, R., 1999, Sting: An Approach 
to Active Spatial Data Miniing. In Proc. of ICDE, pp. 116-125. 
ACKNOWLEDGEMENTS 
The work is supported by Hi-Tech Research and Development 
Program of China under grant No. 2002AA 135340, and Open 
Researches Fund Program of SKISE under grant No. 
SKL(4)003, and IBM Research Award, and Open 
Researches Fund Program of LIESMARS under grant No. 
SKL(01)0303. 
KEY 
ABS 
Geo; 
effic 
ina 
urba 
arch 
prov 
3Dt 
navi 
proc 
spati 
3D « 
wall 
effe 
the € 
f. T 
The 
com 
simt 
mod 
incre 
(WV 
and 
user 
over 
rece 
visu 
oper 
tran: 
info 
(Lin 
200( 
mod 
intei 
deve 
imp 
and 
(19€ 
cliet 
3D: 
inte: 
the 
web 
of tl 
virt