Hi,

PySparNN looks great! I'd like to know if there is a provision for using custom distances as a metric while searching for nearest neighbors.

E.g. For sklearn.neighbors.NearestNeighbors, the documentation mentions:

metric : string or callable If metric is a callable function, it is called on each pair of instances (rows) and the resulting value recorded. The callable should take two arrays as input and return one value indicating the distance between them.

Do we have such a provision for custom distances in PySparNN? Thanks.

I use the MultiClusterIndex class. With the search method, I only changed the parameter k to 10, but fewer than 10 nearest neighbors are found, only 80% of the examples returned 10 NNs. What I can adjust to make sure that I get 10 NNs for all the cases?

Another question is in the examples, the doc_index are for the whole dataset. Isn’t it should be only for the training dataset?

I got it working for Anaconda3 by doing the following:

In cluster_pruning.py

123c123 < records_index = np.arange(features.shape[0])

        records_index = list(np.arange(features.shape[0]))

131c131 < np.arange(clusters_selection.shape[0]))

                             list(np.arange(clusters_selection.shape[0])))

223c223 < if feature <> None and record <> None:

    if feature != None and record != None:

273a274

                    elements = list(elements)

In matrix_distance.py:

123c123,124 < arg_index = np.random.choice(len(scores), k, replace=False)

            lenScores = len(scores)
            arg_index = np.random.choice(lenScores, min(lenScores, k), replace=False)

329a331

In init.py:

7c7 < from cluster_pruning import ClusterIndex, MultiClusterIndex

from .cluster_pruning import ClusterIndex, MultiClusterIndex

I you should just create two more files for ClusterIndex and MultiClusterIndex. Otherwise it will cause issues with importing in Python3 and backwards compatability for Python2

Hi!

I think this project is similar to the toolchain we are currently using in our production - https://github.com/ekzhu/datasketch + https://github.com/src-d/minhashcuda Do you think it is possible to leverage minhashcuda in pysparnn?

Traceback (most recent call last):
  File "/Users/Bhoomit/work/robin/pysparnn/tests/test_pysparnn.py", line 52, in test_veccosine
    return_distance=False)
  File "pysparnn/cluster_pruning.py", line 274, in search
    k_clusters=k_clusters))
  File "pysparnn/cluster_pruning.py", line 208, in _search
    max_distance=max_distance)
  File "pysparnn/matrix_distance.py", line 81, in nearest_search
    dist_matrix = self._distance(sparse_features)
  File "pysparnn/matrix_distance.py", line 182, in _distance
    return 1 - dprod.multiply(magnitude).toarray()
AttributeError: 'matrix' object has no attribute 'toarray'

I had to use return 1 - np.asarray(dprod.multiply(magnitude))

Am I doing something wrong? I'm using python 2.7 and virtualenv.

When I try to build the search index just like in the example I get a Memory Error:. The data I use is wiki data, I have ~50 gb ram than can be used.

MemoryError                               Traceback (most recent call last)
<ipython-input-15-9815ea3148b7> in <module>()
      1 import pysparnn.cluster_index as ci
----> 2 cp = ci.MultiClusterIndex(tfidfdtmatrix, doctexts)
      3 k = 10
      4 nq = 1

~/miniconda3/lib/python3.6/site-packages/pysparnn/cluster_index.py in __init__(self, features, records_data, distance_type, matrix_size, num_indexes)
    425         for _ in range(num_indexes):
    426             self.indexes.append((ClusterIndex(features, records_data,
--> 427                                               distance_type, matrix_size)))
    428 
    429     def insert(self, feature, record):

~/miniconda3/lib/python3.6/site-packages/pysparnn/cluster_index.py in __init__(self, features, records_data, distance_type, matrix_size, parent)
    121         else:
    122             self.is_terminal = False
--> 123             records_data = _np.array(records_data)
    124 
    125             records_index = list(_np.arange(features.shape[0]))

MemoryError: 

>>> tfidfdtmatrix
<310993x1225250 sparse matrix of type '<class 'numpy.float64'>'
	with 34322030 stored elements in Compressed Sparse Row format>
>>> print(type(doctexts))
<class 'list'>
>>> print(type(doctexts[0]))
<class 'str'>

When I run the script with facebookresearch's fasttext, it cannot acommodate it. But the sample script seems to work well. On this line of the example script: cp = snn.ClusterIndex(feat, data_to_return)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-14-61d2fb78a7b1> in <module>()
----> 1 cp = snn.ClusterIndex(feat, data_to_return)

/home/jung4351/pysparnn/pysparnn/cluster_pruning.py in __init__(self, sparse_features, records_data, distance_type, matrix_size, parent)
    144             records_index = np.arange(sparse_features.shape[0])
    145             clusters_size = min(self.matrix_size, num_records)
