  Nearest Neighbor Search (NNS) over generalized weighted distances is
fundamental to a wide range of applications. The problem of NNS over the
generalized weighted square Euclidean distance has been studied in previous
work. However, numerous studies have shown that the Manhattan distance could be
more effective than the Euclidean distance for high-dimensional NNS, which
indicates that the generalized weighted Manhattan distance is possibly more
practical than the generalized weighted square Euclidean distance in high
dimensions. To the best of our knowledge, no prior work solves the problem of
NNS over the generalized weighted Manhattan distance in sublinear time. This
paper achieves the goal by proposing two novel hashing schemes
($d_w^{l_1},l_2$)-ALSH and ($d_w^{l_1},\theta$)-ALSH.
