Hashing Methods for Temporal Data

External dynamic hashing has been used in traditional database systems as a fast method to answer membership queries. Given a dynamic set S of objects, a membership query asks whether an object with identity k is in the most current S. This paper addresses the more general problem of Temporal Hashing. In this setting changes to the dynamic set are timestamped and the membership query has a temporal predicate, as in: "find whether object with identity k was in the set S at time t". We present an efficient solution to the Temporal Hashing problem. Our solution, also termed partially persistent hashing, behaves as if a separate, ephemeral (i.e., non-temporal) dynamic hashing scheme is available on every state assumed by set S over time. However if the buckets of these hashing schemes were to be stored for each time of interest, the space would become prohibitively large (quadratic on the total number of changes in set S's evolution); instead, our method uses linear space. We compare ..