Hacker News Reader

Comment by lostmsu | Hacker News Reader

Quick tip: this is about relational algebra's select operation (which is basically row filtering; choosing columns is called 'project' there).

View on HN

To be precise, this is about the bitlevel SDS rank and select operation.

https://en.wikipedia.org/wiki/Succinct_data_structure

I didn't get that impression at all. This is "get me the rank (index) of the first occurrence of x" in a succinct data structure. Nothing to do with relational algebra AFAICT except to the extent I suppose that some relational algebra implementations may use such data structures under the hood.

Yes, but 'select' is the name of that operation in the relational algebra. Which confuses some people whose first exposure to that model is through SQL, where the keyword implies a combination of 'select' and 'project'. I think the commenter's intent was to clarify that.

Yeah, succinct data structures aren't something taught in most intro to data structures courses, and the concept may even be unfamiliar to oldhats since SDSs are relatively new on the scene -- the public datasphere only started becoming conscious of the idea in 1988 when Guy Jacobson introduced them in his CMU thesis. And I have yet to find a digital copy of it online so for those who want to read the original thesis, you may have to order a paper copy of one or go to the CMU library to read it.

https://scholar.google.com/scholar?q=guy+jacobson

But, there's been a lot of development on succinct data structures since, and this post on the fast select algorithm was in-part a continuation of a conversation from a post yesterday on succinct data structures in general and the open-source lib SDSL 2.0. So if anyone wants to learn more about SDSs in general, there's a bunch of links to videos and reference material in the comments of yesterday's thread...

SDSL – Succinct Data Structure Library 2.0 https://news.ycombinator.com/item?id=18204432

Reply on news.ycombinator.com