Cloud service providers offer many VM types at a range of prices without providing any way of choosing VM types based on workload performance. Performance depends critically on complex latent factors of the work- load and hardware resources complicating the problem of choosing a VM type. This requires costly evaluation across VM types to select an optimal configuration. In this paper, we address this problem by proposing PARIS, a data-driven modeling framework for accurately and economically estimating performance for user workloads across different VM types in the cloud. For a user workload, PARIS maps the range of VM types to performance-cost trade-off space that aids in the choice of a VM type.