Towards Spatially- and Category-Wise k-Diverse Nearest Neighbors Queries

k-nearest neighbor (k-NN) queries are well-known and widely used in a plethora of applications. In the original definition of k-NN queries there is no concern regarding diversity of the answer set, even though in some scenarios it may be interesting. For instance, travelers may be looking for touristic sites that are not too far from where they are but that would help them seeing different parts of the city. Likewise, if one is looking for restaurants close by, it may be more interesting to return restaurants of different categories or ethnicities which are nonetheless relatively close. The interesting novel aspect of this type of query is that there are competing criteria to be optimized. We propose two approaches that leverage the notion of linear skyline queries in order to find spatially- and category-wise diverse k-NNs w.r.t. a given query point and which return all optimal solutions for any linear combination of the weights a user could give to the two competing criteria. Our experiments, varying a number of parameters, show that our approaches are several orders of magnitude faster than a straightforward approach.