ridm@nrct.go.th   ระบบคลังข้อมูลงานวิจัยไทย   รายการโปรดที่คุณเลือกไว้

SparseHC : a memory-efficient online hierarchical clustering algorithm

หน่วยงาน Nanyang Technological University, Singapore

รายละเอียด

ชื่อเรื่อง : SparseHC : a memory-efficient online hierarchical clustering algorithm
นักวิจัย : Nguyen, Thuy-Diem , Schmidt, Bertil , Kwoh, Chee-Keong
คำค้น : DRNTU::Engineering::Computer science and engineering
หน่วยงาน : Nanyang Technological University, Singapore
ผู้ร่วมงาน : -
ปีพิมพ์ : 2557
อ้างอิง : Nguyen, T.- D., Schmidt, B., & Kwoh, C.- K. (2014). SparseHC: A Memory-efficient Online Hierarchical Clustering Algorithm. Procedia Computer Science, 29, 8-19. , 1877-0509 , http://hdl.handle.net/10220/20325 , http://dx.doi.org/10.1016/j.procs.2014.05.001
ที่มา : -
ความเชี่ยวชาญ : -
ความสัมพันธ์ : Procedia computer science
ขอบเขตของเนื้อหา : -
บทคัดย่อ/คำอธิบาย :

Computing a hierarchical clustering of objects from a pairwise distance matrix is an important algorithmic kernel in computational science. Since the storage of this matrix requires quadratic space with respect to the number of objects, the design of memory-efficient approaches is of high importance to this research area. In this paper, we address this problem by presenting a memory-efficient online hierarchical clustering algorithm called SparseHC. SparseHC scans a sorted and possibly sparse distance matrix chunk-by-chunk. Meanwhile, a dendrogram is built by merging cluster pairs as and when the distance between them is determined to be the smallest among all remaining cluster pairs. The key insight used is that for finding the cluster pair with the smallest distance, it is unnecessary to complete the computation of all cluster pairwise distances. Partial information can be utilized to calculate a lower bound on cluster pairwise distances that are subsequently used for cluster distance comparison. Our experimental results show that SparseHC achieves a linear empirical memory complexity, which is a significant improvement compared to existing algorithms.

บรรณานุกรม :
Nguyen, Thuy-Diem , Schmidt, Bertil , Kwoh, Chee-Keong . (2557). SparseHC : a memory-efficient online hierarchical clustering algorithm.
    กรุงเทพมหานคร : Nanyang Technological University, Singapore.
Nguyen, Thuy-Diem , Schmidt, Bertil , Kwoh, Chee-Keong . 2557. "SparseHC : a memory-efficient online hierarchical clustering algorithm".
    กรุงเทพมหานคร : Nanyang Technological University, Singapore.
Nguyen, Thuy-Diem , Schmidt, Bertil , Kwoh, Chee-Keong . "SparseHC : a memory-efficient online hierarchical clustering algorithm."
    กรุงเทพมหานคร : Nanyang Technological University, Singapore, 2557. Print.
Nguyen, Thuy-Diem , Schmidt, Bertil , Kwoh, Chee-Keong . SparseHC : a memory-efficient online hierarchical clustering algorithm. กรุงเทพมหานคร : Nanyang Technological University, Singapore; 2557.