Wikipedia:Articles for deletion/One-pass algorithm

The following discussion is an archived debate of the proposed deletion of the article below. Please do not modify it. Subsequent comments should be made on the appropriate discussion page (such as the article's talk page or in a deletion review). No further edits should be made to this page.

The result was keep. There is consensus that the subject is notable. There was also a mild suggestion of a possible merge as a subtopic of streaming algorithm; it lacked consensus here but could be revisited via a future merge proposal. (non-admin closure) — MarkH₂₁^talk 06:31, 21 April 2021 (UTC)[reply]

One-pass algorithm[edit]

[Hide this box] New to Articles for deletion (AfD)? Read these primers!

(Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL)

Article has been unsourced since Jan 2007. Notability of topic is in question. Coin945 (talk) 05:49, 13 April 2021 (UTC)[reply]

Note: This discussion has been included in the list of Computing-related deletion discussions. Shellwood (talk) 09:14, 13 April 2021 (UTC)[reply]

Keep Loads of hits on scholar and google about this. I believe it can be brought up to encyclopedic standards. //Lollipoplollipoplollipop::talk 10:14, 13 April 2021 (UTC)[reply]
- It's hard to find an actual source for this, but that's because (a) it's so basic and (b) this needs to be treated in a different way. Knuth discusses both single- and multiple- pass algorithms in TAoCP, in the "Coroutines" section, if anyone wants to have Wikipedia discuss this in the way that an expert does. But I see no need for any administrator tools in renaming, refactoring, rewriting, and improving an article that one has researched. Uncle G (talk) 10:43, 13 April 2021 (UTC)[reply]
  - Yes. This is a very basic topic: a lot of the results via google are essentially just lecture notes and lecture slides. But what do you mean treated in a different way? I think there's enough material in sources, and precedent on Wikipedia, for one-pass algorithm and multi-pass algorithm to exist. I will look into TAoCP. //Lollipoplollipoplollipop::talk 11:02, 13 April 2021 (UTC)[reply]
    - Knuth points out that it's a vague concept, and treats both together. Enjoy. Volume 1, of course. Uncle G (talk) 11:42, 13 April 2021 (UTC)[reply]
I added a list of possible sources for the article at Talk:One-pass algorithm //Lollipoplollipoplollipop::talk 15:41, 15 April 2021 (UTC)[reply]
Speedy keep, the nominator does not propose a valid WP:DEL-REASON. The nominator does not say which notability guideline this article fails to meet. SailingInABathTub (talk) 10:25, 13 April 2021 (UTC)[reply]
Comment No valid reason given for speedy keeping. The article only has one listed source. This article as it stands does not pass GNG, although it may well be possible to add enough sourcing to pass that. We should never speedy keep articles that do not as they are written pass GNG.John Pack Lambert (talk) 13:45, 14 April 2021 (UTC)[reply]

Comment IMO the article should be kept and cleaned up. The distinction is important in CS, as a one-pass algorithm by definition can deal with arbitrarily large input with bounded memory. I no longer remember who wrote what, but the definition is clear and useful, and the term itself is clearly in use. To me, the fact that a lot of the references are in things like CS course notes tells me that a Wikipedia page on the topic would be useful, but I don't know where that lands us with Notability standards. The part on cluster representatives seems specific to database algorithms, so I'd be inclined to take it out. I'll see if I can dig up a few references and do a little cleanup --dmh

Keep I missed the link to streaming algorithm. With the text on cluster representatives removed, I think this article is about right: The full details, including the mechanics, are covered under streaming algorithm. This article just calls out that a one-pass algorithm is a particular kind of streaming algorithm, and gives examples of what you can and can't do in one pass. It adds an increment of value over streaming algorithm but mentions some specifics about one-pass algorithms in particular. The one area of improvement would be the examples. It would be good to call out a case that can be solved in more than one pass but not in one. As to notability, "one-pass" algorithm is definitely a term of art in CS. I think the hits for CS courses attest to this, but I don't think they need to be included in the article as references, since they only support notability and don't particularly add to the understanding beyond what's already in the article. --dmh. — Preceding undated comment added 15:45, 14 April 2021 (UTC)[reply]
Keep. This is an important subtopic of streaming algorithms. If it were stubbier, or the streaming algorithm article less broad, then a merge rather than deletion might be warranted, but as it is I think it works well enough as a stand-alone article. Googls Scholar has over 10k hits for "one pass" "streaming" and about the same number for "single pass" "streaming" so notability or availability of sourcing should not be an issue. —David Eppstein (talk) 20:38, 15 April 2021 (UTC)[reply]
Keep. The article needs some more work, but I have added some additional references, more are quite readily available (from searching "one-pass algorithm" or "single-pass algorithm") and it seems fine to me as a stub. jp×g 23:22, 15 April 2021 (UTC)[reply]
Actually, maybe fold into streaming algorithm. I've twice seen material here that's more about particular kinds of streaming algorithm and not about one-pass algorithms in general. First, with the earlier material on cluster representatives, and recently with an assertion that one-pass algorithms work by filtering -- reading input blocks and writing output blocks. Some do, but I don't think any of the original examples do (e.g., finding the sum of a list of numbers). On the other hand, I believe both techniques can just as well be used with multi-pass streaming algorithms. Certainly filtering can -- ask any UNIX pipeline. Rather than having such useful information continually end up in this article, it might be better to make the body of this article a subsection of streaming algorithm and leave this page as a redirect to that section. That still recognizes that one-pass algorithms are a thing, but keeps the technical details under streaming algorithm where (I think) they belong Dmh (talk) 00:18, 16 April 2021 (UTC)[reply]
- Not all streaming algorithms are one-pass algorithms. Streaming algorithms are a broader topic. In particular, turnstile model streaming algorithms are not one-pass algorithms. So although this is a subtopic of streaming algorithms, it is distinct enough from the broader topic that I think it can stand on its own. —David Eppstein (talk) 01:25, 16 April 2021 (UTC)[reply]

The above discussion is preserved as an archive of the debate. Please do not modify it. Subsequent comments should be made on the appropriate discussion page (such as the article's talk page or in a deletion review). No further edits should be made to this page.