The potential of telemedicine in respiratory health care has not been completely unveiled in part due to the inexistence of reliable objective measurements of symptoms such as cough. Currently available cough detectors are uncomfortable and expensive at a time when generic smartphones can perform this task. However, two major challenges preclude smartphone-based cough detectors from effective deployment namely, the need to deal with noisy environments and computational cost. This paper focuses on the latter, since complex machine learning algorithms are too slow for real-time use and kill the battery in a few hours unless specific actions are taken. In this paper, we present a robust and efficient implementation of a smartphone-based cough detector. The audio signal acquired from the device's microphone is processed by computing local Hu moments as a robust feature set in the presence of background noise. We previously demonstrated that pairing Hu moments and a standard k-NN classifier achieved accurate cough detection at the expense of computation time. To speed-up k-NN search, many tree structures have been proposed. Our cough detector uses an improved vantage point (vp)-tree with optimized construction methods and a distance function that results in faster searches. We achieve 18× speed-up over classic vp-trees, and 560× over standard implementations of k-NN in state-of-the-art machine learning libraries, with classification accuracies over 93%, enabling real-time performance on low-end smartphones.