text:
I don't think I'm going out on a limb saying that our conference last week was a success. Thanks to everyone who attended and thanks again to all the speakers. Muthu actually beat us to it and wrote up a nice summary. Very kind words from a great guy. For those of you that couldn't make it (or those that want to relive the fun) we posted the videos and slides. Thanks again to everyone for making it such a success!
Data Science Summit – Update
Foundation Capital and Aggregate Knowledge Sponsor Streaming/Sketching Conference
We, along with our friends at Foundation Capital, are pleased to announce a 1 day mini-conference on streaming and sketching algorithms in Big Data. We have gathered an amazing group of speakers from academia and industry to give talks. If you are a reader of this blog we would love to have you come! The conference will be on 6/20 (Thursday) from 10 AM to 5:30 PM at the 111 Minna Gallery in San Francisco and attendance is limited. Breakfast and lunch included!
There will also be a happy hour afterwards if you cannot make the conference or just want a beer.
The speaker list includes:
Muthu Muthukrishnan
The Count-Min Sketch, 10 Years Later
The Count-Min Sketch is a data structure for indexing data streams in very small space. In a decade since its introduction, it has found many uses in theory and practice, with data streaming systems and beyond. This talk will survey the developments.
Muthu Muthukrishnan is a Professor at Rutgers University and a Research Scientist at Microsoft, India. His research interest is in development of data stream theory and systems, as well as online advertising systems.
David P. Woodruff
Sketching as a Tool for Numerical Linear Algebra
The talk will focus on how sketching techniques from the data stream literature can be used to speed up well-studied algorithms for problems occurring in numerical linear algebra, such as least squares regression and approximate singular value decomposition. It will also discuss how they can be used to achieve very efficient algorithms for variants of these problems, such as robust regression.
David Woodruff joined the algorithms and complexity group at IBM Almaden in 2007 after completing his Ph.D. at MIT in theoretical computer science. His interests are in compressed sensing, communication, numerical linear algebra, sketching, and streaming.
Sam Ritchie
Summingbird: Streaming Map/Reduce at Twitter
Summingbird is a platform for streaming map/reduce used at Twitter to build aggregations in real-time or on hadoop. When the programmer describes her job, that job can be run without change on Storm or Hadoop. Additionally, summingbird can manage merging realtime/online computations with offline batches so that small errors in real-time do not accumulate. Put another way, summingbird gives eventual consistency in a manner that is easy for the programmer to reason about.
Sam Ritchie works on data analysis and infrastructure problems in Twitter's Revenue engineering team. He is co-author of a number of open-source Scala and Clojure libraries, including Bijection, Algebird, Cascalog 2 and ElephantDB. He holds a bachelor's degree in mechanical and aerospace engineering.
Alexandr Andoni
Similarity Search Algorithms
Nearest Neighbor Search is an ubiquitous problem in analyzing massive datasets: its goal is to process a set of objects (such as images), so that later, one can find the object most similar to a given query object. I will survey the state-of-the-art for this problem, starting from the (Kanellakis-award winning) technique of Locality Sensitive Hashing, to its more modern relatives, and touch upon connection to the theory of sketching.
Alexandr Andoni is a researcher in the Microsoft Research at Silicon Valley since 2010, after finishing his PhD in MIT's theory group and year-long postdoctoral position at Princeton University. His research interests revolve around algorithms for massive datasets, including similarity search and streaming/sublinear algorithms, as well as theoretical machine learning.
There will be a panel discussion on the topic of harboring research in startups. Speakers include:
Pete Skomoroch from the LinkedIn data science team.
Rob Grzywinski of Aggregate Knowledge.
Joseph Turian of Metaoptimize
Lightning talks
- Armon Dadgar (Kiip) – Sketching Data Structures at Kiip
- Blake Mizerany (Heroku) – An Engineer Reads a Data Sketch
- Timon Karnezos (AK) – TBD
- Jérémie Lumbroso (INRIA) – Philippe Flajolet's Contribution to Streaming Algorithms
Update! We posted the videos and slides for those of you that couldn't make it (or those that want to relive the fun). Enjoy!
Doubling the Size of an HLL Dynamically – Extra Bits…
Author's Note: This post is related to a few previous posts on the HyperLogLog algorithm. See Matt's overview of the algorithm, and see this for an overview of "folding" or shrinking HLLs in order to perform set operations. It is also the final post in a series on doubling the number of bins in HLLs. The first post dealt with the recovery time after doubling, and the second dealt with doubling's accuracy when taking unions of two HLLs.
The main draw to the HyperLogLog algorithm is its ability to make accurate cardinality estimates using small, fixed memory. In practice, there are two choices a user makes which determine how much memory the algorithm will use: the number of registers (bins) and the size of each register (how high they can count). As Timon discussed previously, increasing the size of each register will only increase the accuracy if the true cardinality of the stream is HUGE.
Recall that HyperLogLog (and most other streaming algorithms) is designed to work with a fixed number of registers, , which is chosen as a function of the expected cardinality to approximate. We track a great number of different cardinality streams and in this context it is useful for us to not have one fixed value of , but to have this evolve with the needs of a given estimation.
We are thus confronted with many engineering problems, some of which we have already discussed. In particular, one problem is that the neat feature of sketches, namely that they allow for an estimate of the cardinality of the union of multiple streams at no cost, depends on having sketches of the same size.
We've discussed how to get around this by folding HLLs, though with some increase in error. We've also explored a few options on how to effectively perform a doubling procedure. However, we started to wonder if any improvements could be made by using just a small amount of extra memory, say an extra bit for each register. In this post we will discuss one such idea and its use in doubling. Note: we don't talk about quadrupling or more. We limit ourselves to the situation where HLL sketches only differ in 's by 1.
The Setup
One of the downfalls in doubling is that it there is no way to know, after doubling, whether a value belongs in its bin or its partner bin. Recall that a "partner bin" is the register that could have been used had our "prefix" (the portion of the hashed value which is used to decide which register to update) been one bit longer. If the binary representation of the bin index used only two bits of the hashed value, e.g. , then in an HLL that used a three-bit index, the same hashed value could have been placed in the bin whose index is either or . Since and are the same number, we call the "partner bin". (See the "Key Processing" section in Set Operations On HLLs of Different Sizes).
Consider an example where we have an HLL with bins.The bin has the value 7 in it, and after doubling we guess that its partner bin, at index , should have a 5 in it. It is equally likely that the bin should have the 5 in it and the bin should have the 7 in it (since the "missing" prefix bit could have been a 1 or a 0)! Certainly the arrangement doesn't change the basic cardinality estimate, but once we start getting involved with unions, the arrangement can make a very large difference.
To see how drastic the consequences can be, let's look at a simple example. Suppose we start with an HLL with 2 bins and get the value 6 in each of its bins. Then we run the doubling procedure and decide that the partner bins should both have 1's in them. With this information, it is equally likely that both of the arrangements below, "A" and "B", could be the "true" larger HLL.
Further suppose we have some other data with which we wish to estimate the union. Below, I've diagrammed what happens when we take the union.
Arrangement A leads to a cardinality estimate (of the union) of about 12 and Arrangement B leads to a cardinality estimate (of the union) of about 122. This is an order of magnitude different! Obviously not all cases are this bad, but this example is instructive. It tells us that knowing the true location of each value is very important. We've attempted to improve our doubling estimate by keeping an extra bit of information as we will describe below.
The Algorithm
Suppose we have an HLL with bins. Let's keep another array of data which holds total bits, one for each bin — we will call these the "Cached Values." For each bin, we keep a 0 if the value truly belongs in the bin in which it was placed (i.e. if, had we run an HLL with bins, the value would have been placed in the first bins in the HLL), and we keep a 1 if the value truly belongs in the partner bin of the one in which it was placed (i.e. if, had we run an HLL with bins, the value would have been placed in the last bins). See the image below for an example. Here we see two HLLs which have processed the same data. The one on the left is half the size and collects the cached values as it runs on the data. The one on the right is simply the usual HLL algorithm run on the same data.
Looking at the first row of the small HLL (with bins), the cache value means that the 2 "belongs" in the top half of the large HLL, i.e. if we had processed the stream using a larger HLL the 2 would be in the same register. Essentially this cached bit allows you to know exactly where the largest value in a bin was located in the larger HLL (if the bin has value and cached value , we place the value in the = bin).
In practice, when we double, we populate the doubled HLL first with the (now correct location) bin values from the original HLL then we fill the remaining bins by using our "Proportion Doubling" algorithm.
Before we begin looking at the algorithm's performance, let's think about how much extra space this requires. In our new algorithm, notice that for each bin, we keep around either a zero or a one as its cached value. Hence, we require only one extra bit per bin to accommodate the cached values. Our implementation of HLL requires 5 bits per bin, since we want to be able to include values up to in our bins. Thus, a standard HLL with bins, requires bits. Hence, this algorithm requires bits (with the extra bins representing the cached values). This implies that this sketch requires 20% more space.
The Data
Recall in the last post in this series, we explored doubling with two main strategies: Random Estimate (RE) and Proportion Doubling (PD). We did the same here, though using the additional information from this cached bit. We want to know a few things:
- Does doubling using a cache bit work? i.e. is it better to fold the bigger one or double the smaller one when comparing HLL's of different sizes?
- Does adding in a cache bit change which doubling strategy is preferred (RE or PD)?
- Does the error in union estimate depend on intersection size as we have seen in the past?
For each experiment we took 2 sets of data (each generated from 200k random keys) and estimated the intersection size between them using varying methods.
- "Folded": estimate by filling up an HLL with and comparing it to a folded HLL starting from and folded down
- "Large": estimate by using two HLL's of a larger HLL of . This is effectively a lower bound for our doubling approaches.
- "Doubled – PD": estimate by taking an HLL of and double it up to using the Proportion Doubling strategy. Once this larger HLL is approximated we estimate the intersection with another HLL of native size
- "Doubled – RE": estimate by taking an HLL of and doubling up to using Random Estimate strategy.
We performed an experiment 300 times at varying intersection sizes from 0 up to 200k (100%) overlapping elements between sets (in steps of 10k). The plots below show our results (and extrapolate between points).
The graph of the mean error looks pretty bad for Random Estimate doubling. Again we see that the error depends heavily on the intersection size and becomes more biased as the set's overlap more. On the other hand, Proportion Doubling was much more successful (recall that this strategy forces the proportion of bins in the to-be-doubled HLL and the HLL with which we will union it to be equal before and after doubling.) It's possible there is some error bias with small intersections but we would need to run more trials to know for sure. As expected, the "Folded" and the "Large" are centered around zero. But what about the spread of the error?
The Proportion Doubling strategy looks great! In my last post on this subject, we found that this doubling strategy (without the cached part) really only worked well in the large intersection size regime, but here, with the extra cache bits, we seem to avoid that. Certainly the large intersection regime is where the standard deviation is lowest, but for every intersection size, it is significantly lower than that of the smaller HLL. This suggests that one of our largest sources of error when we use doubling in conjunction with unions is related to our lack of knowledge of the arrangement of the bins (i.e. when doubling, we do not know which of the two partner bins gets the larger, observed value). So it appears that the strategy of keeping cache bits around does indeed work, provided you use a decent doubling scheme.
Interestingly, it is always much better to double a smaller cache HLL than to fold a larger HLL when comparing sketches of different sizes. This is represented above by the lower error of the doubled HLL than the small HLL. The error bounds do seem to depend on the size of the intersection between the two sets but this will require more work to really understand how, especially in the case of Proportion Doubling.
Notes: In this work we focus solely on doubling a HLL sketch and then immediately using this new structure to compute set operations. It would be interesting to see if set operation accuracy changes as a doubled HLL goes through its "recovery" period under varying doubling methods. It is our assumption that nothing out of the ordinary would come of this, but we definitely could be wrong. We will leave this as an exercise for the reader.
We've found an interesting way of trading space for accuracy with this cached bit method, but there are certainly other ways of using an extra bit or two (per bucket). For instance, we could keep more information about the distribution of each bin by keeping a bit indicating whether or not the bin's value minus one has been seen. (If the value is , keep track of whether has shown up.)
We should be able to use any extra piece of information about the distribution or position of the data to help us obtain a more accurate estimate. Certainly, there are a myriad of other ideas ways of storing a bit or two of extra information per bin in order to gain a little leverage — it's just a matter of figuring out what works best. We'll be messing around more with this in the coming weeks, so if you have any ideas of what would work best, let us know in the comments!
(P.S. A lot of our recent work has been inspired by Flajolet et al.'s paper on PCSA – check out our post on this here!)
Thanks to Jeremie Lumbroso for his kind input on this post. We are much indebted to him and hopefully you will see more from our collaboration.
Sketch of the Day: Probabilistic Counting with Stochastic Averaging (PCSA)
Before there was LogLog, SuperLogLog or HyperLogLog there was Probabilistic Counting with Stochastic Averaging (PCSA) from the seminal work "Probabilistic Counting Algorithms for Data Base Applications" (also known as the "FM Sketches" due to its two authors, Flajolet and Martin). The basis of PCSA matches that of the other Flajolet distinct value (DV) counters: hash values from a collection into binary strings, use patterns in those strings as indicators for the number of distinct values in that collection (bit-pattern observables), then use stochastic averaging to combine m trials into a better estimate. Our HyperLogLog post has more details on these estimators as well as stochastic averaging.
The choice of observable pattern in PCSA comes from the knowledge that in a collection of randomly generated binary strings, the following probabilities occur:
For each value added to the DV counter, a suitable hash is created and the position of the least-significant (right-most) 1 is determined. The corresponding position in a bitmap is updated and stored. I've created the simulation below so that you can get a feel for how this plays out.
(All bit representations in this post are numbered from 0 (the least-significant bit) on the right. This is the opposite of the direction in which they're represented in the paper.)
Run the simulation a few times and notice how the bitmap is filled in. In particular, notice that it doesn't necessarily fill in from the right side to the left — there are gaps that exist for a time that eventually get filled in. As the cardinality increases there will be a block of 1s on the right (the high probability slots), a block of 0s on the left (the low probability slots) and a "fringe" (as Flajolet et al. called it) of 1s and 0s in the middle.
I added a small pointer below the bitmap in the simulation to show how the cardinality corresponds to the expected bit position (based on the above probabilities). Notice what Flajolet et al. saw when they ran this same experiment: the least-significant (right-most) 0 is a pretty good estimator for the cardinality! In fact when you run multiple trials you see that this least-significant 0 for a given cardinality has a narrow distribution. When you combine the results with stochastic averaging it leads to a small relative error of and estimates the cardinality of the set quite well. You might have also observed that the most-significant (left-most) 1 can also be used for an estimator for the cardinality but it isn't as clear-cut. This value is exactly the observable used in LogLog, SuperLogLog and HyperLogLog and does in fact lead to the larger relative error of (in the case of HLL).
The PCSA algorithm is elegant in its simplicity:
m = 2^b # with b in [4...16] bitmaps = [[0]*32]*m # initialize m 32bit wide bitmaps to 0s ############################################################################################## # Construct the PCSA bitmaps for h in hashed(data): bitmap_index = 1 + get_bitmap_index( h,b ) # binary address of the rightmost b bits run_length = run_of_zeros( h,b ) # length of the run of zeroes starting at bit b+1 bitmaps[ bitmap_index ][ run_length ] = 1 # set the bitmap bit based on the run length observed ############################################################################################## # Determine the cardinality phi = 0.77351 DV = m / phi * 2 ^ (sum( least_sig_bit( bitmap ) ) / m) # the DV estimate
Stochastic averaging is accomplished via the arithmetic mean.
You can see PCSA in action by clicking on the image below.
There is one point to note about PCSA and small cardinalities: Flajolet et al. mention that there are "initial nonlinearities" in the algorithm which result in poor estimation at small cardinalities () which can be dealt with by introducing corrections but they leave it as an exercise for the reader to determine what those corrections are. Scheuermann et al. did the leg work in "Near-Optimal Compression of Probabilistic Counting Sketches for Networking Applications" and came up with a small correction term (see equation 6). Another approach is to simply use the linear (ball-bin) counting introduced in the HLL paper.
Set Operations
Just like HLL and KMV, unions are trivial to compute and lossless. The PCSA sketch is essentially a "marker" for runs of zeroes, so to perform a union you merely bit-wise OR the two sets of bitmaps together. Folding a PCSA down to a smaller m works the same way as HLL but instead of HLL's max you bit-wise OR the bitmaps together. Unfortunately for intersections you have the same issue as HLL, you must perform them using the inclusion/exclusion principle. We haven't done the plots on intersection errors for PCSA but you can imagine they are similar to HLL (and have the benefit of the better relative error ).
PCSA vs. HLL
That fact that PCSA has a better relative error than HyperLogLog with the same number of registers () is slightly deceiving in that (the number of stored observations) are different sizes. A better way to look at it is to fix the accuracy of the sketches and see how they compare. If we would like to have the same relative error from both sketches we can see that the relationship between registers is:
Interestingly, PCSA only needs a little more than half the registers of an HLL to reach the same relative error. But this is also deceiving. What we should be asking is what is the size of each sketch if they provide the same relative error? HLL commonly uses a register width of 5 bits to count to billions whereas PCSA requires 32 bits. That means a PCSA sketch with the same accuracy as an HLL would be:
A PCSA sketch with the same accuracy is 3.6 times larger than HLL!
But what if you could make PCSA smaller by reducing the size of the bitmaps? Near the end of the paper in the Scrolling section, Flajolet et al. bring up the point that you can make the bitmaps take up less space. From the simulation you can observe that with a high probability there is a block of consecutive 1s on the right side of the bitmap and a block of consecutive 0s on the left side of the bitmap with a fringe in between. If one found the "global fringe" — that is the region defined by the left-most 1 and right-most 0 across all bitmaps — then only those bits need to be stored (along with an offset value). The authors theorized that a fringe width of 8 bits would be sufficient (though they fail to mention if there are any dependencies on the number of distinct values counted). We put this to the test.
In our simulations it appears that a fringe width of 12 bits is necessary to provide an unbiased estimator comparable to full-fringe PCSA (32-bit) for the range of distinct values we analyzed. (Notice the consistent bias of smaller fringe sizes.) There are many interesting reasons that this "fringe" concept can fail. Look at the notes to this post for more. If we take the above math and update 32 to 12 bits per register (and include the 32 bit offset value) we get:
This is getting much closer to HLL! The combination of tighter bounds on the estimate and the fact that the fringe isn't really that wide in practice result in PCSA being very close to the size of the much lauded HLL. This got us thinking about further compression techniques for PCSA. After all, we only need to get the sketch about 1/3 smaller to be comparable in size to HLL. In a future post we will talk about what happens if you Huffman code the PCSA bitmaps and the tradeoffs you make when you do this.
PCSA provides for all of the goodness of HLL: very fast updates making it suitable for real-time use, small footprint compared to the information that it provides, tunable accuracy and unions. The fact that it has a much better relative error per register than HLL indicates that it should get more credit than it does. Unfortunately, each bitmap in PCSA requires more space than HLL and you still get less accuracy per bit. Look for a future post on how it is possible to use compression (e.g. Huffman encoding) to reduce the number of bits per bitmap, thus reducing the error per bit to match that of HLL, resulting in an approach that matches HLL in size but exceeds its precision!
Notes on the Fringe
While we were putting this post together we discovered many interesting things to look at with respect to fringe optimization. One of the questions we wanted to answer was "How often does the limited size of the fringe muck up a bitmap?" Below is a plot that shows how often any given sketch had a truncation event (that affected the DV estimate) in the fringe of any one of its bitmaps for a given fringe width (i.e. some value could not be stored in the space available).
Note that this is an upper bound on the error that could be generated by truncation. If you compare the number of runs that had a truncation event (almost all of the runs) with the error plot in the post it is quite shocking that the errors are as small as they are.
Since we might not get around to all of the interesting research here, we are calling out to the community to help! Some ideas:
- There are likely a few ways to improve the fringe truncation. Since PCSA is so sensitive to the least-significant 1 in each bitmap, it would be very interesting to see how different approaches affect the algorithm. For example, in our algorithm we "left" truncated meaning that all bitmaps had to have a one in the least-significant position of the bitmap in order to move up the offset. It would be interesting to look at "right" truncation. If one bitmap is causing many of the others to not record incoming values perhaps it should be bumped up. Is there some math to back up this intuition?
- It is interesting to us that the fringe width truncation events are DV dependent. We struggled with the math on this for a bit before we just stopped. Essentially we want to know what is the width of the theoretical fringe? It obviously appears to be DV dependent and some sort of coupon collector problem with unequal probabilities. Someone with better math skills than us needs to help here.
Closing thoughts
We uncovered PCSA again as a way to go back to first principles and see if there are lessons to be learned that could be applied to HLL to make it even better. For instance, can all of this work on the fringe be applied to HLL to reduce the number of bits per register while still maintaining the same precision? HLL effectively records the "strandline" (what we call the left-most 1s). More research into how this strandline behaves and if it is possible to improve the storage of it through truncation could reduce the standard HLL register width from 5 bits to 4, a huge savings! Obviously, we uncovered a lot of open questions with this research and we feel there are algorithmic improvements to HLL right around the corner. We have done some preliminary tests and the results so far are intriguing. Stay tuned!
HyperLogLog Engineering: Choosing The Right Bits
Author's Note: this is just a quick post about an engineering hiccup we ran into while implementing HyperLogLog features that aren't mentioned in the original paper. We have an introduction to the algorithm and several other posts on the topic if you're interested.
Say you had two HyperLogLog data structures with 5-bit-wide registers, one with and the other with , and wanted to compute their union. You could just follow my colleague Chris' advice and "fold" the larger one down to the size of the smaller one and then proceed as usual taking the pairwise max of the registers. This turns out to be a more involved process than Chris makes it out to be if you designed your HLL implementation in a particular way. For instance, if you use the 15 least(/most) significant bits of the 64-bit hashed input to determine register index and the next 30 bits to determine the register value, you end up in a tricky situation when you truncate the last 4 bits of the index to get the new 11-bit index.
If you imagine feeding the same element into an HLL of the smaller size, then the 4 bits you truncated from the index would have actually been used in the computation of the register value.
You couldn't simply take the original register value you computed, you'd have to take into account the new prefix added to the register value bit string. If the prefix has a 1 in it, you would recompute the run of zeroes on just the prefix (because you know it contains a 1 and thus all the information you need), and if not, you'd add the length of the prefix to the original register value computed. Not a ton of work, but having clutter like this in algorithmic code distracts the reader from the true intention. So how do we avoid this?
Well, you could say that it's very, very unlikely that you'll ever need more than 30 bits for your register value, so you could assume that the register width would remain constant forever and use the bottom 30 bits for your register value and the next bits for your register index. That way you could just truncate the last 4 bits of the index and know that your register value would still be the same. On the other hand, if you're Google, that may not be true. In that case, what you should do is use the least (/most) significant bits of your hashed value for the register index and the 30 most (/least) significant bits for the register value.
Now you can just truncate the register index and use the original register value.
If you're using a good hash function like MurmurHash3 that gives you 128 bits of entropy, you could simply compute the register index from the first 64-bit word in the hash and compute the register value from the second 64-bit word and completely ignore this problem up to a mind-bending and register width of 6 (aka the heat death of the universe).
I know it's not always possible to anticipate this problem in the early stages of implementing and vetting an algorithm, but hopefully with a bit of research the next time someone looks to implement HLL they'll see this and learn from our mistake.
Doubling the Size of an HLL Dynamically – Unions
Author's Note: This post is related to a few previous posts dealing with the HyperLogLog algorithm. See Matt's overview of the algorithm, and see this post for an overview of "folding" or shrinking HLLs in order to perform set operations. It is also the second in a series of three posts on doubling the number of bins of HLLs. The first post dealt with the recovery time after doubling and the next post will deal with ways to utilize an extra bit or two per bin.
Let's say we have two streams of data which we're monitoring with the HLL algorithm, and we'd like to get an estimate on the cardinality of these two streams combined, i.e. thought of as one large stream. In this case, we have to take advantage of the algorithm's built-in "union" feature. Done naively, the accuracy of the estimate will depend entirely on the the number of bins, , of the smaller of the two HLLs. In this case, to make our estimate more accurate, we would need to increase this of one (or both) of our HLLs. This post will investigate the feasibility of doing this; we will apply our idea of "doubling" to see if we can gain any accuracy. We will not focus on intersections, since the only support the HyperLogLog algorithm has for intersections is via the inclusion/exclusion principle. Hence the error can be kind of funky for this – for a better overview of this, check out Timon's post here. For this reason, we only focus on how the union works with doubling.
The Strategy: A Quick Reminder
In my last post we discussed the benefits and drawbacks of many different doubling strategies in the context of recovery time of the HLL after doubling. Eventually we saw that two of our doubling strategies worked significantly better than the others. In this post, instead of testing many different strategies, we'll focus instead on one strategy, "proportion doubling" (PD), and how to manipulate it to work best in the context of unions. The idea behind PD is to guess the approximate intersection cardinality of the two datasets and to force that estimate to remain after doubling. To be more specific, suppose we have an HLL and an HLL with bins and bins, respectively. Then we check what proportion of bins in , call it , agree with the bins in . When we doubled , we fill in the bins by randomly selecting bins, and filling them in with the value in the corresponding bins in . To fill in the rest of the bins, we fill them in randomly according to the distribution.
The Naive Approach
To get some idea of how well this would work, I put the most naive strategy to the test. The idea was to run 100 trials where I took two HLLs (one of size and one of size ), ran 200K keys through them, doubled the smaller one (according to Random Estimate), and took a union. I had a hunch that the accuracy of our estimate after doubling would depend on how large the true intersection cardinality of the two datasets would be, so I ran this experiment for overlaps of size 0, 10K, 20K, etc. The graphs below are organized by the true intersection cardinality, and each graph shows the boxplot of the error for the trials.
This graph is a little overwhelming and a bit of a strange way to display the data, but is useful for getting a feel for how the three estimates work in the different regimes. The graph below is from the same data and just compares the "Small" and "Doubled" HLLs. The shaded region represents the middle 50% of the data, and the blue dots represent the data points.
The first thing to notice about these graphs is the accuracy of the estimate in the small intersection regime. However, outside of this, the estimates are not very accurate – it is clearly a better choice to just use the estimate from the smaller HLL.
Let's try a second approach. Above we noticed that the algorithm's accuracy depended on the cardinality of the intersection. Let's try to take that into consideration. Let's use the "Proportion Doubling" (PD) strategy we discussed in our first post. That post goes more in depth into the algorithm, but the take away is that this doubling strategy preserves the proportion of bins in the two HLLs which agree. I ran some trials like I did above to get some data on this. The graphs below represent this.
Here we again, show the data in a second graph comparing just the "Doubled" and "Small" HLL estimates. Notice how much tighter the middle 50% region is on the top graph (for the "Doubled" HLL). Hence in the large intersection regime, we get very accurate estimates.
One thing to notice about the second set of graphs is how narrow the error bars are. Even when the estimate is biased, it still has much smaller error. Also, notice that this works well in the large intersection regime but horribly in the small intersection regime. This suggests that we may be able to interpolate our strategies. The next set of graphs is for an attempt at this. The algorithm gets an estimate of the intersection cardinality, then decides to either double using PD, double using RE, or not double depending on whether the intersection is large, small, or medium.
Here, the algorithm works well in the large intersection regime and doesn't totally crap out outside of this regime (like the second algorithm), but doesn't sustain the accuracy of the first algorithm in the small intersection regime. This is most likely because the algorithm cannot "know" which regime it is in and thus, must make a guess. Eventually, it will guess wrong will severely underestimate the union cardinality. This will introduce a lot of error, and hence, our boxplot looks silly in this regime. The graph below shows the inefficacy of this new strategy. Notice that there are virtually no gains in accuracy in the top graph.
With some trickery, it is indeed possible to gain some some accuracy when estimating the cardinality of the union of two HLLs by doubling one. However, in order for this to be feasible, we need to apply the correct algorithm in the correct regime. This isn't a major disappointment since for many practical cases, it would be easy to guess which regime the HLLs should fall under and we could build in the necessary safeguards if we guess incorrectly. In any case, our gains were modest but certainly encouraging!
HyperLogLog++: Google's Take On Engineering HLL
Matt Abrams recently pointed me to Google's excellent paper "HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm" [UPDATE: changed the link to the paper version without typos] and I thought I'd share my take on it and explain a few points that I had trouble getting through the first time. The paper offers a few interesting improvements that are worth noting:
- Move to a 64-bit hash function
- A new small-cardinality estimation regime
- A sparse representation
I'll take a look at these one at a time and share our experience with similar optimizations we've developed for a streaming (low latency, high throughput) environment.
32-bit vs. 64-bit hash function
I'll motivate the move to a 64-bit hash function in the context of the original paper a bit more since the Google paper doesn't really cover it except to note that they wanted to count billions of distinct values.
Some math
In the original HLL paper, a 32-bit hash function is required with the caveat that measuring cardinalities in the hundreds of millions or billions would become problematic because of hash collisions. Specifically, Flajolet et al. propose a "large range correction" for when the estimate is greater than . In this regime, they replace the usual HLL estimate by the estimate
This reduces to a simple probabilistic argument that can be modeled with balls being dropped into bins. Say we have an -bit hash. Each distinct value is a ball and each bin is designated by a value in the hash space. Hence, you "randomly" drop a ball into a bin if the hashed value of the ball corresponds to the hash value attached to the bin. Then, if we get an estimate for the cardinality, that means that (approximately) of our bins have values in them, and so there are empty bins. The number of empty bins should be about , where is the number of balls. Hence . Solving this gives us the formula he recommends using: .
Aside: The empty bins expected value comes from the fact that
where is the number of bins and the number of balls. This is pretty quick to show by induction. Hence,
as .
Again, the general idea is that the ends up being some number smaller than because some of the balls are getting hashed to the same value. The correction essentially doesn't do anything in the case when is small compared to as you can see here. (Plotted is , where represents , against the line . The difference between the two graphs represents the difference between and .)
A solution and a rebuttal
The natural move to start estimating cardinalities in the billions is to simply move to a larger hash space where the hash collision probability becomes negligibly small. This is fairly straightforward since most good hash functions give you at least 64-bits of entropy these days and it's also the size of a machine word. There's really no downside to moving to the larger hash space, from an engineering perspective. However, the Google researchers go one step further: they increase the register width by one bit (to 6), as well, ostensibly to be able to support the higher possible register values in the 64-bit setting. I contend this is unnecessary. If we look at the distribution of register values for a given cardinality, we see that it takes about a trillion elements before a 5-bit register overflows (at the black line):
The distributions above come from the LogLog paper, on page 611, right before formula 2. Look for .
Consider the setting in the paper where . Let's says we wanted to safely count into the 100 billion range. If we have then our new "large range correction" boundary is roughly one trillion, per the adapted formula above. As you can see from the graph below, even at the large range correction only kicks in at a little under 100 billion!
The black line is the cutoff for a 5-bit register, and the points are plotted when the total number of hash bits required reaches 40, 50, and 60.
The real question though is all this practically useful? I would argue no: there are no internet phenomena that I know of that are producing more than tens of billions of distinct values, and there's not even a practical way of empirically testing the accuracy of HLL at cardinalities above 100 billion. (Assuming you could insert 50 million unique, random hashed values per second, it would take half an hour to fill an HLL to 100 billion elements, and then you'd have to repeat that 5000 times as they do in the paper for a grand total of 4 months of compute time per cardinality in the range.)
[UPDATE: After talking with Marc Nunkesser (one of the authors) it seems that Google may have a legitimate need for both the 100 billion to trillion range right now, and even more later, so I retract my statement! For the rest of us mere mortals, maybe this section will be useful for picking whether or not you need five or six bits.]
At AK we've run a few hundred test runs at 1, 1.5, and 2 billion distinct values under the configuration range and found the relative error to be identical to that of lower cardinalities (in the millions of DVs). There's really no reason to inflate the storage requirements for large cardinality HLLs by 20% simply because the hash space has expanded. Furthermore, you can do all kinds of simple tricks like storing an offset as metadata (which would only require at most 5 bits) for a whole HLL and storing the register values as the difference from that base offset, in order to make use of a larger hash space.
Small Cardinality Estimation
Simply put, the paper introduces a second small range correction between the existing one (linear counting) and the "normal" harmonic mean estimator ( in the original paper) in order to eliminate the "large" jump in relative error around the boundary between the two estimators.
They empirically calculate the bias of and create a lookup table for various , for 200 values less than with a correction to the overestimate of . They interpolate between the 200 reference points to determine the correction to apply for any given raw value. Their plots give compelling evidence that this bias correction makes a difference in the to cardinality range (cuts 95th percentile relative error from about 2% to 1.2%).
I've been a bit terse about this improvement since sadly it doesn't help us at AK much because most of our data is Zipfian. Few of our reporting keys live in the narrow cardinality range they are optimizing: they either wallow in the linear counting range or shoot straight up into the normal estimator range.
Nonetheless, if you find you're doing a lot of DV counting in this range, these corrections are pretty cheap to implement (as they've provided numerical values for all the cutoffs and bias corrections in the appendix.)
Sparse representation
The general theme of this optimization isn't particularly new (our friends at MetaMarkets mentioned it in this post): for smaller cardinality HLLs there's no need to materialize all the registers. You can get away with just materializing the set registers in a map. The paper proposes a sorted map (by register index) with a hash map off the side to allow for fast insertions. Once the hash map reaches a certain size, its entries are batch-merged into the sorted list, and once the sorted list reaches the size of the materialized HLL, the whole thing is converted to the fully-materialized representation.
Aside: Though the hash map is a clever optimization, you could skip it if you didn't want the added complexity. We've found that the simple sorted list version is extremely fast (hundreds of thousands of inserts per second). Also beware the variability of the the batched sort-and-merge cost every time the hash map repeatedly outgrows its limits and has to be merged into the sorted list. This can add significant latency spikes to a streaming system, whereas a one-by-one insertion sort to a sorted list will be slower but less variable.
The next bit is very clever: they increase when the HLL is in the sparse representation because of the saved space. Since they're already storing entries in 32-bit integers, they increase to . (I'll get to the leftover bit in a second!) This gives them increased precision which they can simply "fold" down when converting from the sparse to fully materialized representation. Even more clever is their trick of not having to always store the full register value as the value of an entry in the map. Instead, if the longer register index encodes enough bits to determine the value, they use the leftover bit I mentioned before to signal as much.
In the diagram, and are as in the Google paper, and and are the number of bits that need to be examined to determine for either the or regime. I encourage you to read section 5.3.3 as well as EncodeHash and DecodeHash in Figure 8 to see the whole thing. [UPDATE: removed the typo section as it has been fixed in the most recent version of the paper (linked at the top)]
The paper also tacks on a difference encoding (which works very well because it's a sorted list) and a variable length encoding to the sparse representation to further shrink the storage needed, so that the HLL can use the increased register count, , for longer before reverting to the fully materialized representation at . There's not much to say about it because it seems to work very well, based on their plots, but I'll note that in no way is that type of encoding suitable for streaming or "real-time" applications. The encode/decode overhead simply takes an already slow (relative to the fully materialized representation) sparse format and adds more CPU overhead.
The researchers at Google have done a great job with this paper, meaningfully tackling some hard engineering problems and showing some real cleverness. Most of the optimizations proposed work very well in a database context, where the HLLs are either being used as temporary aggregators or are being stored as read-only data, however some of the optimizations aren't suitable for streaming/"real-time" work. On a more personal note, it's very refreshing to see real algorithmic engineering work being published from industry. Rob, Matt, and I just got back from New Orleans and SODA / ALENEX / ANALCO and were hoping to see more work in this area, and Google sure did deliver!
Sebastiano Vigna brought up the point that 6-bit registers are necessary for counting above 4 billion in the comments. I addressed it in the original post (see "A solution and a rebuttal") but I'll lay out the math in a bit more detail here to show that you can easily count above 4 billion with only 5-bit registers.
If you examine the original LogLog paper (the same as mentioned above) you'll see that the register distribution for LogLog (and HyperLogLog consequently) registers is
where is the register value and is the number of (distinct) elements a register has seen.
So, I assert that 5 bits for a register (which allows the maximum value to be 31) is enough to count to ten billion without any special tricks. Let's fix and say we insert distinct elements. That means, any given register will see about elements assuming we have a decent hash function. So, the probability that a given register will have a value greater than 31 is (per the LogLog formula given above)
and hence the expected number of registers that would overflow is approximately . So five registers out of sixteen thousand would overflow. I am skeptical that this would meaningfully affect the cardinality computation. In fact, I ran a few tests to verify this and found that the average number of registers with values greater than 31 was 4.5 and the relative error had the same standard deviation as that predicted by the paper, .
For argument, let's assume that you find those five overflowed registers to be unacceptable. I argue that you could maintain an offset in 5 bits for the whole HLL that would allow you to still use 5 bit registers but exactly store the value of every register with extremely high probability. I claim that with overwhelmingly high probability, every register the HLL used above is greater than 15 and less than or equal to 40. Again, we can use the same distribution as above and we find that the probability of a given register being outside those bounds is
Effectively, there are no register values outside of . Now I know that I can just store 15 in my offset and the true value minus the offset (which now fits in 5 bits) in the actual registers.
HLL Intersections
The intersection of two streams (of user ids) is a particularly important business need in the advertising industry. For instance, if you want to reach suburban moms but the cost of targeting those women on a particular inventory provider is too high, you might want to know about a cheaper inventory provider whose audience overlaps with the first provider. You may also want to know how heavily your car-purchaser audience overlaps with a certain metro area or a particular income range. These types of operations are critical for understanding where and how well you're spending your advertising budget.
As we've seen before, HyperLogLog provides a time- and memory-efficient algorithm for estimating the number of distinct values in a stream. For the past two years, we've been using HLL at AK to do just that: count the number of unique users in a stream of ad impressions. Conveniently, HLL also supports the union operator ( ) allowing us to trivially estimate the distinct value count of any composition of streams without sacrificing precision or accuracy. This piqued our interest because if we can "losslessly" compute the union of two streams and produce low-error cardinality estimates, then there's a chance we can use that estimate along with the inclusion-exclusion principle to produce "directionally correct" cardinality estimates of the intersection of two streams. (To be clear, when I say "directionally correct" my criteria is "can an advertiser make a decision off of this number?", or "can it point them in the right direction for further research?". This often means that we can tolerate relative errors of up to 50%.)
The goals were:
- Get a grasp on the theoretical error bounds of intersections done with HLLs, and
- Come up with heuristic bounds around , , and the set cardinalities that could inform our usage of HLL intersections in the AK product.
Quick terminology review:
- If I have set of integers , I'm going to call the HLL representing it .
- If I have HLLs and their union , then I'm going to call the intersection cardinality estimate produced .
- Define the between two sets as .
- Define the cardinality ratio as a shorthand for the relative cardinality of the two sets.
- We'll represent the absolute error of an observation as .
That should be enough for those following our recent posts, but for those just jumping in, check out Appendices A and B at the bottom of the post for a more thorough review of the set terminology and error terminology.
We fixed 16 values (0.0001, 0.001, 0.01, 0.02, 0.05, 0.1, 0.15, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0) and 12 set cardinalities (100M, 50M, 10M, 5M, 1M, 500K, 100K, 50K, 10K, 5K, 1K, 300) and did 100 runs of each permutation of . A random stream of 64-bit integers hashed with Murmur3 was used to create the two sets such that they shared exactly elements. We then built the corresponding HLLs and for those sets and calculated the intersection cardinality estimate and computed its relative error.
Given that we could only generate and insert about 2M elements/second per core, doing runs with set cardinalities greater than 100M was quickly ruled out for this blog post. However, I can assure you the results hold for much larger sets (up to the multiple billion-element range) as long as you heed the advice below.
This first group of plots has a lot going on, so I'll preface it by saying that it's just here to give you a general feeling for what's going on. First note that within each group of boxplots increases from left to right (orange to green to pink), and within each plot cardinality ratio increases from left to right. Also note that the y-axis (the relative error of the observation) is log-base-10 scale. You can clearly see that as the set sizes diverge, the error skyrockets for all but the most similar (in both cardinality and composition) sets. I've drawn in a horizontal line at 50% relative error to make it easier to see what falls under the "directionally correct" criteria. You can (and should) click for a full-sized image.
Note: the error bars narrow as we progress further to the right because there are fewer observations with very large cardinality ratios. This is an artifact of the experimental design.
A few things jump out immediately:
- For cardinality ratio > 500, the majority of observations have many thousands of percent error.
- When cardinality ratio is smaller than that and , register count has little effect on error, which stays very low.
- When , register count has little effect on error, which stays very high.
Just eyeballing this, the lesson I get is that computing intersection cardinality with small error (relative to the true value) is difficult and only works within certain constraints. Specifically,
- , and
- .
The intuition behind this is very simple: if the error of any one of the terms in your calculation is roughly as large as the true value of the result then you're not going to estimate that result well. Let's look back at the intersection cardinality formula. The left-hand side (that we are trying to estimate) is a "small" value, usually. The three terms on the right tend to be "large" (or at least "larger") values. If any of the "large" terms has error as large as the left-hand side we're out of luck.
So, let's say you can compute the cardinality of an HLL with relative error of a few percent. If is two orders of magnitude smaller than , then the error alone of is roughly as large as .
by definition, so
In the best scenario, where , the errors of and are both roughly the same size as what you're trying to measure. Furthermore, even if but the overlap is very small, then will be roughly as large as the error of all three right-hand terms.
On the bubble
Let's throw out the permutations whose error bounds clearly don't support "directionally correct" answers ( and ) and those that trivially do () so we can focus more closely on the observations that are "on the bubble". Sadly, these plots exhibit a good deal of variance inherent in their smaller sample size. Ideally we'd have tens of thousands of runs of each combination, but for now this rough sketch will hopefully be useful. (Apologies for the inconsistent colors between the two plots. It's a real bear to coordinate these things in R.) Again, please click through for a larger, clearer image.
By doubling the number of registers, the variance of the relative error falls by about a quarter and moves the median relative error down (closer to zero) by 10-20 points.
In general, we've seen that the following cutoffs perform pretty well, practically. Note that some of these aren't reflected too clearly in the plots because of the smaller sample sizes.
|Register Count
|Data Structure Size
|Overlap Cutoff
|Cardinality Ratio Cutoff
Error Estimation
To get a theoretical formulation of the error envelope for intersection, in terms of the two set sizes and their overlap, I tried the first and simplest error propagation technique I learned. For variables , and a linear combination of those (independent) variables, we have
Applied to the inclusion-exclusion formula:
as in section 4 ("Discussion") of the HLL paper.
Aside: Clearly is not independent of , though is likely independent of . However, I do not know how to a priori calculate the covariance in order to use an error propagation model for dependent variables. If you do, please pipe up in the comments!
I've plotted this error envelope against the relative error of the observations from HLLs with 8192 registers (approximately 5kB data structure).
Despite the crudeness of the method, it provided a 95% error envelope for the data without significant differences across cardinality ratio or . Specifically, at least 95% of observations satisfied
However, it's really only useful in the ranges shown in the table above. Past those cutoffs the bound becomes too loose and isn't very useful.
This is particularly convenient because you can tune the number of registers you need to allocate based on the most common intersection sizes/overlaps you see in your application. Obviously, I'd recommend everyone run these tests and do this analysis on their business data, and not on some contrived setup for a blog post. We've definitely seen that we can get away with far less memory usage than expected to successfully power our features, simply because we tuned and experimented with our most common use cases.
Next Steps
We hope to improve the intersection cardinality result by finding alternatives to the inclusion-exclusion formula. We've tried a few different approaches, mostly centered around the idea of treating the register collections themselves as sets, and in my next post we'll dive into those and other failed attempts!
Appendix A: A Review Of Sets
Let's say we have two streams of user ids, and . Take a snapshot of the unique elements in those streams as sets and call them and . In the standard notation, we'll represent the cardinality, or number of elements, of each set as and .
Example: If then .
If I wanted to represent the unique elements in both of those sets combined as another set I would be performing the union, which is represented by .
Example: If then .
If I wanted to represent the unique elements that appear in both and I would be performing the intersection, which is represented by .
Example: With as above, .
The relationship between the union's cardinality and the intersection's cardinality is given by the inclusion-exclusion principle. (We'll only be looking at the two-set version in this post.) For reference, the two-way inclusion-exclusion formula is .
Example: With as above, we see that and .
For convenience we'll define the between two sets as .
Example: With as above, .
Similarly, for convenience, we'll define the cardinality ratio as a shorthand for the relative cardinality of the two sets.
The examples and operators shown above are all relevant for exact, true values. However, HLLs do not provide exact answers to the set cardinality question. They offer estimates of the cardinality along with certain error guarantees about those estimates. In order to differentiate between the two, we introduce HLL-specific operators.
Consider a set . Call the HLL constructed from this set's elements . The cardinality estimate given by the HLL algorithm for is .
Define the union of two HLLs , which is also the same as the HLL created by taking the pairwise max of 's and 's registers.
Finally, define the intersection cardinality of two HLLs in the obvious way: . (This is simply the inclusion-exclusion formula for two sets with the cardinality estimates instead of the true values.)
Appendix B: A (Very Brief) Review of Error
The simplest way of understanding the error of an estimate is simply "how far is it from the truth?". That is, what is the difference in value between the estimate and the exact value, also known as the absolute error.
However, that's only useful if you're only measuring a single thing over and over again. The primary criteria for judging the utility of HLL intersections is relative error because we are trying to measure intersections of many different sizes. In order to get an apples-to-apples comparison of the efficacy of our method, we normalize the absolute error by the true size of the intersection. So, for some observation whose exact value is non-zero , we say that the relative error of the observation is . That is, "by what percentage off the true value is the observation off?"
Example: If then the relative error is .
HLLs and Polluted Registers
It's worth thinking about how things can go wrong, and what the implications of such occurrences might be. In this post, I'll be taking a look at the HyperLogLog (HLL) algorithm for cardinality estimation, which we've discussed before.
The Setup
HLLs have the property that their register values increase monotonically as they run. The basic update rule is:
for item in stream: index, proposed_value = process_hashed_item(hash(item)) hll.registers[index] = max(hll.registers[index], proposed_value)
There's an obvious vulnerability here: what happens to your counts if you get pathological data that blows up a register value to some really large number? These values are never allowed to decrease according to the vanilla algorithm. How much of a beating can these sketches take from such pathological data before their estimates are wholly unreliable?
Experiment The First
To get some sense of this, I took a 1024 bucket HLL, ran a stream through it, and then computed the error in the estimate. I then proceeded to randomly choose a register, max it out, and compute the error again. I repeated this process until I had maxed out 10% of the registers. In pseudo-python:
print("n_registers_touched,relative_error") print(0, relative_error(hll.cardinality(), stream_size), sep = ",") for index, reg in random.sample(range(1024), num_to_edit): hll.registers[reg] = 32 print(index + 1, relative_error(hll.cardinality(), stream_size), sep = ",")
In practice, HLL registers are fixed to be a certain bit width. In our case, registers are 5 bits wide, as this allows us to count runs of 0s up to length 32. This allows us to count astronomically high in a 1024 register HLL.
Repeating this for many trials, and stream sizes of 100k, 1M, and 10M, we have the following picture. The green line is the best fit line.
What we see is actually pretty reassuring. Roughly speaking, totally poisoning x% of registers results in about an x% error in your cardinality estimate. For example, here are the error means and variances across all the trials for the 1M element stream:
|Number of Registers Modified
|Percentage of Registers Modified
|Error Mean
|Error Variance
Initial Reactions
I was actually not too surprised to see that the induced error was modest when only a small fraction of the registers were poisoned. Along with some other machinery, the HLL algorithm uses the harmonic mean of the individual register estimates when computing its guess for the number of distinct values in the data stream. The harmonic mean does a very nice job of downweighting values that are significantly larger than others in the set under consideration:
In [1]: from scipy.stats import hmean In [2]: from numpy import mean In [3]: f = [1] * 100000 + [1000000000] In [4]: mean(f) Out[4]: 10000.899991000089 In [5]: hmean(f) Out[5]: 1.0000099999999899
It is this property that provides protection against totally wrecking the sketch's estimate when we blow up a fairly small fraction of the registers.
Experiment The Second
Of course, the algorithm can only hold out so long. While I was not surprised by the modesty of the error, I was very surprised by how linear the error growth was in the first figure. I ran the same experiment, but instead of stopping at 10% of the registers, I went all the way to the end. This time, I have plotted the results with a log-scaled y-axis:
Without getting overly formal in our analysis, there are roughly three phases in error growth here. At first, it's sublinear on the log-scale, then linear, then superlinear. This roughly corresponds to "slow", "exponential", and "really, really, fast". As our mathemagician-in-residence points out, the error will grow roughly as p/(1-p) where p is the fraction of polluted registers. The derivation of this isn't too hard to work out, if you want to give it a shot! The implication of this little formula matches exactly what we see above. When p is small, the denominator does not change much, and the error grows roughly linearly. As p approaches 1, the error begins to grow super-exponentially. Isn't it nice when experiment matches theory?
Final Thoughts
It's certainly nice to see that the estimates produced by HLLs are not overly vulnerable to a few errant register hits. As is often the case with this sort of analysis, the academic point must be put in balance with the practical. The chance of maxing out even a single register under normal operation is vanishingly small, assuming you chose a sane hash function for your keys. If I was running an HLL in the wild, and saw that 10% of my registers were pegged, my first thought would be "What is going wrong with my system!?" and not "Oh, well, at least I know my estimate to within 10%!" I would be disinclined to trust the whole data set until I got a better sense of what caused the blowups, and why I should give any credence at all to the supposedly unpolluted registers.
Doubling the Size of an HLL Dynamically – Recovery
Author's Note: This post is related to a few previous posts dealing with the HyperLogLog algorithm. See Matt's overview of HLL, and see this post for an overview of "folding" or shrinking HLLs in order to perform set operations. It is also the first in a series of three posts on doubling the size of HLLs – the next two will be about set operations and utilizing additional bits of data, respectively.
In this post, we explore the error of the cardinality estimate of an HLL whose size has been doubled using several different fill techniques. Specifically, we're looking at how the error changes as additional keys are seen by the HLL.
A Quick Reminder – Terminology and Fill Strategies
If we have an HLL of size and we double it to be an HLL of size , we call two bins "partners" if their bin number differs by . For example, in an HLL double to be size , the bins and are partners, as are and , etc. The Zeroes doubling strategy fills in the newly created bins with zeroes. The Concatenate strategy fills in the newly created bins with the values of their partner bins. MinusTwo fills in each bin with two less than its partner bin's value. RE fills in the newly created bins according to the empirical distribution of each bin.
Some Sample Recovery Paths
Below, we ran four experiments to check recovery time. Each experiment consisted of running an HLL of size 210 on 500,000 unique hashed keys (modeled here using a random number generator), doubling the HLL to be size 211, and then ran 500,000 more hashed keys through the HLL. Below, we have graphs showing how the error decreases as more keys are added. Both graphs show the same data (the only difference being the scale on the y-axis). We have also graphed "Large," an HLL of size , and "Small," an HLL of size , which are shown only for comparison and are never doubled.
One thing to note about the graphs is that the error is relative.
Notice that Concatenate and Zeroes perform particularly poorly. Even after 500,000 extra keys have been added, they still don't come within 5% of the true value! For Zeroes, this isn't too surprising. Clearly the initial error of Zeroes, that is the error immediately after doubling, should be high. A quick look at the harmonic mean shows why this occurs. If a single bin has a zero as its value, the harmonic mean of the values in the bins will be zero. Essentially, the harmonic mean of a list always tends towards the lowest elements of the list. Hence, even after all the zeroes have been replaced with positive values, the cardinality estimate will be very low.
On the other hand, a more surprising result is that Concatenate gives such a poor guess. To see this we need to look at the formula for the estimate again. The formula for the cardinality estimate is where is the value in the bin, is the number of bins, and is a constant approaching about . For Concatenate, the value is equal to . Hence we have that the cardinality estimate for Concatenate is:
Notice that this last term is about equal to 2 times the cardinality estimate of the HLL before doubling. One quick thing that we can take away from this is that it is unlikely for two "partner" bins to have the same value in them (since if this happens frequently, we get an estimate close to that given by Concatenate – which is very inaccurate!).
As for MinusTwo and RE, these have small initial error and the error only falls afterwards. The initial error is small since the rules for these give guesses approximately equal to the guess of the original HLL before doubling. From here, the error should continue to shrink, and eventually, it should match that of the large HLL.
One thing we noticed was that error for Concatenate in the graph above suggested that the absolute error wasn't decreasing at all. To check this we looked at the trials and, sure enough, the absolute error stays pretty flat. Essentially, Concatenate overestimates pretty badly, and puts the HLL in a state where it thinks it has seen twice as many keys as it actually has. In the short term, it will continue to make estimates as if it has seen 500,000 extra keys. We can see this clearly in the graphs below.
Recovery Time Data
I also ran 100 experiments where we doubled the HLLs after adding 500,000 keys, then continued to add keys until the cardinality estimate fell within 5% of the true cardinality. The HLLs were set up to stop running at 2,000,000 keys if they hadn't arrived at the error bound.
Notice how badly Concatenate did! In no trials did it make it under 5% error. Zeroes did poorly as well, though it did recover eventually. My guess here is that the harmonic mean had a bit to do with this – any bin with a low value, call it , in it would pull the estimate down to be about . As a result, the estimate produced by the Zeroes HLL will remain depressed until every bin is hit with a(n unlikely) high value. Zeroes and Concatenate should not do well since essentially the initial estimate (after doubling) of each HLL is off by a very large fixed amount. The graph of absolute errors, above, shows this.
On the other hand, RE and MinusTwo performed fairly well. Certainly, RE looks better in terms of median and middle 50%, though its variance is much higher than MinusTwo's.This should make sense as we are injecting a lot of randomness into RE when we fill in the values, whereas MinusTwo's bins are filled in deterministically.
Recovery Time As A Function of Size
One might wonder whether the recovery time of MinusTwo and RE depend on the size of the HLL before the doubling process. To get a quick view of whether or not this is true, we did 1,000 trials like those above but by adding 200K, 400K, 600K, 800K, 1M keys and with a a cutoff of 3% this time. Below, we have the box plots for the data for each of these. The headings of each graph gives the size of the HLL before doubling, and the y-axis gives the fractional recovery time (the true recovery time divided by the size of the HLL before doubling).
Notice that, for each doubling rule, there is almost no variation between each of the plots. This suggests that the size of the HLL before doubling doesn't change the fractional recovery time. As a side note, one thing that we found really surprising is that RE is no longer king – MinusTwo has a slightly better average case. We think that this is just a factor of the higher variation of RE and the change in cutoff.
Of the four rules, MinusTwo and RE are clearly the best. Both take about 50 – 75% more keys after doubling to get within 3% error, and both are recover extremely quickly if you ask for them to only get within 5% error.
To leave you with one last little brainteaser, an HLL of size , which is then doubled, will eventually have the same values in its bins as an HLL of size which ran on the same data. About how long will it take for these HLLs to converge? One (weak) requirement for this to happen is to have the value in every bin of both HLLs be changed. To get an upper bound on how long this should take, one should read about the coupon collector problem.


text:
Andrés Camilo Montañez
Project Manager in Colombia
During the last 3 years I have worked launching Uber in Latin America. It has been an incredible ride and now I'm excited to go after new challenges. I'm very passionate on how technology can change people's lives. Looking for ways to stay in the startup community and innovate in Colombia and the region

subset: commoncrawl


text:
Posted on Tue, Sep 5, 2017
September 7th, Colossians
The weekly Women's Bible Study will be starting a new study September 7th. This would be a good time to join in the study! They will be doing a study on Colossians. They meet every Thursday morning at 9am. We hope to see you there!
No messages have been posted.
You must first create an account to post.


text:
- Home
- Course
- Digital Marketing
- Art and Design,Crafts
- Business
- Media
- Office Suite
- Health and Fitness
- Language
- Personality Development
- Entrance Exam
- Events
- Trainings
- Resources
- Projects
- Earn Money
Drawing and Painting₹ 4,999.00
Web Analytics helps you get associate insight into the minds of visitors. You can analyse, compute and flip the website traffic in your favour. This module will facilitate to build an efficient strategy supported web statistics, understand the need of customers and deliver them what they need, to achieve high success rate.
Graphic Design₹ 4,999.00
Unlock the secrets of a successful YouTube marketing strategy from Parishkar's marketing expert. Enroll for Youtube Marketing Course!
Quilling Art
The sessions are designed in a fun and interactive manner that makes the learning process a fun experience for the students.


text:
Guernica author Bianca Lakoseljac has several book signings scheduled for the rest of October at Chapters/Indigo Bianca will be signing copies of her novel, Summer of the Dancing Bear (Guernica 2012).
Summer of the Dancing Bear is a historical novel about the rite of passage of 14-year-old Kata. The novel explores Kata's search for a viable identity, acceptance of death, and understanding of love, through her journey of trying to solve the mystery of the disappearance of a two-year-old girl when Kata was eight. The story evolves within a former Yugoslavia village community in the 1960s polarized by racial intolerance between the villagers and the gypsies. This is where Kata has grown up under the care of her grandmother.
Don't miss this opportunity to get your book signed by Bianca!
Saturday, October 20, at 12 to 4pm
Chapters/Indigo, Stoney Creek, 1783 Stone Church Rd. E.
Saturday, October 26, at 12 to 4 pm.
Chapters/Indigo, Burlington, 1250 Brant St.
Sunday, October 27, at 12 to 4 pm.
Chapters/Indigo, Square One Shopping Centre, Mississauga


text:
Tim Bryant Selected by National Trade Publication, Franchise Times, as "Legal Eagle"
Tim Bryant has been recognized as a Franchise Times magazine "Legal Eagle" of 2015. Nominated by their peers, the franchise attorneys chosen for this honor are considered "superior attorneys" and are among the most knowledgeable and experienced in the nation, according to Franchise Times. Bryant was highlighted with other franchise attorneys in the April 2015 edition.
Bryant is also recognized by Benchmark Litigation, Best Lawyers in America, and Chambers USA publications for his work in the areas of franchise law and commercial litigation. He has assisted numerous start up and existing franchise businesses with their relationship agreements and disclosure/regulatory compliance. Bryant has also successfully prosecuted, defended and assisted franchisors in resolving countless disputes related to franchise regulatory, intellectual property and business relationship issues.


text:
Three Young Travel Vloggers Die After Falling In Canada Waterfall
Three young travel vloggers - who posted videos of their adventures around the world - have died after falling over a waterfall in Canada.
Ryker Gamble, 30, Alexey Lyakh, 30 and Megan Scraper, 29, were hiking with friends in Shannon Falls Park, just north of Vancouver, when the accident happened.
Royal Canadian Mounted Police said the group had been swimming in one of the pools at the top of Shannon Falls - the third highest waterfall in British Columbia - when they slipped and fell 30m (98ft) to their death.
The Vancouver Sun reports that all three were swept away after Gamble and Lyakh went to the aid of Scraper who had got into trouble after tripping and falling.
Their bodies were later recovered by a search and rescue team from a pool below.
Gamble and Lyakh were two of the co-founders of a Vancouver-based collective - High on Life SundayFundayz - who regularly posted videos of their extreme adventures around the world.
Scraper, who also posted videos of her adventures - one of which showed her sitting on high metal train tracks, tens of meters above the ground - was the long-term girlfriend of Lyakh.
The members of the group all aged in their 20s and 30s met at high school, and posted weekly videos "to inspire our viewers to get out and explore the world".
Their channel has over 500,000 subscribers, while their Instagram account has over a million followers.
However, some of the vloggers' stunts were seen as controversial and likely to inspire their teenage audience to copy their behaviour.
In 2016, Gamble and Lyakh were banned from a host of US national parks - along another group co-founder Justis Price Brown - after walking on a sensitive hot spring in Yellowstone National Park.
They also received one-week jail sentences and received fines totalling $5000 (£3,770) for a series of violations.
The remaining members of the group made an emotional tribute to their friends in a video on the High As Life YouTube page.
Describing them as "three of the warmest, kindest and most driven and outgoing people you could ever meet", the group fought back tears as they talked about the "pain and the devastation" of losing their friends.
The video has been watched more than 60,000 times in less than 24 hours.
Ryker Gamble's girlfriend posted an emotional tribute to him on her Instagram page, sharing the words of storyteller Heather Obscura as a way of expressing her grief.
A memorial fund page has been set up for friends and families of the three vloggers to help with funeral costs.
The group has also asked fans to share social posts showing how High On Life inspired them using the hashtag #HOLinspired, which they say they will use to "collect all of your love and thoughts in one place".
Credit: Bethany Minelle, sky news
(Excluding for the Headline, this article ("story") has not been edited by MiBiz News and is published from a web feed or sourced from the Internet.)


text:
Pilgrims attending the three open-air Masses during Pope Benedict XVI's visit to Britain will have to pay as much as £25 (US$39) for the privilege.
The Church insists that pilgrims are not being charged to attend the Masses themselves but to cover transport and other essential costs.
But the announcement has provoked furious reactions, particularly in Scotland. Even Hindus have criticised the decision, saying that no one should be charged to hear the word of God. Others have gone as far as to suggest that it is a form of simony.
Still others argue that charging is simply a necessary and prudent step if the Church is not to plunge into debt as it did after John Paul II's visit in 1982.
So, is it right to charge for papal Masses?


text:
Another Partner looks to the Cloud: Telvent/Schneider Electric to Leverage Microsoft Azure
Telvent to Leverage Microsoft Azure
Our first blog post about the use of cloud computing in the Utility sector occurred in December 2008, when we noted how Utilities were already looking to various types of computing models that could achieve greater efficiencies and scale because of the cost-savings possible.
That blog noted how Utilities were naturally interested in cloud computing for customer service and other operations that weren't necessarily connected to their primary mission of reliability. But we also noted how this might change over time as the right infrastructure was put in to place. Check out this post and see how close we were to predicting and answering today's challenges. It was pretty good actually.
Fast forward to an announcement today from Telvent, about its intent to expand our companies' existing alliance agreement to further develop the use of cloud platform, Windows Azure, Microsoft's cloud computing solution. The announcement is one more step forward in terms of that new infrastructure being put in place.
Telvent, along with its parent company Schneider Electric, is a Microsoft Gold Certified Partner and Telvent is also a Smart Energy Reference Architecture participant. I can tell you from my conversation with their leaders that they are in full agreement that the smart grid will inevitably be structured to take advantage of a cloud architecture, allowing Utilities to build scaled applications to any size, as well as provision resources within minutes. Telvent's embrace and development of Azure will help their customers avoid the complexities of traditional solution deployments and accelerate value to customers and stakeholders. "Integration-ability" and ease of management is built in to the cloud's operating premise. Telvent fully recognizes those advantages.
Telvent and Microsoft have already been busy at work developing joint cloud-based applications since January 2012 and Schneider Electric is currently conducting evaluations of the Azure platform for software development across its other business units. Their first Azure-based products are expected to be available in 2013. Telvent's ArcFM server is the first product that offers advanced GIS data visualization tools across the entire Utility enterprise to be offered on Windows Azure. You can learn more about Telvent ArcFM on our solution data sheet here. – Jon C. Arnold


text:
Following its sold out 2015 event, Untapped Festival, Texas' hugely popular craft beer and music festival, returns to Austin on Saturday, May 14 at Carson Creek Ranch with over 75 breweries and more than 300 beers. Pre-sale tickets are available February 18 through March 1.
Tapping an exciting and diverse music lineup spanning two stages, Untapped Festival Austin features headliners Atlas Genius, Deltron 3030, JR JR, Kaleo, Lady Lamb, Coast Modern, and more.
This year, Untapped Festival introduces its VIP 'Stout Package' to Untapped Austin, giving festival-goers access to early entry, the Untapped Clubhouse, side stage access, an open bar featuring beer and wine plus food from some of Austin's best restaurants and more.
"Five years is an incredible milestone for us at Untapped, and we're thrilled to kick off the 2016 festival series with our return to Austin," said Festival Co-founder Matthew Harber of Spune Productions. "The tremendous response we received from Untapped Austin's debut last year exceeded all our expectations and proved why Austin is a true destination for music and beer. This year, Austin attendees can expect bigger and better."
In celebration of the festival series' five year anniversary, Untapped Festival introduces the Untapped Season Pass, giving attendees access to all five Untapped Festivals in 2016, including Austin, Fort Worth – 6/11, San Antonio – 9/17, Houston – 10/22 and Dallas – 11/12.
Untapped Festival Austin, Saturday, May 14, Carson Creek Ranch 3:00 p.m. (2 p.m. for VIP/Stout ticket holders) to 10:30 p.m. Music from Atlas Genius, Deltron 3030, JR JR, Kaleo, Lady Lamb, Coast Modern, and more.
Presale tickets available from February 18 to March 1. Public on-sale date starts March 2. For tickets to Untapped Festival Austin and more information visit the Untapped Austin website.
General Admission tickets are available for $37 ($32 during presale). Package details and pricing featured below.


text:
This page provides additional resources to that provided under Session Two in the book. Here, by holding your cursor over the title of this page in the menu just below the picture, you can:
- learn more about Sheila Cassidy
- listen to my comments on the Bible passage
- read the complete Ogden Nash poem I refer to
- explore Pelagius and Augustine
- find prayers on the topic of self-care
- explore more about what Jung might have meant
This is also where you can make a comment about either the passage by Sheila Cassidy or my comments on the bible passage or the topic in general.
Sheila Cassidy writes about the tendency people who care have to hide their vulnerability. She implies this is sometimes necessary but often we do it when it isn't.
My thought suggests that we need to learn to love ourselves because often in growing up we learnt not to.


text:
On the internet has turned into a fast-growing global pastime. There are lots of kinds of games to select from. Puzzle Games are extremely popular, and can include jigsaw, word, logic, combination, construction, transport, picture, sliding, tour, and mechanical puzzles.
The jigsaw puzzle is among the earliest kinds of puzzles that individuals happen to be enjoying for several years, and can enjoy for years to come.
Jigsaw Puzzles were initially crafted by painting an image on the flat wood, after which performing into pieces and in a number of different shapes utilizing a jigsaw. This is when the name, jigsaw puzzle, originates from. Commercialized jigsaw puzzles began appearing throughout the 1760s and also have be a permanent fixture in lots of homes since that time.
Jigsaw puzzles are available getting quite a number of images. Some include photos and photographs with natural, urban, contemporary and traditional styles. Jigsaw puzzles come in a number of sizes with different levels of pieces usually varying from 300 to 1000. Jigsaw puzzles have evolved over time. Puzzle accessories for example boards, cases and frames could be readily bought in local stores. 3d jigsaw puzzles can be found available on the market. These 3-D puzzles usually form a sphere, and planets are normal subjects for this kind of jigsaw puzzle games.
Most lately, jigsaw puzzles in most varieties are available online. Puzzles of Fashion followers, cars, creatures, works of art, cartoons, famous landmarks and a whole lot are available with only a couple of keystrokes. The present yield for any Search on "jigsaw puzzle games" is nearly seven million, which number grows every single day.
Online jigsaw puzzles are performed by clicking, dragging and shedding the pieces using the mouse. A large number of puzzles are for sale to beginner, novice, intermediate, and expert puzzle solvers.
Jigsaw Puzzleshave started out individually hand crafted puzzles constructed from wood and paint, to digital puzzles constructed from zeros and ones. A minumum of one factor still is true for jigsaw puzzles in the past to the current. They continuously entertain people of every age group, cultures and lifestyles for any lengthy time.


text:
Best Lightake Coupon Code, Discount Code, Deals
Lightake Coupons are the Best Ways to Save Money When You Shop Online at www.Lightake.com. Our Coupon Portal Brings you Only The Top lightake Discount Codes to Use them Online. To view the Codes you have to click on "Show Coupon". Sometimes Lightake.com Brings You Direct Discount Without Adding a Code and Just Click on "Redeem Offer" and the Discount Offer Will be Activated Immediately. If one of the coupons for lightake does not work then you can try other codes until you find the valid code that works.
Recently Added Lightake.com Coupons & Promo Codes
0 coupons
Best Lightake.com Promo Codes
|Offer Type
|Discount Details
Tips About Lightake.com
Coupons and offers from similar stores
Other lightake Discount Codes
3 unverified coupons
Spend $100 get $20 Off Site Wide!
Spend $100 get $20 Off Site Wide! Excluding Sale Items. Use code at Lightake.com
Buy one get one 25% off
Its World Kindness Day! Treat a friend with Buy one get one 25% off at Lightake.com Use code Ends 11/14
Free Shipping on RC Toys and Hobbies
Free Shipping on RC Toys and Hobbies – Using Code at LighTake.com!


text:
Dear Vaishnavas around the world,
Please accept my humble obeisances! All glories to Srila Prabhupada!
Kindly pray for the departed soul of devotees who have left their bodies in tragic air plane crash accident in Nepal on the way to their pilgrimage trip. Most of them were devotees connected with the congregation in Sri Sri Radha Gopinath Mandir, ISKCON Chowpatty, Mumbai, India.
Following are the devotees:
– HG Kunjabihari prabhu, his wife HG Madhupriya mataji & his son HG Shivam Prabhu from Bombay Central
– HG Gokulrani mataji & her small daughter HG Taruni from Khar (She also acted in many ads, films & dramas – she was Krsna in the famous drama "Wonderful Krsna")
– HG Murlimohan Prabhu & his brother Gagan
– HG Gaura Krishna prabhu, bramachari from Sri Sri Radha Gopinath Mandir, ISKCON Chowpatty.
This is really devastating news. Ultimately everything is in Lord Krsna's control and many times we fail to understand His divine plan.
At the tomb of the namacharya Srila Haridas Thakur, Srila Bhaktivinode Thakur wrote the following poem which is often cited in thinking about the life and passing of a devotee:
He reasons ill who says that Vaishnavas die,
When thou art living still in sound!
The Vaishnavas die to live, and living try
To spread the holy name around.
Please pray for them for our purification.
Thank you very much.
Your servant
Rasamrita Das
It is important to remind ourselves that at the end of the day all we really have is each other.


text:
Want to Earn a Buck? Short a Euro!
MarketWatch columnist David Weidner visits Mean Street and makes the argument that now may be the time to short the Euro. It could earn you some dollars. REUTERS/Jo Yong-Hak/Files
This transcript has been automatically generated and may not be 100% accurate.
go ... short singer all ... and make Alcock ... says David Weidner ... in his MarketWatch column ... writing on the walls I was told he ... can come on come on board ... normally my car not that I think it you can get a deal with when I get it I don't I get a nice but then I love I love the colors that effect on that on that and make it mandatory for for all my ... usual thing from a coach ... ticket for what he got a band's Web yet again ... right now I don't yet I don't I the eye of the color that you would expect how am ... I the Audi now I don't have the exact what you expect me to ... but let's turn ... to other European attitudes European car of nowhere to go here in the European market ... Magellan you're telling your readers ... I can assure think ... he's I don't like to give the auto and I don't like to give investor buys because you know it is usually wrong elected by the horror of what ... you say ah Europe is don't ... you always do so many times ... in investment history have Investors been telegraphed ... that ... you know deal was coming the way they've been taught there for two years ... and yet if you shorten the euro at the beginning of the year ... the Privee barely breaking even think you have been losing money for most of the year I was there was can happen tomorrow ... as the all ... the euro was trading above ... all these all the small points that we've had in ... February th unwary ... part of last year ... currencies when offer ... the money that that that ... I hear the printing presses used a different you're thinking of what the yet we just that Matthew Karnitschnig the Wall Street Journal bureau chief and in Europe ... Cup on to explain to us how the Australians in the German Subotky other northern Europeans still believe in my money still believe them to fight inflation ... still are kicking screaming going into buying more bonds they still believe in keeping the euro strong year vote gets the Germans were chosen with the Yorker new coach Net Schmid hit ... hard ... what I did things that do anything that says ... he and other members like ... we know when to repay that money ... out ... of the dispute was two one two years ago this ... Seyam thing they did what you think uni any ... grow and serve ... closet Sobel War between the ... the the tough North Anna profligate self you think the profit and sales winds down in the ... I think that either way it goes in there we had this massive bailout that can cost ... hundreds of billions were saying the euro need to print money to weaken the currency for Greece is going to default rate than the more he is going to go to hell ... sorry I don't know if we can said the bank meets the ministry ... ministry ideas major Sokol in and out of where the other way euro is going to get absolutely clobbered annual and now additional ago put your money where your mouth and I can ... tell you shorting are aware that I could mean you'd like to retire by Norio to us that we have the lawsuit that the baby doesn't apply to you yet ... I mean just I Perkins will ensure bet that I'd add on was that the that the Treasury yields were not to go anywhere below ... forty or two point seven five percent read Jane Eyre the ... nail in one voice on right now ... don't see where viewers of the short the end of production at the whereof David Weidner short or bet on Europe going going to help ... get the creepy but Europe ... will be talking about this later in the show ... is the question can you hope they'll ... be the uncertainty and with the Youtube link are you see ... how it your point of the stupid these countries after the bank said the iPhone ... you know ... Italy owns a ton of Portuguese debt and vice versa at all it's it's just so it's a


text:
SHIPPING TERMS: Shipped bareroot sealed with soft packaging materials to withstand shipping conditions. Phytosanitary Certificate and Care Instructions included in packing slip envelope.
FEATURES: Leaves have a faint pattern like a snake skin, sharp tipped leaves. A dwarf variety of the Sansevieria family; dark green in color. They are very hardy to the touch and can grow at a height of 12 inches. Shoots small white flowers randomly and gives a hint of sweet fragrance.
DESCRIPTION: A VERY POPULAR decorative plant for indoor and office reception and tables. A plant tolerant of irregular watering; with or without sunlight. Also known as snake plant or Mother in law's tongue , this plant is one of the best for filtering out formaldehyde, which is common in cleaning products. These species of plants in an enclosed room interestingly absorbs carbon dioxide and releases oxygen at night (the opposite of the process most plants follow). Because of its hardy leaves and long lasting, the leaves or plant itself is used for floral arrangements. In addition, believed and practiced in some countries that this plant brings good luck and positive energy.
PROPAGATION: This plant can be propagated by leaf cuttings or root rhizomes.


text:
Modern understated typography and painted watercolor leaves come together to create a contemporary design perfect for an au natural outdoor event or any couple looking for something different. This fresh look is sure to make a statement when announcing your news.
SIZE: 3.5"x5" – Double-sided
PAPER: Printed on thick lux textured 120lb card
OPTIONS: Colorful Design on front with addressing and details on back in black ink. Space is limited on the back left side. These do not come with an envelope


text:
Nobel Prize for Literature 2000
Gao Xingjian was born in China but now lives in France. It was there that his novel La Montagne de L'ame or Soul Mountain was originally published and became a best-seller, going into three editions. Mabel Lee's English language translation of the novel was first published by HarperCollins Publishers Australia in July 2000 (see below).
Mabel Lee is represented by Australian Literary Management, and ALM is the lead agent for the English language translation of Soul Mountain.
Following links from the SAMPLES page above, you can read the first chapter of Soul Mountain on this website, as well as Mabel's perceptive and informative Introduction to the book, and the Swedish Academy's bibliographical note published on the occasion of the 2000 Nobel Prize.
"On the traveller's journey to Soul Mountain he visits a nature reserve, listens to toothless old men and women squatting along the river banks, hears atrocious stories which make up the history of the country: women violated by outlaws of the Red Army, women who know how to embroider but who have guns hidden under their clothes, women with flashing eyes hungry for love, young women singing for the festival of the boat dragons, women who threaten their unfaithful lovers with a knife. Portraits of these admirable women punctuate the journey in the form of temptations towards drunkenness, nostalgias and violent sexuality." (Le Figaro, 11/1/96)
Gao's second novel One Man's Bible focuses the political horrors of the twentieth century through the lens of desire and memory. It has received rave reviews in the US.
Gao has also released a beautiful collection of short stories Buying a Fishing Rod for my Grandfather, HarperCollins 2004.
The Case for Literature, a collection of Gao Xingjian's essays, including his Nobel Laureate address, was released by HarperCollins Australia in 2006 and has been contracted to Yale University Press.
ALM represents the English language translations of Gao's novels internationally.
Gao Xingjian is also known as a painter with a strong yet subtle style. You can view some of his watercolors on the website of the Art Gallery La Tour des Cardinaux in France, at http://www.cardinaux.com/site_eng/gao_eng.htm