The application of cartesian-join of bloom filters to supporting membership query of multidimensional data

Publication Type:
Conference Proceeding
Citation:
Proceedings - 2014 IEEE International Congress on Big Data, BigData Congress 2014, 2014, pp. 288 - 295
Issue Date:
2014-01-01
Metrics:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail06906792.pdf Published version489.28 kB
Adobe PDF
© 2014 IEEE. With the rapid accumulation of data in various types, modern database systems are facing the problem of managing multidimensional data. The main challenge is to design a highly efficient storage mechanism which can support fast item lookup with exact membership queries or partial information membership queries. This paper presents a novel data structure called Cartesian-join of Bloom Filters. The method maintains a matrix that stores the Cartesian product of attribute bloom filters, each of which represents one dimension of the dataset. Experiments show that the proposed approach can not only achieve the same false positive rate as the traditional bloom filter with the same size, but also have an advantageous feature of by-attribute membership query. The data structure uses only ten bits to store a four-dimensional item and the average false rate for a query is one percent. The algorithm is robust even if it goes through high-correlated queries.
Please use this identifier to cite or link to this item: