Add sparse vector implementation

[mikera]

Various applications (machine learning, collaborative filtering, recommender systems) depend on large sparse vectors, which contain relatively few non-zero values relative to their size.

Proposal is to add sparse vectors with the following attributes:

• Space requirement grows only with the number of non-zero elements
• Fast element access O(log32 n) or better
• Fast updates O(log32 n) or better
• All other vector operations implemented with reasonable efficiency.

Efficiency is probably best achieved with a shallow tree data structure, though a hashmap based sparse vector could also be an option.

[mdekstrand]

Over in LensKit, we take a somewhat different design:

• The valid keys for a sparse vector are fixed when the vector is created
• O(lg n) access & update (keys & values stored in parallel arrays)
• Sorted by key
• Very fast dot products & other pairwise vector-vector operations

The big things that we need are performance-related:

• Low memory use
• Minimize on-the-fly memory allocation
• Fast access/update (we even have an API that allows constant-time updates while iterating over a vector)
• Fast vector-vector operations, even with non-identical key sets
• Handle any long as valid keys (including negative values)
• Mutable and immutable versions — while it would be possible to get away from this, it is fairly foundational to how we've designed and documented our APIs.

[mikera]

@elehack thanks for the comments - very interesting. I need to have a think about how much of this we can support in Vectorz. Initial thoughts:

• longs as valid keys are probably OK for sparse vectors, but dense vectors can't be made bigger than int size for obvious reasons
• negative indexes are problematic: we're quite strict on 0... n-1 index ranges in the API contracts. How much of a big deal is this and why is it needed?
• immutable vector versions should be OK, it hasn't been a priority so far but the API is designed to allow it. it does imply a slight performance overhead though - curious as to why you need this?
• all the performance stuff is OK (and matches the overall Vectorz philosophy)

[mdekstrand]

• Yep, we use int keys for our dense vectors too (although our dense vectors aren't used much yet). And sometimes we map user/item ids down to consecutive indexes to store them in an array or dense vector.
• We support negative keys because we use sparse vectors to store lots of user/item vectors; user/item IDs come from the client-configured data access layer, and we impose no restrictions on that interface aside from the existence of unique long IDs. Most data sources have non-negative IDs, but I've been known to take advantage of that to use negative IDs as synthetic IDs in some test/evaluation code. It might not be a huge deal, or used anywhere, but it would be a notable new restriction on the behavior of the data access abstraction (which has been unchanged in this regard since the earliest releases).
• We use immutable vectors a lot so that classes can be guaranteed that they're allowed to hang on to a vector without copying it and not worry about some other component modifying it. LensKit has lots of decoupled components that don't know what each other are doing, and immutable vectors allow us to statically prohibit a lot of undesirable interactions.

Our vectors have 3 versions with 2 concrete implementations:

• Base class SparseVector — abstract, provides the read-only API. Many components that act on sparse vectors take a SparseVector. If you have a reference to a SparseVector, the type system says you can't modify it, but does not prohibit another component from modifying it.
• MutableSparseVector — concrete mutable implementation.
• ImmutableSparseVector — concrete immutable implementation. If a component has one of these, not only is it prohibited from changing it, but it is guaranteed that no other code can change it.

[mikera]

Got it. The immutable / mutable approach is consistent with what we do in Vectorz, we actually have two distinct tests:

• isMutable : i.e. can the vector be modified at all. If false, you can depend on the vector being immutable.
• isFullyMutable : i.e. does the vector support mutable setting to any value in any position (so e.g. your MutableSparseVector would not meet this criteria since the key domain is limited)

Also Vectorz is getting some adoption as the main pure-JVM matrix library in Clojure, so immutability is an important priority.

The negative indexes I think can't be supported with the current Vectorz AVector API - this is for a whole bunch of reasons: performance, the need to guarantee certain type invariants, the fact that Vectorz supports composite / concatenated vector views etc.

This still leaves open the option of a sparse vector implemented as a wrapper over a Vectorz dense vector. That might actually be a good solution: a lot of performance would come from the underlying dense vector, while the wrapper could take care of the mapping and indexing. Could be something like an enhanced variant of the current SparseIndexedVector:

• https://github.com/mikera/vectorz/blob/master/src/main/java/mikera/vectorz/impl/SparseIndexedVector.java

[mikera]

FWIW, I've now added immutable vectors and matrices to the latest development branch of Vectorz. Will be in the 0.25.0 release

[mikera]

OK we now have a SparseHashedVector, which takes care of the fully mutable sparse vector case. Should be in 0.27.0 release.

Closing this specific issue as I think the original scope is now covered. Hopefully this solves the mutable sparse case for LensKit as well - if not then should probably be a new issue.