This paper introduces a high efficient local spatiotemporal descriptor, called gradient boundary histograms (GBH). The proposed GBH descriptor is built on simple spatio-temporal gradients, which are fast to compute. We demonstrate that it can better represent local structure and motion than other gradient-based descriptors, and significantly outperforms them on large realistic datasets. A comprehensive evaluation shows that the recognition accuracy is preserved while the spatial resolution is greatly reduced, which yields both high efficiency and low memory usage.