We present a new implementation of the commonly used Box-fitting Least Squares (BLS) algorithm, for the detection of transiting exoplanets in photometric data. Unlike BLS, our new implementation—Sparse BLS, does not use binning of the data into phase bins, nor does it use any kind of phase grid. Thus, its detection efficiency does not depend on the transit phase, and is therefore slightly better than that of BLS. For sparse data, it is also significantly faster than BLS. It is therefore perfectly suitable for large photometric surveys producing unevenly-sampled sparse light curves, such as Gaia.