Multi-set membership queries are fundamental operations in data science. In this paper, we propose a new data structure for multi-set membership queries, named coloring embedder, which is fast, accurate, and memory efficient. The idea of coloring embedder is to first map elements to a high-dimensional space, which nearly eliminates hashing collisions, and then use a dimensional reduction representation, similar to coloring a graph, to save memory. Theoretical proofs and experimental results show that the coloring embedder is effective in solving the problem of multi-set membership queries. We also find that web cache sharing is one of the typical application scenarios of the multi-set membership queries and current methods based on Bloom filters always send redundant queries. We apply coloring embedder to web cache sharing by arranging our data structure on the on-chip and off-chip memory and designing query, insertion and deletion operations for this scenario. The experimental results show that compared with the present method, our method can reduce the queries sent by proxies while reaching equal hit rate with the same size of on-chip memory. The source code of coloring embedder has been released on Github.

Conventional frame-based cameras for multimedia computing have encountered important challenges in high-speed and extreme light scenarios. However, how to design a novel paradigm for visual perception that overcomes the disadvantages of conventional cameras still remains an open issue. In this paper, we propose a novel solution, namely retinomorphic sensing, which integrates fovea-like and peripheral-like sampling mechanisms to generate asynchronous visual streams using a unified representation as the retina does. Technically, our encoder incorporates an interaction controller to switch flexibly between dynamic and static sensing. Then, the decoder effectively extracts dynamic events for machine vision and reconstructs visual textures for human vision. The results show that our strategy enables it to sense dynamic events and visual textures meanwhile reduce data redundancy. We further build a prototype hybrid camera system to verify this strategy on vision tasks such as image reconstruction and object detection. We believe that this novel paradigm will provide insight into future multimedia computing. The code can be available at https://github.com/acmmm2021-bni-retinomorphic/retinomorphic-sensing.