A data structure to do a specific lookup fast I have 30,000 items; each item has 30 parameters that take values from 0 to 5. These parameters are named $p_0$ to $p_{29}$ and their value is an integer between 0 and 5. I want to store these items in a data structure where I can do this lookup quickly: find the parameter with a given value for $(p_0, \ldots, p_{29})$.

All items that have $p_i$ less than or equal $x_i$.

So having 50 values $x_0$ to $x_{29}$ I run the above lookup and it returns all items that satisfy it. I used PostgreSQL and created indices for each of these parameters. Querying in PostgreSQL happens in ~20ms. I stored them in a Python list and did a simple [i for i in items if all(i['p' + str(j)] &lt; n[j] for j in range(30))] and it takes ~250ms. By using 30 dicts each containing 6 sets for different values of each parameter and doing the lookup in dicts and intersecting sets I was able to each ~10ms (a bit memory consuming but not that much). Does anyone know about a better data structure to do this query faster? Memory is not an issue as long as it's below 2GB.

In formal language I'd describe it this way:
I have 30,000 records; each record contains 30 values, each in range 0..5:

type Record: array[1..30] of 0..5
var Store: array[1..30000] of Record


I need to find all records in the store, where each element is smaller than in the target one:

procedure Find(target: Record):
  for item in Store:
    if item[0]&lt;=target[0] and item[1]&lt;=target[1] and ... and item[30]&lt;=target[30]: 
      print item


I need to perform Find quick, and can preprocess the Store to make the lookups faster. What data structure and algorithm can I use?
Using SSE2 operations, you can save the entire dataset in 512 KB and search through it, with 4-core CPU, is less than 10 microseconds.

PCMPB+PMOVMSKB instructions will give you 16-bit mask made from 16 byte-wide comparisons. You need to combine two such masks as a&lt;&lt;16+b and make sure that result is all 0s.



Even faster approach is to make bitmap for each p[i]&lt;k condition, overall you need 30*6=180 bitmaps. Each bitmap takes 30K/8=3.75 KB, overall 675 KB.

You need to AND-combine 30 maps corresponding to chosen x[i], i.e. AND-process 675/6=112.5 KB of data. With 128-bit SSE operations, this requires 7K operations, and on the same 4-core CPU, it's less than microsecond long.