--> 146             clusters_selection = random.sample(records_index, clusters_size)
    147             clusters_selection = sparse_features[clusters_selection]
    148

/usr/lib/python3.4/random.py in sample(self, population, k)
    309             population = tuple(population)
    310         if not isinstance(population, _Sequence):
--> 311             raise TypeError("Population must be a sequence or set.  For dicts, use list(d).")
    312         randbelow = self._randbelow
    313         n = len(population)

TypeError: Population must be a sequence or set.  For dicts, use list(d).

The search function, returns only matched value and the similarity score. Is there a way to get which row# in the index the match was found for the top k results?

Hello, I have spatial data (points in Cartesian x, y, z.). I need to designate new value “z” using algorithm Natural Neighbour. Should I use PySparNN or different library? I ask because I haven’t been able to install annoy in win7.

From README:

Note on min_distance thresholds - Each document is assigned to the closest candidate cluster. When we set min_distance we will filter out clusters that dont meet that requirement without going into the individual clusters looking for matches. This means that we are likely to miss some good matches along the way since we wont investigate clusters that just miss the cutoff. A (planned) patch for this behavior would be to also search clusters that 'just' miss this cutoff.

When you are dealing with a large number of duplicate items the recursive nature of the alg goes into an infinite loop. Instead of getting the duplicates distributed evenly at a level they are all allocated to the first item in the matrix.

The current fix is not very efficient:

Line ~96 in nearest_search within matrix_distance.py

if scores.sum() < 0.0001 and len(scores) > 0:
    # they are all practically the same
    # we have to do this to prevent infinite recursion
    # TODO: would love an alternative solution
    arg_index = np.random.choice(len(scores), k, replace=False)
else:
    arg_index = np.argsort(scores)[:k]

Issue Type

[x] Bug (Typo)

Steps to Replicate and Expected Behaviour

• Examine pysparnn/matrix_distance.py and observe implmentation, however expect to see implementation.
• Examine pysparnn/cluster_index.py and observe reccomended, however expect to see recommended.
• Examine pysparnn/matrix_distance.py and observe shortucts, however expect to see shortcuts.
• Examine pysparnn/cluster_index.py and observe perameters, however expect to see parameters.
• Examine pysparnn/cluster_index.py and observe naievely, however expect to see naively.
• Examine pysparnn/cluster_index.py and observe multtiple, however expect to see multiple.
• Examine pysparnn/cluster_index.py and observe doccuments, however expect to see documents.

Notes

Semi-automated issue generated by https://github.com/timgates42/meticulous/blob/master/docs/NOTE.md

To avoid wasting CI processing resources a branch with the fix has been prepared but a pull request has not yet been created. A pull request fixing the issue can be prepared from the link below, feel free to create it or request @timgates42 create the PR. Alternatively if the fix is undesired please close the issue with a small comment about the reasoning.

https://github.com/timgates42/pysparnn/pull/new/bugfix_typos

Thanks.

We have observed some weird behavior seeing small distances at the end of the list of closest matches.

I believe the problem is that the distances are returned as string types and then the sorting does not work

https://github.com/facebookresearch/pysparnn/blob/c299c825fd99f263f3957e9b31197daf23a1e7a3/pysparnn/cluster_index.py#L26

Thanks to provide this convenient toolkit I retrieve bm25 and tfidf sparse vector from lucene indexer (provide by pyserini) and use this project to generate sparse indexer to search. i find that these indexer can not beat original lucene search results. (this problem seems not have much effect on tiny datasets or semantic disperse datasets, but with the dataset become larger, the shortcomings seems can not be omitted which is the situation to use this project.)

This is not the problem of your clustering search algorithm. But the sparse feature itself. And if i use SVD to decrease the dimension of sparse data, it can only maintain topic level feature. So i don’t understand the truly usage of sparse feature except calculate some search scores(like bm25) Because they seems weak than truly lexicon based score (bm25) and dense semantic similarity based on BERT sentence embedding (like Sentence-Transformers)

Can you provide some truly awesome text sparse feature construction reference materials that can use this project in a suitable way ?

From a very quick test with a small index, this seems to work well with dense vectors (I tried d=300), but is there any specific impact of using dense vectors on performance for building or searching the index?

python: 3.6 os: ubuntu numpy:1.16.1 scipy:1.0.0

cp = ci.MultiClusterIndex(features, data_to_return) with open('cluterIndex.bin', 'wb') as fh_out: pickle.dump(cp, fh_out)

obj_file = 'cluterIndex.bin' def test_memory_leak(obj_file): while True: with open('cluterIndex.bin', 'rb') as file_: cp =pickle.load(file_) if name == 'main': test_memory_leak(obj_file )