TY - JOUR

T1 - How to search in history

AU - Chazelle, Bernard

N1 - Funding Information:
Consider the problem of maintaining a dynamic data structure over time. Typical operations will involve inserting new objects, deleting old objects, and of course, querying the data structure about its current state. If the structure is a dictionary a query is to look up a given item; if it is a priority queue it is to retrive the minimum or maximum element from the current set. In some applications it is sometimes needed to keep track of the configurations the data structure held at previous times. This need might arise in databases, for example, when one wishes to retrieve old information, or in other words, search in the past. In other contexts, the notion of time is only indirectly relevant. In circuit design rule checking, for instance, sweep-line algorithms are often used to report all pairs of intersecting rectangles (McCreight, 1980). It is convenient (and colorful) to think of, say, the sweeping direction as a time axis. This is all the more relevant that a sweep-line algorithm will indeed induce a one-to-one correspondence * This paper is a revised and expanded version of a paper presented at the International Conference on "Foundations of Computation Theory" held in Borgholm, Sweden, August 21-27, 1983. * This research was supported in part by NSF Grant MCS 83-03925 and the Office of Naval Research and the Defense Advanced Research Projects Agency under Contract N00014-83-K-0146 and ARPA Order 4786.

PY - 1985

Y1 - 1985

N2 - This paper considers the problem of granting a dynamic data structure the capability of remembering the situation it held at previous times. We present a new scheme for recording a history of h updates over an ordered set S of n objects, which allows fast neighbor computation at any time in the history. The novelty of the method is to allow the set S to be only partially ordered with respect to queries and the time measure to be multi-dimensional. The generality of the method makes it useful for a number of problems in 3-dimensional geometry. For example, we are able to give fast algorithms for locating a point in a 3-dimensional complex, using linear space, or for finding which of n given points is closest to a query plane. Using a simpler, yet conceptually similar technique, we show that with O(n2) preprocessing, it is possible to determine in O(log2 n) time which of n given points in E3 is closest to an arbitrary query point.

AB - This paper considers the problem of granting a dynamic data structure the capability of remembering the situation it held at previous times. We present a new scheme for recording a history of h updates over an ordered set S of n objects, which allows fast neighbor computation at any time in the history. The novelty of the method is to allow the set S to be only partially ordered with respect to queries and the time measure to be multi-dimensional. The generality of the method makes it useful for a number of problems in 3-dimensional geometry. For example, we are able to give fast algorithms for locating a point in a 3-dimensional complex, using linear space, or for finding which of n given points is closest to a query plane. Using a simpler, yet conceptually similar technique, we show that with O(n2) preprocessing, it is possible to determine in O(log2 n) time which of n given points in E3 is closest to an arbitrary query point.

UR - http://www.scopus.com/inward/record.url?scp=0020495002&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020495002&partnerID=8YFLogxK

U2 - 10.1016/S0019-9958(85)80045-0

DO - 10.1016/S0019-9958(85)80045-0

M3 - Article

AN - SCOPUS:0020495002

VL - 64

SP - 77

EP - 99

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 1-3

ER -