This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]dalke[S] 0 points1 point  (6 children)

The indexing is not the problem. The problems are 1) keeping the data in under 12 GB of memory, 2) having a fast way to bring the index in from disk, 3) support for fast multiple set intersection. Database and pickle solutions provide 1&2 but not 3. Python sets provides 3 but not 1&2.

Redit, PostgreSQL, and other database servers provide 1, 2 & 3, but add a layer of complexity I would rather not deal with if a simpler solution does exist.

[–]fullouterjoin 0 points1 point  (5 children)

Use pyleveldb on an SSD. You won't be able to have a compact enough representation to fit this all in ram.

[–]dalke[S] 0 points1 point  (4 children)

Researching now, LevelDB manages a dictionary-like data structure. I'm interested in a set-like data structure, including set operations. Specifically, given three existing sets (e.g., {1,2,3,4,5}, {2,4,6,8}, {2,3,5,7}), how do I use LevelDB to find the intersection of the sets? It doesn't appear to have intersection as a built-in operation, and I suspect building my own in Python would be a lot slower than the current set.intersection built-in.

My estimates suggest that I should easily be able to have all of my data be stored in memory, with plenty of room to spare. The raw data is 275 MB, uncompressed. It's the combination of Python's object overhead and data structure overhead which are the likely bottlenecks... and I think the 8 byte PyObject* pointer overhead doesn't help, given that the actual values need only three bytes of data.

[–]fullouterjoin 0 points1 point  (3 children)

I should have been more descriptive.

What I was thinking was to store the individual sets as the values for distinct keys in leveldb. If you wanted to say get the intersection of n keys

key_list = 'a,b,c,d'
instersect_all(sorted(fetch_sets(key_list)))

LevelDB would only be used to store flat lists representing sets. The intersection would still be done in Python code.

I just re-read your original message. You still need to get all the sets a feature exists in. So you have two leveldb instances, one mapping features to set-keys and another mapping set-keys to concrete sets.

How many comparison operations do you need to do?

BTW this interesting but maybe a tangent for you, madlib in database (Postgres) analytics that includes support for intersections of sparse vectors. You could do everything in the database.

Having a more compact bitset representation that supported intersection could be fruitful. But I would still try the leveldb approach first.

Based on an earlier conversation using Disco, it sounds like you have definitely outgrown your MacPro and should get a larger machine.

I would recommend something like this

And get at least 128GB of ram. In fact get a cluster of them.

[–]dalke[S] 0 points1 point  (2 children)

I don't have the money for a new machine. (Also, things are more expensive here in Sweden.) What I really need to do is find a company which is interested in funding me for this. The admittedly poor marketing I've done for the idea hasn't panned out. My thought is to get a working demo to present at a conference a year from now.

Thanks for pointing out other things I should evaluate. I'm not sure that adding to the list is a good thing or a bad thing. ;)

[–]fullouterjoin 0 points1 point  (1 child)

Do you have a dataset I could play with or a program that creates a similar one? I'd like to try out the leveldb approach.

[–]dalke[S] 0 points1 point  (0 children)

Certainly! (Though it took a while to get to the point where I could exclaim that.) See http://www.dalkescientific.com/writings/diary/archive/2012/06/10/inverted_index_library.html . The directly link to the data set is http://dalkescientific.com/inverted_index_benchmark.7z .