Search by overlap-match-count ?

[vsraptor]

I can store sequence of numbers as a key :

kv.Set('str-list','[1,2,3]')
kv.Get('str-list').GetValue()
[1, 2, 3]
type(kv.Get('str-list').GetValue())
list
kv.Set('[1,2]','kwy-str-list')
kv.Get('[1,2]').GetValue()
'kwy-str-list'

Given that, I want to store as a KEY a sequence of S numbers, where S < N. f.e. N=100, S=5

[4,6,16,44,89]
[12,13,46,55,67]  
[9,14,56,82,85]
[4,7,16,55,92]
...

and then given another sequence f.e. [4,9,16,46,92] to match/find either the KEY with most overlapping numbers,
in this case :

[4,7,16,55,92] # matches:4,16,92

and/or the top X KEYS by sorted by overlap f.e. if X == 3

[4,7,16,55,92]   #4,16,92
[4,6,16,44,89]   #4,16
[12,13,46,55,67]  #46 

Is this possible by Keyvi or FST ? Regex?
The numbers in the KEY can be sorted like here..

[hendrikmuhs]

Am I getting this right: you are looking for exact matches for a number of elements in the vector?
The elements are not dimensions, that means re-ordering does not change the meaning: [1,2] == [2,1]

For this case you could build subsets of the key. Because free ordering you don't need every permutation.

e.g. from [4,7,16,55,92]

you could build

4,7,16 - > [4,7,16,55,92]
4,7,55 - > [4,7,16,55,92]
4,7,92 - > [4,7,16,55,92]
4,16,55 - > [4,7,16,55,92]
4,16,92 -> [4,7,16,55,92]
...
7, 55, 92 -> [4,7,16,55,92]
...
16,55,92 -> [4,7,16,55,92]

This looks wasteful on the 1st look, and would cause a lot of overhead if you do this and put the key/values into a hash set. But with an FST and minimization it should create a small lookup dictionary.

A similar idea has been used for multiword completion matching: https://github.com/KeyviDev/keyvi/blob/master/python/examples/completion/multiword_completion_writer.py.

For the multiword completion case we built a key-only dictionary and made the "value" part of the key separated by a magic separator. This was needed because of conflicting keys, e.g. this would conflict:

4,16 -> [4,6,16,44,89]
4,16 -> [4,7,16,55,92]

That's why the lookup is special, too.

So, I think it is "somehow" possible, but requires some coding and experimentation.

[vsraptor]

Correct the ordering does not matter.

The problem with the lookup idea is I dont know how big the overlap is in advance, I need to get back the full sequence back that has the maximum overlap.

it is like extracting the most similar item by using overlap-match instead of Levenstain-dist.

You can look at it as 100bit binaries :

   1001100....
   01001100..
   10000101..

and doing overlap = count(a & b) for best match.

I'm using numbers instead of 0|1, because the vectors are sparse and very large ... N = 1000 ... 100_000, S = 2% of N

So instead of 1000 0|1, I can use just 20 numbers representing the positions of the 1s

In a sense I want to use keyvi as a memory for large sparse binary vectors. Numpy is slow as the size grows.

[hendrikmuhs]

GetNear matches exact as long as possible and returns close matches after exact matching fails. You can choose to run it in greedy mode, which means it even returns more matches below the exact path. It's iterator based, that means it matches when you advance the iterator, that way you can e.g. stop after 10 or stop after 100 matches.

The application for GetNear is matching geohashes or other z-order or hilbert curve encoded strings. The big advantage of such encodings is their increasing precision with every bit/byte. E.g. a geohash is basically binary search on a world map, with increasing length you increase the precision. In addition you interleave longitude and latitude. I imagine this works for more dimensions, e.g. latitude, longitude and height, but will get ineffective for > 8 dimensions.

It would be good if for your case something like this is possible as well. Otherwise I don't see an advantage using keyvi, because in the end you will have to compare almost every key. Therefore I suggest to do some research on z-order or hilbert curve and see if you can apply something like that.

[vsraptor]

sound complex, have to reread it many times. where is the doc for GetNear

[hendrikmuhs]

Docs remain problematic (but I am working on it).

A good example from unit tests (its for the index, but works for dictionaries in a similar way):
https://github.com/KeyviDev/keyvi/blob/master/python/tests/index/index_test.py#L123