This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
Daily pageviews of this article
A graph should have been displayed here but
graphs are temporarily disabled. Until they are enabled again, visit the interactive graph at
pageviews.wmcloud.org |
Is there a word for an online algorithm that has the additional property that partial results can be combined? That is, if I want to run an algorithm in parallel, I want to be able to combine partial results. For example, the sum of a set of numbers is the sum of the partial sums. —Ben FrantzDale 01:00, 7 December 2006 (UTC)
{{
cite journal}}
: External link in |title=
(
help)CS1 maint: multiple names: authors list (
link)I had added " Online algorithms for calculating mean and variance" to the see-also section but it got removed with a comment that "streaming algorithm" was a more appropriate place for it. While I'm not 100% clear on the difference between a streaming and an online algorithm, computing the mean and standard deviation of a sequence in a single pass seems like an ideal simple example of an online algorithm. At first glance it is obvious that the mean can be computed in a single pass with O(1) storage, but that isn't obvious about the variance. Could someone explain why these are better examples of streaming algorithms than of online algorithms? —Ben FrantzDale ( talk) 20:58, 30 April 2009 (UTC)
Seems to describe the same class of algorithms. QVVERTYVS ( hm?) 09:59, 21 July 2013 (UTC)
I think the title of that section should be replaced, not sure to what title though. The content of the section does not give the definition of what is an online algorithm (it does provide a definition of the term "competitive ratio"), rather it discusses (not necessarily all main) properties of (not necessarily all) online algorithms.-- Shay Zakov ( talk) 08:08, 6 August 2020 (UTC)
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
Daily pageviews of this article
A graph should have been displayed here but
graphs are temporarily disabled. Until they are enabled again, visit the interactive graph at
pageviews.wmcloud.org |
Is there a word for an online algorithm that has the additional property that partial results can be combined? That is, if I want to run an algorithm in parallel, I want to be able to combine partial results. For example, the sum of a set of numbers is the sum of the partial sums. —Ben FrantzDale 01:00, 7 December 2006 (UTC)
{{
cite journal}}
: External link in |title=
(
help)CS1 maint: multiple names: authors list (
link)I had added " Online algorithms for calculating mean and variance" to the see-also section but it got removed with a comment that "streaming algorithm" was a more appropriate place for it. While I'm not 100% clear on the difference between a streaming and an online algorithm, computing the mean and standard deviation of a sequence in a single pass seems like an ideal simple example of an online algorithm. At first glance it is obvious that the mean can be computed in a single pass with O(1) storage, but that isn't obvious about the variance. Could someone explain why these are better examples of streaming algorithms than of online algorithms? —Ben FrantzDale ( talk) 20:58, 30 April 2009 (UTC)
Seems to describe the same class of algorithms. QVVERTYVS ( hm?) 09:59, 21 July 2013 (UTC)
I think the title of that section should be replaced, not sure to what title though. The content of the section does not give the definition of what is an online algorithm (it does provide a definition of the term "competitive ratio"), rather it discusses (not necessarily all main) properties of (not necessarily all) online algorithms.-- Shay Zakov ( talk) 08:08, 6 August 2020 (UTC)