NDLI: A new linear approximate clustering algorithm based upon sampling with probability distribution

Content Provider	IEEE Xplore Digital Library
Author	Chang-an Yuan Chang-jie Tang Chuan li Jian-jun Hu Jing Peng
Copyright Year	2005
Description	Author affiliation: Coll. of Comput., Sichuan Univ., China (Chang-an Yuan; Chang-jie Tang; Chuan li; Jian-jun Hu; Jing Peng)
Abstract	Clustering is an important research direction in knowledge discovery. As the classical method in clustering, the k-median algorithm is with serious deficiency such as low efficiency, bad adaptability for large data set etc. To solve this problem, a new method named LCPD (linear clustering based on probability distribution) is proposed in this paper. The main contribution includes: (1) partitions the buckets by using the space of equal probability in the m-dimension super-cube to make the number of data items in each layer ( namely the bucket of Hash) approximate equal, gets the layering sampling with the small cost; (2) The samples under the new algorithms is with sufficient representative power for total data set; (3) proves that the complexity of the new algorithm is O(n); (4) by the comparing experiment shows that the performance of LCPD is 2 magnitude higher than traditional with the number of data set near to 10000, and the clustering quantity is increase 55% with number of data set near to 8000.
Sponsorship	IEEE Syst., Man and Cybernetics Tech. Comm. on Cybernetics, Hong Kong Polytechnic Univ. Hebei Univ. South China Univ. Chongqing Univ. Sun Yat-sen Univ. Harbin Inst. of Technol. and Int. Univ. in Germany
Starting Page	1518
Ending Page	1523
File Size	327040
Page Count	6
File Format	PDF
ISBN	0780390911
DOI	10.1109/ICMLC.2005.1527185
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-08-18
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Linear approximation Clustering algorithms Sampling methods Partitioning algorithms Costs Statistical distributions Probability Educational institutions Distributed computing Information technology Sampling k-median algorithm Clustering Probability Distributing Hash function
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in