In this paper, we present CrowdSense, an algorithm for estimating the crowd's majority opinion by querying only a subset of it. CrowdSense works in an online fashion where examples come one at a time and it dynamically samples subsets of labelers based on an exploration/exploitation criterion. The algorithm produces a weighted combination of a subset of the labelers' votes that approximates the crowd's opinion. We also present two probabilistic variants of CrowdSense mat are based on different assumptions on the joint probability distribution between the labelers' votes and the majority vote. Our experiments demonstrate that we can reliably approximate the entire crowd's vote by collecting opinions from a representative subset of the crowd. Copyright © 2012, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.