Two emerging trends of Internet applications, video traffic becoming dominant and usage-based pricing becoming prevalent, are at odds with each other. Given this conflict, is there a way for users to stay within their monthly data plans (data quotas) without suffering a noticeable degradation in video quality? In this paper, the authors develop an online video adaptation system, called Quota Aware Video Adaptation (QAVA) that manages this tradeoff by leveraging the compressibility of videos and by predicting consumer usage behavior throughout a billing cycle. They propose the QAVA architecture and develop its main modules, including Stream Selection, User Profiling, and Video Profiling. Online algorithms are designed through dynamic programming and evaluated using real video request traces.