Many Internet applications are designed and deployed as overlay applications. The potential mismatch between the application overlay and the network underlay has driven the demand for designing locality-aware applications in order to reduce emerging huge inter-domain traffic load. In this paper, we study a fundamental problem of measuring AS paths between two Internet hosts using three methods including traceroute-based direct measurement, BGP-based indirect inference and graph-based shortest AS path. We conducted a measurement study of AS paths to evaluated the accuracy and complexity of the above three AS path measurement methods and the corresponding tools. Inspired from our experiment results, we proposed a hybrid progressive method to combine the traceroute probes and the BGP tables to enhance the IP-to-AS mapping process to achieve a more accurate estimation of AS paths. We also found that the missing IP addresses in the traceroute measurement decrease the accuracy of the traceroute-based method; however, this performance degradation can be compensated using BGP tables. Our study leads a more accurate IP-to-AS mapping tool and it can provide a solid support for locality-aware Internet applications.