Transcript No Slide Title

Kinetic data structures
Goal
• Maintain a configuration of moving
objects
• Each object has a posted flight plan
(this is essentially a well behaved
function of time)
Example 1
Maintain the closest pair among points moving in the
plane
Example 2
Maintain the convex hull of points moving in the plane
Elements of a KDS
• An event queue (A heap of discrete
times)
• The event queue will contains all times
where the combinatorial structure of
the configuration may change
• Like a “sweep” of the time dimension
Example 3
Maintain the topmost among points moving along the
y-axis
Look at the ty-plane
y
t
We are interested in the upper
envelope
y
t
Solution
• Calculate this upper envelope !
• Sharir, Hart, Agarwal and others:
– The complexity of the envelope is close
to linear if any pair of function intersect
at most s times
– Can compute it in O(n log(n)) time
Problem
• If we would like to change a
trajectory then we need to
recompute te envelope
• That takes O(nlog(n)) time
• We want to be able to change a
trajectory faster
Another solution
• Maintain the points sorted
• For every pair of points put in the
event queue the time when they
switch order
Example 3
Problem
• We process Ω(n2) events
• But the configuration changes only
linear (or close to linear) number of
times…
So what do we want from a KDS
to be good
• You maintain a set of certificates
that as long as they are valid the
configuration does not change.
• Want: The number of times a
certificate fails (internal events) to
be small relative to the number of
times the configuration changes
(external events)
 Efficient
So what do we want from a KDS
to be good (Cont)
• Process a certificate failure fast
 responsive
• Small space
 compact
• Object participates in a small # of
cetificates (can change trajectories
easily)
 local
Dynamic KDS
• Want also to be able to insert and
delete objects efficiently
So what would be a good
solution for this problem ?
Maintain the topmost among points moving along the
y-axis
A tournament tree
d
c
b
a
b
d
a
c
A tournament tree
d
c
b
a
d
c
d
b
d
a
c
A tournament tree
d
c
b
a
d
c
d
b
d
a
c
For each internal node maintain in an event queue the
next time where the children flip order
d
c
d
b
d
a
c
d
c
b
a
y
Processing of an event: Replace the winner and
replace O(log(n)) events in the event queue
Takes O(log2(n)) time  responsive
Linear space  compact
Each point participates in O(log n) events  local
t
d
1
b
r
d
d
2
a
c
c
d
c
b
a
y
What is the total # of events ?
Events at r correpond to changes at the upper
envelope, lets say there are O(n)
Events at 1 correponds to change at the upper
envelope of {b d}  O(n/2) …
In total we get O(nlog(n)) events  efficient
t
d
1
b
r
d
d
2
a
c
c
d
c
b
a
y
Handeling insertions/deletions ?
Use some kind of a balanced binary search tree
Each node charges its events to the upper envelope of
its subtree
Without rotations we get O(nlog(n)) events
t
d
1
b
r
d
d
2
a
c
c
d
c
b
a
y
Handeling insertions/deletions
Because of rotations each point participates in more
than O(log n) envelopes
Use a BB[alpha] tree  think of each pair of nodes
participating in a rotation as new nodes, then the total
size of envelopes corresponding to new nodes is
O(nlog(n))
t
d
1
b
r
d
d
2
a
c
c
d
c
b
a
y
We’ll focus now a bit more at the case where the
points move with constant velocity
Can redefine the problem so we do not insist on
maintaining the upper envelope explicitly at all times
t
Parametic Heap
A collection of items, each with an associated key.
key (i) = ai x + bi
ai,, bi reals, x a real-valued parameter
ai = slope, bi = constant
Operations:
make an empty heap.
insert item i with key ai x + bi into the heap: insert(i,ai,bi)
find an item i of minimum key for x = x0: find-max( x0)
delete item i : delete(i)
Kinetic Heap
A parametric heap such that successive x-values of find maxs are
non-decreasing.
(Think of x as time.)
xc = largest x in a find max so far (current time)
Additional operation:
increase the key of an item i, replacing it by a key that is no larger
for all x > xc : increase-key(i,a,b)
What is known about parametric and kinetic
heaps?
Equivalent problems:
maintain the upper envelope of a collection of lines in 2D
projective duality
maintain the convex hull of a set of points in 2D
under insertion and deletion
Results I
Overmars and Van Leeuwen (1981)
O( log n) time per query
O(log2n) time per update, worst-case
Chazelle (1985), Hershberger and Suri (1992)
(deletions only)
O( log n) time per query, worst-case
O(n log n) for n deletions
Results II
Chan (1999)
Dynamic hulls and envelopes
O( log n) time per query
O(log1+en) time per update, amortized
Brodal and Jacob (2000), Kaplan, Tarjan, Tsioutsiouliklis (2000)
O( log n) time per query
O( log n log log log n) time per insert,
O( log n log log n) timer per delete, amortized
Results III
Basch, Guibas, and Hershberger (1997)
“Kinetic” data structure paradigm
Broadcast Scheduling
Server:
many
data items
Users
Broadcast
channel
(single-item)
One server, many possible items to send (say, all the same length)
One broadcast channel.
Users submit requests for items.
Goal: Satisfy users as well as possible, making
decisions on-line. (say, minimize sum of waiting times)
Scheduling policies
Greedy = Longest Wait first (LWF):
Send item with largest sum of waiting times.
R x W: send item with largest (# requests x longest waiting time)
-1
-4
(vs. number of
requests or longest
single waiting time)
Questions (for an algorithm guy or gal)
LWF does well compared to what?
Open question 1
_ Try a competitive analysis
Can we improve the cost of LWF?
_ What data structure?
Will talk about
this
Broadcast scheduling via kinetic heap
Need a max-heap (replace find min by find max,
decrease key by increase key, etc)
Can implement LWF or R x W or any similar policy:
Broadcast decision is find max plus delete
Request is insert (if first) or increase key (if not)
Only find max need be real-time, other ops can proceed
concurrently with broadcasting
Slopes are integers that count requests
Broadcast scheduling via kinetic heap
(Cont.)
LWF:
Suppose a request for item i arrives at time ts
If i is inactive then insert(i, t-ts)
If i is active with key at+b then increase-key(i, (a+1)t+(b-ts))
To broadcast an item at time ts we perform delete-max(ts)
and broadcast the item returned.