Range-max queries on uncertain data
Farah Chanchary
Carleton University

Many computational geometry problems start with 'Given a set of points in the plane --'. However, in many "real-world applications", due to noise and limitation of devices, the location or the existence of the data obtained may be imprecise or only partially reliable. In this situation, there has been a growing interest in managing uncertain datasets (or stochastic datasets), in which the data points are allowed to have some uncertainties. It is not clear how to use existing range-aggregation data structures to answer queries for uncertain points because they are not always range decomposable. A recent paper by Agarwal et al. (JCSS, 2018) presents an index structure to report the expected maximum value and the most likely maximum value for points lying in a d-dimensional orthogonal query rectangle in sublinear time using subquadratic space.