concept course in category algorithms

appears as: course, course
Algorithms and Data Structures in Action

This is an excerpt from Manning's book Algorithms and Data Structures in Action.

But the improvement we get with trees comes to a price, of course. First, as with any data structure that uses pointers (lists, graphs, trees, etc...) we have a memory overhead in comparison to arrays. While with the latter we just need to reserve space for the data (plus maybe, depending on the implementation details, some constant space for pointers and the node structure itself), every tree node requires extra space for the pointers to its children and possibly to its parent.

So far with the theory, but of course implementing associative arrays to be used on real systems is a completely different thing.

Figure 4.4 Checking if an entry is in a Bloom filter, step by step.
(A) We start with the email we would like to check, “duffy@acme.com”.
(B) The key (our email) is processed through our set of hash functions: in our example we assume k=3, so we’ll have 3 different hash functions, H0, H1 and H2.
(C) Each hash function produces an index for our binary array: in this case the three indices might be, for instance, <9, 6, 2>.
(D) We access the elements of the binary array at those indices.
(E) The first element, at index 2, is 0. The other bits are 0 and 1 respectively.
(F) Since not all the bits we checked were equals to 1, it means that “duffy@acme.com”.is not stored in the Bloom filter, and we will return false.
The same workflow is followed for “roger@acme.com”, on the right: because all three bits checked are set to 1, we return true: this means that “roger@acme.com” might have been stored in the Bloom filter, with a certain degree of confidence.
Listing 10.10 The SsNode:: updateBoundingEnvelope method
function SsNode::updateBoundingEnvelope()                    #1
  points ← this.getCentroids()                        #2
  for i in {0..k-1} do                            #3
    this.centroid[i] ← mean({point[i] for point in points}        #4
  this.radius ← max{distance(this.centroid, entry) + entry.radius for entry in points}    #5