Record Details

Constraint-based clustering in large databases

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Constraint-based clustering in large databases
 
Creator TUNG, AKH
HAN, JW
LAKSHMANAN, LVS
NG, RT
 
Description Constrained clustering finding clusters that satisfy user-specified constraints-is highly desirable in many applications. In this paper, we introduce the constrained clustering problem and show that traditional clustering algorithms (e.g., k-means) cannot handle it. A scalable constraint-clustering algorithm is developed in this study which starts by finding an initial solution that satisfies user-specified constraints and then refines the solution by performing confined object movements under constraints. Our algorithm consists of two phases: pivot movement and deadlock resolution. For both phases, we show that finding the optimal solution is NP-hard. We then propose several heuristics and show how our algorithm can scale up for large data sets using the heuristic of micro-cluster sharing. By experiments, we show the effectiveness and efficiency of the heuristics.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T13:31:01Z
2011-12-15T09:11:10Z
2011-10-23T13:31:01Z
2011-12-15T09:11:10Z
2001
 
Type Article; Proceedings Paper
 
Identifier DATABASE THEORY - ICDT 2001, PROCEEDINGS,1973,405-419
3-540-41456-8
0302-9743
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15141
http://hdl.handle.net/100/1897
 
Source 8th International Conference on Database Theory (ICDT 2001),LONDON, ENGLAND,JAN 04-06, 2001
 
Language English