QoS parameters are used to describe services in terms of their behavior and can be used to rank services according to non-functional criteria. To provide an accurate characterization of the quality of a service, we propose a samplingbased technique. The proposed technique uses Adaptive and Sequential Sampling strategies to estimate the QoS parameters that satisfy the required confidence levels while the size of the sample remains small. QoS estimates are used by a hybrid composer, named PT-SAM, to identify the service compositions that satisfy a functional condition and best meet non-functional criteria of a user query. PT-SAM adapts a Petri-Net unfolding algorithm to find a desired marking from an initial state by using a utility function defined on QoS estimates and functional properties of the available services. PT-SAM uses a QoS-based utility function to guide the search into portions of good quality service compositions; thus, PT-SAM is able to scale up to large-scale search spaces of services. We report on the quality of the sampling techniques and the performance of the composer. First, we show correlation between the estimates and the real values of the QoS parameters; then, we report on the benefits of using these estimates to traverse large search spaces of service compositions (e.g., in the range of 1,000 to 100,000 services). Our experiments show that the quality of the compositions identified by our algorithm is close to the optimal solution produced by the exhaustive algorithm.