For handling large-scale problems, methods like Gaussian processes can be computationally challenging. In this paper, we discuss how use of alternative kernel methods can be employed to accelerate computations, without loss of modeling power. We examine this in the context of general nonparametric Bayesian models, with specific applications within the Beta process. The theoretical and algorithmic issues are discussed, with demonstration via several examples.