# Incremental Extractive Opinion Summarization Using Cover Trees

arXiv: https://arxiv.org/abs/2401.08047 · HTML: https://mlsanity.com/paper/2401.08047/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 69 references that are in the map.
- First posted on arXiv 16 Jan 2024.

## Builds on (most cited first, 30 of 34)

- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [On Faithfulness and Factuality in Abstractive Summarization](https://mlsanity.com/paper/2005.00661/) (2020)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering](https://mlsanity.com/paper/1602.01585/) (2016)
- [Extractive Summarization as Text Matching](https://mlsanity.com/paper/2004.08795/) (2020)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Extractive Opinion Summarization in Quantized Transformer Spaces](https://mlsanity.com/paper/2012.04443/) (2020)
- [Prompted Opinion Summarization with GPT-3.5](https://mlsanity.com/paper/2211.15914/) (2022)
- [Searching for Effective Neural Extractive Summarization: What Works and What's Next](https://mlsanity.com/paper/1907.03491/) (2019)
- [Building Real-World Meeting Summarization Systems using Large Language Models: A Practical Perspective](https://mlsanity.com/paper/2310.19233/) (2023)
- [Extractive is not Faithful: An Investigation of Broad Unfaithfulness Problems in Extractive Summarization](https://mlsanity.com/paper/2209.03549/) (2022)
- [Examining the State-of-the-Art in News Timeline Summarization](https://mlsanity.com/paper/2005.10107/) (2020)
- [MemSum: Extractive Summarization of Long Documents Using Multi-Step Episodic Markov Decision Processes](https://mlsanity.com/paper/2107.08929/) (2021)
- [Unsupervised Extractive Opinion Summarization Using Sparse Coding](https://mlsanity.com/paper/2203.07921/) (2022)
- [Unsupervised Abstractive Opinion Summarization by Generating Sentences with Tree-Structured Topic Guidance](https://mlsanity.com/paper/2106.08007/) (2021)
- [Summarization Programs: Interpretable Abstractive Summarization with Neural Modular Trees](https://mlsanity.com/paper/2209.10492/) (2022)
- [Weakly-Supervised Opinion Summarization by Leveraging External Information](https://mlsanity.com/paper/1911.09844/) (2019)
- [Medoids in almost linear time via multi-armed bandits](https://mlsanity.com/paper/1711.00817/) (2017)
- [Large-Scale and Multi-Perspective Opinion Summarization with Diverse Review Subsets](https://mlsanity.com/paper/2310.13340/) (2023)
- [Ultra Fast Medoid Identification via Correlated Sequential Halving](https://mlsanity.com/paper/1906.04356/) (2019)
- [Beyond Opinion Mining: Summarizing Opinions of Customer Reviews](https://mlsanity.com/paper/2206.01543/) (2022)
- [Can LMs Generalize to Future Data? An Empirical Analysis on Text Summarization](https://mlsanity.com/paper/2305.01951/) (2023)
- [A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree](https://mlsanity.com/paper/2111.15478/) (2021)
- [Revisiting the Centroid-based Method: A Strong Baseline for Multi-Document Summarization](https://mlsanity.com/paper/1708.07690/) (2017)
- [PDSum: Prototype-driven Continuous Summarization of Evolving Multi-document Sets Stream](https://mlsanity.com/paper/2302.05550/) (2023)
- [Follow the Timeline! Generating Abstractive and Extractive Timeline Summary in Chronological Order](https://mlsanity.com/paper/2301.00867/) (2023)
- [Attributable and Scalable Opinion Summarization](https://mlsanity.com/paper/2305.11603/) (2023)
- [Unsupervised Opinion Summarization Using Approximate Geodesics](https://mlsanity.com/paper/2209.07496/) (2022)

## Built on by (most cited first, 4 of 4)

- [OpinioRAG: Towards Generating User-Centric Opinion Highlights from Large-scale Online Reviews](https://mlsanity.com/paper/2509.00285/) (2025)
- [SUMIE: A Synthetic Benchmark for Incremental Entity Summarization](https://mlsanity.com/paper/2406.05079/) (2024)
- [Distilling Opinions at Scale: Incremental Opinion Summarization using XL-OPSUMM](https://mlsanity.com/paper/2406.10886/) (2024)
- [LFOSum: Summarizing Long-form Opinions with Large Language Models](https://mlsanity.com/paper/2410.13037/) (2024)

## Abstract (arXiv)

Extractive opinion summarization involves automatically producing a summary of text about an entity (e.g., a product's reviews) by extracting representative sentences that capture prevalent opinions in the review set. Typically, in online marketplaces user reviews accumulate over time, and opinion summaries need to be updated periodically to provide customers with up-to-date information. In this work, we study the task of extractive opinion summarization in an incremental setting, where the underlying review set evolves over time. Many of the state-of-the-art extractive opinion summarization approaches are centrality-based, such as CentroidRank (Radev et al., 2004; Chowdhury et al., 2022). CentroidRank performs extractive summarization by selecting a subset of review sentences closest to the centroid in the representation space as the summary. However, these methods are not capable of operating efficiently in an incremental setting, where reviews arrive one at a time. In this paper, we present an efficient algorithm for accurately computing the CentroidRank summaries in an incremental setting. Our approach, CoverSumm, relies on indexing review representations in a cover tree and maintaining a reservoir of candidate summary review sentences. CoverSumm's efficacy is supported by a theoretical and empirical analysis of running time. Empirically, on a diverse collection of data (both real and synthetically created to illustrate scaling considerations), we demonstrate that CoverSumm is up to 36x faster than baseline methods, and capable of adapting to nuanced changes in data distribution. We also conduct human evaluations of the generated summaries and find that CoverSumm is capable of producing informative summaries consistent with the underlying review set.