Based on the self-organization of Kohonen feature map (SOFM), recently, Pei et al. presented an efficient color palette indexing method to construct a color table for compression. Taking the palette indexing method as a representative, this paper presents two new strategies, the pruning-based search strategy and the lookup table (LUT)-based update strategy, to speed up the learning process in the SOFM. Based on four typical testing images, experimental results illustrate that our proposed two strategies have 35% execution-time improvement ratio in average. The practical improvement ratio is very close to that in the theoretical analysis.