In outsourced spatial databases, the LBS provides query services to the clients on behalf of the data owner. However, the LBS provider is not always trustworthy and it may send incomplete or incorrect query results to the clients. Therefore, ensuring spatial query integrity is critical. In this paper, we propose efficient R
NN query verification techniques which utilize the influence zone to check the integrity of query results. The methods in this work aim to verify both monochromatic and bichromatic R
NN queries results. Specifically, our methods can gain efficient performance on verifying bichromatic R
NN query results. Extensive experiments on both real and synthetic datasets demonstrate the efficiency of our proposed authenticating methods.