Please use this identifier to cite or link to this item:
Title: FRSDE : fast reduced set density estimator using minimal enclosing ball approximation
Authors: Deng, Z
Chung, FL 
Wang, S
Keywords: Core-set
Data condensation
Minimal enclosing ball
Reduced set density estimator
Issue Date: 2008
Publisher: Elsevier
Source: Pattern recognition, 2008, v. 41, no. 4, p. 1363-1372 How to cite?
Journal: Pattern recognition 
Abstract: Reduced set density estimator (RSDE) is an important technique that can be used to replace the classical Parzen window estimator (PW) for saving the computational cost. Though RSDE demonstrates a nicer performance in the density accuracy and the computational time compared with several existing methods, it still faces the critical challenge for practical applications because of its high time complexity (no less than O (N 2)) and space complexity (O (N 2)) in training the model weighting coefficients on large data sets. In order to overcome this shortcoming, a fast reduced set density estimator algorithm (FRSDE) is proposed in this study. First, the relationship between RSDE and the minimal enclosing ball problems (MEB) in computational geometry is revealed. Then, the finding that RSDE is equivalent to a special MEB problem is derived. With this finding, the fast core-set based MEB approximation algorithm is introduced to develop the proposed algorithm FRSDE. Compared with RSDE, FRSDE has the following distinctive advantage: it can guarantee that the upper bound of the time complexity is linear with the size N of a large data set and the upper bound of the space complexity is independent of N. Our experimental results show that the proposed FRSDE has a competitive performance in the density accuracy and an overwhelming advantage over RSDE for large data sets in the data condensation rate and the training time for the weighting coefficients.
ISSN: 0031-3203
EISSN: 1873-5142
DOI: 10.1016/j.patcog.2007.09.013
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Aug 9, 2018


Last Week
Last month
Citations as of Aug 8, 2018

Page view(s)

Last Week
Last month
Citations as of Aug 12, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.