   very large union find data structure
  Hi guys I am in need of a union find algorithm that is capable of handling very large datasets. The roots, i.e. each union must hold a linked list. This is easy to implement myself but the core issue is that the tree structure can be larger than RAM can support. Therefore I was hoping a library already exists that is capable of storing the entire structure on the harddrive and still efficiently perform the necessary operations. Can this be done efficiently using a standard relational databse? If so how, otherwise is there another library?-CProgrammer   
  I'm not very experienced in this area, but here's some URLs that might be good food for thought:http://hadoop.apache.org/core/http://en.wikipedia.org/wiki/BigTable   ;  you should create a file with headers at the beginning of each node's data, so you can quickly jump to internal nodes... for example:This is a single data node:Node Header: - Some sort of identifier for this node - Number of subnodes (for example: 3) - Offset to subnode 1 - Offset to subnode 2 - Offset to subnode 3 - Data sizeData: - Store all the data for the current node hereThis way, you can quickly see if you're at the correct node by using the identifier (or by reading the data), if not, you can jump through the file by the offsets specified in the header. I hope you can work out the implementations yourself. Im unaware of any library that does this for you.   ;  Also: how large is the file you're talking about?gigabytes? petabytes? yottabytes?   ;  Thanks for all the input. The size is Gigabytes for now but may be larger in the future. Hadoop sounds very intriguing, the capabilities are endless and I should be able to create an implementaion of this with it. Ill start by making a simple file based version and then adding hadoop.Thanks.CProgrammer;  This isn't exactly what you asked for but i think it might be useful information for you.I've heard that heap sort can efficiently sort data that is too large to be held in memory all at the same time.That might help your task somewhere in there :P   ;  It's an interesting question. The difficulty would not be in representing the structure -- a tree can easily be stored on disk -- but in keeping stuff arranged so that traversal would be as localized as possible. I would say the best way to do this would be to piggyback re-localization onto path compression, by moving nodes during a find operation in addition to reparenting them. The tricky part would be identifying a good place to move the nodes, and to set things up such that trees tend towards spatial locality in the long run, even when they're moved after being compressed and unioned.Also, I don't know of a library to do any of this. Sorry.EDIT: Actually, now that I think about it, re-localization wouldn't be necessary. Trees would still be distributed around the disk, but thanks to the path compression, the number of blocks one would have to access would tend towards two per find. Actually, it's pretty much an ideal algorithm for high-latency storage.[Edited by - Sneftel on May 21, 2009 9:33:46 PM];Quote:Can this be done efficiently using a standard relational databse?Certainly, computing unions is one of the primitives of relational algebra.   ;Quote:Original post by loufoqueQuote:Can this be done efficiently using a standard relational databse?Certainly, computing unions is one of the primitives of relational algebra.That's not what he's talking about. clicky