Hashing methods for temporal data
George Kollios, Vassilis J. Tsotras · IEEE Transactions on Knowledge and Data Engineering · 2002
External dynamic hashing has been used in traditional database systems as a fast method for answering membership queries. Given a dynamic set S of objects, a membership query asks whether an object with identity k is in (the most current state of) S. This paper addresses the more general problem of temporal hashing. In this setting, changes to the dynamic set are time-stamped and the membership query has a temporal predicate, as in: "Find whether object with identity k was in set S at time t". We present an efficient solution for this problem that takes an ephemeral hashing scheme and makes it partially persistent. Our solution, also termed partially persistent hashing, uses a space that is linear on the total number of changes in the evolution of set S and has a small {O[log/sub B/(n/B)]} query overhead. An experimental comparison of partially persistent hashing with various straightforward approaches (like external linear hashing, the multi-version B-tree and the R*-tree) shows that it provides the faster membership query response time. Partially persistent hashing should be seen as an extension of traditional external dynamic hashing in a temporal environment. It is independent of the ephemeral dynamic hashing scheme used; while this paper concentrates on linear hashing, the methodology applies to other dynamic hashing schemes as well.