This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
Why is the author concerned about 'adversarial users' messing with his data structures? Security through obscurity is not very secure anyway. Doesn't this discussion of security of data structures belong in a separate article?
NO! The author is not discussing data security here and has made no mention of data security. The author is discussing the possibility that a user might, accidentally or otherwise, create a worst-case scenario for the data structure's performance. The "adversarial user" is a mnemonic mechanism for the programmer to keep in mind as he programs or designs an algorithm. This is a performance issue and not a security issue as you have misconstrued. Note "worst possible run-time" in the article text.
We're still touting the advantages of randomness to combat adversarial users. I think Wikipedia is a perfect example: how many vandals spend their time making minor edits to an article to stealthily vandalize it, and how many just blank the page? Ensuring that the underlying data structure is obscure seems rather pointless when said 'adversarial' user can simply remove the entire list, or fill it with meaningless values. There are other reasons for randomization (covered above); I believe the article should be rewritten to de-emphasize or remove the 'adversarial user' explanations. (As an aside, inserting randomness does not improve the worst possible case—there is still some sequence of operations that will cripple the data structure—so it seems primarily a security-through-obscurity measure, not a performance "guarantee".) – 74 15:35, 12 February 2009 (UTC)
Wikipedia's manual of style has a section on writing in mathematics articles that I think applies here (see Wikipedia:Manual_of_Style_(mathematics)#Writing_style_in_mathematics). If we could remove the conversational style and have the article read more like an encyclopedia rather than a textbook, it would be an improvement to this article. Sancho McCann 22:02, 10 February 2007 (UTC)
I attempted to remove the conversational tone from the article 192.17.161.202 23:38, 17 October 2007 (UTC)
The part about Jacobson could use a rewrite.
I wonder if it's possible to implement these cute Skip Lists using only TWO fields to navigate in it, i.e. "below" and "next", instead of the usually suggested FOUR including "above" and "before"...? However, I'm not sure how to handle the tower construction if one can't get levels up and nodes before a particular node. How about removing a node? Again, all the tower nodes need to be isolated, isn't that so? How do we do this, using only a "next" and a "below" fields? Could any expert comment on this?
Epsilon1 20:34, 1 April 2007 (UTC)
Read the original paper; N pointers are required for each node, all pointing "forward" different amounts in the list. No "backward" or "up" pointers are used or needed. If for some reason one wanted to traverse backwards in the list, "backward" pointers would solve that problem. However, since this behavior is not usually needed, it's a lot of storage to use on something that won't be used a lot.
I removed the linked page because it is based on a bad implementation and bad information. Nowhere does it say what the skip average was and why it would use a height of 24 nodes or how these were allocated. A height of 24 for 6 million entries is ridiculous. For that many items, a height of 8 is more than sufficient. Depending on the allocation scheme, this will greatly reduce the extra memory and reduce the amount of comparisons done. I've actually tested skip lists extensively and can tell you that in C++ at least, skip lists are exactly on par and occasionally faster with the map template for speed and use about the same amount of memory. Skip lists memory usage and speed can be tweaked according to your need and can reproduce a map quite easily. -- V —Preceding unsigned comment added by 74.106.242.11 ( talk) 01:17, 27 September 2007 (UTC)
I am a very intelligent native speaker of the English language, and the lead section of this article is completely incomprehensible to me. Highly technical language may be appropriate in later sections of an article on a highly technical subject, but the lead section of an article on ANY subject should be comprehensible to a person who is not an expert in the field, without having to follow links to other articles that may be no more comprehensible than it is. This one fails completely. I am adding a well deserved {{Technical}} to this article, with particular emphasis on the lead section.-- Jim10701 ( talk) 09:25, 26 October 2011 (UTC)
The picture doesn't do it for you?
99.94.144.123 (
talk) 00:53, 19 December 2011 (UTC)David
The article is concentrated on skip list with randomized fast links. Does it make sense to add some analysis of list with deterministic logic for fast links? I.e. case where for each node the topmost link points to a node in the middle between current one and the tail. The next one points to the middle between current and above fast link, etc.? Such structure provides more consistent and predictable result in data access. — Preceding unsigned comment added by Azemerov ( talk • contribs) 19:35, 28 February 2012 (UTC)
The issue with such a construction is that you need to add balancing mechanisms to make it work when you insert. It has been done, but is still fairly complicated. — Preceding unsigned comment added by Redmjoel ( talk • contribs) 00:20, 14 May 2013 (UTC)
I've made an animation to show the process of element inserting to skip list. Do you have any comments for animation? Do you have any objections not to include animation to article? Artyom Kalinin ( talk) 06:32, 10 December 2013 (UTC)
Shouldn't the widths of the head nodes in the diagram for indexable skip list be 0 instead of 1? (Or not set at all?) Gvanrossum ( talk) 16:27, 31 March 2014 (UTC)
Though the paper claims it is a probabilistic data structure, it actually isn't! A probabilistic data structure does not keep the data itself and therefore when queried, replies will have some error rate. A skip-list, on the other hand, uses a random function for the structure itself but all data is kept and since there is no data loss, there is no error-rate. I suggest removing the probabilistic tag! Kigelim ( talk) 21:33, 6 January 2020 (UTC)
Currently the article only has information about 'search'. The only sentence about 'erase' and 'insert' is
"Insertions and deletions are implemented much like the corresponding linked-list operations, except that "tall" elements must be inserted into or deleted from more than one linked list."
Then the other 90% of that section is about the quasirandom variant, which is incomprehensible without an explanation of the standard random implementation. — Preceding unsigned comment added by 73.42.179.192 ( talk) 03:47, 11 January 2021 (UTC)
This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
Why is the author concerned about 'adversarial users' messing with his data structures? Security through obscurity is not very secure anyway. Doesn't this discussion of security of data structures belong in a separate article?
NO! The author is not discussing data security here and has made no mention of data security. The author is discussing the possibility that a user might, accidentally or otherwise, create a worst-case scenario for the data structure's performance. The "adversarial user" is a mnemonic mechanism for the programmer to keep in mind as he programs or designs an algorithm. This is a performance issue and not a security issue as you have misconstrued. Note "worst possible run-time" in the article text.
We're still touting the advantages of randomness to combat adversarial users. I think Wikipedia is a perfect example: how many vandals spend their time making minor edits to an article to stealthily vandalize it, and how many just blank the page? Ensuring that the underlying data structure is obscure seems rather pointless when said 'adversarial' user can simply remove the entire list, or fill it with meaningless values. There are other reasons for randomization (covered above); I believe the article should be rewritten to de-emphasize or remove the 'adversarial user' explanations. (As an aside, inserting randomness does not improve the worst possible case—there is still some sequence of operations that will cripple the data structure—so it seems primarily a security-through-obscurity measure, not a performance "guarantee".) – 74 15:35, 12 February 2009 (UTC)
Wikipedia's manual of style has a section on writing in mathematics articles that I think applies here (see Wikipedia:Manual_of_Style_(mathematics)#Writing_style_in_mathematics). If we could remove the conversational style and have the article read more like an encyclopedia rather than a textbook, it would be an improvement to this article. Sancho McCann 22:02, 10 February 2007 (UTC)
I attempted to remove the conversational tone from the article 192.17.161.202 23:38, 17 October 2007 (UTC)
The part about Jacobson could use a rewrite.
I wonder if it's possible to implement these cute Skip Lists using only TWO fields to navigate in it, i.e. "below" and "next", instead of the usually suggested FOUR including "above" and "before"...? However, I'm not sure how to handle the tower construction if one can't get levels up and nodes before a particular node. How about removing a node? Again, all the tower nodes need to be isolated, isn't that so? How do we do this, using only a "next" and a "below" fields? Could any expert comment on this?
Epsilon1 20:34, 1 April 2007 (UTC)
Read the original paper; N pointers are required for each node, all pointing "forward" different amounts in the list. No "backward" or "up" pointers are used or needed. If for some reason one wanted to traverse backwards in the list, "backward" pointers would solve that problem. However, since this behavior is not usually needed, it's a lot of storage to use on something that won't be used a lot.
I removed the linked page because it is based on a bad implementation and bad information. Nowhere does it say what the skip average was and why it would use a height of 24 nodes or how these were allocated. A height of 24 for 6 million entries is ridiculous. For that many items, a height of 8 is more than sufficient. Depending on the allocation scheme, this will greatly reduce the extra memory and reduce the amount of comparisons done. I've actually tested skip lists extensively and can tell you that in C++ at least, skip lists are exactly on par and occasionally faster with the map template for speed and use about the same amount of memory. Skip lists memory usage and speed can be tweaked according to your need and can reproduce a map quite easily. -- V —Preceding unsigned comment added by 74.106.242.11 ( talk) 01:17, 27 September 2007 (UTC)
I am a very intelligent native speaker of the English language, and the lead section of this article is completely incomprehensible to me. Highly technical language may be appropriate in later sections of an article on a highly technical subject, but the lead section of an article on ANY subject should be comprehensible to a person who is not an expert in the field, without having to follow links to other articles that may be no more comprehensible than it is. This one fails completely. I am adding a well deserved {{Technical}} to this article, with particular emphasis on the lead section.-- Jim10701 ( talk) 09:25, 26 October 2011 (UTC)
The picture doesn't do it for you?
99.94.144.123 (
talk) 00:53, 19 December 2011 (UTC)David
The article is concentrated on skip list with randomized fast links. Does it make sense to add some analysis of list with deterministic logic for fast links? I.e. case where for each node the topmost link points to a node in the middle between current one and the tail. The next one points to the middle between current and above fast link, etc.? Such structure provides more consistent and predictable result in data access. — Preceding unsigned comment added by Azemerov ( talk • contribs) 19:35, 28 February 2012 (UTC)
The issue with such a construction is that you need to add balancing mechanisms to make it work when you insert. It has been done, but is still fairly complicated. — Preceding unsigned comment added by Redmjoel ( talk • contribs) 00:20, 14 May 2013 (UTC)
I've made an animation to show the process of element inserting to skip list. Do you have any comments for animation? Do you have any objections not to include animation to article? Artyom Kalinin ( talk) 06:32, 10 December 2013 (UTC)
Shouldn't the widths of the head nodes in the diagram for indexable skip list be 0 instead of 1? (Or not set at all?) Gvanrossum ( talk) 16:27, 31 March 2014 (UTC)
Though the paper claims it is a probabilistic data structure, it actually isn't! A probabilistic data structure does not keep the data itself and therefore when queried, replies will have some error rate. A skip-list, on the other hand, uses a random function for the structure itself but all data is kept and since there is no data loss, there is no error-rate. I suggest removing the probabilistic tag! Kigelim ( talk) 21:33, 6 January 2020 (UTC)
Currently the article only has information about 'search'. The only sentence about 'erase' and 'insert' is
"Insertions and deletions are implemented much like the corresponding linked-list operations, except that "tall" elements must be inserted into or deleted from more than one linked list."
Then the other 90% of that section is about the quasirandom variant, which is incomprehensible without an explanation of the standard random implementation. — Preceding unsigned comment added by 73.42.179.192 ( talk) 03:47, 11 January 2021 (UTC)