Network traffic measurement serves as a critical foundation for network monitoring systems. However, in large-scale networks, full-mesh measurement of the traffic data is infeasible. Matrix completion (MC) with sparse samples enables low-overhead network traffic measurement. Existing traffic measurement schemes based on MC employ the random sampling strategy, which has obvious limitations in data collection efficiency. Sampling strategy based on ridge leverage scores can achieve high quality sampling by quantifying the contribution of matrix elements. However, the computational cost of the ridge leverage scores increases in polynomial time with matrix size, which makes it unsuitable for network traffic measurement. To address these challenges, we propose an efficient and low cost traffic measurement method called fuzzy ridge leverage scores deterministic sampling matrix completion (FRDMC). FRDMC estimates the rank of ridge leverage scores without calculating the exact scores, which significantly reduces the computational cost. Experimental results on several real network traffic datasets demonstrate that the FRDMC traffic measurement RMSE was only \(48.06\%\) of the uniform sampling MC, and the average sampling runtime overhead of the FRDMC was reduced by \(99.15\%\) compared with ridge leverage score deterministic sampling matrix completion.