Yanqing Peng
PhD Student. Research Interest: Distributed chain database.


Book Chapter  Journal  Conference  Workshop  Tech Report]

Conference

2018

  • Persistent Bloom Filter: Membership Testing for the Entire History, Talk
    By Yanqing Peng,    Jinwei Guo,    Feifei Li,    Weining Qian,    Aoying Zhou
    In Proceedings of 37th ACM SIGMOD International Conference on Management of Data (SIGMOD 2018),  pages 1037-1052,  June,  2018.
    Abstract

    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 a web 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.