training difficult (both in terms of scalability and learning the appropriate concept). For example, the number of URLs available for training can be in the order of millions (or even billions). As a result, the training time for traditional models may be too high to be practical. Consequently, Online Learning [@hoi2014libol], a family of scalable learning techniques have been heavily applied for this task. Similarly, for this task, URLs are represented using the bag-of-words (BoW) features. These features basically indicate whether a particular word (or string) appears in a URL or not - as a result every possible type of word that may appear in any URL becomes a feature. This representation may result in millions of features which would be very sparse (most features are absent most of the time, as a URL will usually have very few of the millions of possible words present in it). Accordingly, a learning method should exploit this sparsity property to improve learning efficiency and efficacy. Despite the promising generalizing ability of machine learning approaches, one potential shortcoming of these approaches for malicious URL detection may be their resource intensive nature (especially while extracting features that are non-trivial and expensive to compute), reducing 