An Efficient Incremental Lower Bound Approach for Solving Approximate Nearest Neighbor Problem of Complex Vague Queries

In this paper, we define a complex vague query as a multi-feature nearest neighbor query. To answer such queries, the system must search on some feature spaces individually and then combine the results in order to return the final ones to the user. The feature spaces are usually multidimensional and maybe consist of a vast amount of data. Therefore searching costs are prohibitively expensive for complex vague queries. For only such a single-feature space, to alleviate the costs, problem of answering nearest neighbor and approximate nearest neighbor queries has been proposed and quite well addressed in the literature. This paper, however, introduces an approach for finding (1+??)-approximate nearest neighbor(s) of complex vague queries, which must deal with the problem on some feature spaces. This approach is based on a novel, efficient and general algorithm called ISA-Incremental hyper-Sphere Approach [12, 13], which has been recently introduced for solving nearest neighbor problem in the VQS-Vague Query System [22]. To the best of our knowledge, the work presented in this paper is one of the vanguard solutions for dealing with problem of approximate multi-feature nearest neighbor queries generally. Experimental results prove the efficiency of the proposed approach.