Comments (8)
So you need a family of hash functions to pull this off. If you have n hashfunctions, and an array of size s, the following block of code does the rest:
scala> def hashFunction(n:Int, s:Int) = {
| val p = math.ceil( (1 + math.sqrt(1+4*n))/2.0).toInt
| val a = (1 to (p-1))
| val b = (1 to p)
| (k:Int) => a.map( ia => b.map( ib => ((ia*k+ib)%p)%s)).flatten.slice(0,n)
| }
hashFunction: (n: Int, s: Int)Int => scala.collection.immutable.IndexedSeq[Int]
So if you need 10 hash functions over an array with capacity to store 100 elements:
scala> hashFunction(10,100)
res3: Int => scala.collection.immutable.IndexedSeq[Int] = <function1>
To actually use the 10 hash functions on a key, say key = 34
scala> res3(34)
res4: scala.collection.immutable.IndexedSeq[Int] = Vector(3, 0, 1, 2, 1, 2, 3, 0, 3, 0)
---
The family of hashfunction algo : From pg 267, Corman & Leiserson ( Designing a universal class of hash functions )
from algebird.
Edit: p has to be prime, btw :)
So the algorithm above needs a little more work.
from algebird.
We've already done this three times in the code: min hash, count min sketch, and bloom filter. Here's one more approach: http://stackoverflow.com/questions/9553989/what-hashing-techniques-to-use-when-building-a-bloom-filter-in-clojure
I don't think we need a new hash family. In fact, I'd argue we should only use one approach in this code.
from algebird.
Agreed, we should have a HashFamily that gets used by all of these.
BTW this is a variation of what @jmhodges calls "The opposite of a bloom filter", right?
http://www.somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter/
from algebird.
In that case, the 'val hashFunctions' implementation in min hash should suffice for my purposes.
I will suggest benchmarking... the Leiserson algo is very,very cheap - generate a prime number once and integral mod twice. Whereas the implementation you have uses a random number gen plus other heavy machinery - maybe more robust but also more expensive.
from algebird.
Do you feel aFlowerFilter.contains(item) should return a Boolean or an ApproximateBoolean like BloomFilter?
Although it goes against the precedent, I believe it might be better to return a Boolean because:
- goal is to be fast/streaming and calculating probability for this structure is really expensive (based on http://eng.42go.com/flower-filter-an-update/ plus extra multiplicative factor for possible collisions when converting item to Byte or Short)
- the user sets their decay and accuracy thresholds when initializing
- wouldn't be that useful for standard use cases
Feedback appreciated.
from algebird.
David, if we could get a correct bound on the Boolean, then we should do so. So, when it says true, the probabilty it is correct is 1. But when we say absent, what is the probability that another item has evicted that item? Can we derive such a bound?
from algebird.
Yes sir, a slight modification to http://eng.42go.com/flower-filter-an-update/ for fingerprinting collisions yields the true probability. Two other things that I missed:
- We can find a simple log bound as opposed to exact computation
- We can make the computation lazy so that the data structure is fast when the probabilities are not used.
from algebird.
Related Issues (20)
- Release cadance of algebrid, next planned release? HOT 5
- Scala 3 support? HOT 7
- microsite is failing CI because it depends on a very old ruby
- Release v.0.13.10 HOT 1
- SketchMap is not commutative
- `MinHasher32` tests are flaky
- Idea: BloomFilterAggregator can directly rely on a BitSet instead of a BFMonoid
- use fast immutable bitset for better bloom filter HOT 6
- The GeneratedTupleAggregator is not recognized HOT 2
- Add combinators on Semigroup, Monoid, Aggregator to reverse order. HOT 1
- flakey test: downsiding HLL to 4 bits HOT 1
- investigate flaky test on AdaptiveVector
- Latest version published with `-optimize` HOT 1
- configure mergify.io HOT 1
- H
- Investigate flaky `com.twitter.algebird.CollectionSpecification` test HOT 8
- Possible buffer overflow for lengths over 127. Why are you doing .toByte in order to represent an integer size of 4 bytes? For example item length of 184 will result in -72 and thus in NegativeArraySize Exception when deserializing in fromBytes : 94. HOT 1
- Possible buffer overflow for lengths over 127. HOT 4
- SparseVector monoid flake
- New release? HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from algebird.