Skip to content
master
Switch branches/tags
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
src
 
 
 
 
 
 

QuotientFilter

Java implementation of the approximate membership query set (AMQ)

A quotient filter, introduced by Bender et al. in 2011, is a space-efficient probabilistic data structure used to test whether an element is a member of a set (an approximate member query filter, AMQ). A query will elicit a reply specifying either that the element is definitely not in the set or that the element is probably in the set. The former result is definitive; i.e., the test does not generate false negatives. But with the latter result there is some probability, ε, of the test returning "element is in the set" when in fact the element is not present in the set (i.e., a false positive). There is a tradeoff between ε, the false positive rate, and storage size; increasing the filter's storage size reduces ε. Other AMQ operations include "insert" and "optionally delete". The more elements are added to the set, the larger the probability of false positives.

Build

cd $QuotientFilter_Dir

mvn clean package -DskipTests

Example:

See src/test/java/org/bucaojit/filter/InsertTest.java for a working example:

		QuotientFilter qf = new QuotientFilter(75);
		try {
			qf.insert(new String("value"));
			qf.insert(new String("second value"));
			qf.insert(new Long(343443));
			qf.insert(new Integer(444));
			qf.insert(new Integer(23));
			qf.insert(new String("343443"));
			qf.printQF();
			
			int output = qf.lookup(new String("value"));
			System.out.println("The value output: " + output);
			Assert.assertEquals(58, output);
			
			int outputSecond = qf.lookup(new Integer(23));
			System.out.println("The 23 output: " + outputSecond);
			Assert.assertEquals(0, outputSecond);
			
			int outputThird = qf.lookup(new Integer(444));
			System.out.println("The 4444 output: " + outputThird);
			Assert.assertEquals(1, outputThird);
			
			int outputFourth = qf.lookup(new String("Not Exists"));
			System.out.println("The 'Not Exists' output: " + outputFourth);			
		}
		catch(Exception e) {
			e.printStackTrace();
		}

Resulting output:

100:23 111:444 <empty><empty><empty>100:15763 <empty><empty><empty><empty>100:-6527 <empty><empty><empty><empty>
<empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty>
<empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty>
<empty><empty><empty><empty><empty><empty><empty><empty><empty><empty>100:-15675 <empty><empty>100:-28303 <empty>
<empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty><empty>


The value output: 58
The 23 output: 0
The 4444 output: 1
The 'Not Exists' output: -1

More Details here: http://en.wikipedia.org/wiki/Quotient_filter

About

Java implementation of the approximate membership query set (AMQ)

Resources

Releases

No releases published

Packages

No packages published

Languages