TY - GEN
T1 - Persistent bloom filter
T2 - 44th ACM SIGMOD International Conference on Management of Data, SIGMOD 2018
AU - Peng, Yanqing
AU - Guo, Jinwei
AU - Li, Feifei
AU - Qian, Weining
AU - Zhou, Aoying
N1 - Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/5/27
Y1 - 2018/5/27
N2 - Membership testing is the problem of testing whether an element is in a set of elements. Performing the test exactly is expensive space-wise, requiring the storage of all elements in a set. In many applications, an approximate testing that can be done quickly using small space is often desired. Bloom filter (BF) was designed and has witnessed great success across numerous application domains. But there is no compact structure that supports set membership testing for temporal queries, e.g., has person A visited aweb server between 9:30am and 9:40am? And has the same person visited the web server again between 9:45am and 9:50am? It is possible to support such "temporal membership testing" using a BF, but we will show that this is fairly expensive. To that end, this paper designs persistent bloom filter (PBF), a novel data structure for temporal membership testing with compact space.
AB - Membership testing is the problem of testing whether an element is in a set of elements. Performing the test exactly is expensive space-wise, requiring the storage of all elements in a set. In many applications, an approximate testing that can be done quickly using small space is often desired. Bloom filter (BF) was designed and has witnessed great success across numerous application domains. But there is no compact structure that supports set membership testing for temporal queries, e.g., has person A visited aweb server between 9:30am and 9:40am? And has the same person visited the web server again between 9:45am and 9:50am? It is possible to support such "temporal membership testing" using a BF, but we will show that this is fairly expensive. To that end, this paper designs persistent bloom filter (PBF), a novel data structure for temporal membership testing with compact space.
KW - Bloom filter
KW - Persistent bloom filter
KW - Persistent data structure
UR - https://www.scopus.com/pages/publications/85048824288
U2 - 10.1145/3183713.3183737
DO - 10.1145/3183713.3183737
M3 - 会议稿件
AN - SCOPUS:85048824288
T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data
SP - 1037
EP - 1052
BT - SIGMOD 2018 - Proceedings of the 2018 International Conference on Management of Data
A2 - Das, Gautam
A2 - Jermaine, Christopher
A2 - Eldawy, Ahmed
A2 - Bernstein, Philip
PB - Association for Computing Machinery
Y2 - 10 June 2018 through 15 June 2018
ER -