Multi value dictionary

[kamcio181]

Hello,

I can see that during compilation I can add multiple values for one key and then after compilation I can see in Statistics that there are one key but many values. However I cannot figure out how to retrieve more than one value for a given key.
I am using python.

[hendrikmuhs]

A key can only have one value, if you add a key multiple times with different values the behavior is unspecified. Only one entry will end up in the dictionary. Internally the FSA generator ignores a key that is added again, however the order isn't defined, the compiler sorts key/values and the sort algorithm does not guarantee stable sort (a stable sort algorithm keeps insertion order for equal entries).

Multi value dictionaries need to be implemented client side, e.g. if you use a json dictionary you could wrap your values in an array.

[kamcio181]

At the beginning I tried to check whether duplicated keys are ignored so I compiled two dictionaries:

1. one key, 100 unique values
2. one key 100000 unique values
   The second file is multiple times bigger than the first one, so I thought that multiple values are stored somehow in compiled file but I cannot retrieve it.

However if it should be implemented client side I will try to find some solution.
But maybe you could give me a hint - I am retrieving data in batches and passing the data to JsonDictionaryCompiler so I do not know all values for given key upfront. As a result I cannot build json array and pass it to the complier.
Is there any hack or keyvi feature I could use in such case?

[hendrikmuhs]

yes, the values are stored, however they are not connected to a key in this case. That means the space is basically wasted.

But maybe you could give me a hint - I am retrieving data in batches and passing the data to JsonDictionaryCompiler so I do not know all values for given key upfront. As a result I cannot build json array and pass it to the complier.
Is there any hack or keyvi feature I could use in such case?

That's hard: as said a key value store does not support this case, you can only set 1 value per 1 key. Other stores work-around this by supplying special operations, e.g. redis supports list values, where you can push/pop/insert values to a list. However the ordinary set/get works the same way: it overwrites the old value.

Instead of using a dictionary you could use an index and get the old value, create a new value by concatenating the old and new one and write the concatenated value. This will of course cost some performance compared to your current raw compiling.

To be aware of: a keyvi index works "near realtime", that means writes are not immediately available(similar to Lucene/Elasticsearch). However if you can ensure that a batch does not contain duplicate keys, you could explicitly flush the index before every new batch.

(For illustration: assume you have key1:value1 and set key1:value1,value2 and shortly after you want to add value3. If the index is not flushed, you still retrieve key1:value1 and therefore write key1:value1,value3 instead of key1:value1,value2,value3. A flush happens internally every 1s, but can also be externally triggered, which us what I suggest per batch)

(Longer term we could add a feature to the index that concatenates values internally, this would avoid the extra round-trip if done in the application layer)

[narekgharibyan]

hey @kamcio181

The second file is multiple times bigger than the first one, so I thought that multiple values are stored somehow in compiled file but I cannot retrieve it.

Right, we are adding all values to the value store, but later on when another entry with same key is being added, one of them is becoming like a "dangling" value, without a reference to it.
This is done, because we try to minimize compilers memory footprint, so we write the entry to the file as soon as possible.

But maybe you could give me a hint ...

One possible workaround on this is to make use of prefix matching.

Like you can keep a global counter, and add it to the end of each key, this way all keys in your dictionary will be unique, and value pointers won't be overwritten.

Later on when reading from file you can do a prefix lookup and find all the matches that belong to your key.

Something like this:

import keyvi.compiler
import keyvi.dictionary
import keyvi.completion

KEYVI_FILE_NAME = 'keyvi.kv'


class MultiValueDictionary:
    def __init__(self, filename):
        self._dictionary = keyvi.dictionary.Dictionary(filename)

    def get_values(self, key):
        prefix_completion = keyvi.completion.PrefixCompletion(self._dictionary)
        for match in prefix_completion.GetCompletions(key):
            yield match.GetValue()


def stream_data():
    return (
        ('key1', 'value1'),
        ('key1', 'value2'),
        ('key1', 'value3'),
        ('key2', 'value4'),
    )


compiler = keyvi.compiler.JsonDictionaryCompiler()

counter = 0
for key, value in stream_data():
    unique_key = f'{key}:{counter}'
    compiler.Add(unique_key, value)
    counter += 1

compiler.Compile()
compiler.WriteToFile(KEYVI_FILE_NAME)

multi_value_dict = MultiValueDictionary(KEYVI_FILE_NAME)
print('----- key1 -----')
values_iter = multi_value_dict.get_values('key1')
print(list(values_iter))
print('----- key2 -----')
values_iter = multi_value_dict.get_values('key2')
print(list(values_iter))

Output

-> python multi_value_keyvi.py
----- key1 -----
['value1', 'value2', 'value3']
----- key2 -----
['value4']

Sure this can be improved with some additional checks and etc, but the basic idea is ^.

[kamcio181]

Thank you guys for the prompt response. It is clear that I need to implement multi value feature on client side.
At this point I ended up with processing in two stages. First is compiling key only Dictionary where item is composed from key, delimiter and value, so similar to @narekgharibyan suggestion. Second one is iterating over created dictionary in order to create final Json Dictionary where value is an array of values for a given key, so something @hendrikmuhs suggested in his very first response. It puts some overhead during compilation but provides better performance during lookups.
However I do not consider this solution as final one, maybe I will come up with something better.
During tests I noticed that creating dictionary with 12 kk items using Index approach takes a lot of time when you use small batches i.e. 10k.
Also I noticed that using prefix completion is much slower than using GetNear directly from Dictionary with proper minimum prefix.

P.S. Keyvi is great piece of code and I can't wait to explore it more deeply.