In this paper, we attack the problem of storing purpose and consent metadata. This special kind of data brings a constraint where a false positive signifies the violation of a regulation. Our approach allows necessary metadata for purpose and consent maintenance and enforcement to be efficiently organized as a custom filter data structure to enhance metadata storage and fast retrieval. Contrary to other filters in the literature, we show that our approach guarantees that no false positives occur to the users’ consent. We analyze the configuration knobs of this data structure, discuss improvements, and our experimental results show that our method outperforms a more traditional approach of storing a foreign key to refer to a purpose storage table.