Action recognition is one of the top challenges in computer vision. In this paper, we present two binary-based video descriptors with outstanding characteristics in terms of recognition rate, computational times and memory requirements. The descriptors are called Binary Wavelet Differences (BWD) and Binary Dense Trajectories (BDT). Our proposed descriptors are based on the local binary patterns and produce binary vectors with a very low dimensionality. Specifically, we propose to analyze the spatio-temporal support regions of a video sequence to generate binary strings via wavelets patterns. We also propose to encode the motion information obtained from optical flow into a compact binary representation. Our evaluations on the KTH and UCF50 datasets demonstrate that our proposed descriptors achieve very competitive recognition accuracy. Moreover, they are able to attain shorter computational times and smaller memory requirements. Specifically, our proposed descriptors can be calculated up to 20X faster than orientation-based descriptors and require up to 225X less memory. Due to its binary nature, associated calculations in action recognition, e.g. clustering and classification, can be done up to 40X faster than state-of-the-art descriptors. Finally, our descriptors require codebooks with 2X fewer words than those required by other state-of-the-art descriptors.