Understanding and Improving Proximity Graph based Maximum Inner Product
  Search
  The inner-product navigable small world graph (ip-NSW) represents the
state-of-the-art method for approximate maximum inner product search (MIPS) and
it can achieve an order of magnitude speedup over the fastest baseline.
However, to date it is still unclear where its exceptional performance comes
from. In this paper, we show that there is a strong norm bias in the MIPS
problem, which means that the large norm items are very likely to become the
result of MIPS. Then we explain the good performance of ip-NSW as matching the
norm bias of the MIPS problem - large norm items have big in-degrees in the
ip-NSW proximity graph and a walk on the graph spends the majority of
computation on these items, thus effectively avoids unnecessary computation on
small norm items. Furthermore, we propose the ip-NSW+ algorithm, which improves
ip-NSW by introducing an additional angular proximity graph. Search is first
conducted on the angular graph to find the angular neighbors of a query and
then the MIPS neighbors of these angular neighbors are used to initialize the
candidate pool for search on the inner-product proximity graph. Experiment
results show that ip-NSW+ consistently and significantly outperforms ip-NSW and
provides more robust performance under different data distributions.
