Timezone: »

 
Poster
Norm-Ranging LSH for Maximum Inner Product Search
Xiao Yan · Jinfeng Li · Xinyan Dai · Hongzhi Chen · James Cheng

Tue Dec 04 02:00 PM -- 04:00 PM (PST) @ Room 517 AB #145
in Tue Poster Session B »

Neyshabur and Srebro proposed SIMPLE-LSH, which is the state-of-the-art hashing based algorithm for maximum inner product search (MIPS). We found that the performance of SIMPLE-LSH, in both theory and practice, suffers from long tails in the 2-norm distribution of real datasets. We propose NORM-RANGING LSH, which addresses the excessive normalization problem caused by long tails by partitioning a dataset into sub-datasets and building a hash index for each sub-dataset independently. We prove that NORM-RANGING LSH achieves lower query time complexity than SIMPLE-LSH under mild conditions. We also show that the idea of dataset partitioning can improve another hashing based MIPS algorithm. Experiments show that NORM-RANGING LSH probes much less items than SIMPLE-LSH at the same recall, thus significantly benefiting MIPS based applications.

Keywords: Information Retrieval
[ Paper] 

Author Information

Xiao Yan (The Chinese University of Hong Kong)
Jinfeng Li (The Chinese University of Hong Kong)
Xinyan Dai (The Chinese University of Hong Kong)
Hongzhi Chen (CUHK)
James Cheng (The Chinese University of Hong Kong)

More from the Same Authors