COMP90056 Stream Computing and Applications Assignment 1 (15 marks) — Analysis of Distinct Count Algorithms Start date: 09:00 Monday 7 September 2020 Due date: 17:00 Monday 21 September 2020 Background Estimating the number of distinct elements of a stream is an important problem in Computer Science, hav- ing wide-ranging applicability. In this assignment you will implement and compare the performance of two algorithms (BJKST I and HyperLogLog), reporting on your findings and providing a recommendation on their suitability for varying applications. Task 1: Implementation There is no specified programming language for this assignment. You may use whichever programming language you wish. Implement each of the algorithms and performance metrics below. The hash functions may be based on the Hash.java implementation from Tutorial 5. • A baseline algorithm for the distinct count problem—this should not be probabilistic, but instead give a correct answer every time. You may use existing data structures (such as HashMap in Java). • BJKST I algorithm as presented in Theorem 1 of [1] (also in the lecture notes): – Include a priority queue that tracks the t smallest hash values. – Include inputs and δ that give desired theoretical performance by running multiple copies of the algorithm and outputting the median value. • The HyperLogLog algorithm as presented in Fig. 3 of [2]. – It should be able to work with m = 2b substreams, where b ∈ {4, 5, . . . , 16}. – The algorithm makes use of adjustments to the estimate E. Note that the small-range correction is the linear counting algorithm discussed in lectures. The large-range correction is made when estimates exceed 232, but there will not be a need to explore the algorithm in this range. • A stream of integers as input for the algorithm where the range of values is user-defined. The more types of input streams used for algorithm testing the better. • Define relative error Erel of an estimate Fˆ0 compared to its true value F0 as |Fˆ0 − F0|/F0. • Compute the speed in which the distinct count problem is solved. • Be able to calculate the memory usage of your implementations. If possible use a pre-existing tool (function) specific to your programming language that measures runtime consumption. Make use of a random seed(s) for the data and algorithms so that you are able to apply different algorithms to the same input data and to ensure your results are reproducible. Task 2: Report Complete a short report analysing the two algorithms including the following points. Since you will be con- sidering probabilistic algorithms, steps will need to be taken to make results more definitive. Plots should be well described and clear to visualise. Refer to Section 4 of [3] for a good example of analysis including plots to describe the performance of algorithms (your report is not expected to be as detailed). • Set-up—A description of the experimental set-up to aid reproducibility. For example, include the CPU frequency, memory, operating system, programming language, compiler (if applicable). [1 mark] • A description of steps taken to gain confidence in the implementations (i.e., testing) and ensuring a fair comparison between the algorithms. [1 mark] • Verification that the hash function has uniformly distributed output values. [1 mark] 1 • An investigation of the effect of the small-range correction to the estimate in the HyperLogLog algorithm. Plot average absolute error vs exact distinct count (up to 108 or more) to compare these effects and comment on any differences observed. [2 marks] • Histograms for the BJKST and HyperLogLog algorithms similar to those given in Figure 4 of [2] show- ing the distribution of estimates for values of n = 104 and 106 and for each case specify parameters guaranteeing an estimate within ±5% of the true value with probability 0.9. [2 marks] • A plot of average relative error vs exact distinct count comparing the BJKST and HyperLogLog algorithms with a choice of parameters to enable a fair comparison. [2 marks] • A plot of average memory consumption (kB) as a function of actual distinct count (up to 108) comparing the three algorithms. (If unable to compute memory usage for your program you may do a theoretical analysis for half marks.) Use a legend to combine plots having multiple input parameters. Point out where the algorithms differ and possible reasons for this. [2 marks] • A plot of average accuracy vs runtime comparing the two algorithms. Use a legend to incorporate multiple input parameters. Point out where the algorithms differ and possible reasons for this. [1 mark] • Practical considerations—point out any differences between practice and theory and possible explanations for the difference. [1 mark] • Conclusion and recommendation—which would be your recommended algorithm for practical use? In- dicate how your answer depends on the application (e.g., speed, accuracy or memory requirements). [2 marks] Marking Scheme The marks for each component in the report are as shown. The grading will be based on the clarity and rigour of your description or analysis for each part. The code will not be assessed but should be presented and documented well enough that others could reproduce the whole experimental study of your report and obtain similar results. Submissions You should lodge your submission for Assignment 1 via the LMS (i.e., Canvas). You must identify yourself in each of your source files and the report. Poor-quality scans of solutions written or printed on paper will not be accepted. Solutions generated directly on a computer are of course acceptable. Submit two files: • A report.pdf file comprising your report for the experimental study. • A code.zip file containing all your source files of the implementations for the experiments. Do not include the testing files, as these might be large. REPEAT: DO NOT INCLUDE TESTING FILES! It is very important, so that you can justify ownership of your work, that you detail your contributions in comments in your code, and in your report. Administrative Matters Late Work The late penalty for non-exam assessment is two marks per day (or part thereof) overdue. Requests for extensions or adjustment must follow the University policy (the Melbourne School of Engineering “owns” this subject), including the requirement for appropriate evidence. Late submissions should also be lodged via the LMS, but, as a courtesy, please also email Chaitanya Rao when you submit late. If you make both on-time and late submissions, please consult the subject instructor as soon as possible to determine which submission will be assessed. Individual work You are reminded that your submission for this Assignment is to be your own individual work. Students are ex- pected to be familiar with and to observe the University’s Academic Integrity policy http://academicintegrity. unimelb.edu.au/. For the purpose of ensuring academic integrity, every submission attempt by a student may be inspected, regardless of the number of attempts made. Students who allow other students access to their 2 work run the risk of also being penalised, even if they themselves are sole authors of the submission in question. By submitting your work electronically, you are declaring that this is your own work. Automated similarity checking software may be used to compare submissions. You may re-use code provided by the teaching staff, and you may refer to resources on the Web or in published or similar sources. Indeed, you are encouraged to read beyond the standard teaching materials. However, all such sources must be cited fully and, apart from code provided by the teaching staff, you must not copy code. Finally Despite all these stern words, we are here to help! Frequently asked questions about the Assignment will be answered in the LMS discussion group. References [1] Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D., and Trevisan, L. Counting distinct elements in a data stream. Proc. 6th International Workshop on Randomization and Approximation Techniques, pp. 1–10, 2002. [2] Flajolet,
P., Fusy, E´., Gandouet, O., and Meunier, F. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. Discrete Mathematics and Theoretical Computer Science Proceedings, pp. 127–146, 2007. [3] Luo, G., Wang, L., Yi, K., and Cormode, G. Quantiles over data streams: experimental comparisons, new analyses, and further improvements. The VLDB Journal vol. 25, pp. 449–472, 2016. COMP90056 team September 2020 3
