There has been substantial research on sub-linear time approximate algorithms for maximum inner product search (MIPS). To achieve fast query time, state-of-the-art techniques require significant preprocessing, which can be a burden when the number of subsequent queries is not sufficien