
This code package implements two functions:
(1) It takes the input text stream and outputs z-values 
    (both accurate and approximate z using full-space and
    CM sketch algorithm respectively) of a Zipf distribution.
(2) Take z output from (1) and the updated CM sketch, the
    program outputs an estimate for a point query with an 
    upperbound that is given by z. The analysis is described
    in the paper "Summarizing and Mining Skewed Data Streams"
    by G. Cormode and S. Muthukrishnan, in SIAM Conf. on Data
    Mining, 2005.

==============================================================
		File Package and Compilation
==============================================================
Unzip the .tar file, the root directory contains the following 
files:

-C172 (sample text file: a bag of word ID's--unsigned int's, stop 
       words excluded)
-test.txt (sample text file: a bag of words, may include stop words)
-stopwords.txt (a list of linguistic function words, which are not
 used for further computation. The stopwords file is a plain text
 file with one word per row.)

-makefile
-topiczipf.c
-topiczipf (executable)

-one_word_per_line.pl
-word_to_int.pl
-/util
(used as building blocks of the program)

Open a terminal and type

> ./makefile

to compile. If it doesn't work, you may need to input the 
complete path of 'gcc' command. And the makefile generates
one output file, topiczipf, to execute the above two
functions.

===========================================================
		How to Run the Program
===========================================================
The program accepts two formats of input text streams:
(1) A bag of unsigned integers, each of which is a word ID.
    This form of input text streams has excluded all stop words.
    (e.g. C172)
(2) A bag of words. This form of input text stream may include
    stop words, defined in "stopwords.txt". Most but not all
    punctuation is removed. (e.g. test.txt)

topiczipf takes 6 parameters on the command line:
> ./topiczipf -f <filename> -width <num> -depth <num>
  -int <0/1> -s <num> -t <num>

-f <filename> defines the input text file name, the contents
 of which are used as a text stream. 
-width <num> defines the width of the CM sketch to use. Its
 default value is 2048. Increasing this will bring increased
 accuracy.
-depth <num> defines the depth of the CM sketch to use. Its
 default value is 5. Increasing this will given greater confidence.
-int <0/1> defines the format of the input text stream:
 0 -- a bag of words,
 1 -- a bag of unsigned int's.
-s <num> defines the starting rank of a word used to compute z.
 Its default value is 100.
-t <num> defines the ending rank of a word used to compute z. 
 Its default value is 1000.
(The details of the last two parameters will be explained in
"How to Compute z".)

Examples of running topiczipf are as follows:

> ./topiczipf -f C172 -width 2048 -depth 5 -int 1 -s 100 -t 1000

or 

> ./topiczipf -f test.txt -width 2048 -depth 5 -int 0 -s 100 -t 1000

The first command generates the following output:

Part 1: Z Parameter Estimation
==============================

Running Full-Space Algorithm ...
exact z = 1.267380
running time = 45746 ms
 
Running Sublinear Algorithm ...
approx ^z = 1.183415
running time = 1295 ms
 
total # of words = 635088
relative error = |(z-^z)/z| = 6.63%

This indicates that 635088 words from the input text stream were 
processed. The relative error from using CM sketch was 6.63% over
top frequent words with ranks between starting and ending rank.

Part 2: Point Queries of Word Frequencies 
=========================================

Input word ID (0-47236, -1 to exit) : 28
        Exact frequency = 952
        Approx frequency = 968
        Upper bound = 1095.40

After the prompt "Input word ID (0-47236, -1 to exit) :", user 
inputs a word ID (i.e. 28 in the above example) for point query.
Note that the input word ID should range from 0 to 47236, as
indicated by the prompt line. After the <enter> from the user
input, the program outputs exact, approximate word frequency, 
by using full-space and CM sketch summary respectively. And a
theoretical upper bound for the point query, given z parameter,
is also displayed on screen. With high probability, the approximate
point query result should be between the exact answer and the upper
bound. The program terminates when the input word ID is -1.

=================================================================
			How to Compute z
=================================================================
A Zipf distribution with parameter z has the property that f_i,
the frequency of the i-th most frequent item is given by 
f_i = c * i^{-z}, where c is an appropriate scaling constant. 
When plotted on log-log scales, (i, f_i) appears (ideally) as
a straight line with slope -z. 

When fitting a zipf distribution to real data, deviations from the
line are usually observed at the head, known as top cancavity; on
the other hand, sampling effects occur at the end of the tail (higher
slope than the true value). Therefore, to get a good estimate of z,
one typically drops the first few readings, and not fit the entire
tail. As mentioned earlier, our program uses,

-s <num> to define starting rank to compute z;
-t <num> to define ending rank to compute z.

Algorithm outline : 
===================
Input: a text stream
Output: z and ^z computed using full-space data structure and 
        CM sketch respectively.

1. get (rank, word frequency) pairs (i, f_i) for all i's;
2. use least-squares to fit a line to (i, f_i) with i between
   starting and ending rank defined via program parameters
   -s and -t;
3. return slope of the line as -z.

Full-space algorithm computes (i, f_i) exactly by maintaining
a counter for each i. Algorithm using CM estimates f_i. 

Some details :
==============

1. CM sketch has good estimates for frequent items (a.k.a. heavy
   hitters). Hence, our sublinear algorithm using CM estimates ^z
   from top frequent items. Usually, the ending rank we set is 
   one half of the sketch width (e.g. -t 1000 -width 2048). 
2. Assume the maximum word ID observed is max, then the overall
   space usage of CM is width*depth*log_2(max). 

