Data partitioning via bucketing bloom filters

Details Data partitioning via bucketing bloom filters Data partitioning via bucketing bloom filters

2007-06-11

2010-06-22

To, Baoquoc N (Department: 2162)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

07743013

ABSTRACT:
Multiple Bloom filters are generated to partition data between first and second disjoint data sets of elements. Each element in the first data set is assigned to a bucket of a first set of buckets, and each element in the second data set is assigned to a bucket of a second set of buckets. A Bloom filter is generated for each bucket of the first set of buckets. The Bloom filter generated for a bucket indicates that each element assigned to that bucket is part of the first data set, and that each element assigned to a corresponding bucket of the second set of buckets is not part of the first data set. Additionally, a Bloom filter corresponding to a subsequently received element can be determined and used to identify whether that subsequently received element is part of the first data set or the second data set.

REFERENCES:
patent: 5813000 (1998-09-01), Furlani
patent: 6691109 (2004-02-01), Bjornson et al.
patent: 6795817 (2004-09-01), Agarwal et al.
patent: 6907422 (2005-06-01), Predovic
patent: 6920477 (2005-07-01), Mitzenmacher
patent: 6978458 (2005-12-01), Ghosh et al.
patent: 7080101 (2006-07-01), Watson et al.
patent: 2005/0147240 (2005-07-01), Agrawal et al.
patent: 2007/0033354 (2007-02-01), Burrows et al.
patent: 2007/0078827 (2007-04-01), Sareen et al.
Cohen, et al., “Spectral Bloom Filters”, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, Date: 2003, pp. 241-252, ACM Press, New York, USA.
Li, et al., “On the Feasibility of Peer-to-Peer Web Indexing and Search”, p. 1-6, http://project-iris.com/irisbib/papers/searchfeasibility:iptps03/paper.pdf.
Lu, et al., “Panaché: A Scalable Distributed Index for Keyword Search”, pp. 1-10, http://pdos.csail.mit.edu/6.824-2002/projects/panache.pdf.

Affiliated with

Also associated with

Rating

Data partitioning via bucketing bloom filters does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data partitioning via bucketing bloom filters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data partitioning via bucketing bloom filters will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4176636