In Internet routing, an Autonomous System (AS) is a legitimate origin AS of an IP prefix only if it is authorized by the prefix owner to originate this prefix. However, on the one hand, the Border Gateway Protocol (BGP) itself cannot validate whether an AS has the authority to originate a given IP prefix; on the other hand, the routing registry information in Regional Internet Registry (RIR) or Internet Routing Registry (IRR) is incomplete and outdated. Consequently, there are lots of erroneous and prefix hijacking attacks disrupting the Internet routing. To validate whether an AS is in fact authorized to originate an IP prefix, we propose a novel approach by evaluating the trustworthiness of prefix-AS mappings from large collections of history BGP routing information. Drawing further on this, we present a scalable scheme for evaluating the trustworthiness of arbitrary prefix-AS mappings and tracing the evidences to validate these prefix announcements. We apply our methods on large-scale collections of prefix-AS mappings from continuous BGP routing snapshots of RouteViews, and verify our method with well-known prefix hijacking events. The results reveal that illegitimate prefix announcements can be detected and validated by the proposed methods.