Norm-Range Partition: A Universal Catalyst for LSH based Maximum Inner Product Search (MIPS)
This work addresses efficiency bottlenecks in MIPS for applications like recommendation systems, though it is incremental as it builds on existing LSH methods.
The paper tackles the problem of improving efficiency in Locality Sensitive Hashing (LSH) based Maximum Inner Product Search (MIPS) by introducing norm-range partition, which reduces query processing complexity and significantly decreases the number of probes needed to achieve the same recall on real datasets.
Recently, locality sensitive hashing (LSH) was shown to be effective for MIPS and several algorithms including $L_2$-ALSH, Sign-ALSH and Simple-LSH have been proposed. In this paper, we introduce the norm-range partition technique, which partitions the original dataset into sub-datasets containing items with similar 2-norms and builds hash index independently for each sub-dataset. We prove that norm-range partition reduces the query processing complexity for all existing LSH based MIPS algorithms under mild conditions. The key to performance improvement is that norm-range partition allows to use smaller normalization factor most sub-datasets. For efficient query processing, we also formulate a unified framework to rank the buckets from the hash indexes of different sub-datasets. Experiments on real datasets show that norm-range partition significantly reduces the number of probed for LSH based MIPS algorithms when achieving the same recall.