125
contained inside other regions will also get higher priorities, the right endpoint of an inter-
val will always be further to the left than the right endpoint of an interval that contains it.
With this priority function, the problem can solved with a slightly non-standard application
of a priority search tree.
Priority search trees support what are known as two and a half-dimensional queries. A
priority search tree storing pairs (x, y), can support queries asking for all pairs with
x
1 £ x £ x
2 and y £ y
1 , where x
1 , x
2 , and y
1 are arbitrary query values. The y-dimension of the
priority search tree does not support fully general range queries, but fortunately the queries
it does support are sufficient. We represent a segment (s, e)with startsand endeas a pair
(e, s). To test for a segment with right endpoint less than or equal topthat overlaps a point
at v, search for all stored pairs withv £ x £ pand withy £ v. The condition onxandven-
sures that the result interval ends after the query point, and the condition on xandpen-
sures that the interval has a higher priority than p. The condition onyandvensures that
the result interval starts before v.
This structure enables the determination of whether an address is deleted by a move op-
eration with priority higher than a given value, in logarithmic time. Two small subtleties are
worth noting. Priority search trees require that all endpoints on the x-axis be unique in or-
der to maintain the runtime guarantees. This can be ensured in the standard way by making
the y-value a secondary key along thex-axis. But there is an additional need, imposed by
the constraint that Palimpsest must work in fully distributed environments without requir-
ing global communication. Two moves may well be created at separate sites with the same
right endpoints, but they must still have unique priorities, in case they are merged into the
same version. The uniqueness of these priorities must be ensured by additional information
to supplement the priority information given by the right endpoint of the move’s source
range. Fortunately the unique IDs of changes can be used to augment the positional order of
contained inside other regions will also get higher priorities, the right endpoint of an inter-
val will always be further to the left than the right endpoint of an interval that contains it.
With this priority function, the problem can solved with a slightly non-standard application
of a priority search tree.
Priority search trees support what are known as two and a half-dimensional queries. A
priority search tree storing pairs (x, y), can support queries asking for all pairs with
x
1 £ x £ x
2 and y £ y
1 , where x
1 , x
2 , and y
1 are arbitrary query values. The y-dimension of the
priority search tree does not support fully general range queries, but fortunately the queries
it does support are sufficient. We represent a segment (s, e)with startsand endeas a pair
(e, s). To test for a segment with right endpoint less than or equal topthat overlaps a point
at v, search for all stored pairs withv £ x £ pand withy £ v. The condition onxandven-
sures that the result interval ends after the query point, and the condition on xandpen-
sures that the interval has a higher priority than p. The condition onyandvensures that
the result interval starts before v.
This structure enables the determination of whether an address is deleted by a move op-
eration with priority higher than a given value, in logarithmic time. Two small subtleties are
worth noting. Priority search trees require that all endpoints on the x-axis be unique in or-
der to maintain the runtime guarantees. This can be ensured in the standard way by making
the y-value a secondary key along thex-axis. But there is an additional need, imposed by
the constraint that Palimpsest must work in fully distributed environments without requir-
ing global communication. Two moves may well be created at separate sites with the same
right endpoints, but they must still have unique priorities, in case they are merged into the
same version. The uniqueness of these priorities must be ensured by additional information
to supplement the priority information given by the right endpoint of the move’s source
range. Fortunately the unique IDs of changes can be used to augment the positional order of
