Sunday, March 12, 2006

Streaming exercise

Here is an (HW?) exercise in streaming algorithm design.

Given a stream of items a_1,...,a_n, a_i \in [1,u], find the average of items below the median or the median of items below the average.

There is previous work on finding the median (or more generally, the quantiles) and the kth frequency moments \sum_i f_i^k, where f_i is the frequency of i (k=1 is the average). The exercise here is an example of cascaded aggregation: computing the kth frequency moment following a quantile computation.

As is standard in streaming algorithms, one has to use space and per-item update time of polylog(n,u) and obtain reasonable approximation.

13 Comments:

Anonymous Weight Loss Help said...

low calorie diet Having problems with weight loss? To achieve lasting weight loss requires some knowledge and a little work. Your food intake must consist of the right amounts of protein carbohydrate and fat. (or it won�t work!) And you need proper exercise intensity, frequency and duration (not what you think). To get more info. please visit low calorie diet

6:03 AM  
Anonymous Weight Loss Help said...

diet food Are you having problems with losing weight even though you�re dieting? You might have reached a weight loss plateau. For free tips and information on overcoming weight loss plateaus please visit diet food

7:58 AM  
Anonymous Weight Loss Help said...

weight loss calories Looking for the right diet? To help you choose we have reviewed the top diet plans available today. Simply fill out a free profile and choose one you�re most comfortable with. Please visit weight loss calories

5:37 PM  
Anonymous Weight Loss Help said...

diet programs Having problems with weight loss? To achieve lasting weight loss requires some knowledge and a little work. Your food intake must consist of the right amounts of protein carbohydrate and fat. (or it won�t work!) And you need proper exercise intensity, frequency and duration (not what you think). To get more info. please visit diet programs

6:44 AM  
Anonymous Weight Loss Help said...

weight loss calories How many calories do you need per day? Learn more. Please visit weight loss calories

12:45 PM  
Blogger kevin said...

Once an individual suffers from obesity or overweight, it becomes highly important for him to trigger off weight loss and altogether weight loss is necessary to keep a whole lot of obesity induced disorders, namely, diabetes, arthritis, high blood pressure et al at bay. Dieting and regular physical exercises can help in achieving weight loss and altogether the “weight loss” section of the website http://www.pill-care.com informs you that weight loss medicines such as Phentermine, Xenical etc can also help you trigger off instant weight loss if taken in accordance with the instructions of the doctor.

4:11 AM  
Blogger luccy said...

If you have fallen prey to obesity and would like to trigger off weight loss as soon as possible, then you should opt for diet pills such as Phentermine and Adipex that are extremely popular for inducing rapid weight loss among people across the world. You will find the relevant details of weight loss pills at http://www.weight-loss-truths.com that inform you that Phentermine is to be taken only after procuring a Phentermine prescription and also in accordance with the instructions of the doctor. So, get hold of a Phentermine prescription, administer the drug properly and transform your weight loss dreams into reality.

2:15 AM  
Anonymous Plamen said...

Nice blog. :)

3:44 AM  
Anonymous Anonymous said...

I got there lots of helpful content and great information. Thanks a lot for your help.
www.just4ubootcamp.com

9:13 AM  
Anonymous Anonymous said...

Natural weight loss

2:54 AM  
Blogger majianlin said...

[url=http://www.review6.com]Website Review Evaluation[/url]

9:32 AM  
Blogger Jennifer said...

I've tried various low-carb, low-calorie, and low-fat diets for the past couple of years. Although the Atkins diet is very popular, it made me feel somewhat unhealthy.
The diet plan I'm on right now is the Medifast Diet. The caloric intake is roughly 800-1000 calories. However, it doesn't make my body feel weak. It is a bit of a pricey diet, but there are plenty of coupons available on the internet (i.e. http://www.swoopup.com/stores/deals/Medifast-Diet). You should never pay full price.
My advice is just choose a diet plan which your body reacts positively to. No one knows your body better than you do!

9:29 AM  
Blogger stephanie said...

I have tried another way to lose
weight. I tried adipex and it is really effective. i have lost lots
of weight. I ordered it online from
www.medsheaven.com I highly
recommend this, and this didn't
require a prescription!

9:15 PM  

Post a Comment

<< Home