FROSH: FasteR Online Sketching Hashing

Many hashing methods, especially those that are in the data-dependent category with good learning accuracy, are still inefficient when dealing with three critical problems in mod- ern data analysis. First, data usually come in a streaming fashion, but most of the exist- ing hashing methods are batch-based models. Second, when data become huge, the exten- sive computational time, large space require- ment, and multiple passes to load the data into memory will be prohibitive. Third, data often lack sufficient label information. Although the recently proposed Online Sketching Hashing (OSH) is promising to alleviate all three issues mentioned above, its training procedure still suffers from a high time complexity. In this paper, we propose a FasteR Online Sketching Hashing (FROSH) method to make the train- ing process faster. Compared with OSH, we leverage fast transform to sketch data more compactly. Particularly, we derive indepen- dent transformations to guarantee the sketch- ing accuracy, and design a novel implemen- tation to make such transformations applica- ble to online data sketching without increas- ing the space cost. We rigorously prove that our method can yield a comparable learning accuracy with a lower time complexity and an equal space cost compared with OSH. Finally, extensive experiments on synthetic and real- world datasets demonstrate the excellent per- formance of our method.