What is the difference between Index and Dictionary ??

[vsraptor]

What is the difference between Index and Dictionary ??

It is not clear from the docs !!
I can store KV pair in .Index, why would I use Dict !!

[hendrikmuhs]

It started with dictionaries:

"The immutable FST data structure can be used stand-alone for static datasets."

A dictionary is a static, immutable container, that means it can not be updated once it is written. You get fast access and compact size, for the price of being not update-able.

To overcome this limitation an index is nothing else than a stack of dictionaries. Think of 1 big dictionary and a small dictionary which contains the update. At lookup you first check the small dictionary and if you don't find the answer there, you look into the big dictionary.

"If you need online writes, you can use keyvi index, a near realtime index."

In an index you can create, update, delete entries any time. In the background the index creates dictionaries and maintains a stack. But the index does another important thing, it merges dictionaries in the background. This reduces the size and the number of inner lookups. If you stop writing to an index you will end up with 1 dictionary per index.

If you want to read/learn more about this, you can look for content that describes how Lucene works. In the Lucene world you have segments, segments are the counterpart of dictionaries in keyvi from a storage perspective(Otherwise the comparison is not quite accurate, because segments store more than key value pairs).

For static datasets there are still use cases to use the dictionary directly. Actually most users of keyvi still use dictionaries and not the index. That might be historical reasons, as said, it started with dictionaries. Another reason are features, there are features that are not available for indexes, but only for dictionaries, e.g. some approximate matching use cases. However, if you look at the open PR's, you will see, we are working on bringing this functionality to indexes. Even if indexes are able to do everything a dictionary is able to do one day, dictionaries have its place and I would not want to hide them.

LBNL the quality of docs: You are absolutely right, docs are a weak point. It's an open source project and time is limited.

[vsraptor]

Very clever ... thanks
now i understand .. i saw you have getfuzzy (arg2 permanent prefix, arg3 levinstein dist, or was the other way around ) for index too .. but Dict have some others i was unable to decipher ;)

I use index for now. The index ends up ~4-5 files .. how do i merge them ?
Is the format the same i.e. I can open index.kv as Dictionary ?

[vsraptor]

BTW what i like about keyvi is that it does 700ns .. 1micro-sec access, which is the ideal for cache .. nothing else come closer an on top of that compresses ..

i just recently discovered FST even that i implemented this : https://github.com/vsraptor/multi_regex

almost year ago ;)

[vsraptor]

LBNL the quality of docs: You are absolutely right, docs are a weak point. It's an open source project and time is limited.

what i do is open a jupyter lab page and when i feel it write 5-6 REPL lines .. later i fill some comments.. after day or two.. rinse and repeat ...in a weeks you will have the full docs... just keep it open .. and REPL is ready and waiting.. then just upload the file github renders it for you... try it ;)

import keyvi

[hendrikmuhs]

yeah, jupyter notebooks would be great for all the examples, back in the days gh did not support it, but meanwhile this works really well.

I use index for now. The index ends up ~4-5 files .. how do i merge them ?

This happens automatically if you keep the index open(python continues to run and you still have a handle to the index).

The other option: The C++ backend has a ForceMerge(num_segments = 1) method that blocks until merges produced the desired number of segments(dictionaries), e.g. 1. This is a borrowed concept from Lucene/Elasticsearch. However, I just saw, this method is not exposed to the python binding, not a big deal to add. In addition I was thinking of a GetDictionary method in the index, that lets you turn the index into a dictionary (I would only allow this call if the index consists of 1 dictionary).

Is the format the same i.e. I can open index.kv as Dictionary ?

Yes, same format. In a nutshell an index is simply a directory of dictionaries, however it has more files:

• a toc file that contains the stack of dictionaries and some meta data
• up to 2 files per dictionary for deleted keys. These are temporary files with sets of keys that are deleted, at merge time the dictionary gets rewritten and entries get deleted. So a merge can also happen for 1 dictionary and 1 delete file.
  • Why 2 per dictionary? Imagine another delete is called while a merge is in progress. So the merge removes the keys at the time the merge has been started, deletes that happen afterwards are not part of this merge, but need to be remembered until the next merge which than can permanently delete the entries.