TY - JOUR

T1 - Dynamic layers of maxima with applications to dominating queries

AU - Kipouridis, E.

AU - Kosmatopoulos, A.

AU - Papadopoulos, A. N.

AU - Tsichlas, K.

PY - 2021

Y1 - 2021

N2 - Over the past years there has been an enormous increase in the amount of data generated on a daily basis. A critical task in handling the information overload is locating the most interesting objects of a dataset according to a specific configuration or ranking function. Our work is based on the concept of dominance which compares data objects based on maximization preferences on the attribute values. Each data object is represented as a point in a multidimensional space based on its attribute values. The layers of maxima configuration assigns layer numbers to dataset points so that (some) points inside a layer dominate (some) points in subsequent layers and no point in a layer dominates another in the same layer. Furthermore, top-k dominating queries combine the merits of skyline (maxima) queries and top-k queries by returning the k first points with the highest dominance score, where the dominance score of an object is the number of objects it dominates. In this work we focus on 2-dimensional data and present, for the first time, algorithms and data structures with non-trivial asymptotic guarantees for maintaining the first k layers of maxima of a dataset under point insertions and deletions. Furthermore, we apply this solution in a sliding window problem setting, where one of the attributes is the insertion time of the object, and deletions always remove the oldest object. Finally, we tackle updates of arbitrary points in the semi-dynamic problem setting which permits point insertions and in the fully-dynamic problem setting which supports both point insertions and deletions. All of our solutions assume the word RAM model of computation. More precisely, the coordinates of each point are numbers that can be represented with w bits, where w is a parameter of the model (for example, in practice, usually w=64). All solutions require space linear with the number of points which is a crucial requirement for modern day applications.

AB - Over the past years there has been an enormous increase in the amount of data generated on a daily basis. A critical task in handling the information overload is locating the most interesting objects of a dataset according to a specific configuration or ranking function. Our work is based on the concept of dominance which compares data objects based on maximization preferences on the attribute values. Each data object is represented as a point in a multidimensional space based on its attribute values. The layers of maxima configuration assigns layer numbers to dataset points so that (some) points inside a layer dominate (some) points in subsequent layers and no point in a layer dominates another in the same layer. Furthermore, top-k dominating queries combine the merits of skyline (maxima) queries and top-k queries by returning the k first points with the highest dominance score, where the dominance score of an object is the number of objects it dominates. In this work we focus on 2-dimensional data and present, for the first time, algorithms and data structures with non-trivial asymptotic guarantees for maintaining the first k layers of maxima of a dataset under point insertions and deletions. Furthermore, we apply this solution in a sliding window problem setting, where one of the attributes is the insertion time of the object, and deletions always remove the oldest object. Finally, we tackle updates of arbitrary points in the semi-dynamic problem setting which permits point insertions and in the fully-dynamic problem setting which supports both point insertions and deletions. All of our solutions assume the word RAM model of computation. More precisely, the coordinates of each point are numbers that can be represented with w bits, where w is a parameter of the model (for example, in practice, usually w=64). All solutions require space linear with the number of points which is a crucial requirement for modern day applications.

KW - Dynamic queries

KW - Layers of maxima

KW - Top-k dominating query

U2 - 10.1016/j.comgeo.2020.101699

DO - 10.1016/j.comgeo.2020.101699

M3 - Journal article

AN - SCOPUS:85089728013

VL - 93

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

M1 - 101699

ER -