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

Book Chapter  Journal  Conference  Workshop  Tech Report]



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

    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.