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

Wang, Z; Luo, T; Xu, G; Wang, X

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

Wang, Z Luo, T Xu, G

Wang, X

Permalink

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

Closed Access

	Filename	Description	Size
	06906792.pdf	Published version	489.28 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Wang, Z	en_US
dc.contributor.author	Luo, T	en_US
dc.contributor.author	Xu, G https://orcid.org/0000-0003-4493-6663	en_US
dc.contributor.author	Wang, X	en_US
dc.date.issued	2014-01-01	en_US
dc.identifier.citation	Proceedings - 2014 IEEE International Congress on Big Data, BigData Congress 2014, 2014, pp. 288 - 295	en_US
dc.identifier.isbn	9781479950577	en_US
dc.identifier.uri	http://hdl.handle.net/10453/33775
dc.description.abstract	© 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.	en_US
dc.relation.ispartof	Proceedings - 2014 IEEE International Congress on Big Data, BigData Congress 2014	en_US
dc.relation.isbasedon	10.1109/BigData.Congress.2014.49	en_US
dc.title	The application of cartesian-join of bloom filters to supporting membership query of multidimensional data	en_US
dc.type	Conference Proceeding
utslib.for	080101 Adaptive Agents and Intelligent Robotics	en_US
utslib.for	0806 Information Systems	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - AAI - Advanced Analytics Institute Research Centre
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

© 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:

http://hdl.handle.net/10453/33775