0

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!

3
  • Have you considered using Aerospike ? Feb 20 '20 at 8:05
  • How do you ensure that an element or list of elements given to search for is unique? You said it was user activity. Users do what they like. In cases where it's not unique what result do you want? Feb 20 '20 at 8:20
  • Will the input patterns always be at the start of the arrays? That can be handled pretty efficiently by indexing/sorting/partitioning the arrays. Or could the pattern be a substring of the array? That would make indexing less feasible, and you can't really prevent a complete scan of all array contents.
    – amon
    Mar 21 '20 at 10:26
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.

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.