Pairing Clustered Inverted Indexes with kNN Graphs for Fast Approximate Retrieval over Learned Sparse Representations

• URL: http://arxiv.org/abs/2408.04443v1
• Date: Thu, 08 Aug 2024 13:14:39 GMT
• Title: Pairing Clustered Inverted Indexes with kNN Graphs for Fast Approximate Retrieval over Learned Sparse Representations
• Authors: Sebastian Bruch, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini,
• Abstract summary: We present Seismic, a highly-accurate approximate retrieval algorithm. Seismic is one to two orders of magnitude faster than state-of-the-art inverted index-based solutions. We introduce two innovations to Seismic's query processing: first, we traverse blocks in order of importance, rather than arbitrarily. Our extension, named SeismicWave, can reach almost-exact accuracy levels and is up to 2.2x faster than Seismic.
• Score: 8.796275989527054
• License:
• Abstract: Learned sparse representations form an effective and interpretable class of embeddings for text retrieval. While exact top-k retrieval over such embeddings faces efficiency challenges, a recent algorithm called Seismic has enabled remarkably fast, highly-accurate approximate retrieval. Seismic statically prunes inverted lists, organizes each list into geometrically-cohesive blocks, and augments each block with a summary vector. At query time, each inverted list associated with a query term is traversed one block at a time in an arbitrary order, with the inner product between the query and summaries determining if a block must be evaluated. When a block is deemed promising, its documents are fully evaluated with a forward index. Seismic is one to two orders of magnitude faster than state-of-the-art inverted index-based solutions and significantly outperforms the winning graph-based submissions to the BigANN 2023 Challenge. In this work, we speed up Seismic further by introducing two innovations to its query processing subroutine. First, we traverse blocks in order of importance, rather than arbitrarily. Second, we take the list of documents retrieved by Seismic and expand it to include the neighbors of each document using an offline k-regular nearest neighbor graph; the expanded list is then ranked to produce the final top-k set. Experiments on two public datasets show that our extension, named SeismicWave, can reach almost-exact accuracy levels and is up to 2.2x faster than Seismic.

Related papers

• Top-Down Partitioning for Efficient List-Wise Ranking [24.600506147325717]
  We propose a novel algorithm that partitions a ranking to depth k and processes documents top-down. Our algorithm is inherently parallelizable due to the use of a pivot element, which can be compared to documents down to an arbitrary depth concurrently.
  arXiv  Detail & Related papers  (2024-05-23T14:00:26Z)
• Efficient Inverted Indexes for Approximate Retrieval over Learned Sparse Representations [8.796275989527054]
  We propose a novel organization of the inverted index that enables fast retrieval over learned sparse embeddings. Our approach organizes inverted lists into geometrically-cohesive blocks, each equipped with a summary vector. Our results indicate that Seismic is one to two orders of magnitude faster than state-of-the-art inverted index-based solutions.
  arXiv  Detail & Related papers  (2024-04-29T15:49:27Z)
• LIST: Learning to Index Spatio-Textual Data for Embedding based Spatial Keyword Queries [53.843367588870585]
  List K-kNN spatial keyword queries (TkQs) return a list of objects based on a ranking function that considers both spatial and textual relevance. There are two key challenges in building an effective and efficient index, i.e., the absence of high-quality labels and the unbalanced results. We develop a novel pseudolabel generation technique to address the two challenges.
  arXiv  Detail & Related papers  (2024-03-12T05:32:33Z)
• Temporal-aware Hierarchical Mask Classification for Video Semantic Segmentation [62.275143240798236]
  Video semantic segmentation dataset has limited categories per video. Less than 10% of queries could be matched to receive meaningful gradient updates during VSS training. Our method achieves state-of-the-art performance on the latest challenging VSS benchmark VSPW without bells and whistles.
  arXiv  Detail & Related papers  (2023-09-14T20:31:06Z)
• Hybrid Inverted Index Is a Robust Accelerator for Dense Retrieval [25.402767809863946]
  Inverted file structure is a common technique for accelerating dense retrieval. In this work, we present the Hybrid Inverted Index (HI$2$), where the embedding clusters and salient terms work to accelerate dense retrieval.
  arXiv  Detail & Related papers  (2022-10-11T15:12:41Z)
• Text Summarization with Oracle Expectation [88.39032981994535]
  Extractive summarization produces summaries by identifying and concatenating the most important sentences in a document. Most summarization datasets do not come with gold labels indicating whether document sentences are summary-worthy. We propose a simple yet effective labeling algorithm that creates soft, expectation-based sentence labels.
  arXiv  Detail & Related papers  (2022-09-26T14:10:08Z)
• An Efficient Coarse-to-Fine Facet-Aware Unsupervised Summarization Framework based on Semantic Blocks [27.895044398724664]
  We propose an efficient Coarse-to-Fine Facet-Aware Ranking (C2F-FAR) framework for unsupervised long document summarization. In the coarse-level stage, we propose a new segment algorithm to split the document into facet-aware semantic blocks and then filter insignificant blocks. In the fine-level stage, we select salient sentences in each block and then extract the final summary from selected sentences.
  arXiv  Detail & Related papers  (2022-08-17T12:18:36Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Temporal Query Networks for Fine-grained Video Understanding [88.9877174286279]
  We cast this into a query-response mechanism, where each query addresses a particular question, and has its own response label set. We evaluate the method extensively on the FineGym and Diving48 benchmarks for fine-grained action classification and surpass the state-of-the-art using only RGB features.
  arXiv  Detail & Related papers  (2021-04-19T17:58:48Z)
• Automated Concatenation of Embeddings for Structured Prediction [75.44925576268052]
  We propose Automated Concatenation of Embeddings (ACE) to automate the process of finding better concatenations of embeddings for structured prediction tasks. We follow strategies in reinforcement learning to optimize the parameters of the controller and compute the reward based on the accuracy of a task model.
  arXiv  Detail & Related papers  (2020-10-10T14:03:20Z)

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.