Which is the best data structure for searching under these conditions
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),&amp; \text{if } count(a,b,...,m,n)&lt;t\\
count(a,b,...,m,n),&amp; \text{otherwise}
\end{cases}
$

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