Stratified Locality-Sensitive Hashing for Accelerated Physiological Time Series Retrieval

We introduce stratified locality-sensitive hashing (SLSH) for retrieving similar physiological waveform time series. SLSH further accelerates the sublinear retrieval time obtained by the standard locality-sensitive hashing ( LSH) method. The standard family of locality-sensitive hash functions is limited to provide only a single perspective on the data due to its one-to-one relationship to a distinct distance function for measuring similarity. SLSH incorporates multiple locality-sensitive hash families with various distance functions enabling it to examine the data with more diverse and refined perspectives. We provide the procedures of SLSH with locality-sensitive hash families for the l(1) and the cosine distances, and compare its performance to the standard LSH on an arterial blood pressure time series data extracted from the physiological waveform repository of the MIMIC2 database. The time to retrieve five most similar waveforms by SLSH is 14 times faster than the linear search and 1.7 times faster than the standard LSH when we allow 5% decrease in accuracy as a trade-off.