User-Qualified Group Search using Bidirectional Sweep Planes

Abstract

In this paper, we propose a nearest user-qualified group (NUG) query that searches a group of objects to obtain a result. In detail, given a dataset P, query q, distance delta, and cardinality k, the NUG query returns the nearest group of objects from q, such that more than k objects within delta distance from the point, called a representative, are in the group. Although the NUG query has large spectrum of applications, an efficient processing algorithm for NUG queries has not been studied so far. Therefore, we propose the plane sweep-based incremental search algorithm and heuristic that stops the plane sweep early to reduce the search space. A performance study is conducted on both synthetic and real datasets and our experimental results show that the proposed algorithm can improve the query performance in a variety of conditions.