  Nearest Neighbor Search (NNS) over generalized weighted distance 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 practical than the Euclidean distance for high-dimensional NNS. To the
best of our knowledge, no prior work presents a sublinear time solution to the
problem of NNS over the generalized weighted Manhattan distance. In this paper,
we propose two novel sublinear time hashing schemes ($d_w^{l_1},l_2$)-ALSH and
($d_w^{l_1},\theta$)-ALSH to solve the problem.
