Indoor localization has attracted more and more attention in the past few years. To achieve indoor robot navigation, it usually applies multi-on-board sensors. However, the computation loading could increase dramatically. This paper utilizes a light detection and ranging (LIDAR) device as the only sensor to detect surroundings and develops a new scan matching algorithm to realize indoor localization. To attenuate the computation effort as well as preserve localization robustness and precision, a weighted parallel ICP (WP-ICP) with interpolation is proposed. The accuracy and real time estimation capability of the proposed methods are validated through experiments. Finally, experiment comparisons are carried out and it shows that the proposed method is capable of reducing computation effort significantly and preserve localization precision simultaneously.