A new kind of Key/Value store. In this architecture, keys and values are stored within two separate 'data objects' which are linked together. One holds all the unique values along with their reference counts, the other contains all the keys and links to their mapped values. The architecture allows any value to be mapped to one or more keys and any key to be mapped to one or more values (unless an attribute on the dat…
Sounds kinda like tuplespaces/Linda (which I think are very good, largely unpursued ideas).
If the KV store is a 'state' column in a DB table of US customer addresses for example, the number of unique values is limited to 50 (if you ignore D.C., Puerto Rico, etc.). The table might have 100M customers, each mapped to at least one state. Each state (except less populated ones like Wyoming) might have millions of rows mapped to it. Many customers might have addresses in more than one state.
The system has to do things like: "Find every key mapped to a state that starts with the letter 'M'" or "Find every value that is mapped to this set of keys". These are the kinds of things a normal SQL query has to do.