# Which is the best data structure for searching under these conditions

I have a system with some factors, say A, B, C, and D. There can be different values of all these factors. Let us consider few values to have a better understanding.

Let's say A has 4 different values, A1, A2, A3, A4. B may have 3 or 5(anything, no order or logic here), similarly C and D may also have many different values.

What I have to do is keep count of is how many times a given combination occurs.

For e.g., one combination is A1, B1, C1, D1. Another may be A1, B1, C2, D1 and so on.

I need to read the count of occurrences of these combination once from a text file, and search for it when queried, and give the corresponding count. There is one more condition. There is a threshold for the count. For example, let's say the threshold is 10. If the count for (A1, B1, C1, D1) is less than 10, then I need to find the count of (A1, B1, C1, Dany), if this is less than 10, then just (A1, B1, Cany, Dany) or (A1, B1).

A trie might have been an option, but searching will take more time than hashmaps there.

Which would be the best data structure to do so in Java?

Of course, the simplest and most obvious solution is to use hashmaps. But the factors(A,B,C,D) may be ten or twenty, and may take thousands of values. Though the file where I am reading values from is updated only once a day, so updating the hashmap is not a problem, but I am not sure if storing this amount of data at once in a DS is possible or not. Also loading it into hashmaps is going to take a lot of space I guess, as we are going to store all the possible permutations in the hashmaps.

Thank you in advance for all your suggestions and efforts, much appreciated.

• Do you also have to query the count of (A1, B_any, C2, D3) or is the "any" always at the end of the tuple? – Socowi Dec 9 '16 at 8:53
• If the number of different values is small, a tree structure is probably good. I'd go for a sorted list though. – adrianN Dec 9 '16 at 8:55
• @Socowi always at the end. To reach Bany, C, D must be Cany, Dany. – Optimus Prime Dec 9 '16 at 8:59
• @OptimusPrime It would help if you made it more clear what the typical situation is and which operations you want to optimize. How many factors and values do we have? What are the values (numbers, strings, ...)?. Are the values fixed/known in advance? Are the values sparse/dense? How many of the combinations actually appear in your text? Do you want to optimize the query for one concrete combination (O(1) for HashMap) or just the query with the threshold (O(#Factors) for HashMap). – Socowi Dec 9 '16 at 11:34
• Cross-posted: stackoverflow.com/q/41047584/781723, cs.stackexchange.com/q/67142/755, cstheory.stackexchange.com/q/37121/5038. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. See also the comments on Stack Overflow for additional feedback on the question. – D.W. Dec 9 '16 at 22:27

Edit: Seems like my proposed structure is not more efficient than a HashMap with additional entries like (A3,B1,Cany,Dany).

# Typical values

There are F=20 factors (A, B, ..., T)
Each factor has V=1000 values (A1, A2, ..., A1000).
A lot of combinations (A524,...,T123) do no appear at all. The data structure should be sparse.

## Suggestion: Use the following tree structure

• Non-root Nodes represent a factor-value (for instance A1).
There can be multiple nodes per factor-value.
• Per Node Xx we store
• The number of (...Xx, Yany, Zany, ...) in the structure
• A HashMap from Y1,...,YV to the corresponding nodes.

# Example

We have the factor-values
A1–A3, B1–B2, and C1–C4.
In our text, the following combinations appeared:
2 times (A1, B1, C1), 1 time (A1, B1, C4), 4 times (A1, B2, C4)

Then our tree looks like the one in the picture below.

The counter per node is green, the hashmap is red.

# Operations and costs

Insertion is O(F). Query (using "any" or not, and using threshold or not) is O(F).
In case the number of factors F is constant, operations are O(1).

### Insertion

We found x new occurrences of combination (Aa, Bb, ..., Nn) and want to update the structure.

curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., N_n)
nextNode := curNode.hashMap[nextFactorValue]
if (nextNode == null)
nextNode := new Node(nextFactorValue)
curNode.hashMap[nextFactorValue] := nextNode
endif
curNode.count := curNode.count + x   // update the "any" counts
curNode := nextNode
endfor
curNode.count := curNode.count + x     // update the concrete count


Should you want to decrement the stored counts, you may want to remove nodes once their counter hits 0.

### Query

Retrieve $count(a,b,...,i)$ = number of found (Aa, Bb, ..., Ii, jany, ..., Nany)

curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., I_i)
nextNode := curNode.hashMap[nextFactorValue]
if (nextNode == null)
return 0
endif
curNode := nextNode
endfor
return curNode.count


### Query with threshold

Compute $count_t(a,b,...,m,n) = \begin{cases} count_t(a,b,...,m),& \text{if } count(a,b,...,m,n)<t\\ count(a,b,...,m,n),& \text{otherwise} \end{cases}$

curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., N_n)
nextNode := curNode.hashMap[nextFactorValue]
if (nextNode == null || nextNode.count < t)
return curNode.count
endif
curNode := nextNode
endfor
return curNode.count

• I will be using Hashmaps. But accepting this answer as this is the best answer on this question :) Also, appreciate your efforts. – Optimus Prime Dec 13 '16 at 9:46