Efficient inner product search is important for many data ranking services, such as recommendation and Information Retrieval. Efficient retrieval via inner product dramatically influences the performance of such data searching and retrieval systems. To resolve deficiencies of prior approaches, embodiments of a new index graph construction approach, referred to generally as Norm Adjusted Proximity Graph (NAPG), for approximate Maximum Inner Product Search (MIPS) are presented. With adjusting factors estimated on sampled data, NAPG embodiments select more meaningful data points to connect with when constructing a graph-based index for inner product search. Extensive experiments verify that the improved graph-based index pushes the state-of-the-art of inner product search forward greatly, in the trade-off between search efficiency and effectiveness.