A memory data structure that supports logical queries

Question

I need to store data in memory, where I map one or more lines of keys to an object, as follows:

"green", "blue" -> object1 "red", "yellow" -> object2 

So, in Java, a data structure may exist:

 Map<Set<String>, V> 

I need to be able to efficiently get a list of objects where the strings match some logical criteria, for example:

 ("red" OR "green") AND NOT "blue" 

I work in Java, so a ready-made Java library would be an ideal solution. Nevertheless, I am ready to implement something from scratch, if necessary.

Does anyone have any ideas? I would rather avoid the overhead of the database in memory, if possible, I hope for something comparable in speed to the HashMap (or at least the same order of magnitude).

Answer 1

I could not find a satisfactory solution, so I decided to prepare my own and publish it as an open source project (LGPL), find it.

Answer 2

Actually, I liked the problem, so I implemented a complete solution in the spirit of my earlier answer:

http://pastebin.com/6iazSKG9

A simple solution, an unsafe thread or something else, but fun and a good starting point, I think.

Edit: some development, on request

---

See unit test for use.

There are two interfaces: DataStructure<K,V> and Query<V> . The DataStructure behaves like a map (and in my implementation, it actually works with an internal map), but it also provides reusable and immutable query objects that can be combined as follows:

  Query<String> combinedQuery = structure.and( structure.or( structure.search("blue"), structure.search("red") ), structure.not( structure.search("green") ) ); 

(A query that searches for objects marked as (blue or red) AND NOT green). This query is reused, which means that its results will change whenever the backup card changes (sort of like an iTunes smart playlist).

Request objects are already thread safe, but there is no backup card, so there is room for improvement. In addition, queries can cache their results, but that probably means the interface needs to be expanded to provide a cleanup method (like the disconnect method in Wicket models), which would not be very pretty.

As for licensing: if someone wants this code, I will gladly put it on SourceForge, etc ....

Sean

Answer 3

Were the criteria for indexing a bitmap: http://en.wikipedia.org/wiki/Bitmap_index ?

Answer 4

I would say that the easiest way is to simply recursively filter and wedge when, for example, an estimate of X AND Y , where X was evaluated in an empty set.

However, the display should be from tags (such as "red" or "blue") to sets of objects.

The base register (resolution of atomic tags) recursion will then be a simple search on this map. AND will be implemented using intersection, OR using union, etc.

Answer 5

Check out the Apache Commons - Collections project . They have tons of great materials that you can use, in particular the CollectionUtils class to perform strong collection-based logic.

For example, if your values ​​were stored in a HashMap (as suggested by another answer) as follows:

 myMap["green"] -> obj1 myMap["blue"] -> obj1 myMap["red"] -> obj2 myMap["yellow"] -> obj2 

Then, to get results that match: ("red" or "green") and not "blue , you can do the following:

CollectionUtils.disjunction (CollectionUtils.union (myMap.get ("red"), myMap.get ("green")), myMap.get ("blue"))

Answer 6

You can map the string keys to a binary constant, and then use the bit offset to create the corresponding mask.

Answer 7

In fact, I think some kind of database solution is your best bet. SQL easily supports querying data on

 (X and Y) and not Z 

Answer 8

this would also work reusable condition / expression classes

Answer 9

The Google Collections SetMultimap looks like an easy way to get a basic structure, and then combine static filters with Maps to get the required query behavior.

Construction will be like

 smmInstance.put(from1,to1); smmInstance.put(from1,to2); smmInstance.put(from2,to3); smmInstance.put(from3,to1); smmInstance.put(from1,to3); //... 

requests would look like

 valueFilter = //...build predicate Set<FromType> result = Maps.filterValues(smmInstance.asMap(),valueFilter).keySet() 

You can do any number of fancy predicate constructions, but Predicates has several methods that are likely to be sufficient to execute, contains / does not contain style queries.