Collision frequency locality-sensitive hashing for prediction of critical events

We present a fast, efficient method to predict future critical events for a patient. The prediction method is based on retrieving and leveraging similar waveform trajectories from a large medical database. Locality-sensitive hashing (LSH), our theoretical foundation, is a model-free, sub-linear time, approximate search method enabling a fast retrieval of a nearest neighbor set for a given query. We propose a new variant of LSH, namely Collision Frequency LSH (CFLSH), to further improve the prediction accuracy without sacrificing any speed. The key idea is that the more frequently an element and a query collide across multiple LSH hash tables, the more similar they are. Unlike the standard LSH which only utilizes the linear distance calculation, in CFLSH, the short-listing step from a pool of pre-selected candidates filtered by hash functions to the final nearest neighbor set relies upon the frequency of collision along with distance information. We evaluate CFLSH versus the standard LSH using the L1 and cosine distances, for predicting acute hypotensive episodes on arterial blood pressure time series data extracted from the MIMIC II database. Our results show that CFLSH for the L1 distance has a higher prediction accuracy and further accelerates the sub-linear querying time obtained by the standard LSH.