COMP9318 (13S2) PROJECT
1. Objective
In this project, you will implement and experiment with several algorithms to approximate historical item counts in a space efficient manner. Note that it will take you quite some time to complete this project even if you are familiar with Java programming and have good programming experience. Therefore, we earnestly recommend that you start working on this project as early as possible.
2. Background
This project will be based on the paper \Hokusai - Sketching Streams in Real Time" [MSA12].You are required to implement the two algorithms in the paper | the time aggregation and the item aggregation. Both the Count-Min sketch (denoted as cm-sketch in the rest
of this specification) [CM04] and the two algorithms have been introduced in the Data Stream Mining lecture slides; nevertheless, you are expected to read the corresponding sections of the paper [MSA12] for further details. Note that the paper has several typos and inconsistencies, and you need to _x them. See also Section 4.Finally, in addition to the implementation, you will also need to submit a report on corrections to the paper and ideas for possible improvement.
3. Task I: Implementation
Your first task is to write a Java class named Proj1, which receives six command line arguments:
- DATAFILE: the file that contains the data stream items. Its format will be described
- shortly.
- QUERYFILE: the file that contains the queries. Its format will be described shortly.
- METHOD: it is a string of either time or item.
- WIDTH: it is the width of each cm-sketch.
- DEPTH: it is the depth of each cm-sketch.
- SEED: it is an integer that initiates the random generator in Java (i.e., java.util.Random).
Your program should use time or item aggregation as specified in the METHOD to process
the data stream in the DATAFILE, and then computes the estimates for each query specified
in the QUERYFILE; the cm-sketches constructed in your algorithms should use the parameter
WIDTH, DEPTH, and SEED.
2 DUE DATE: 23:59 15 OCT 2013 (TUE)
3.1. Data File Format. The DATAFILE consists of one or more lines. Each line species
the items and their frequencies in the current timestamp; the first line corresponds to
Timestamp 0 and the second line corresponds to Timestamp 1, and so on and so forth.
Each line consists of multiple fields separated by a white space character. Each field has
the format of ITEM:COUNT, where ITEM is a non-empty string, and COUNT is a non-negative
integer specifying the number of times the string ITEM has been observed at the current
timestamp.
3.2. Query File Format. The QUERYFILE consists of one or more lines. Each line consists
of three fields separated by a white space character. The three fields are:
- a string specifying the query item (denoted as Q)
- an integer specifying the start timestamp (denoted as t1)
- an integer specifying the end timestamp (denoted as t2)
Hence each query asks for (t2 ?? t1 + 1) estimates of the total count of Qattimesamp
i, for t1 _ i _ t2.
3.3. Output Format. If there are m queries in the QUERYFILE, you need to output m
lines, where each line is the estimated numbers for each corresponding query. The estimated
numbers should be separated by a comma (i.e., ,); if the estimated number is a routing
number, you should round it down to an integer and display it as the estimated total count.
3.4. Hash Functions and Random Seed. We will source the hash functions used in
the cm-sketches from the following universal hashing function family:
h(x) = ((a _ x + b) mod p) mod w
where a 2 [1; p ?? 1] and b 2 [0; p ?? 1] are random integers (deterministically derived from
the given random seed)1, p is a large prime number, and w is the width of the cm-sketch.
To make sure we can reliably test your program, you have to use the SEED given from
the command line to initiate your random hash functions. The logic in the following code
should be used:
// p = 2147483647
Random r = new Random(SEED);
for (int i = 0; i < depth; ++i)
{
a[i] = 1 + r.nextInt(p-1);
b[i] = r.nextInt(p);
}
For example, if given the seed 1234, the first two hash functions should be:
h1(x) = ((1388524629 _ x + 557894633) mod p) mod w
h2(x) = ((2043025134 _ x + 509900220) mod p) mod w
1Check out \hashing integers" in https://en.wikipedia.org/wiki/Universal_hashing if interested.
COMP9318 (13S2) PROJECT 3
You perhaps need to beware certain care is needed as Java does not support unsigned datatypes.
To convert a string into an integer, we use String::hashCode() method.
4. Task II: Report
You need to write a report with the following components:
- _ Present the correct version of Algorithms 2 and 3 in [MSA12]. You should follow the style and typesetting of the algorithms as much as possible while addressing the following goals:
Ø For Algorithm 2: fix the error(s) in the algorithm, and also make sure there is no useless computation in the pseudo-code level.
Ø For Algorithm 3: fix the algorithm so that it starts with timestamp 0 (rather than 1). Your corrected version should work as that shown in the lecture slides, i.e., it has two full-width cm-sketches, followed by two half-width, four quarter-width sketches, and so on and so forth.2
Describe the estimation algorithm for sketched obtained via time aggregation.
- Describe at least one way to improve the methods to deliver a possibly more accurate solution to the problem. You should clearly describe (1) the problem(s) of the current solution(s), and (2) your proposed method.
5. Example
Let input.txt be
a:1 b:2 c:3
a:2 b:4 c:6
a:4 b:8 c:12
Let query.txt be
a 0 2
c 1 2
If we run your implementation as
java Proj1 input.txt query.txt item 16 2 1234
the output should be
1,2,4
6,12
6. Marking
Your implementation will be auto-marked and contribute 70% of the final mark; the rest
30% comes from your report, with each component scoring 10%.
2This interpretation is exactly what the pseudocode of Algorithm 3 produces, except that it starts from timestamp 1. Do not modify the algorithm such that there is only one full-width cm-sketch.
4 DUE DATE: 23:59 15 OCT 2013 (TUE)
6.1. Auto marking Your Implementation. Auto-marking will be used to mark your
implementation on a Linux machine. Especially, we will
(1) Unbar the proj1.tar and run javac *.java to compile your .java _les.
(2) Run your program with some valid parameters and record your output and compare
it with sample output.
(3) Repeat Step b) several times, each with a deferent set of parameters.
Therefore, you need to make sure:
Your java program can be correctly compiled. Make sure you do not put some of
your java source files at a sub-directory.
- Your java program can be run by java Proj1 DATAFILE QUERYFILE METHOD WIDTH DEPTH SEED. Make sure you do not use package for your code.
- Your java program output results in a format exactly identical to that described in Section 3.3. Make sure you do not output does not contain other messages (e.g., debugging information).Be warned that you will receive 0 mark if your program cannot be compiled or run correctly in our testing environment (e.g., program exit due to some Exception).
7. Submission
Please tear your source codes and a report _le name proj1.pdf into a _le named proj1.tar. All your source codes must be in the same directory (i.e., no sub-directory allowed).
Your submission should contain at least a _le named Proj1.java. You are free to add any other Java classes.
You can submit your _le by giving cs9318 proj1 proj1.tar
Late Penalty. -10% for each of the first five days, and -20% for each of the following days.
Plagiarism. Make sure you read \8. Academic honesty and plagiarism" in https://www.cse.unsw.edu.au/~cs9318/13s2/intro.html
References
[CM04] Graham Cormode and S. Muthukrishnan. An improved data stream summary: The count-min
sketch and its applications. In LATIN, pages 29{38, 2004.
[MSA12] Sergiy Matusevych, Alexander J. Smola, and Amr Ahmed. Hokusai - sketching streams in real
time. In UAI, pages 594{603, 2012.