The paper studied the multipath interference mitigation in global navigation satellite system (GNSS). A novel efficient weighted RELAXation (WRELAX) based algorithm considering the characteristic of the correlation of GNSS signal is proposed. The proposed algorithm has the advantage of lower computation burden compared with the state of art methods. In the proposed algorithm, by windowing the auto-correlation of the reference signal and the cross-correlation between the received data and the local reference signal, the data length in the iterative parameter estimation process is greatly shortened. Therefore, the amount of computation burden is reduced. Experimental results indicate that the proposed algorithm has similar performance and much low computation burden compared with the original WRELAX algorithm.