0
$\begingroup$

I'm looking for a data structure to help me solve the following problems:

EDIT: This describes a skyline query.

Given a set of points (x,y), find the subset of points where if you order strictly increasing by one dimension, we only take points that are also strictly increasing in the other dimension.

We must be able to keep this subset consistent through updates of the values of these data points. Adding / deleting elements does not need to be supported.

E.g. order the dataset first strictly increasing in x, and then take only the data points where y is strictly increasing.

This is fairly trivial to solve if there's no updates. However, I'd like to find a good data structure to gives optimal complexity when updates are made to the data points. This feels somewhat non trivial, as some types of updates results in points falling out of the set, or points not in the active set to the added in.

More context, the application of this data structure is for the following problem. The values of x and y are the value of different functions and derivatives at point 0.

(f(0), f'(0)), (g(0), g'(0)), (h(0), h'(0)),....

All of the functions have a positive value at 0, and a negative derivative.

I'm building a fast lookup for an arbitrary value of x, which of these functions has the greatest value. My method is based on the following observation: if a function has a larger value at 0, we know for a small value of x then it will be greater. If the derivative of the small function is more steeply negative, then that function will always be less. However, if the function with the smaller value has a less steep derivative, then past some value x, the second function will be greater.

This translates fairly easily into the following algorithm: sort the values first by the function value, and iterate over the data and remove any points where the derivative value is not strictly increasing.

However, the parameters that define these functions may change over time, resulting in either their values or derivatives changing. I'd like to keep my lookup table up to date through these updates.

Improve this question
$\endgroup$
5
  • $\begingroup$ 1. Are you asking to be able to maintain the results of a skyline query (i.e., the Pareto front), as the data points change? 2. I don't really understand the specification of the subset in the second paragraph of the question: when you talk about "order by one dimension", it's not clear whether you mean "order by one dimension in strictly increasing order" or "order by one dimension in strictly decreasing order". 3. What kinds of update operations do you want to support? Can you edit the question to clarify these points? $\endgroup$
    – D.W. ♦
    Commented Sep 13, 2022 at 3:49
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/154110/755, stackoverflow.com/q/73697182/781723. Please do not post the same question on multiple sites. $\endgroup$
    – D.W. ♦
    Commented Sep 13, 2022 at 3:50
  • $\begingroup$ 1. Having read more about it, I believe you are correct that this is the same as a skyline query. 2. I don't think the ordering of the first dimension matters? 3. The set of points stays fixed, the values of the points (and therefore the ordering) get updated over time. $\endgroup$
    – sprw121
    Commented Sep 13, 2022 at 4:07
  • $\begingroup$ Please don't use "EDIT:". Instead, revise the question so it reads well for someone who encounters the question for the first time. See cs.meta.stackexchange.com/q/657/755. $\endgroup$
    – D.W. ♦
    Commented Sep 13, 2022 at 4:46
  • $\begingroup$ The definition in the paragraph beginning "Given a set..." does not match a skyline query. I suggest working through a small example. $\endgroup$
    – D.W. ♦
    Commented Sep 13, 2022 at 4:47

0

Reset to default

Browse other questions tagged or ask your own question.