Please help me find a good skip list algorithm [C/C++]

[Elledan]

So far I've found HybridList, interval skip list (IS), but the former lacks any kind of documentation, and the latter is quite old (1994), which makes me doubt its efficiency.

The operations which need to be done as quickly as possible are inserting, updating, deleting and retrieving of data.

Thanks in advance

 

[Cat]

Get the paper from the UMD PhD, which was written in the late 90s. Maybe it's the 94 paper you're talking about. 6 years isn't that old. If you're really that concerned that his approach is outdated, email him. Check his website for further papers. I found the paper pretty self-explanatory.

 

[Cat]

Also: inserting, updating, deleting and retrieving of data?

What other operations could you possibly need from a data structure? I think you've got to determine what ops are most important to you. You can't have them all

 

[Elledan]

<< Also: inserting, updating, deleting and retrieving of data?

What other operations could you possibly need from a data structure? >>

Well, sorting is one of them


<< I think you've got to determine what ops are most important to you. You can't have them all >>

True true but that doesn't mean that wishful thinking is forbidden =)

i would say that retrieving of data has the highest priority.

 

[Elledan]

<< Get the paper from the UMD PhD, which was written in the late 90s. >>

UMD?

I know, I'm a newbie =)

 

[singh]

If retrieving the data is important, perhaps hash tables might help (they could guide you in the skipping part perhaps). Haven't worked with Skip Lists before (haven't needed them), so hopefully someone can give you some good ideas.

 

[Elledan]

<< If retrieving the data is important, perhaps hash tables might help (they could guide you in the skipping part perhaps). Haven't worked with Skip Lists before (haven't needed them), so hopefully someone can give you some good ideas. >>

Nah, hash tables are a VERY bad idea when working with large amounts of data. I previously was looking at using red-black BSTs, but skip lists are even faster.

To give you an idea of my needs: the data to be stored in the structure can reach 500+ MB and I'll have to retrieve data from it about 200 times per second.

Sounds insane enough?

 

[Cat]

UMD is the University of Maryland. Find the the original skip list .pdf (google), and also find his web site. Implement said algorithm.

 

[Elledan]

<< UMD is the University of Maryland. Find the the original skip list .pdf (google), and also find his web site. Implement said algorithm. >>


Gotcha. Thanks!

 

[Elledan]

<< UMD is the University of Maryland. Find the the original skip list .pdf (google), and also find his web site. Implement said algorithm. >>


No luck. I can't find the file anywhere

 

[Elledan]

Okay, I found the (C++) source for a deterministic skip list (DSL). Looks quite good.

Any comments?

 

[Cat]

ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

 

[CSoup]

<<

<< UMD is the University of Maryland. Find the the original skip list .pdf (google), and also find his web site. Implement said algorithm. >>


No luck. I can't find the file anywhere >>



That's the paper that I linked to in the other thread when you inquired about skiplists. Good to see that you are investigating the use of skiplists over balanced trees.

here it is.

Oh, also, the guy teaches at UMD, but was a Cornell PHd when he invented the skiplist.
I wrote a skiplist implementation in java once. Don't have the code and it is likely not the most efficient implementation anyways.

Don't know of sources of implementations offhand, but if you want a C++ version, try not to use a version that uses templates because templates in C++ are not too efficient.

 

[Elledan]

<< ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf >>


Thank you, Cat!



<< Don't know of sources of implementations offhand, but if you want a C++ version, try not to use a version that uses templates because templates in C++ are not too efficient. >>


Hmm... to be honest, I have never really used templates with C++. I just don't see any reason to use them =)

Thanks for the advice!