Incremental Extractive Opinion Summarization Using Cover Trees
Authors: Somnath Basu Roy Chowdhury
Nicholas Monath
Kumar Avinava Dubey
Manzil Zaheer
Andrew McCallum
Amr Ahmed
Snigdha Chaturvedi
Venue: Accepted by TMLR ()

Abstract: 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 accrue over time, and opinion summaries must 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 25x 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.

Published in Transactions on Machine Learning Research (03/2024)
Incremental Extractive Opinion Summarization Using Cover Trees
Somnath Basu Roy Chowdhury', Nicholas Monath?, Kumar Avinava Dubey Manzil Zaheer", Andrew McCallum', Amr Ahmed', Snigdha Chaturvedi' UNC Chapel Hill, 2 Google DeepMind, Google Research
{somathh snigdha)dcs. unc. edu (nmonath, avénavadubey, manailzaheer, mecal lam, amra)@google.com
Reviewed on OpenReview: https: // openreview. net/ forun? id= IzmLJI t498
Abstract
Extractive opinion summarization involves automatically producing summary of text about an entily (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 subset of review sentences closest 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 a cover tree and maintaining a reservoir of candidate summary review sentences. CoverSumm's 's efficacy is supported by a theoretical and empirical analysis of rumning time. Empirically, 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.
1 Introduction
Opinion summarization (Hu & Liu, 2004; Medhat et al., 2014; Pang, 2008) is the process of automatically generating summaries of user reviews about entities (such as e-commerce products). The summarized text is useful in many ways, including assisting customers in making informed purchasing decisions and aiding sellers in understanding user feedback. Incremental opinion summarization is particularly important as online marketplaces continue to grow and the efficiency and accurate evolution of product summaries is paramount. Most. of the current. opinion summarization systems operate in static setup generating summary based on the complete set of reviews. Updating opinion summaries with such static systems is expensive, as the entire set of reviews must be processed each time a new review arrives. This necessitates the development of techniques that can efficiently update summaries with changes in the review set. Even when utilizing the LLMs, such as GPT-4 (Bubeck et al., 2023), performing opinion summarization still poses challenges due constraints like token limit as well as high computational cost in incremental settings (Bhaskar al., 2023).
Code available here: https:/ hteee//gitttt http://ggtttth.ooo htt.o////reeaaaa/ooooooooo /CoverSumm.

---

Published in Transactions on Machine Learning Research (03/2024)
Opinion summarization systems can produce either abstractive (Isonuma et al., 2021; Kim Amplayo et al., 2022) or extractive summaries (Kim et al., 2011). While abstractive summaries allow for novel phrasing, they often suffer from hallucination (Ji et al., 2022), lack of faithfulness (Maynez et al,, 2020) and interpretability (Saha et al., 2022), especially for larger review sets. Extractive summarics, which are the focus of this work, reduce concerns about hallucination and lack of faithfulness (Zhang et al., 2023) by producing a summaay consisting only of a carefully selected subset of review sentences. Most extractive opinion summarization systems operate in an unsupervised setup due to the large volume of reviews in real-world settings. In the incremental setup, providing supervision becomes even more challenging, as it necessitates having oracle or summaries at each time step, which is expensive. Therefore, we focus on unsupervised approaches to perform incremental extractive opinion summarization.
Unsupervised extractive summarization approaches assign saliency scores to review sentences and extract the ones with the highest scores as the summary (Peyrard, 2019; Angelidis et al., 2021). The quality and efficiency of producing the summary depend on the extractive summarization method. While previous work presented complex graph-based objectives that use lexical features to extract summarizing sentences (Erkan & Radev, 2004; Mihalcea & Tarau, 2004; Nenkova & Vanderwende, 2005), recent work has demonstrated that a simple centrality-basee approach with learned representations for the input reviews produces state-of-tho-nn results across wide variety of datasets (Chowdhury et al., 2023; 2022; Chu & Liu, 2019). This objective, known as CentroidRank (Radev et al., 2004), functions by calculating the centroid of review sentences in the representation space, and selecting the nearest neighbors of the centroid as the summary. Note that CentroidRank's objective is closely related to classic problems in machine learning such as finding the central nodes in a graph (Okamoto et al., 2008) or (sdoid within a dataset (Bagaria et al., 2018; Baharav & Tse, 2019). Previous work (Chowdhury et al., 2022; 2023) has advanced the statc-of-tho-art in extractive summarization using CentroidRank approaches by improving the represenlation learning method for the imput reviews. There is less work focusing on the algorithmic aspects of these methods. In particular, there is limited work in adapting these methods to incremental settings, where reviews are added over time. and a summary needs to be kept up-to-date with each addition.
In this paper, we focus on the task of incremental extractive opinion summarization, which involves the extraction of salient sentences from contimuous stream of reviews they arrive. We propose novel algorithm CoverSumm, that executes centroid-based extractive summarization (Chowdhury et al., 2022; Li et al., 2023; Gholipour Ghalandari, 2017; Radev et al., 2004; Rossiello et al., 2017) in an incremental setup. bentroid-based incremental extractive summarization requires computing the k-nearest neighbours of the centroid (where & is the number of sentences in the summary) at each point in time. CoverSumm efficiently performs incremental summarization by maintaining a small reservoir of input samples (reviews) without. processing the entire review set at every time step. Empirical evaluation shows that CoverSumm up to 36x faster than baselines. The speedup occurs as CoverSumm limits most of the nearest neighbour search queries to the reservoir instead of the entire review set. We perform experiments on large real-world review sets and show that generated summaries align with the aggregate user reviews. Our primary contributions are:
We study the problem of extractive opinion summarization in an incremental setup, where a system generates an updatod summary with cach incoming user review (Section 2).
We extend the paradigm of centroid-based summarization to incremental setup, and propose CoverSumm that performs extractive summarization using cover trees (Section 3).
We perform thcoretical analyses to show that CoverSumm generates exact nearest neighbours (NN) and provide bounds for the number of NN queries, as well as maximum storage required (Section 3.1).
We evaluate CoverSumm to show that it is significantly faster than baselines (up to 36x), and requires minimal additional space. We also perform experiments to gauge the quality of the generated summaries, and if the content of the summaries aligns with the aggregate user reviews (Section 4).
2 Preliminaries & BBckkroond
In this scction, we first describe centroid-based extractive summarization in the incremental sotting. Then, we present the data structures used for efficient nearest neighbor and range search in CoverSumm. Following that, we will outline some simple baselines that utilize these data structures.
2

---

Published in Transactions on Machine Learning Research (03/2024)
2.1 Problem Formulation
In this section, we formally describe the problem of extractive summarization and then its extension in an incremental setting. Given a set of review sentences for product, the objective of the extractive summarization system is to select subset of sentences as the sunmary. Similar to prior works, we compute the saliency score for each review sentence and select a subset of sentences with high salience scores as the summary. We build on the paradigm of centroid-baser extractive summarization techniques (Radev et al., 2004; Rossicllo al., 2017), where the saliency score of a review sentence is quantified as its distance to the centroid in the representation space. We assume access to a representation model that yields a numerical representation for imput texts. In this paradigm of summarization, the system greedily selects k-nearest neighbours of the centroid as the output summary. Mathematically, given a set of sentence representations in D-dimensional space, X = [g,,.. E BTXD, the summary representation with budget k is S E R*xD and is computed as:
= E F
Σ T E.
(1)
The final summary is concatenation of review sentences whose reprosentations are present in S.
Incremental Summarization Task. We study this paradigm of summarization in an incremental setup, where at every time step t, a new representation Ia arrives and we have the representation set X = [ Using this set, the system should generate a summary S, consistent with the formulation Equation 1. We aim to develop efficient algorithms that accurately estimate S.. In this work, we primarily focus on reducing computation overhead, not storage space, as storing text representations is relatively inexpensive.
2.2 Efficient Nearest Neighbour Data Structures
Efficient retricval of nearest neighbors of a centroid can be performed using index-based data structuros. In this work, we will focus on cover tree-based index structures (Beygelzimer al., 2006; Zaheer el al., 2019).
Cover Trees (Beygelzimer al., 2006). Each node in cover tree is associated with representative point E X. The nodes of the tree arranged into series of levels. Nodes in level e, denoted Ct, have an associated parameter 7 used to define the the following set of invariants:
Covering: For each representation x E C₁, there exists at least a representation y E Ct-1 such that distance d(z, y) S Sf One such representation y that satisfies the condition must be a parent of x. Separation: Any pair of representations x, y E Ct are separated by at least d(x, y) 7 Nesting: If z appears at level e, it must appear at all lower levels. Therefore, Ce Cz-1-
Cover trees support efficient nearest neighbor search using the algorithms presented by Beygelzimer et al. (2006) and modified for use in our method (Algorithm 2). The construction operations (e-g., insert) of the cover tree can be performed in an incremental manner. For a detailed discussion of the running time of search and construction of cover trees, we refer readers to (Elkin & Kurlin, 2022; 2023).
Stable Greedy (SG) Trees (Zaheer et al., 2019). SG trees are defined similarly to cover trees, with a modified separation property. Rather than requiring all nodes in the level to be separated, only sibling nodes in the tree structure are required to be scparated, c.g., all pairs of siblings x, y E C2 are at least d(x, y) > o apart. An illustration of an SG Tree is shown in Figure 1 (bottom left). Zaheer et al. (2019) demonstrated that SG trees empirically improve on the online construction time compared cover trees. the following sections, we will observe that in our proposed algorithm, construction poses more of a bottleneck than search queries. Therefore, in practice, we will use SG trees for our experiments. In presenting our proposed methods, will refer to the tree structures cover trees (since the results are general to the broader class of cover tree data structures of which SG trees are an instance).
2.3 Baselines
In this section, we will discuss baseline approaches for performing incremental centroid- basod summarization before introducing our proposed algorithm, CoverSumm.
3

---

Published in Transactions on Machine Learning Research (03/2024)
Incremental CentroidRank
CentroidRank selects the k-nearest neighbours of the current centroid as the summary.
Hy Centroid at the i-th time step
M++1
H1+2
1143
H4t
Incomiin review
representations over time
SG Tree:
ReservoirSeaacc((1:.2..
Reservoir Search Query
All incoming points are indexed in the SG Tree. tree the reservoir using ReservoirSearch queries.
Enter subtree only d(j, 4max I d(j,
update
I yltl
d(u, 9)
Level /
Query μ
SY
ss
S y
S r
d(u, n)
Oc.. 2 -
Candidate NN 7
Level (1
Figure 1: Overview of the incremental ControidRank-basee summarization task and the utility of nearest neighbour (NN) data structures. (Top): We show the CentroidRank task in the incremental setting, where the centroid (1:) evolves over time. Additionally, we illustrate the benefits of maintaining reservoir of candidate samples for NN retrieval. (Bottom): We show how utilizing efficient NN retrieval data structures, such as the SG Tree, can enhance the efficiency of incremental summarization using reservoir search (discussed in Section 3), particularly scenarios where the reservoir does not have all the NNs the centroid.
Brute Force Algorithm. In this approach, we compute the centroid representation at every time step P4 = L/t RD, Then, we compute the summary at step t: S, = knn(X,, Brute-force computation of nearest neighbours (Equation 1) requires (t)) time at each summarization step. Assuming a total of n text representations in the input stream, the time complexity O
Naive Algorithm with Cover Tree. The bulk of the computation in the brute force algorithm relies knn queries (as centroid is updated in O(1) w.r.t. the number of instances). The running time of the k-nearest neighbor operation can be reduced by using any exact or approximate nearest neighbour retrieval data structures. We use cover trees (Beygelzimer et al., 2006) to improve the performance of the brute-force algorithm. each time step 6, we execute the following queries on a cover tree insert((;) and knn(p)). For a total of reviews, this yields an overall time complexity of O(n log While our work uses cover because of its theoretical properties illustrated above, the index could be replaced with any efficient nearest neighbour retricval index (c.g., kd-tree (Bentley, 1975), quad tree (Samet, 1984), r-tree (Guttman, 1984), HNSW (Malkov & Yashuniu, 2018b), etc.) that supports similar kinds of incremental operations like insertions, nearest neighbour, and range search.
3 Cover Tree based Summarization (CoverSumm)
In this section, we present an efficient algorithm, CoverSumm, for performing centroid-based extractive summarization in an incremental setup. CoverSumm builds on the observation that as the number reviews increases, there are smaller perturbations in their centroid, Pt (assuming that the representations belong the same distribution with fixed centroid), thereby resulting in infrequent changes the k-nearest. neighbours of μ4- Motivated by this observation, we improve upon the Naive CT algorithm (Section 2.3) by
4

---

Published in Transactions on Machine Learning Research (03/2024)
reducing the number of knn(j4) queries executed. This is achieved by maintaining small reservoir R of representations that we anticipate to be the k-nearest neighbours of future centroids Pyt- This allows us to work with a small number of representations in R without having to execute expensive nearest neighbour queries on the entire set, X. To describe our algorithm preciscly, we first define the following propositions:
Proposition (Bounding distance to centroid). Let 21, be i.i.d. samples from distribulion with centroid a supported on [-b/2, 6/2] P and H4 = -i= Deft. Then, the Euclidean distance of any sample x from bt can be bounded with probubility (1 -5)0 as:
Db (2/6) Ve E b-b/2,
x) S 2( +
(2)
2t
We obtain the above result by applying the Hoeffding- Azumaa inequality (Hoeffding, 1963) (more details in Appendix A.1) to each dimension of the vector followed by triangle inequality (proof in Appendix A.2). Next, we use the result from Proposition 1 to derive a bound on how much subsequent centroids shift over time. The detailed proof of Proposition is provided in Appendix A.3.
Proposition 2 (Bounding distance between subsequent centroids). Let I1, ,2, be i. samples from a distribution with centroid μ supported on b/2b and 14 = Ei= xz/t. Then, we con bound the Euclidean dislance belween subsequent centroids jet and ptti with probability (1 8)20:
2D (2/(2 VI E In - 11, E |m - 1..
d(He, S
(3)
Outline. Equipped with these results, we present our summarization algorithm, CoverSumm (Algorithm 1). The main idea behind our approach is to maintain a small reservoir of sentences R (with a maximum capacity of (max) along with the cover tree index (ct). The reservoir's capacity R set to be more than the summary budget k. R. facilitates the computation of k-nearest neighbours of jt+z (i >>>>>>>> 0), in the subsequent time steps instead of executing expensive knn queries on the entire cover tree. We initialize R with points close to the current centroid Pr from the cover tree, ct. Naively applying range search query in the cover tree can return all representations within radius of r to the input query pa. To have more than k representations in R, the range search radius r, should be at least r 2 d& (where dz is the distance of the k-th nearest neighbour from Me). We use Proposition 2 (which provides an estimate of how far the centroid may shift) to set the radius of the range search query as shown below:
r da + D0 log(2/0)/L.
(4)
where a is a hyperparameter. We set the confidence 8 O(1t).. The size of the reservoir R proportional to the radius r, more samples would be selected with higher r. Depending the reservoir budget Cmax: the radius can be tuned using the parameter, a.
Therefore, re-initializing the reservoir requires the following queries to the cover tree: (a) k-nearest neighbour query to estimate d, (required in computing r in Eqn. 4) and (b) range search query with the radius r. These queries are executed for the same point He and their sequential execution involves quite a bit of redundant. computation. A naive way to reduce this computation is through memorization. Instead, we present an elegant algorithm, reservoir search, to retrieve the reservoir elements given threshold À and summary budget. k in Algorithm 2. This algorithm can retrieve the reservoir in single tree traversal in O(logn).
Reservoir Scarch. In Algorithm 2, we use modified version of the nearest ncighbour search algorithm in SG Trees to populate the reservoir R whenever the distance lo a node is within the range search radius (Line 13). This algorithm does not miss out on any potential reservoir candidates because at any time the d; estimate is more than the exact distance to the k-th neighbour. We perform a filtering stop at the end remove points outside the actual range search radius (Line 21). We also use the range radius to ignore nodes that do not have any children within the search radius (Tine 15). We use the reservoir search method to
5

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm CoverSumm Algorithm
Algorithm 2 Cover Tree Reservoir Search
1: function CoverSumm(Sentence 24)
1: function ReservoirSeeach
μe, Threshold
2: Hyperparameters and Cmax-
X, Summary Budget k):
3: X = X; U 2t
2: Candidate NN List M = {7, Reservoir R = {
4: Pr = [[X]] // updated in ((1)
3: Queue Q7 = (oot))
// insert 24 in the cover tree
while Q not empty do
insert(x;)
q- -Qppop()
// drift of μr from the last query Plast
1/ N..: max distance of any neighbour from pag. At start M.max oc.
A 1ipee Mlast
if A Z X/2 V [R] 2 Cmax then
7:
if d(p..g) q) S N.mmx then
10:
8 = (1/()) // set confidence
8:
Insert (g, d(j,, q)) into Sorted List W if N sizee( > then N N.pop() dç N.max // update dg end if
11:
// compute threshold acc. to Equ. 4
9:
12:
X = /2a log(//)))
10:
13:
// reinitialize reservoir from cover tree
11:
14:
R R.seervoirSerrch A)
12:
r dx + // set search radius
15:
compute the radius of R
13:
if d(ue, q) S then R = Ug // don't explore nodes outside search range if d(u, q) - q.max > r then continue for each child of do if d(w,, c) c.max < then Q = Que end for end while
16:
max{d( g)(g E R}
14:
17:
Mast = Pt // update Plast
15:
18:
else
16:
19:
// add xy to R it within radius r if || xell S r then
17:
20:
24
18:
21:
end if
19:
22: // form summary using kNN search in R
20:
// filter out points outside of range
23:
S. -nn (R.
21:
R = (r R)d(p,,)) S A.max + X}
24: return S
22: return R
25: end function
23: end function
efficiently update the reservoir, R, during incremental summarization in Algorithm 1. Next, we describe the outline of our incremental summarization algorithm, CoverSumm.
CoverSumm Algorithm. In Algorithm 1, every time step 4, update the current centroid μt (Line 4) and insert 2, into the cover tree ct (Line 6). We also compute the drift A, which measures how much Pa has shifted from Plat (Line 8), when the last time reservoir search was performed. If the drift A was more than the threshold X/2 or the reservoir is at capacity, it implies that the current reservoir R does not contain all the k-nearest neighbours of 14 (proof in Proposition 4). In this case, we reinitialize the reservoir by executing reservoir search query on the cover tree (Line 14). If is within the threshold, we update the R with current point 2, if needed (Line 20). Finally, we compute the summary S, by performing k-ncarest neighbour search in the reservoir. The review text corresponding the k-nearest neighbours is the output extractive summary. An illustration of the overall summarization algorithm is shown in Figure 1.
We can improve the efficiency of CoverSumm even further, by delaying the cover tree insertions (Line 6) to only when the drift exceeds the threshold (Line 9) as the cover tree is not utilized in the other computation flow. CoverSumm can also facilitate the deletion reviews cases where certain reviews need to be deleted due to spai or offensive content (more details Appendix D). In the following section, we present several theoretical properties of CoverSumm.
3.1 Theoretical Analysis
In this section, we analyze properties of the efficiency and accuracy of CoverSumm, including its ability to produce the correct nearest neighbors for CentroidRank, the number of reservoir search querics required, the size of the reservoir used, and the rate of change of search queries.
Proposition 3 (Correctness of Reservoir Search). If ct is a SG Tree, then ReservoirSearchl X, k) returns all the neighbours of μ within dislance of (de + >), where dy is the distance of p. to its k-th nenrest neighbour.
6

---

Published in Transactions on Machine Learning Research (03/2024)
A12
Af2 dg 2.2
P++1
d2
Muss
d2
Haast
d2
Musz
P2-2
An illustration of CoverSumn's operation over three consecutive time steps. Red circles represent centroids at different times, green circles @ indicate current nearest neighbors in reservoir R, and blue circles denote representations outside R. The figure displays the last query Plast with radius (dh + A). In the first. two cases, the current centroid is within distance À of Mlatt and the summary can be retrieved from the reservoir. The rightmost figure shows boundary case where representation is just outside the reservoir's boundary and summary compulation requires querying the cover tree.
Figure 2:
Proof. First, we note that ..max = oo at the beginning and de (Line 10) is always more than or equal to the exact distance to the k-th NN during the algorithm. This means that Line 17 cannot throw away any grandparent of a ncarest neighbour within distance r = dę + X. Similarly, Line 13 cannot ignore a nearest neighbour within distance r. Since, the reservoir R now contains all the possible NN candidates, Line 21 returns the set of exact nearest neighbours within distance of query p.
Proposition 4 (Exact nearest neighbours). The k-nearest neighbours returned by Algorithm S, are the exact k-nearest neighbours of μt, the meon at every time step t, i.e., S, = knn(X.
Proof. We first note that R is initialized using reservoir search with radius r = d2 + X, where de is the distance of μr to its k-th neighbour. Therefore, for any radius r 2 dx, the reservoir size is always [ 2 k.
Next, we consider the case when the updated controid 14 is within distance || 1 Mlst l| < A/2. In this case, the distance from 14 of any representation not in the reservoir (blue circles @ in Figure (left & center)) is at least d(z, pe) > dmin = dy + A/2, Vz X2 \ R. Now, note that all points in Stest R, as the R. has not been updated after that (also [Satt = k)). Next, we can show that:
Vo E must, dx, pe) S d(x,, (last) + d(jsts d(sse)Masst)
(5)
< <d + A/2 dmin
This shows that the reservoir has at least l points within dman of pt. Therefore, performing knn within R is exact. When the updated mean be drifts more A 2 X/2 (shown in Figure 2 (right)), we perform reservoir search query on the entire cover tree which is also exact.
J
Now that we know that CoverSumm generates the exact nearest neighbours at all time steps. We focus on estimating the number of reservoir search queries (Line 14 in Algorithm 1) required to achieve it in the following proposition (proof in Appendix A.5).
Proposition (Number of reservoir search queries). Assurring incoming points x, E b/bb/2b// the number of reservoir search queries on the cover tree ezecuted The = Oollon), where n is the total number of points (e.g., review sentences) and D is the dimensionality of the data.
We observe that the reservoir search query count grows with the logarithm of the total number of representa- tions n, unlike baseline approaches that execute nearest neighbour queries at every step. Although the overall complexity of our am is O(n lo) since we perform insertions (Ollgg complexity) at each step, the constants involved for nearest neighbour and range search queries on cover trees are significantly larger. As a result, limiting the number of nearest neighbour queries lcads to substantial speed improvements in practico.
Next, we investigate the storage cost involved in maintaining the reservoir R (detailed proof in Appendix A.6).
7

---

Published in Transactions on Machine Learning Research (03/2024)
Proposition 6 (Maximum reservoir size). For points arriving from metric space (X, d), the upper bound of the reservoir size (RR) at large time sleps (1 > 0) is O(k).
The above result shows that the storage cost of the reservoir large time sleps is relatively low and does not scale with the number of points or dimensions of the data. We provide additional theoretical results about the interval between consccutive nearest neighbour cover queries in Appendix A.7.
4 Evaluation
In this section, we describe the datasct and bascline approaches used in our experiments.
Datasets. We evaluate CoverSumm on both synthetic and real-world datasets. For synthetic data, we experiment with two different setups: (a) we sample representations x from a uniform distribution, where each representation serves as a proxy text represcntation, and (b) we sample synthetic data from an LDA process (more details in Appendix C) to mimic data from the textual domain. We use 10K vectors of TR. 100 for all experiments using synthetic data. We also perform experiments on two real-world datasets: (a) SPACE dataset (Angelidis et al., 2021) has 3K hotel reviews per entity with a total of 2 50K review sentences. We use sentence representations, x E R8992 from the state-of-the-art extractive summarization system SemAE (Chowdhury et al., 2022) on SPACE. (b) Amazon US reviews (He & McAuley, 2016) have product reviews along with their temporal order. We only consider products with more than 1000 reviews in this setup. To simulate an incremental setup, we present an algorithum with one review sentence at a time and evaluate its performance by reporting the computation time and quality of the generated summaries.
Basclines. We compare the efficiency gains of CoverSumm with the following centroid- basclines:
Brute force: computes the ANN from the updated mean Hr at every step.
Naive CT: performs nearest neighbour query on the cover tree at each step.
Naive HNSW: performs NN query on an HNSW (Malkov & Yashunin, 2018a) index at each step.
Naive FAISS: performs NN query on a FAISS (Johnson et al., 2019) index al each step.
CoverSumm trange: uses a modification of the proposed algorithm (Algorithm 1), where separate knn and range search query is exccuted on the cover tree instcad of the reservoir scarch.
CoverSumm (reservoir): implements the proposed online summarization approach in Algorithm 1.
CoverSumm (lazy reservoir): modifies the CoverSumm's 's summarization routine by delaying the insertions into the cover tree only when required (Line 9 is satisfied). This is the most efficient version of our proposed algorithm, and we will often refer to it as simply CoverSumm.
The above baselines can produce the exact nearest neighbours every time step. We also compare CoverSumm with some naive variants that approximate the nearest neighbors to assess the trade-offs between nearest. neighbor accuracy and runtime. The variants are listed below:
CoverSumm (random): randomly decides whether an incoming point should be included in the reservoir R. CoverSumm (decay A): uses an exponential decay term as the threshold (independent of the current points) to decide whether a new point should be part of the reservoir. Specifically, we change Line 6 of the CoverSumm algorithm to A s C1 exp-"x"" =eaT" where C1, C2 are hyperparameters.
We also compare the quality of CoverSumn's summarics with different extractive summarization algorithms: SunBasic (Vanderwende et. al., 2007), LexRank (Erkan & Radev, 2004), TextRank (Mihalcea & Tarau, 2004), Centroid-OPP (Ghalandari, 2017), and Latent Semantic Analysis (LSA) (Ozsoy et al., 2011). Centroid OPT is the most similar to CentroidRank. CentroidOPT constructs the summary by greedily selecting sentences that maximize the similarity of the constructed summary with the centroid. While CentroidRank measures the similarity between a sentence and the centroid, CentroidOPT does so for the summary. In our experiments, we use the SG Tree implementation available in graphgrove library (more details Appendix E.1). We set hyperparameters by using grid search on a held-out development set for each dataset.
4.1 Main Results
We evaluate CoverSumm on several opinion summarization datasets and perform additional experiments analyze its performance.
8

---

Published in Transactions on Machine Learning Research (03/2024)
Uniform
LDA
SPACE
AMAZON
Algorithm
Time (s)
Ace. (%)
Time (8)
Acc. (%)
Time (8)
Acc. (%)
Time (s)
Acc. (%)
Brute force
28.23
100.0
26.09
100.0
7.78
100.0
49.82
100.0
Naive CT
26.37
100.0
25.21
100.0
3.23
100.0
17.53
99.6
Exact
Naive Faiss
2.22
100.0
2.25
100.0
1.30
100.0
4.81
99.6
CoverSumm (kun-Frange)
1.08
100.0
1.34
100.0
1.43
100.0
2.30
99.7
Cover (reservoir)
0.91
100.0
0.96
100.0
1.25
100.0
1.47
99.7
CoverSumm (lazy reservoir)
0.87
100.0
0.92
100.0
1.14
100.0
1.36
99.7
Naive INNSW
5.35
4.9
4.44
26.6
3.25
72.3
7.07
81.2
Appo.
CoverSumm (random)
0.53
0.2
0.59
0.2
1.02
2.3
0.62
0.5
CoverSumm (decay X)
1.28
1.0
0.70
8.9
1.35
10.7
0.53
2.3
Table 1: Total incremental summarization runtime (per entity) and nearest neighbour (NN) accuracy for different centroid-based algorithms for representations from synthetic (Uniform & LDA) and opinion review (SPACE& & AMAZON) datasets. We observe that CoverSumm outperforms baseline approaches, showcasing up to 36x speedup. We also observe that reservoir search achieves up to 28% speedup compared to sequentially performing knn and range queries on the tree. Among the algorithms that retrieve ezact NNs, we highlight the best time achieved in bold.
In Table 1, we compare the computation efficiency of CoverSumm with other centroid-baser baseline methods in the incremental setting. Since centroid- based summarization relies on ANN retrieval, we evaluate the accuracy that the generated nearest neighbours exactly match the actual nearest neighbours. We report the average time required to complete the incremental summarization process per entity across 5 runs. For the synthelic datasel, to be incorrect if either any of the elements or their order does not match. We retrieve k = 20 nearest neighbours in our experiments. This serves as a proxy for the quality of the gencrated summary. We observe that CoverSumm out performs baseline approaches by a significant margin, showcasing up to 36x speed gains while generating exact nearest neighbours. Moreover, we observe that CoverSumm (lazy reservoir) achieves the best time performance. This is expected as the implementation of performing insertions in batch can be parallelized using SG Trees. In Figure 3, show an illustration of how CoverSumm's runtime fares with baselines during the online summarization process on synthetic dataset. In Table 1, we also observe that the speed gains on SPACE dataset are lower than others. This is due to the higher data dimension (I25192), as the confidence bound in Proposition weakens with an increase in data dimension D, leading to more ANN queries. We analyze this phenomenon further in Section 4.2.
consider all 10K presentations belonging to a single entity. We consider an oulput
Speedup. We compare CoverSumm's runtime with other paradigms of extractive summarization in Table 4 on samples from the SPACE and AMAZON datasets. These algorithms are quite expensive and some of them ran out of time for synthetic benchmarks (with >10K samples) reported in Table 1. A few algorithms like TextRank require access to text inputs and cannot be applicd to synthetic data. We observe that our proposed algorithm, CoverSumm, obtains significantly better runtime compared to baseline approaches. This is because centroid-based algorithms are generally much faster, brute force algorithm has a time complexity O(n?) with knn search being (nn) per step. While the other extractive summarization paradigms utilize either the PageRank algorithm (O(n²) complexity) or aigen-dccomposition (O(n") complexity). Note that although we refer to ext exctivvvve summarization systems by their approach (e-g., centroid-based) these algorithms are being used in state-of-the systems, like SemAE (Chowdhury et al., 2022) (e.g., Brute Force in Table 1 on SPACE is identical to SemAE).
Automatic Evaluation of Summary Quality. In this experiment, we probe the quality of the generated online summarics. Since we do not have access to buman-written summarics at every time step, we construct silver extractive summaries by greedily selecting sentences (seen till time step t) with high ROUGE overlap human-written with final human written ones. We perform this experiment on the SPACE (Angelidis et al., 2021) dataset and report the ROUGE overlap with the silver summaries. We measure different ROUGE scores after every 20 steps and report the average score.
1 Exact methods on Amazon US reviews achieve slightly less than 100% due to numerical stability issues in the cover tree implementation edge cases, which can handle up to 32 bit numbers.
9

---

Published in Transactions on Machine Learning Research (03/2024)
120
Centroid Rank
Algorithm
R1
R2
RL
Time (s)
Compute Time (s)
Naive CT
90
CoverSumm
LSA
25.01
1.66
15.34
825.57
CentroidOPT
27.74
4.82
16.39
263.84
60-
TextRank
30.84
5.27
17.40
1147.89
LexRank
30.04
5.70
17.59
160.63
SumBasic
31.55
5.00
15.66
287.80
30
Naive HNSW
43.53
14.61
26.17
3.25
Naive Faiss
43.48
14.51
25.99
1.30
10K 15k
20K
CoverSumm (random)
39.19
11.64
22.92
1.02
Number of reviews
CoverSumm (decay
41.03
12.18
24.03
1.35
Figure 3: Time required by CoverSumm com- pared to baseline algorithms with an increas- ing number of reviews. We observe that the processing time of brute-force CentroidRank and Naive CT gradually increases, while the processing time of CoverSumm only slightly increases during sunmarization.
CoverSumm
12.46
14.06
25.15
1.14
Figure 4: Average ROUGE scores obtained by different incre- mental summarization systems on SPACE dataset. RI. R2, RL denote the average ROUGE-1, ROUGE-2, and ROUGE-L scores respectively. We also report the time taken for incremen- tal summarization per entity by different algorithms.
In Table 4, we observe that CoverSumm achieves the best tradeoff between summarization performance (in terms of ROUGE scores) and runtime in the incremental sctting. Here, we would like to emphasize that the improving the efficiency of centroid-based summarization systems,
focus behind designing CoverSumm not enhancing summary quality. Apart from ROUGE scores, we further evaluate the quality of the generated summaries by their ability to track content in user reviews and human evaluation. We report these experiments in the following section.
4.2 Analysis
In this section, we analyze the functioning of CoverSumm through various experiments. First, we gange the quality of CoverSumm's summaries using Amazon US reviews (He McAuley, 2016), which contains real-world review sets. Since gold summarics are infeasible for such large review sets, we evaluate if the summaries mimic proxy measures like sentiment polarity and user ratings of the aggregate reviews.
User ratings. In Figure 5(a), report the overall user rating (in green) and the summary rating (in blue), where the reviews arrive in a temporal order provided by the dataset. We observe that the summary ratings mimic the overall trends in the user ratings. The absolute difference between user and summary ratings was 0.42. In Figure 5(b) & (c), we simulate a drift in the user reviews by ordering them according to ratings from low to high or vice-versa. We observe that CoverSumm is able to tackle such scenarios where the sumnaary ratings still track the aggregate ratings.
Sentiment Polarity. In this experiment, we probe the sentiment polarity of the generated summarics and verify if they are consistent with the sentiment of the aggregate reviews. We use the VADER (Hutto & Gilbert, 2014) to extract sentiment polarity. We assign summaries a sentiment polarity score based on the average polarity score of their individual sentences. In Figure 6(a) & (b), we report the summary polarity (in green), the average review polarity (in blue), and human-written summary's polarity (in black). We report the scores for two distinct entities the SPACE dataset. We observe that the generated summaries' sentiment. polarity generally follows trends in the overall review polarity while achieving polarity score close to the human-written summary with an increase in reviews. In general, the summary's polarity doesn't 't exactly track the aggregate review polarity many reviews are neutral, and selecting them would result in less informative summarics (more details in Appendix E.3).
Aspect discovery. In this experiment, we assess CoverSumm can capture the underlying aspects in user reviews. To investigate this, we progressively fed the system reviews from each aspect (e.g., hotel reviews about food first. followed by service, and so on). In Figure 6(c), we compute the number of unique aspects in the summarics and reviews different time steps. We found that summaries successfully captured new aspects as they introduced in the review stream. Additionally, calculated the average absolute
10

---

Published in Transactions on Machine Learning Research (03/2024)
5.0
4.0
5.00
4.5
User Ratings
3.0
4.50
4.0
4.25
3.5
2.0
4.00
Reviews
3.0
1.5
3.75
CoverSumm
1.0
3.50
250
500
750
1000
1250
250
500
750
1000
1250
250
500
750
1000
1250
Time step (t)
Time step (0)
Time step (0)
Figure Evolution of user ratings CoverSumm's 's summary and user reviews during summarization in an incremental setting. The goal of this experiment to determine if the user ratings can be accurately reflected in the incremental summaries from CoverSumm. We report the rosults in three settings when reviews arrive in their: (a) original temporal order; (b) ascending order of their ratings; (c) descending order of their user ratings. We observe that CoverSumm's ' summary can track drifts in the ratings.
Sentiment Polarity
Sentiment Polarity
Reviews
Random
0.7
0.7
CoverSumm
Aspects Count
CoverSumm
0.6
4
0.5
0.4
0.4
2
0.3
200
400
600
800
200
400
600
800
200
400
600
800
Time step
Time (t)
Time step
Figure 6: (a) & (b) Evolution of sentiment polarity in CoverSumm's summaries an incremental setting (for entities in SPACE dataset), and (c) the number of unique aspects found in the CoverSumm's ' summary and aggregate reviews. Random denotes the CoverSumm (random) baseline. These experiments show that the generated summaries can track finer aspects of the user reviews like sentiment polarity and aspects.
difference between the number of unique aspects in the reviews and summarics to be 0.32. This demonstrates that CoverSumm effectively captures the underlying semantics and selects relevant aspects from reviews.
Number of reservoir search queries (nts). In this experiment, we probe the number of reservoir search queries (the most expensive step in Algorithm executed by CoverSumm. In Figure (a), we visualize the rs queries using data sampled from a uniform distribution and observe that CoverSumm performs small number of queries (e.g., less than 150 queries when the number of points is 10K). We also observe that with an increasing number of points, the gap between subsequent reservoir search queries increases. This is expected as the nearest neighbours of the centroid change less frequently. We repeat the same experiment with different data dimensions and observe an increase reservoir search queries with increasing data dimension, D. This is expected the confidence for the bound in Proposition 2 is (1 8)2D decreases for higher data dimension, D. Therefore, nearest neighbour candidates can be outside the rescrvoir more frequently.
Reservoir size ((R.)). In this experiment, we investigate the size of R during summarization. We perform synthetic experiment where points are randomly sampled from uniform distribution. In Figure 7(b), we observe that the reservoir size at any time step is siguificantly small (< 100) compared to the number of points (~10K). We also experiment by varying the summary budget, k, and observe a nearly linear increase in reservoir size as predicted by Proposition 5.
Data distribution ablations. In this experiment, we investigate CoverSumm's performance (time) when the imput samples arise from multi-moda distribution. Specifically, we sample Σm a,V from multi-dimensionall gaussian distributions, where = 1/m, i il and m is the number of modes. In Figure 7(c), we observe that the time required by CoverSumm gradually increases with the number of modes in the input distribution. This behavior is expected as the number of representations near the centroid may change frequently as the number of modes increases.
Human Evaluation. To assess the quality of the summaries generated by CoverSumm, we perform human evaluation of the generated summaries from SPACE and Amazon US reviews dataset. We compare CoverSumm
11

---

Published in Transactions on Machine Learning Research (03/2024)
150
250
2
3.0
mode
120
200
2.5
5 modes
k-80
2.0
10 modes
90
Computo Time
1.5
60
50
100
1.0
D 100
30
D = 150
0.5
10
10a
12
10f
2K
4K
10K
0.0
2.5K
5K
7.5K
10K
Time step (0)
Time step (4)
Time step (4)
Figure 7: Plots showcasing (a) the cumulative number of reservoir search queries (Nys), (b) the variation in reservoir size [R], and (c) compute time when points are sampled from multi-modal distribution.
with its two variants: CoverSumm (random) and CoverSumm (decay A). We perform human evaluation experiments on Amazon MTurk. Since evaluating the entire set of summaries is expensive, we selected consecutive summary pairs, which had at least one change in them. Specifically, given a summary pair, we ask the annotator judge whether the change was: (a) redundant: if the information was already provided in the previous summary, and (b) informative: if the new selected review sentence is informative or "summary worthy" (e.g., sentence like 'The boots wore off after month' is summary worthy while sentence like 'I do not like them' is not). We provide more details about the human evaluation setup in Appendix E.2.
In Table 2, we report the percentage of summary pairs marked as redun- dant or informative. On A AMAZON, we observe that CoverSumm gener- ates the least redundant summarics (only 8.8% are marked as redundant) while making the most informative changes (around 65% of the time). On SPACE, we observe that different systems achieve similar performance with CoverSumm achicving the best results informativeness. To put these results in perspoctive, we need consider some of the key differences between AMAZON and SPACE datasets. SPACE reviews have similar structure with sentences like "The room was great", "The staff was helpful", etc. On the other hand, AMAZON US Reviews have much more diverse set of reviews c.g., "Overall I'm very pleased with the purchase", "When I got it was surprised how soft the lamb skin is, very nice". We see these properties manifest. in the human evaluation results. In the SPACE dataset, we hypothesize that when reviews are altered with similar positive information, this is generally seen as informative, yielding high informative scores. CoverSumm (random) algorithm may be less sensitive to redundancy scores in this setup as it randomly chooses instances to be in the reservoir thereby encouraging diversity in the final summary. Overall, this experiment illustrates the need for evaluation on diverse set of reviews to effectively gauge the system's performance.
AMAZON
SPACE
Algorithm
Redund.
Info. t Redund. +
Info. t
CoverSumm (random)
28.2%
54.0%
21.6%
78.2%
CoverSumm (decay A)
12.3%
63.4%
25.8%
79.9%
CoverSumm
8.8%
65.4%
24.1%
80.7%
Table 2: Human evaluation results evaluating the redundancy and infor-
mativeness of generated summaries from CoverSumm and its variants.
5 Conclusion
In this paper, we proposed CoverSumm, an efficient algorithm to perform sentroid-based extractive summariza- tion an incremental setup. CoverSumm leverages cover trees to perform nearest neighbour search efficiently, thereby obtaining up to 36x speed improvement over naive baselines. We perform extensive theoretical and empirical analysis to show that CoverSumm generates high-quality opinion summaries that accurately track the semantics in the review set. Detailed analysis shows that CoverSumm's performance is dependent on the underlying data distribution, and its efficiency can suffer in adversarial scenarios. Most works use empirical evaluations on specific datasets to choose a summarization technique. In this work, we focus on centrality- based measures for extractive summarization. Nevertheless, determining the optimal summarization paradigm for different domains remains an open question. Future work could explore the use of efficient data structures like CoverSumm or improved confidence intervals (Wandby-Shin Smith & Ramdas, 2024) further improve efficiency aicienney/ccuuragg /accuracy trade-offs across broad class of summarization methods.
12

---

Published in Transactions on Machine Learning Research (03/2024)
6 Acknowledgements
The authors are thankful to Michael Boratko, Anneliese Brei, Rahul Kidambi, Haoyuan Li, and Anvesh Rao Vijjini for helpful leedback and discussions. Somnath Basu Roy Chowdhury and Snigdha Chaturvedi were partly supported by the National Science Foundation under award DRL-2112635.
References
James Allan, Rahul Gupta, and Vikas Khandelwal. Temporal summaries of new topics. In Proceedings of the 24th annuol international ACM SIGIR conference Research and development in information retrieval, pp. 10-18, 2001.
Stefanos Angelidis, Reinald Kim Amplayo, Yoshihiko Suhara, Xiaolan Wang, and Mirella Lapata. Extractive opinion summarization in quantized transformer spaces. Transactions of the Association for Computational Linguistics, 9:277-293 2021.
Vivek Bagaria, Govinda Kamath, Vasilis Ntranos, Martin Zhang, and David Tse. Medoids in almost-linear time via multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pp- 500-509. PMLR, 2018.
Tavor Baharav and David Tse. Ultra fast medoid identification via correlated sequential halving, Advances in Neural Information Processing Systems, 32, 2019.
Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, (8(9)5509 517, 1975.
Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd international conference on Machine learning, pp. 97 104, 2006.
Adithya Bhaskar, Alex Fabbri, and Greg Durrett. Prompted opinion summarization with gpt-3.5. In Findings of the Association for Computational Linguistics: ACL 2023, pp. 9282 22-99300, 2023.
David M Blei, Andrew Y Ng, and Michael I Jordan. Latent dirichlet allocation. Journal of machine Learning research, 3(Ja 1022, 2003.
Sébasticn Bubeck, Varun Chandrasckaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et. al. Sparks of artificial general intelligence: Early experiments with gpt-4, arXiv preprint 10X1:22303.2711, 2023.
Chi Cheang, Hou Chan, Derek Wong. Xuebo Liu, Zhaocong Li, Yanming Sun, Shudong Liu, and Lidia Chao. Can LMs generalize to future data? An Empirical Analysis Text Summarization. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Lan- guage Processing, pp. 16205 16217, Singapore, December 2023. Association for Computational Linguistics. org//023 emnlp-main, 1000.
doi: 10.18653/v1 htt.11222222m1l///1 mmwlp-main.nnmmm.mmmmmmmmmmmmamm 1007. URL
Xiuying Chen, Mingzhe Li, Shen Gao, Zhangming Chan, Dongyan Zhao, Xin Gao, Xiangliang Zhang, and Rui Yan. Follow the timeline! generating an abstractive and extractive timeline summary in chronological order. ACM Transactions Information Systems, 41 (1)::31-3 2023.
Somnath Basu Roy Chowdhury, Chao Zhao, and Snigdha Chaturvedi. Unsupervised extractive opinion summarization using sparse coding, In Proceedings of the 60th Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers), pp. 1209-1225, 2022.
Somnath Basu Roy Chowdhury, Nicholas Monath, Avinava Dubey, Amr Ahmed, and Snigdha Chaturvedi. Unsupervised opinion summarization using approximate goodesics. In Findings of the Empirical Methods in Natural Language Processing: EMNLP 2023, Singapore, December 2023. Association for Computational Linguistics.
13

---

Published in Transactions on Machine Learning Research (03/2024)
Eric Chu and Peter Liu. Meansum: a neural model for unsupervised multi-document abstractive summarization. In International Conference on Machine Learning, pp.
PMLR, 2019.
Yury Elkin and Vitaliy Kurlin. Counterexamples expose gaps in the proof of time complexity for cover trees introduced in 2006. In 2022 Topological Data Analysis and Visualization, (TopoIn Vis), pp- 9-17. TEFE, 2022.
Yury Elkin and Vitaliy Kurlin. A new near-lincar time algorithm for k-nearest neighbor search using a compressed cover tree. In International Conference on Machine Learning, pp. 9267 9311. PMLR, 2023.
Günes Erkan and Dragomir R Radev. Lexrank: Graph-based lexical contrality as salience in text summariza- tion. Journal of artificial indelligence research, 22:457 479, 2004.
Tao Ge, Lei Cui, Baobao Chang, Sujian Li, Ming Zhou, and Zhifang Sui. News stream summarization using burst information networks. In Proceedingg of the 2016 Conference on Empirical Melhods in Natural Language Processing, pp. 784-794, 2016.
Demian Cholipour Ghalandari. Revisiting the centroid-based method: A strong baseline for multi-document summarization. EMNLP 2017, pp. 85, 2017.
Demian Gholipour Ghalandari and Georgiana Tfrim. Examining the state-of-the-art in news timeline summarization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 1322-1334, 2020.
Demian Gholipour Ghalandari. Revisiting the centroid-based method: A strong baseline for multi-document summarization. In Proceedings of the Workshop on New Frontiers in Summarization, pp. 85-90, Copenhagen, Denmark, September 2017. Association for Computational Linguisties. doi: 10.18653/v v1 WW17-411. URL https://aclantthol. wrt..///5...//11-4111111
Nianlong Gu, Elliott Ash, and Richard Hahnloser. MemSum: Extractive summarization of long documents using multi-step episodic markov decision processes. In Proceedings of the 60th Annual Meeting of the Associalion for Compulational Linguislics (Volume 1: Long Papers), pp. 6507 6522, 2022.
Antonin Guttman. R-trees: A dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD international conference Management of data, pp. 47-37, 1984.
Ruining He and Julian McAuley. Ups and Downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In proceedings of the 25th international conference on world wide web, pp. 507 517, 2016.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13 30, 1963.
Tom Hosking, Hao Tang, and Mirella Lapata. Attributable and scalable opinion summarization, In Proceedings of the 61st Annual Meeting of the Association for Compulational Linguistics (Volume 1: Long Papers), pp- 2023.
Minqing Hu and Bing Liu. Mining and summarizing customer reviews. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 168-177, 2004.
Clayton Hutto and Eric Gilbert. Vader: A parsimonious mule-based model for sentiment analysis of social media text. In Proceedings of the international AAAI conference web and social medio, volume 8, pp. 216-225, 2014.
Masaru Isonuma, Junichiro Mori, Danushka Bollegala, and Ichiro Sakata. Unsupervised abstractive opinion summarization by generating sentences with tree-structured topic guidance. Transactions of the Association for Computational Linguislics, 9:945-990 961, 2021.
Ziwei Ji, Naycon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Yejin Bang, Andrea Madotto, and Pascale Fung. Survey of hallucination in natural language generation. ACM Computing Surveys, 2022.
14

---

Published in Transactions on Machine Learning Research (03/2024)
Han Jiang, Rui Wang, Zhihua Wei, Yu Li, and Xinpeng Wang. Large-scale and multi-perspeetiin opinion summarization with diverse review subsets. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 5641 5656, Singapore, December 2023. Association for Computational Linguistics. doi: 10.18653/v / htt.://.............m... crntings-emmll.3..5 URL https::t////ttt hacpt///oll.a wwwp:/o3..r/........ andings-emnll.
Johney John and S Asharaf. Ineremental multi-document summarization: An incremental clustering based approach. In 2014 International Conference on Data Science & Engineering (ICDSE), pp. 136-139. IEFE, 2014.
Jeff Johnson, Matthijs Douze, and Hervé Jégon. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 7(3):535 547, 2019.
Hyun Duk Kim, Kavita Ganesan, Parikshit Sondhi, and ChengXiang Zhai. Comprehensive review of opinion summarization. 2011.
Reinald Kim Amplayo, Arthur Brazinskas, Yoshi Suhara, Xiaolan Wang, and Bing Liu. Beyond opinion mining: Summarizing opinions of customer reviews. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 3447 1447-3450, 2022.
Md Tahmid Rahman Laskar, Yong Fu, Cheng Chen, and Shashi Bhushan TN. Building real-world meeting summarization systems using large language models: A practical perspective. In Mingxuan Wang and Imed Zitouni (eds.), Proceediigs of the 2023 Conference on Empirionl Methods in Natural Language Processing: Industry Track, pp. 343 352, Singapore, December 2023. Association for Computational Linguisties. doi: 10.18653/vi wttp12/..emnlpp-.. 1aanllpiduustr.33... URL attps://aclantee
org/2023. emnlp- emnlp-industre industry.. 33.
Haoyuan Li and Snigdha Chaturvedi. Rationale-based opinion summarization. 2024.
Haoyuan Li, Somnath Basu Roy Chowdhury, and Snigdha Chaturvedi. Aspect-aware unsupervised extractive opinion summarization. In Findings of the Association for Computational Linguistics: ACL 2023, pp. 12662 12678, 2023.
Yu Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4):824- 836, 2018a.
Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 2018b.
Ramesh Manuvinakurike, Saurav Sahay, Wenda Chen, and Lama Nachman. Incremental temporal summa- rization in multi-party meetings. In Haizhou Li, Gina-Anne Levow, Zhou Yu, Chitralekha Gupta, Berrak Sisman, Siqi Cai, David Vandyke, Nina Dethlefs, Yan Wu, and Junyi Jessy Li (eds.), Proceedings of the 22nd Annual Meeting of the Special Interest Group on Discourse and Dialogue, pp. 530-541, Singapore and Online, July 2021. Association for Computational Linguistics. doi: 10.18653/v1. 11/2021.sigdiall 1.55. URL attps://aclanthae
org/2021 sigdiallgiiii
Qianren Mao, Shaobo Zhao, Jiarui Li, Xiaolei Gu, Shizhu He, Bo Li, and Jianxin Li. Bipartite graph pre-training for unsupervised extractive summarization with graph convolutional auto-encoders. In Honda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 4929-4941, Singapore, December 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023. htg.://///////.....nniggg-gg/- emnlp.328. findings-emmlp.325. URL http:://aclanthology www.o023........... wwndiiii-nnnninnnn
Joshua Maynez, Shashi Narayan, Bernd Bohnet, and Ryan McDonald. On faithfulness and factuality abstractive summarization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 1906-1919, 2020.
15

---

Published in Transactions on Machine Learning Research (03/2024)
Richard McCreadie, Craig Macdonald, and Iadh Ounis. Incremental update summarization: Adaptive sentence selection based on prevalence and novelty. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, CIKM '14, pp. 2014. Association for Computing Machinery. ISBN 9781450325981. doi: 01144//666182926611111 URL https://doi... org/ 10. 1145/2661222999/1 2661951.
New York, NY, USA,
Walaa Medhat, Ahmed Hassan, and Hoda Korashy. Sentiment analysis algorithms and applications: A survey. Ain Shams engineering journal, 5(4):1093-13) -1188, 2014.
Rada Mihalcea and Paul Tarau. Text Bringing order into text. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, pp. 404-411, Barcelona, Spain, July 2004. Association for Computational Linguistics. URL httpp://aallarthology org/X04-3252.
Ani Nenkova and Amit Bagga. Facilitating email thread access by extractive summary generation. In RANLP, volume 260, pp. 287-296, 2003.
Ani Nenkova and Lucy Vanderwende. The impact of frequency on summarization. Microsoft Research, Redmond, Washington, Tech. Rep. AISR-TR-200 101, 2005.
Kazuya Okamoto, Wei Chen, and Xiang- Kinn Li. Ranking of closeness centrality for large-scale social networks. Lecture Notes in Computer Science, 5059:186-1955 2008.
Makbule Gulein Ozsoy, Ferda Nur Alpaslan, and lyas Cicekli, Text summarization using latent semantic analysis. Journal of Information Science, 37 37(4):405-411 2011.
Bo Pang. Opinion mining and sentiment analysis. Foundations and trends in information retrieval, 2(1-2): 135, 2008
Maxime Peyrard. A simple theoretical model of importance for summarization. In Anna Korhonen, David Traum, and Lluís Mårquez (eds.), Proceedings of the 57th Annual Meeting of the Association for Compulational Linguislics, pp. 1059- 1073, Florence, Italy, July 2019. Association for Computational org/P19-1101.
Linguistics. doi: 11118853//1/I11 1101. URL
Adithya Pratapa, Kevin Small, and Markus Dreyer. Background summarization of event timelines. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.). Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 8111 8136, Singapore, December 2023. Association for Computational Linguistics. doi: 10.1865//v122223 wwwweeennnnnnneeee 505. URL https: httpa/:///aaaaahgggagae .orechooooogooogg////ooo 2023. e.13emmmlp-minnn 505.
Dragomir R Radev, Hongyan Jing, Malgorzata Stys, and Daniel Tam. Centroid-based summarization of multiple documents. Information Processing & Management, 40(6):919 938, 2004.
Gaetano Rossiello, Pierpaolo Basile, and Giovanni Semeraro. Centroid-based text summarization through
compositionality of word embeddings. In Proceedings of the MultiLing 2017 Workshop on Summarization and Summary Evaluation Across Source Types and Genres, pp. 12 12-21, 2017.
Swarnadeep Saha, Shiyue Zhang, Peter Hase, and Mohit Bansal, Summarization programs: Interpretable abstractive summarization with neural modular trees. In The Eleventh International Conference on Learning Representations, 2022.
Hanan Samet. The quadtree and related hierarchical data structures. ACM Computing Surveys (CSUR), 16 (2):187-260, 1984.
Tejpalsingh Siledar, Suman Banerjce, Amey Patil, Sudhanshu Singh, Muthusamy Chelliah, Nikesh Garera, and Pushpak Bhattacharyya. Synthesize, if you do not have: Effective synthetic dataset creation strategies for sele-iupe opinion summarization in E-commerce. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2029, pp. 13480- 134491, Singapore, December 2023. Association for Computational Linguistics. doi: 10.18653/v1 12022 /2t./..nnn.nnss...m. caapggs-mmll..999. 899. URL http:////aaaathogg..ooooo
findings-- inddngg-emnnl..ee 899.
16

---

Published in Transactions on Machine Learning Research (03/2024)
Tiberiu Sosea, Hongli Zhan, Junyi Jessy Li, and Cornelia Caragea. Unsuperviscd extractive summarization of emotion triggers. In Amna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61sl Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9550 9569, Toronto, Canada, July 2023. Association for Compatational Linguistics. doi: 10.18653 w1///222 acl- sondl-oon..3.. 531. URL
org/ longlloog..... 531.
Julius Steen and Katja Markert. Abstractive timeline summarization. In Proceedings of the 2nd Workshop New Frontiers in Summarization, pp. 21 31, 2019.
Luey Vanderwende, Hisami Suzuki, Chris Brockett, and Ani Nenkova. Beyond sumbasic: Task-focused summarization with sentence simplification and lexical expansion. Information Processing 8 Management, 43(6):1606 1618, 2007.
Ian Waudby-Smith and Aaditya Ramdas. Estimating mcans of bounded random variables by betting. Journal of the Royal Statislical Sociely Series B: Stalislical Methodology, 86(1):1 27, 2024.
Rui Yan, Liang Kong, Congrui Huang, Xiaojun Wan, Xiaoming Li, and Yan Zhang. Timeline generation through evolutionary trans-temporal summarization. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pp. 433 443, 2011a.
Rui Yan, Xiaojun Wan, Jahna Otterbacher, Liang Kong, Xiaoming Li, and Yan Zhang. Evolutionary timeline summarization: a balanced optimization framework via iterative substitution. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, pp. 745-754, 2011b.
Susik Yoon, Hou Pong Chan, and Jiawei Han. PDSum: Prototype-driven continuous summarization of evolving multi-document sets stream. In Proceedings of the ACM Web Conference 2023, pp. 1650-1661, 2023.
Manzil Zaheer, Guru Guruganesh, Golan Levin, and Alex. Smola. Terrapattern: A nearest neighbor search service. Preprint, 2019.
Shiyue Zhang, David Wan, and Mohit Bansal, Extractive is not faithful: An investigation of broad unfaithfulness problems in extractive summarization. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 2153-2174 Toronto, Canada, July 2023. Association for Computational Linguistics. doi: (..18633/v1/2000 htl.//22aaclloooog.......a lcl- 120. URL / org/2020 2023.223.... acl- acl-long. 120.
Chao Zhao and Snigdha Chaturvedi. Weakly-supervisedd opinion summarization by leveraging external information. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 9644-9651, 2020.
Ming Zhong, Pengfei Liu, Danqing Wang, Xipeng Qiu, and Xuanjing Huang. Searching for effective neural extractive summarization: What works and what's 's next. In Anna Korhonen, David Traum, and Lluís Mårquez (eds.), Proceedings of the 57th Annual Meeting of the Association for Computational Länguisties, pp. 1049-1058, Florence, Italy, July 2019. Association for Computational Linguistics. doi: org/P19-1100.
10.18653/v 111199111111111111 1100. URL attps://aclann:
Ming Zhong, Pengfei Liu, Yiran Chen, Danqing Wang, Xipeng Qiu, and Xuanjing Huang. Extractive summarization as text matching. In Dan Jurafsky, Joyce Chai, Natalic Schluter, and Joel Tetreault (eds.), Proceedings of the 58th Annual Meeling of the Associalion for Compulational Linguistics, pp. 6197 6208, Online, July 2020. Association for Computational Linguistics. doi: https: https://aclanthology 2020.020..0 acl aallmminn555 552.
URL
17

---

Published in Transactions on Machine Learning Research (03/2024)
A Theoretical Proofs
Contents
A.1 Hoeffding's s Inequality
18
A.2 Proof of Proposition
18
A.3 Proof of Proposition
18
A.4 Proof of Proposition
A.5 Proof of Proposition 5
19
A.6 Proof of Proposition 6
19
A.7 Additional Theoretical Results
20
A.1 Hoeffding's Inequality
Theorem 1 FHocfffing-Azuma incquality (Hoeffding, 1963)). Let F be ii.dd random variables supported on b-b/2, b/2]. Define E[x1] and 1 Ei= Tt. Then, for any 8 (0,1), with probability at least (1 5), it holds that
2 log((/00 (2/
1
P
(6)
2t
A.2 Proof of Proposition
Proof. We proceed by applying the Hoelfding inequality (Theorem 1) to individual dimensions the estimated centroid vector as shown below:
12/6)
Ni (
(0)
+
21
Using triangle inequality, we can bound the Euclidean distance to μe from any point a E R::;
ba log(2/8)
| - æ|| || - x + ell, where e() = =V
2t
|| æ||| ||l||
Db2 log(2/0)
1| - æ|| +
2t
Therefore, for an Euclidean distance metric d(.,)), have obtained the following result:
DD2 log(2/8)
d(pr,x) = =
The above proof can be exlended to any distance metric that follows triangle inequality. The new bound can be written d(pe,)) d(p,)) + [|e]] where
+ 1 log (2/
A.3 Proof of Proposition
Proof. We estimate the distance between subsequent centroids using the triangle inequality of Euclidean distance and use the results from Proposition as follows:
18

---

Published in Transactions on Machine Learning Research (03/2024)
((n,,4t) & d(pr p)) d(peti:p) p.)
DDa 1og(2/5)
Dba 1og(2/6)
I d(p, pi) +
+ d(H,, + V
2t
2( + i)
DD? log(2//)
22
2t
2D12 1og(2/0)/L.
A.4 Proof of Proposition
Proof. To prove this proposition, we first note that R initialized using reservoir search with radius ds + X, where d3 the distance of μr its k-th neighbour. Therefore, for any radius r 2 dg, the reservoir size is always [R| 2 k.
Next, consider the case when the updated centroid 2 is within distance || Minst || < X/2. In this case, the distance from μr of any representation not in the reservoir (blue circles in Figure 2 (left & center)) is at least d(x,, (ba) > dmin = dg + X/2, Va E X, \ R. Now, note that all points in S E R, as the R. has not been updated after that (also [Statt = kt.. Next, we can show that:
Voz Sjast d(z, Hi) d(z, plast) + d(pte plast)
< <dy + X/2 = dmii
This shows that the reservoir has at least à points within dmin of pe- Therefore, performing knn within R is exact. When the updated mean Pe drifts more A 2 X/2 (shown in Figure 2 (right)), perform reservoir search query on the entire cover tree which is also exact.
A.5 Proof of Proposition 5
Proof. First, we note that reservoir search queries on the cover tree are executed when the bound obtained in Proposition 2 is violated. This happens with probability pt = - (1 5)2D at each time step I. Therefore, the expected value n, can obtained as follows:
Thp Σ Pt
Σ 1- 11-11-87
Σ 2DS D(2D 1)82
2D +
D(2D (2D 2) +...
dt
3+3
2D +
D(2D (2D 2)
+ +...
313
D(2D (2D 2)
2D log n +
6n
= O(D n).
We set 8 ((1/t) as used in our algorithm and assume that n D in the above proof.
A.6 Proof of Proposition
Proof. For metric space (X, d), we assume the doubling constant to be c. The size of the reservoir [R] is given by the maximum number of elements in the ball B(Jn, de e)), where pr, is the last query for range
19

---

Published in Transactions on Machine Learning Research (03/2024)
search in the cover tree, and d c) is the radius used for the same. We know that [B d3)) = k. Using this, we proceed to formulate the bound as follows:
[R| < Bun, du (1 +))]
<c (1 (Baa, de)l
(8)
(log (1+ aaD (2g(
From Equation 8, we observe that we can control the reservoir size using the hyperparameter a. Next, we show that the reservoir size bound is only dependent data dimension D, mumber of nearest neighbour
k and aspect ratio A of X. For large > 0, we have the limit: lime
log(2() - Plugging this result
2
Equation 8, we get the following
[R| S [ ck,
(9)
where for large 0,
small constant.
Discussion. Therefore, later time steps, we observe that [R| is directly proportional to the number of nearest neighbours, k. For metric space (X, d), the doubling constant (c) can be bounded as c 2 A], where A is the aspect ratio of the space. The aspect ratio A is defined as the ratio of the largest to the smallest interpoint distance in that space.
A.7 Additional Theoretical Results
Proposition 7 (Interval between reservoir search queries). The number of steps (interval) between two consecutive reservoir search queries (m) grows linearly with the time step, i.e,, m = O()..
Proof. The evolving centroid computed in O(1) time as shown below:
(1
(1-11)
1
Pt+1
1
Me + 1 1+1 Xe+1-
In similar manner, we can compute f4+2 as follows:
1
Pe+2
1. 1 2
Me+1
1 2
X1+2
(1
1
[
ue
t t 2
t ++1
1
1
1+ X++1 1+2 Xt+2
1 2
X4+1 + Xt+2
Ut
t ++ 2
++2
Inductively, we have the following:
t
>n X(+i
P1+m
+
1
m
Now let us consider that the last reservoir search query was executed at time step t (Minst = pt). We compute the drift from plat after steps follows:
A
|| Mast
M4+ml
I
Di=l X
Mlast
+ m
+ m
m
m
Plast
xcti/m m
f + m
| M441:44m
+ m
20

---

Published in Transactions on Machine Learning Research (03/2024)
where M4+1a+m is the mean of m representations observed after the last reservoir search query. Now, let consider the scenario where the centroid drift just exceeds the threshold, A R
m
X
M
M++1i+mml
+ m
2
77 P2
2 Mlst
Pr+ 1:t4ml
A
m (t),
where À is confidence bound defined in Equation 4.
Discussion. We observe that the interval between consecutive reservoir search queries directly proportional to the time step of the last query t (A remains constant for any reasonably large t). This shows that the reservoir search queries become infrequent as more samples processed. We also observe that m reduces as the |Mase M++1:++m| increases, which implies that the reservoir search queries become more frequent whenever there is a shift in the underlying input distribution.
Proposition (Interval between reservoir search during distribution drift). The number of steps (interval) between two consecutive reservoir search queries (m) when the centroid of the distribution drifts, increases with the number of representations processed m O(ytlog)).
Proof. Let us consider the scenario where the centroid of the distribution from which representations are sampled shifts from μ1 to #2 (where P1, Mi./22 E Rd). The unit vector the direction of the drift is given as
#1 م 1all- During the drift., we assume that representations are sampled from the dynamic distribution
~ N(n + B8, el), where < 3 and is the current mean of all samples seen so far. We assume a specific form of distribution shift as shown below:
Pe+1
Pt +
+
t+1
M4 30 cl t+1
Pt +
i 1+1
3ö + cl
14 +
1+1
Extending this for m steps, we get the following:
b+
Ma+m = p4 + (50 + el)
i i+1
1=1
Pe+m M1 = ee)
++
Hell S B
Incorporating the upper bound on the harmonic scries, En = log(m)) +em, with cm 2 0, and monotonically decreasing.
1| - Mell S B (log(t (1+ + m) - log(())
m
B 1
t
21

---

Published in Transactions on Machine Learning Research (03/2024)
Now assuming Plast = Mr is the last time the reservoir search query executed. We compute the number of steps till the centroid drift. A 2 exceeds the threshold:
m A m (OXP((A/23)
3 log(1
2
-1
1
a log 2t)
exp
1
2/3
2t
aD log (2))
l
1
23
21
1
Dt (2t)
23
O Vtllgt)
In this derivation, for large t >> O, the term X/2 is quite small allowing us to write the exponent term ===44 =1+a v, which provides a final complexity of O(V[lg!)) l).
Discussion. The above result shows that the interval between consecutive reservoir search queries is smaller when there is a distribution drift. We also observe that m is inversely proportional to the amount of drift B, which implies that reservoir search queries are called more frequently when the amount of drift is large.
22

---

Published in Transactions on Machine Learning Research (03/2024)
B Additional Related Work
Extractive Opinion Summarization. The task of extractive opinion summarization has been extensively researched by a long line of work (Kim et al., 2011; Zhong et al., 2019; Zhao & Chaturvedi, 2020; Zhong et al., 2020; Gu et al., 2022; Hosking et al., 2023; Mao et al., 2023; Siledar et al., 2023; Jiang et al., 2023; Sosea et al., 2023; Li & Chaturvedi, 2024). Most systems operate in an unsupervised setup, where saliency scores are assigned to review sentences and a subset of sentences are selected based on their saliency scores. Several forms of saliency compulation methods have been explored by prior works using: raw textual frequency features (Nenkova & Vanderwende, 2005; Nenkova & Bagga, 2003), distance from centroid (Radev et al., 2004), graph-based approaches (Erkan & Radev, 2004; Mihalcea & Tarau, 2004), among others. More recent neural approaches (Angelidis et al., 2021; Chowdhury et al., 2022; 2023; Li et al., 2023) perform summarization in a two-step process by learning review representations followed by an inference algorithm to generate the summary using the learned representations. In our algorithm, we follow the controid-based summarization paradigm and use a similar saliency scoring mechanism to perform opinion summarization incrementally.
Timeline Summarization. Our work on incremental opinion summarization is closely related to the task of timeline summarization. Timeline summarization, which is form of temporal summarization similar to our setup, has been studied extensively for news articles (Allan et al., 2001; McCreadie et al., 2014; Ge et al., 2016; Ghalandari & Ifrim, 2020; Pratapa et al., 2023) and in multi-document settings (John & Asharaf, 2014; Manuvinakurike et al., 2021; Yoon et al., 2023; Laskar et al., 2023). This task involves generating a sequence of summaries that reflect the timeline of loug-ranging news topics. Timeline summaries (Yan el al., 2011b;a; Steen Markert, 2019; Chen al., 2023) are expected have the following features: summaries should discuss important events in a time segment and consecutive summaries should not be redundant. Recently, (Cheang et al., 2023) has shown several challenges involved in using language models for timeline summarization pre-training of LMs affect the faithfulness of future summaries. In contrast to timeline summaries, opinion summaries in an incremental setup should capture the dominant opinions at each time step without any redundancy constraints, as only one summary is presented to the user at a time.
23

---

Published in Transactions on Machine Learning Research (03/2024)
C Synthetic Data Generation
In this section, we describe the process of sampling synthetic representations from the LDA (Blei ct al., 2003) process. The overall algorithm is presented in Algorithm 3. First, we sample the word distribution about each topic. Secondly, for every document or review, we estimate its length. Thirdly, we select the words within each review by imitially sampling a topic, and subsequently, picking a word from that topic's specific word distribution. We consider 10 different topics (can be considered as aspects for opinion summarization), vocabulary size [V] = 100, average review length L. = 150, and generate total of 10 reviews. We consider onc-hot vectors for each word the repr(-) function and retrieve the mean of all words the review representation Finally, the entire set of synthetic representations & is returned to the user.
Algorithm 3 Synthetic LDA data generation
1: function LDA(Topic Count k; Vocabulary Size [V], Average review length L, Reviews Count n). a 11k 8= 3=11 1=
// sample word distribution per topic
Φ Dir(3) [XX[V|
ε // emply representation set.
6:
for i= i do
7:
// sample topic distr. and review longth Dir(a), 4 Pois(L)
W; / words the i-th review
10:
for j = 1...4 do
11:
// sample word
12:
~ Multinomial(O))
13:
w ~ Multinomial(Os)
14:
W: = w; Uw // add the new word
15:
end for
16:
mean word representation
17:
e; E [w- [r]]
18:
ε & Ue, add representation
19:
end for
20: return 3
21: end function
24

---

Published in Transactions on Machine Learning Research (03/2024)
D Review Deletion Using CoverSumm
In this section, we show that we can use CoverSumm to update summarics when subset of reviews is deleted. This scenario may be useful when some reviews are flagged for their reliability or foul language. In this setting, the user provides the system with a set of sentences Xdel to be deleted and expects the updated summary as the output. In Algorithm 4, we present the algorithm to retrieve the updated summary when of sentences are deleted. First, we remove the sentences from the overall sentence Xx cover tree ct, and reservoir R. Next, we observe that need perform reservoir search the entire cover tree if either of the conditions met: the reservoir size is less than k, the new mean has drifted beyond X/2 (Line 11). If neither of the above conditions are met, the algorithm existing reservoir R. We observe that the most expensive step in Algorithm is deletion from cover trees (Line 4), therefore executing the DELETE(-) function should at least take O(m log (xl)) time (where m the number of sentences to deleted and [ the total number of elements in the cover tree during deletion).
generate the summary from the
Algorithm CoverSumm Delction Routine
1: function DELETD(Sentences to delete Xdel, last centroid jlatt reservoir R)
2:
X = x \ Xael // remove X,te
3: // delete Xdel from the cover tree
ct deeeeeeexeeeeee
// computed incrementally in ([xaal)
Me [[X]
7:
// drift of Pr from the last query Plast
8:
A = l1pe- - Masst
9:
R = R Xdel // delete Xdel from R
10:
// check if drift exceeds threshold or R has less than & elements
11:
if A X/2 [ < & then
12:
A = V 2(t-|xaa)) ((aa))
13:
R ct RessrrvollrSerrcc(h........
14:
Plast Pr
15:
end if
16: S, = knn (R, mc)
17:
return S,
18: end function
25

---

Published in Transactions on Machine Learning Research (03/2024)
E
Experiments
E.1
Implementation Details
We implemented all our experiments in Python 3.6 on a Linux server. The experiments were run on single In) Re) Silver 4214 CPU @ 2.20GHz processor. In our experiments, we set = 1/6 and perform a grid search on a small held-out set to determine o, for each dataset. The summary budget all experiments was k 20. In our experiments, we use the SG Tree implementation available graphgrove library." We will make the codebase, along with detailed instructions on how to replicate our experiments, publicly available after the double-blind review phase. We used the default set of hyperparameters available with HNSW and FAISS.
E.2 Human Evaluation Details
We performed human evaluation experiments on Amazon MTurk. We considered entitics from the Amazon US reviews dataset. where the number of reviews was more than 1000. In Table 2, we report the percentage of summary pairs marked as redundant informative. All the datasets used for the evaluation were in English language and we did not perform additional data collection on our own. Human judges were compensated at a wage rate of $15 per hour.
E.3 Additional Experimental Results
Adversarial distributions. A limitation of CoverSumn is that its performance is dependent on the input data distribu- tion. If the input points are not bounded, and the centroid of the input representations shifts frequently, CoverSumm's perfor- mance worsens as we need to perform ANN queries on the cover tree quite often. To simulate this scenario, we sample points from & dynamic distribution where the mean shifts continuously. Specifically, sample the i-th representation ~ NM4, E), where 14 (i/n)1 and n is a hyperparameter. In Table 3, we observe that CoverSumm is quite slow in this scenario and obtains similar time complexity to the brute force method. We
Algorithm
Time (s) 4
Brute force
25.51
Naive CT CoverSumm (reservoir)
14.75
15.36
CoverSumm (reservoir + lazy)
15.39
Table 3: Runtime of different algorithms when the points are sampled from an adver- sarial distribution.
also observe that the Naive CT is the fastest algorithm in this setting, as does not have additional range search and reservoir computations. However, adversarial distributions are rare in real-world settings. In such scenarios, we recommend using Naive CT instead of CoverSumm.
50
Taxttakk
17.5
45
15.0
40
ROUGE
ROUGER
35
10.0
30
7.5
25
2.5
200
400
600
800
200
400
200
400
600
800
Time step (2)
Time step (3)
Time step (U)
Figure 8: Evolution of ROUGE scores during incremental summarization. CoverSumm achieves the best scores with a gradual increase over time as more reviews are observed. CoverSumm abbreviatod CS.
Summarization Quality. this experiment, we investigate how the quality the generated summarics improves the incremental setup. Specifically, we measure the ROUGE scores of the generated summaries with the human-written summaries for all the reviews and report their evolution over time. In Figure 8, we observe gradual improvement in summary quality (in terms of ROUGE overlap with the human-written
26

---

Published in Transactions on Machine Learning Research (03/2024)
User Ratings
User Ratings
4.5
User Ratings
4.0
3.5
2.5
3.5
2,0
3.0
200
400
800
1000
1200
200
400
600
800
1000
250
500
750
1000
1250
step
Time step (1)
stop (7)
User Raliigs
User Rattings
User w
6.4
500
500
1000 1200
Time step
Time step
Time (0)
User Ratings
4.5
User Ratiogs
4.0
2.4
2.5
4.0
2.0
2.0
CoverSumm
200
400
500
800 1000 1200
250
590
750
1000
1250
200
4:00
600
800
1000
Time stop
Time step (1)
step (?)
Figure 9: Evolution of average Amazon US reviews dataset. We observe that the user ratings in CoverSumm's summaries can track the aggregate review ratings closely for all products.
ratings in the summary and user reviews for different products in the
summary) across different summarization systems. We also observe that CoverSumm and its variants achieve the best. ROUGE scores throughout. the incremental summarization process.
User ratings. We report the evolution of average user ratings and summary ratings using CoverSumm during the incremental summarization process. In Figure 9, showcase the summary rating trajectory for 9 different product entities from the Amazon dataset. We observe that for all instances the average summary rating mimics the aggregate user ratings across all time steps during summarization.
Generated Summaries. In Table 4, we report the summaries generated by CoverSumm over time for an entity in the SPACE dataset. We observe that the extracted summaries can uninformative or redundant. when there are only a few reviews, but the quality of summarics improves as more reviews pour in over time.
Sentiment Polarity. We report the evolution of sentiment polarity of CoverSumm's summaries and aggregate reviews in Figure 10 for 21 different products from the SPACE dataset. For all products, observe that the summary is able to capture the trends of sentiment polarity change in the original reviews. The generated summary also achieves sentiment polarity scores that are close to the aggregale user reviews.
27

---

Published in Transactions on Machine Learning Research (03/2024)
Time Step
CoverSumm Summaries
t 10
I've been all three of the Key West Marriott Hotels and this is my favorite for value and relaxation. Has a great relaxing pool layout, full continental+ breakfast and on this last visit a staff which worked harder than most travel agents finding some last minute actívities and making the bookings for our family. I did complain about the room at reception and they apologised and we were only staying the one night.
t 50
We took 2 night 3 day vacation and stayed at the Fairfield Inn in Jammary 2012. The bathroom smelled like sewer water, the front door couldn't open wider, it felt like were in motel. The location was good and the price reasonable for Key West. The Fairfield Inn is the absolute best value and the staff is nothing short of fantastic. Rooms nothing special; not very spacious and 'weird" bathroom. Good location.
t- 100
The staff is hospitable, and the hotel was very reasonably prieed and good location. We had good time the pool and the bar is great. We took 2 night. day vacation and stayed at the Fairfield Iun in Jamuar 2012. The location was good and the price reasonable for Key West. The staff was very Friendly and helpful. The room was very clean. Good location.
t- 300
The hotel staff was very friendly and accommodating. The front desk people were very helpful and friendly. Staff was friendly and helpful. We would definitely stay here again. Rooms nice and clean. We would definitely stay there again and would highly recommend this hotel. The pool area is very nice. Breakfast was more than adequate and the pool area was very enjoyable. The room was very clean. They succeeded! This hotel great.
t 500
The hotel staff very friendly and accommodating. friendly. Staff was friendly and helpful. Rooms were nice and clean. We would definitely stay here again. Staff are very courteous and professional. The pool area is very nice. Breakfast was more than adequate and the pool area was very enjoyable. We would definitely stay there again and would highly recommend this hotel. They succeeded! The rooms are loud.
The front desk people were very helpful and
t 915 (final)
Staff was friendly and helpful. The front desk people were very helpful and friendly. 'Tee hotel staff was very friendly and accommodating. The pool was nice, but we did not use it. Rooms were nice and clean. We would definitely stay here again. The pool area very nice. A big plus was the free parking and large selection for continental hreakfast. Staff are very courteous and professional. We were not disappointed! They succeeded!
Table 4: Generated summarics from CoverSumm at different time steps for an entity from the SPACE dataset.
28

---

Published in Transactions on Machine Learning Research (03/2024)
0.8
0.7
0.5
0.5
0.4
0.5
0.4
0.2
0.4
0.0
100
200
300
400
500
600
700
800
100
230
300
400
509 600 700 800
200
400
600
200
Time
stop (F)
Time
stop (f)
Tima stop (7)
0.7
0.8
0.5
0.5
0.5
0.4
0.4
0.3
Time (f)
Time (t)
Time (1)
0.8
0.7
0.6
0.5
0.6
0.5
0.4
0.4
0.3
200
200
520
600
100
400
0.5
0.7
0.7
0.7
0.6
0.5
0.5
0.1
0.4
0.3
100
200
300
RUD 500 300 700 80U 900
300
200
500
400
500 600
730 800
100
200
300
400
500 BUD
700 BUD 900
Time step (1)
Time step (1)
Time step (2)
0.7
0.6
0.5
0.4
0.1
0.2
0.4
0.2
400 Time stop 1t)
200
0.0
300
700
Time stop (t)
Tima
(2)
0.6
0.8
0.5
0.7
0.5
0.4
0.6
0.5
0.2
0.2
0.1
300
600
420
500
step
0.6
0.7
0.7
Restews
Cover Summ
0.6
Human
0.4
0.1
0.3
100 200 300 420 SOU SOU 700 800 Time step (D)
200 200
300
400
600 700 500 step (1)
500
100 200
300 400 Step
500
50U
700
200
Figure 10: Evolution of sentiment polarity in CoverSumm's summarios and aggregate user reviews for different: products in the Amazon US reviews dataset. We observe that CoverSunm's summaries can track the trends in sentiment polarity of the aggregate review set while achieving scores similar to the human-written summary.
29


Reviews:
[{"review_id": "1iYKUDbjAu", "reviewer": "Reviewer_izSt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ This paper is very well written with theoretical background and proofs.\n+ The experiments show strong results and support the main claim of this paper.\n\nWeaknesses:\n\n+ The core of the proposal is not limited to update opinion summarization, but for k nearest neighbors with incremental data points. To be more precise, this paper does not include any proposal that is specific to opinion summarization. For example, the title of this paper can be something like \"k nearest neighbors with incremental data points using cover trees.\" I'm wondering why the authors limit the scope of this work to opinion summarization.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an algorithm and theory for retrieving k nearest neighbors to a centroid when the data points arrive incrementally, and applies the algorithm to the summarization task. The algorithm maintains a small number of reservoir representations R that have a high chance of being selected as kNNs in the future. This reduces the execution time of kNN, focusing on the limited number of entries (R) instead of the entire entries. The main contribution of this work is the theoretical proofs that give the foundations for the maintenance of the reservoir. The experimental results confirm that the proposed algorithm finds the exact solution of kNNs in a shorter running time. The experiments also demonstrate the superiority of the proposed method on SPACE dataset over the baseline methods in terms of ROUGE scores and running time. This paper also reports various analyses, for example, user rating, sentiment polarity, and human evaluation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Minor point:\n\n+ Change \"Beygelzimer et al. (2006); Zaheer et al. (2019)\" to \"(Beygelzimer et al., 2006; Zaheer et al., 2019)\" in P3.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "RVBq9wQgrv", "reviewer": "Reviewer_LCuR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. The paper addressed a unique aspect of the summarization problem that fits real-world applications.\n2. The paper provided both theoretical bounds and empirical results. The reduction in runtime achieved was outstanding.\n3.  The paper included additional analyses to confirm the theoretical bounds and highlight the strengths and weaknesses of the proposed algorithms.\n\n### Weakness\n\n1. Most of the paper was well written, but the evaluation section missed some important details.\n    1. It is unclear how the \"Time\" in Table 1 was computed (i.e., total time of the whole simulation or average time per sentence added.)\n    1. There were 10k reviews in the syntactic data, but how many entities?\n1. Why was SemAE selected as a representation model? Was there any particular reason not to use general sentence embedding models? If there was one sentence to come in at a time, how would we obtain SemAE pre-trained with the datasets?\n1. The omitted result might not fully support the claim. The Amazon review and the SPACE datasets were not similar as shown in Table 3 and Table 4. The inclusion of the Amazon review dataset in Table 1 should be necessary.\n1. I appreciated that the author presented the human evaluation result, but the silver summaries' quality was still questionable.\n1. No empirical evidence of the deletion case (i.e., reviews of a product evolved over time, getting better or worse.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses a unique problem of incremental extractive summarization that is well suited in review summarization, where new product or service reviews arrive incrementally. While methods to extract summaries existed, such as direct predictions by deep learning models or centrality-based approaches, a method to do so efficiently in an incremental setting did not yet exist. The authors extended the centroid-based approach and proposed a new algorithm, CoverSum, that used a stable greedy (cover) tree and reservoir candidate representations to find the nearest neighbors and update the centroid efficiently. \n\nThe authors provided theoretical proof that bounded the efficiency (number of queries and reservoir size) of CoverSum. In the experiments, the authors used both synthetic and real-world datasets. The authors showed that CoverSum ran faster than other baseline algorithms, including brute force and naive cover tree, while returning extract nearest neighbors. In addition, the extracted summaries achieved high ROUGE scores and tracked the changes in user rating and sentiment. Additional analyses also supported the theoretical bounds.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Changes\n1. I think the authors should include the performance of both real-world datasets in the main text. While many experiment results in the appendix seemed duplicates, some were conflicting or omitted. For example, Table 4 conflicts with Table 3 (with a good reason). \n1. It might be possible to compute the ROUGE scores of the silver summaries.\n1. Would it be possible to simulate the reviews \"expiring\" over time to demonstrate the deletion cases? \n\n\n### Minor changes\n1. Section 2.2 contained both $l$ and $\\ell$. I believed they were meant to be the same symbol.\n1. 25x was coming from the synthetic dataset of 100D vectors. I think the authors should make this claim more realistic.", "broader_impact_concerns": "There is no ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VGsj2wnnqE", "reviewer": "Reviewer_Hkk2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Thanks to the authors on the hard work on this paper.\n\nStrengths\n------------\n- Their algorithm is general - it will work beyond the one specific use-case of iterative opinion summarization.\n- Theoretical results (which I did not closely check) are nice to have\n- Clear writing\n- Good results (but I do ask for extra baselines below)\n\nWeaknesses\n----------------\n- What's CentroidOPT? How come it's not as good as CoverSumm? In the intro you said \"This objective, known as CentroidRank (Radev et al., 2004), functions by calculating the centroid of review sentences in the representation space, and selecting the nearest neighbors of the centroid as the summary\". So it seems like CentroidOPT (which I assume is some sort of iterative version of CentroidRank) is trying to do the same thing as NaiveCT/CoversSumm. \n- The actually reads like two different papers stapled together. Sections 2 and 3 are about a general-purpose algorithm where the goal is to keep a reservoir of neighbors to the centroid up to date as new data arrives. Section 4 is about an application of this general algorithm to one very specific setting with a few datasets. It's nice that you show CoverSumm works well in Table 2, but this is just performance on one dataset - is your intention to show that CoverSumm is a good general-purpose interative opinion summarization dataset? If so, you need more datasets with Rouge scores, probably in line with however-many are in your most recent competitor.\n- What is the exact formula for $\\delta$? How do you set it? Do you need cross-validation? Similarly, how were *all* the hyperparamters set? Both for your algorithm, and also everything else in Table 2?\n- I don't understand the baseline CoverSumm (decay $\\lambda$). What is the motivation here? At what rate do you decay? What is this baseline showing? What if you start with a bigger $\\lambda$ than the normal one you set? You may want to get rid of this baseline...\n- I think you need another baseline. Upon reading the description of the problem, my first instinct (I'll call this R2's Naive Baseline) was to just use a well-known approximate nearest neighbor package (HNSW or FAISS) + iterative computation of the centroid as follows:\n\n(1) Initialize empty ANN and null centroid.\n(2) For step $n$, given a new sample $x_n$, insert into ANN, and update centroid with $$\\mu_n = \\frac{1}{n} \\left((n-1)\\cdot\\mu_{n-1}  + x_n\\right)$$ (please double check my math)\n(3) Issue the centroid as k-NN query to ANN.\n\nI think this would be fairly easy to implement and run with off-the-shelf tools. There is the matter of setting hyperparameters for the ANN, but you can use whatever techniques you used for various algs in Table 2. Hopefully they were set in some rigorous way.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "A fast exact iterative k-nearest-neighbors to the centroid algorithm with theoretical analysis. Experiments showing how it performs for opinion summarization.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please make sure the baselines (like CentroidOPT) are all clearly (if succinctly) described - critical\n- Make clear how hyperparameters were set, and (especially) clarify how $\\delta$ is chosen and what happens when you choose poorly - critical\n- Add the R2's Naive Baseline to Table 1 and 2 - critical", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an algorithm and theory for retrieving k nearest neighbors to a centroid when the data points arrive incrementally, and applies the algorithm to the extractive summarization task. After author rebuttal, it received Accept, Accept, Leaning Reject recommendations. 

On one hand, reviewers agree that (1) the paper is well written with theoretical background and proofs; (2) experimental results support the main claim of this paper, the reduction of the proposed method in runtime is encouraging. So, overall, it is a nice executed paper. 

On the other hand, two concerns remain. (1) After adding additional baselines during author rebuttal, it seem like the proposed method is only a bit faster than a naive baseline (Naive Faiss) and not much else. (2) The proposed method is general; this paper does not include any proposal that is specific to opinion summarization. It is a little bit pity that the authors limit the scope of this work to opinion summarization.

Overall, the merits of the paper outweigh its flaws; therefore, the Action Editor would like to recommend acceptance of the paper.
Decision: Accept (poster)