How can one store a mutable set of items `(t, p)` so that queries for the `k` items with minimized `(n-t)*p` for some `n` are efficient?

Question

For example: Given a list of objects with a time of last update (t) and a priority (p), when making updates to the objects we would like to minimize the worst (n - t) * p (at n = time now).

This is unsuitable to a normal priority queue as the results will vary in order from ascending t to descending p as n grows, but such a structure could be very useful if implementable on a database with millions of updateable rows of varying importance or for perfect, fast fair queueing in application logic.

Answer 1

In the absolute deterministic sense, I assert you won't have an efficient solution that is still fair - because your sorting key intrinsically "rots" as the time passes, therefore re-indexing would be needed.

However, if your priorities are a limited (small) set, you can arrange a stochastic way of processing:

1. keep P FIFO-s for jobs with equal priorities (P number of priorities)
2. in a loop, generate a random numbers X in [1..P] with a distribution varying with the priority and take the first job in the queue X

Think: at every N high priority jobs, one needs to pick some M (

Some notes:

1. generating random numbers with a custom distribution - if the language/library doesn't offer support for that (e.g. C++ does with std::discrete_distribution), a poor-man's solution would be to create an array with many equal entries for a priority and then uniform-randomly pick in index from it. E.g. for priorities 0..P, your array could look like [0,1,1,2,2,2,..., (Q+1 entries for priority Q)...]. You can apportion different weights by choosing how many "entries in the lottery" a certain priority will be granted (maybe you are not happy with the priority 1 being twice as lucky as priority 0 in the choice above).

2. treating the case of "the randomly picked queue is empty" - so many choices here: assign the wining lottery ticket to the underdog, or to the immediately higher priority non-empty queue, or just repeat the lottery... etc.

Answer 2

You can adapt the Overmars--van Leeuwen data structure for dynamic convex hull to get a data structure that provides insert/query/delete in time O(log^2 n).

OvL is a simple idea with a lot of data structural machinations to get the time and space complexity bounds that it achieves. In essence, the idea is to implement a divide and conquer algorithm for the upper convex hull problem with a very efficient merge step (O(log n)). When we change an item, we redo the O(log n) merge steps affected at a total cost of O(log^2 n).

I don't have time to type out the data structural details (IIRC, they're in the computational geometry textbook coauthored by Overmars, though I'm not near my copy), but I'll describe the analogy between this problem and computing a hull.

Consider, first, the upper hull. Let's suppose that we have three points p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3) with x1 < x2 < x3. The point p2 is contained in the upper hull of the points p1 and p3 if the line segment connecting p1 and p3 is "above" p2, i.e.,

(x3 - x2) y1 + (x2 - x1) y3
--------------------------- >= y2.
         (x3 - x1)

Consider, second, the urgency "hull" consisting of the items that are most urgent at some time past or present, where, for an item (t, p), the urgency at time n is (n - t) p, the sort key of interest. Given items i1 = (t1, p1), i2 = (t2, p2), i3 = (t3, p3) with p1 < p2 < p3, we say that i2 is subsumed by i1 and i3 if, at any time, either i1 or i3 is more urgent than i2. Formally, for all n, we have (n - t1) p1 >= (n - t2) p2 or (n - t3) p3 >= (n - t2) p2.

There is an analogy between subsumption and "above"ness.

In the sufficiently distant past, i1 is the most urgent of the three items. In the sufficiently distant future, i3 is the most urgent. The question is whether i2 is ever most urgent. If it is, then there exists n such that (n - t2) p2 > (n - t1) p1 and (n - t2) p2 > (n - t3) p3, and

p3 - p2               p2 - p1
------- (n - t1) p1 + ------- (n - t3) p3 < (n - t2) p2
p3 - p1               p3 - p1

  p3 - p2         p2 - p1
- ------- t1 p1 - ------- t3 p3 < - t2 p2
  p3 - p1         p3 - p1

(p3 - p2) (-t1 p1) + (p2 - p1) (-t3 p3)
--------------------------------------- < -t2 p2,
                p3 - p1

since the fractional coefficients of the first inequality are nonnegative and sum to one. Note the resemblance to the converse of the earlier inequality, with p replacing x and -t p replacing y.

Conversely, suppose that i2 is never most urgent. Let's find the crossover time n* where i1 and i3 have equal urgency. The quantity n* is the solution to the equation

(n* - t1) p1 = (n* - t3) p3

which is equivalent to

n* p3 - t3 p3 = n* p1 - t1 p1

n* (p3 - p1) = t3 p3 - t1 p1

     t3 p3 - t1 p1
n* = -------------.
        p3 - p1

Before n*, i1 is more urgent than i3 (and thus i1 is more urgent than i2). After n*, i3 is more urgent than i1 (and thus i3 is more urgent than i2). At n*, both i1 and i3 are hence at least as urgent as i2, so

(n* - t1) p1 >= (n* - t2) p2
(n* - t3) p3 >= (n* - t2) p2

p3 - p2                p2 - p1
------- (n* - t1) p1 + ------- (n* - t3) p3 >= (n* - t2) p2
p3 - p1                p3 - p1

  p3 - p2         p2 - p1
- ------- t1 p1 - ------- t3 p3 >= - t2 p2
  p3 - p1         p3 - p1

(p3 - p2) (-t1 p1) + (p2 - p1) (-t3 p3)
--------------------------------------- >= -t2 p2.
                p3 - p1

Apologies in advance about all of the degenerate cases that I'm ignoring.