.png){kind=icon}
返回
Hashing methods for temporal data
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2002.1019221.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 A: 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 timestamped 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 linear space on the total number of changes in the evolution of set S and has a small (O(log(B)(n/B))) query overhead. An experimental comparison of partially persistent hashing with various straightforward approaches (like external linear hashing, the Multiversion 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 the paper concentrates on linear hashing, the methodology applies to other dynamic hashing schemes as well.
Keyword:
hashing
temporal databases
transaction time
access methods
data structures
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.4
论文数:
6.8K
被引数:
3.2W
机构
暂无机构信息
引用论文
.png){kind=icon}
查看更多内容