Key-value database for dynamic/changing keys

Question

I have the following dataset:

[234,565,678,90,66,7,8,44,5]
[275,23,54,34,5]
[4745,23,54,4,556,65,89,5,4,569,87,412]
[75,273,59,5,4,567,412]
[44,34,556,69,5,4,569,812]

Each array represents a web session. Each element in the array represents an activity that the user did during the session.

What's shown above is only a subset of the entire array list (which consists of over million arrays).

My task is to provide the next element, across all arrays, given an element or list of elements.

Here's an example: if [234] was given, I need to return 565 because [234] matches with the first element of the first array. So I need to return the subsequent 565

But I also need to be able to return a result given an array of elements, like following: if [275,23,54] was given, I need to return 34, because [275,23,54] matches with the first three elements of the second array, and 34 follows that.

This can be done fairly easily in Java-like language if I cache the entire data set in memory, and then search across those. But my challenge is using a database to store and search these. I was leaning towards key/value databases like Redis. My challenge here is that I don't have a "good" key here. My input could be any of the elements in any array, or a list of elements.

What would be the optimal way of storing and searching this.

Cheers!

Answer 1

If I understand well, you want to find the next action based on the cumulated experience of all the sessions together. This means that you'll ignore that there could be very different types of behaviors across two independent sessions.

With a key/value store, you'd be very limited:

• you could have the action as key, and as value the list of next actions sorted by decreasing probability. But this works only if predicting the next of one action, independently of the previous ones.
• you could take into account several successive actions to predict more accurately by using a compound key made of pairs or triplets of actions . But then you'd have to combine several sets of key/values (first triplet, then pairs, then solo), to find out the successor with highest probability.

Alternatively, you could consider a graph database:

• the nodes are the actions, the edges are the probability of the subsequent action. But the challenge is, how to construct the edges. You could just put a weight (reading the sessions and incrementing the weight of the edges on the path). But this will again not consider the action history so well.
• you could also use conditional edges, which give the probability depending of the preceding nodes (edge has 2 attributes: weight and previous node). This will give similar results than the compound key explained for key/value.
• alternatively, you could think of building a [trie graph][1 ("trie" and not "tree": it's not a typo, look at the link). You'd manage this graph as a prefix trie, each action being a letter of your alphabet.

My recommendation: the graph database to construct a prefix trie. But some more research could be necessary.