Inverted Files
This package implements inverted files, also known as inverted indexes, that are data structures that represents a large sparse matrix, specially organized to compute some distance functions and fetch k
nearest neighbors.
It is mainly used for full text search and other search tasks where data can be formulated as large sparse vectors.
In particular, the package implements three types of inverted files:

WeightedInvertedFile
: Inverted files for sparse vectors, it can solve$k$ nearest neighbors using the normalized cosine distance,$1  dot(u, q)$ 
BinaryInvertedFile
: Inverted file for sparse binary data, it can solve$k$ nearest neighbors using Jaccard, Dice, and Cosine distances, and also the intersection dissimilarity measure. 
KnrIndex
: An approximated similarity search index based on inverted files. It supports general metric spaces.
These structs integrates with the SimilaritySearch
environment, such that you can use it as a dropin replacement of other indexes. In particular, inverted files are wellknown for its scalability when the proper setup is used.
Installation
using Pkg
Pkg.add("InvertedFiles")
KnrIndex
About the This package defines the KnrIndex
similarity search index that takes advantage of multithreading systems.
It is based on inverted files InvertedFiles
and SimilaritySearch
.
In particular, it supports any SemiMetric distance function, as defined in Distances
package. For instance, you can use distances for vectors, sets, strings, etc.,
as defined in SimilaritySearch
or StringDistances
packages.
As SearchGraph
in SimilaritySearch
, the KnrIndex
supports autoconfiguration, using optimize!
. Contrary to SimilaritySearch
, the optimization it is only performed for searching purposes.
See https://github.com/sadit/SimilaritySearchDemos, almost all examples should be reproduced using the KnrIndex
defined in NeighborhoodApproximationIndex
,
just using the index and calling optimize!
with the corresponding arguments (see documentation for more details).
The basic ideas of this package are described in
Edgar Chavez, Mario Graff, Gonzalo Navarro, Eric S. Tellez:
Near neighbor searching with K nearest references. Inf. Syst. 51: 4361 (2015)
Eric S. Tellez, Edgar Chavez, Gonzalo Navarro: Succinct nearest neighbor search. Inf. Syst. 38(7): 10191030 (2013)
Eric S. Tellez, Edgar Chavez, Gonzalo Navarro: Succinct nearest neighbor search. SISAP 2011: 3340 (2011)
The KnrIndex
supports appending and automatic optimization to achieve some desired performance, also, userbased distance functions could work pretty fast since the indexes are written in the Julia language.
Nonetheless, the inverted files are plain inmemory structures without any kind of compression or compactness. The compressed datastructure can be found in the old C# library natix.