Processing Conflict-Aware $k$ Nearest Neighbor Queries in Euclidean Space

The k-nearest neighbor (kNN) query is one of the important research topics in location-based services, with widespread applications in mapping services and geographic information systems. Unlike the traditional k-nearest neighbor query with a single query point, when a large number of queries initiate requests simultaneously, there may be situations where the same moving object is returned for multiple query points. We refer to this situation as kNN query conflict and the multiple kNN queries that may result in conflicts as conflict-sensitive kNN queries. In most practical applications, we cannot assign the same moving object to multiple queries; instead, we need to find
$k$
distinct moving objects for each query separately, different from the results of other queries. To address this, this paper proposes a globally optimized algorithm for conflict-sensitive kNN queries in Euclidean space. This algorithm, without computing the exact kNNs for each query point, quickly identifies the set of kNN queries that might have conflicting results, and then rapidly returns the query results for queries without conflicts with other queries. For the set of kNN queries that might have conflicting results, it computes an optimal assignment of moving object, ensuring that each query in the set is assigned
$k$
distinct moving objects, minimizing the sum of distances from each query point to their respective assigned
$k$
moving objects among all possible assignment schemes. Finally, the correctness and excellent performance of the algorithm are verified through extensive experiments conducted on a variety of datasets.