0
$\begingroup$

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)] < 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]<=target[0] and item[1]<=target[1] and ... and item[30]<=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?

$\endgroup$
  • 1
    $\begingroup$ Please don't just reply to a comment: also edit your question to add the information. I've edited your question based on my understanding of your comment. Please review and correct it if that wasn't what you meant. $\endgroup$ – Gilles Sep 7 '18 at 22:32
  • $\begingroup$ As a practical matter, this is the kind of problem that databases were made to solve, so you may have a hard time beating a database engine at its own game.. $\endgroup$ – Gilles Sep 7 '18 at 22:32
  • $\begingroup$ @Gilles thanks for the edit. Yeah usually databases are supposed to solve these kind of problems, but considering that my dataset is static and never changes and considering the low number of rows and the fact that the lookup is a special kind of lookup it should be possible to beat database engines (at least those that store in disc) my answer and Bulat's answer are 2 examples of how to do better than database engines. $\endgroup$ – Sassan Sep 7 '18 at 23:07
  • $\begingroup$ What do you mean by "find the parameter with a given value for $(p_0, \ldots, p_{29})$"? Do you mean "find the item with a given value for $(p_0, \ldots, p_{29})$? I don't understand what "All items that have pi less than or equal xi." is communicating. That is not a complete sentence, and it's not clear how it relates to anything else. Please edit your question to specify your task more clearly. $\endgroup$ – D.W. Sep 8 '18 at 18:04
  • 1
    $\begingroup$ I understand if you don't have time to edit it; time is precious. You might be more likely to get others to volunteer their time to help you find a better solution if you can edit it to improve. If you don't want to spend the time to make it easy for others to help you, that's your choice, but it might affect whether others want to spend their time to understand the question and answer. $\endgroup$ – D.W. Sep 9 '18 at 18:11
1
$\begingroup$

This is how I optimized it so far: created python dictionary that contains 30 keys for 30 parameters, each value is another dict that contains keys from 0 to 5 (including) for different values each parameter can take. then the values of this final dicts are sets that include indices of the items in original list of items. To look up the query, I simply intersect the relevant sets finding them with fast dict lookups. To optimize it further I sort sets that I want to intersect by their size before intersecting them so that intersections happen with smaller sets.

Suppose that all items are stored in list L:

L = [
    {"entry":"e1","p0":0,"p1":2,"p2":3,"p4":0,...}.
    {"entry":"e2","p0":5,"p1":1,"p2":0,"p4":4,...},
...
]

I build the above mentioned dict like this:

index = {p + str(i): {
            j: {k for k in range(len(words))
                if words[k]['p' + str(i)] <= j} for j in range(5)
        } for i in range(30)}

It just runs once and takes few seconds. Then to lookup I run:

[L[i]['entry'] for i in sorted(functools.reduce(
            operator.and_,
            sorted(
                [index[p + str(i)][x[i]]
                    for i in range(30)],
                key=lambda set: len(set),
            ),
        ))]

It runs in ~5ms and is 4 times better than Postgresql results (as expected because it runs in memory with no disc usage.) But I think it's not smart enough, I'm consuming lots of memory, it's alright for 30,000 items and only 5 values which is the requirements of my real world problem, but I'm still curious to know if this problem has a better solution with less memory usage or even faster?

$\endgroup$
  • $\begingroup$ How about using a kd-tree (or quadtree, R-Tree, ...)? Your items can be stored as 3-dimensional data points/vectors... $\endgroup$ – TilmannZ Sep 8 '18 at 10:04
1
$\begingroup$

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<<16+b and make sure that result is all 0s.


Even faster approach is to make bitmap for each p[i]<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.

$\endgroup$
  • $\begingroup$ Even checking this solution is hard for me, but if correct, it's a perfect solution. specially I like the second solution you provided. For first solution I need to research a bit to understand it so that I can check it and mark this answer as accepted. $\endgroup$ – Sassan Sep 7 '18 at 23:10
  • $\begingroup$ @Sassan The second solution is faster and easier to understand. I think that even with pure Python, it can work faster than your ideas. Or you can write a bit of C code, or find a library dealing with bit arrays (or just supporting AND operation on arrays of ints), or use a Python compiler with static typing. $\endgroup$ – Bulat Sep 7 '18 at 23:21
  • $\begingroup$ @Sassan now you may need to ask Python community where you can find fast bit array implementation, may be there is something right in built-in libraries. $\endgroup$ – Bulat Sep 7 '18 at 23:46
  • $\begingroup$ using this for my real world problem is definitely overkill, so I'm not trying to use it with python. I'll check it with C next free weekend. $\endgroup$ – Sassan Sep 8 '18 at 6:19
  • $\begingroup$ @Sassan googling "bitset python" i found intbitset.readthedocs.io/en/latest - if you spend more time you may find even better solutions. Key point should be the speed of iterating over resulting bitset $\endgroup$ – Bulat Sep 8 '18 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.