Campus Event Calendar

Event Entry

What and Who

Faster Nearest Neighbors Queries on Geographic Data

Niko Hastrich
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Thursday, 16 March 2023
30 Minutes
E1 4


The problem of finding the k-nearest neighbors (kNNs) of a point in a given set has been studied extensively due to its relevance in areas such as pattern recognition, machine learning, and location-based services. A major issue of the problem is that its complexity typically increases quickly with k, which we aim to mitigate in two steps. First, we build on the fact that the kNNs can be found using the radius they lie within, thus, reducing the initial problem to finding functions that represent these radii. Second, since the exact representation of these functions is intricate, we propose to utilize the structural properties of the input data in order to obtain simple upper bounds on these functions.

In the context of geographic data, we argue that concatenating segments of inverted quadratic functions yields suitable bounds and formalize an optimization problem with respect to the number of segments. We then present an approximation algorithm that computes such functions efficiently. The basic idea is to exploit geometrical properties of the underlying problem, allowing us to find suitable segments using linear programming and to obtain guarantees on the quality of the approximation.

We complement our theoretical analysis with an empirical evaluation of our algorithm on real-world data. With respect to run times, we observe that the resulting technique improves upon conventional methods for answering kNN queries, especially for larger k. In particular, we obtain speed-up factors of up to 18. Additionally, the experiments indicate that our method requires little space.


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 02/13/2023 16:21 -- Created document.