Data structure to support searches based on a full key or part of a key
I need to be able to search based on the full key or part of the key.
eg. I could store keys like 10,20,30,40 11,12,30,40,12,20,30,40
I want to be able to search for 10,20,30,40 or 20,30,40
What's the best data structure to achieve this ... best for timing.
our programming language is Java. Any pointers to open source projects would be appreciated.
Thanks in advance.
If these were the actual numbers that I was working with, I would use an array where the given index contains an array of all the records that contain the index. If the actual numbers were larger, I would use a hash table used in the same way.
So the structure will look like (empty indices were escaped, in the case of an array implementation):
10 => ((10,20,30,40)),
11 => ((11,12,30,40)),
12 => ((11,12,30,40), (12,20,30,40)),
20 => ((10,20,30,40), (12,20,30,40)),
30 => ((10,20,30,40), (11,12,30,40), (12,20,30,40)),
40 => ((10,20,30,40), (11,12,30,40), (12,20,30,40)),
It's not clear to me if your searches are included (OR based) or exclusive (AND based), but you are looking at groups of records for each element of the search set anyway; for an inclusive search you will find their union, and for an exclusive search you will find their intersection.
source to share
Since you've seen the concern for lookup time on other issues (like space), I suggest you use a hash table and you enter your elements multiple times, once per subsection. So you put ("10,20,30,40", mydata), then put ("20,30,40", mydata) and so on (of course that would be a method, you are not going to manually call that many times ).
source to share
Use a tree structure. Here is an open source project that might help ... written in Java :-)
http://suggesttree.sourceforge.net/
source to share