Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes?

• URL: http://arxiv.org/abs/2409.06464v1
• Date: Tue, 10 Sep 2024 12:46:23 GMT
• Title: Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes?
• Authors: Jimmy Lin,
• Abstract summary: We provide experimental results on the BEIR dataset using the open-source Lucene search library. Our results provide guidance for today's search practitioner in understanding the design space of dense and sparse retrievers.
• Score: 62.57689536630933
• License:
• Abstract: Practitioners working on dense retrieval today face a bewildering number of choices. Beyond selecting the embedding model, another consequential choice is the actual implementation of nearest-neighbor vector search. While best practices recommend HNSW indexes, flat vector indexes with brute-force search represent another viable option, particularly for smaller corpora and for rapid prototyping. In this paper, we provide experimental results on the BEIR dataset using the open-source Lucene search library that explicate the tradeoffs between HNSW and flat indexes (including quantized variants) from the perspectives of indexing time, query evaluation performance, and retrieval quality. With additional comparisons between dense and sparse retrievers, our results provide guidance for today's search practitioner in understanding the design space of dense and sparse retrievers. To our knowledge, we are the first to provide operational advice supported by empirical experiments in this regard.

Related papers

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Semi-Parametric Retrieval via Binary Token Index [71.78109794895065]
  Semi-parametric Vocabulary Disentangled Retrieval (SVDR) is a novel semi-parametric retrieval framework. It supports two types of indexes: an embedding-based index for high effectiveness, akin to existing neural retrieval methods; and a binary token index that allows for quick and cost-effective setup, resembling traditional term-based retrieval. It achieves a 3% higher top-1 retrieval accuracy compared to the dense retriever DPR when using an embedding-based index and a 9% higher top-1 accuracy compared to BM25 when using a binary token index.
  arXiv  Detail & Related papers  (2024-05-03T08:34:13Z)
• Efficient Data Access Paths for Mixed Vector-Relational Search [8.80592433569832]
  Machine learning and the adoption of data processing methods using vector embeddings sparked a great interest in creating systems for vector data management. While the predominant approach of vector data management is to use specialized index structures for fast search over the entirety of the vector embeddings, once combined with other (meta)data, the search queries can also become selective on relational attributes. As using vector indexes differs from traditional relational data access, we revisit and analyze alternative access paths for efficient mixed vector-relational search.
  arXiv  Detail & Related papers  (2024-03-23T11:34:17Z)
• LeanVec: Searching vectors faster by making them fit [1.0863382547662974]
  We present LeanVec, a framework that combines linear dimensionality reduction with vector quantization to accelerate similarity search on high-dimensional vectors. We show that LeanVec produces state-of-the-art results, with up to 3.7x improvement in search throughput and up to 4.9x faster index build time.
  arXiv  Detail & Related papers  (2023-12-26T21:14:59Z)
• Dense X Retrieval: What Retrieval Granularity Should We Use? [56.90827473115201]
  Often-overlooked design choice is the retrieval unit in which the corpus is indexed, e.g. document, passage, or sentence. We introduce a novel retrieval unit, proposition, for dense retrieval. Experiments reveal that indexing a corpus by fine-grained units such as propositions significantly outperforms passage-level units in retrieval tasks.
  arXiv  Detail & Related papers  (2023-12-11T18:57:35Z)
• Lexically-Accelerated Dense Retrieval [29.327878974130055]
  'LADR' (Lexically-Accelerated Dense Retrieval) is a simple-yet-effective approach that improves the efficiency of existing dense retrieval models. LADR consistently achieves both precision and recall that are on par with an exhaustive search on standard benchmarks.
  arXiv  Detail & Related papers  (2023-07-31T15:44:26Z)
• WISK: A Workload-aware Learned Index for Spatial Keyword Queries [46.96314606580924]
  We propose WISK, a learned index for spatial keyword queries. We show that WISK achieves up to 8x speedup in querying time with comparable storage overhead.
  arXiv  Detail & Related papers  (2023-02-28T03:45:25Z)
• Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform [0.0]
  We show that for Learned, and as far as the bf SOSD software is concerned, the use of the Standard routine is superior to the Uniform one. Our experiments also indicate that Uniform Binary and k-ary Search can be advantageous to use in order to save space in Learned.
  arXiv  Detail & Related papers  (2022-01-05T11:46:16Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  We use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) to answer spatial range queries. We show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension. We also refine using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions.
  arXiv  Detail & Related papers  (2020-08-24T12:09:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.