SeekStorm’s LSMT-IVF for Billion-Scale Approximate Nearest Neighbor Search

  1. War of the worlds vs. we come in peace
  2. Data structures and algorithms
  3. LSMT-IVF for Billion-Scale Approximate Nearest Neighbor Search
  4. Benchmarking

Vector vs. keyword search 3: LSMT-IVF for Billion-Scale Approximate Nearest Neighbor Search

Challenges in vector search

  • scaling for large document numbers: either the index size or the indexing time required for “construction” or “learning” grow quadratically
  • indexing / precalculation latency
  • search latency
  • recall in approximate nearest neighbor search (ANNS)
  • expensive cosine similarity calculation for large vectors with many dimensions/features
  • index size
  • CRUD support and incremental indexing and updating: many indices are immutable write-once, the require all documents of the corpus at once for the “learning phase” before the indexing into the “learned” index can start, and they require re-learning/re-indexing if the whole index if something has changed, is updated or deleted.
  • true real-time search capability including concurrent indexing/updating and searching
  • for the same recall, we can trade-off between indexing speed vs. query speed
  • additionally, we can trade recall for both indexing speed and query speed
  • nlist, nprobe, and different clustering methods are parameters to balance this trade-off
  • Incremental training/indexing,
  • true real-time search,
  • RAM/SSD hybrid index for large index size
  • Hybrid RAM/SSD storage
  • unlimited scaling for a large number of documents (billion-scale)
  • incremental indexing (streaming instead requiring upfront the whole corpus for training)
  • concurrent indexing, updating and searching
  • full CRUD support (index is updatable vs. immutable index that requires re-training and re-indexing the whole corpus)
  • full real-time persistence with ACID
  • SIMD CPU hardware acceleration for dot product and cosine vector calculation
  • high indexing speed, independent from corpus size (linear instead of quadratic construction or learning)
  • low query latency (<10 ms) with high recall for billions of documents
  • true real-time search
  • faceted search filtering for vector search (value and range facets)
  • integrated document and object store
  • agnostic to vector data source of arbitrary dimensions/features
  • selectable similarity metrics
  • pluggable clustering algorithms
  • pluggable dimensionality reduction and compression algorithms

--

--

Founder SeekStorm (Search-as-a-Service), FAROO (P2P Search) https://seekstorm.com https://github.com/wolfgarbe https://www.quora.com/profile/Wolf-Garbe

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store