An Efficient Approach to Store and Access Wikipedia’s Revision History for Large-Scale Analysis

Amit Arjun Verma and Simran Setia

Abstract

The history-based content present on Wikipedia has been used for various NLP-related research. For large-scale analysis, efficient retrieval of past states of Wikipedia is a prerequisite. However, the lack of efficient tools for managing the massive amount of provided data acts as a bottleneck. We present a detailed analysis of online algorithms to efficiently compress and retrieve the revision history of Wikipedia articles. We give theoretical evidence that our methods perform efficient compression and extraction while optimizing time and space complexity. Moreover, the experiments on sampled Wikipedia articles using the online parameters extraction method show that our algorithm can compress the dataset up to 94% of its original size. To the best of our knowledge, this is the first attempt to show a detailed analysis of Wikipedia's full revision history dataset compression.

CCS CONCEPTS

• Information systems →Specialized information retrieval; Information extraction; Data extraction and integration; Digital li- braries and archives.

KEYWORDS

Wikipedia, Edit-History, Datasets, Natural Language Processing, Compression, Algorithm

1 INTRODUCTION

Over the past decade, Wikipedia, the free online collaborative ency- clopedia, has been a subject of enormous interest in the various re- search domains [8, 18, 34]. The intense collaboration on Wikipedia and its open dataset have attracted researchers to study various tasks such as to study online collaboration dynamics [10, 16, 33], to examine its impact on other online collaborative portals [28], and to

revision is stored as a full revision. A similar approach was followed by Ferschke et al. [7], where the value of 𝑘(interval length) was fixed to 1000 irrespective of input article. Following the lines of Ferschke et al.’s work, Verma et al. [27] proposed a method for compressing the revision history using the interval length 𝑘= √𝑛. We propose an online algorithm to compress and retrieve the Wikipedia article’s revisions, which can scale up with the Wikipedia dataset size. We show that our approach outperforms the previ- ously established methods in terms of retrieval time and space complexity. Moreover, the dataset consisting of the compressed

309

HT ’24, September 10–13, 2024, Poznan, Poland Amit Arjun Verma & Simran Setia

representation of Wikipedia articles’ full revision history will be a novel source of knowledge for Wikipedia-based analysis. The articles’ full revision history can be used to train a model for van- dalism detection [5], to identify semantic edit intentions [31], to extract semantic information from Wikipedia [25], to identify edi- tor’s role in Wikipedia [32], to correct grammatical errors [3], or to create longitudinal Wikipedia link network [6]. With the proposed algorithm, we reduce the required storage space to less than 7% of its original size. We validate our results empirically on a sampled Wikipedia full revision history dataset. We also compare the space and time complexity of our method with Ferschke et al.’s method.

bytes. Each revision of a Wikipedia article is a combination of previ- ous revisions and the current edits. Assume there are 𝑛revisions for a Wikipedia article, define R = {𝑟𝑖| 𝑟𝑖is the 𝑖threvision, 0 ≤𝑖≤𝑛} to be the set of all 𝑛revisions of the article, where 𝑟0 denotes the empty revision. R can also be considered as the XML dump of a Wikipedia article. Let 𝑑𝑟𝑖denote the difference between two consec- utive revisions 𝑖and 𝑖−1 i.e.,𝑑𝑟𝑖= 𝑟𝑖⊖𝑟𝑖−1, where ⊖: R×R →𝑑R is the diff operator which is defined as the smallest set of dele- tions and insertions required to create one text from the other [14]. Thus, 𝑑R is the set of all difference revision obtained from diff operator. Since edits made in the current revision results in the successive revision, 𝑟𝑖can also be written as 𝑟𝑖= 𝑟𝑖−1 ⊕𝑑𝑟𝑖, where ⊕: R × 𝑑R →R restores one of the revisions that generated 𝑑𝑟, acting as a decompressor. One way of storing the data is to store only the difference 𝑑𝑟𝑖, ∀𝑖∈[1,𝑛] rather than the entire revision. Though this results in significant amount of compression, the reconstruction time of a particular revision is more than its uncompressed counterpart. A revision 𝑟𝑖can be retrieved by loading 𝑑R to the main memory and recursively constructing 𝑟1, 𝑟2, · · · , 𝑟𝑖using 𝑑𝑟1, 𝑑𝑟2, · · · , 𝑑𝑟𝑖−1 respectively, i.e.,

2 RELATED WORK

Accessing Wikipedia data has always been challenging. A sig- nificant amount of effort is required to mine and preprocess the Wikipedia dataset [20]. Many toolkits have been developed to solve the Wikipedia data extraction issue. One possibility to retrieve the Wikipedia revision history is to parse the Wikipedia XML dump manually. Various tools to extract and parse the Wikipedia data dump are available. For instance, Verma et al. [27] developed a python based library named KDAP to extract and analyze the dataset of online collaborative portals, including Wikipedia. How- ever, it requires one to download each article’s full revision history and store it in the local machine. Even with the parallel processing, parsing a broad set of articles is infeasible. Wikibrain [24] is an- other example of data dump parser which provides state-of-the-art algorithms ranging from extracting pageviews to finding semantic relatedness, but the number of extraction algorithms is limited. Var- ious other parsers provide similar parsing features (e.g., MediaWiki Utilities [11]), but requires full revision history dataset. Similar to general analysis toolkits, application specific tollkits are also avail- able to extract and parse the Wikipedia data (e.g., WikiMirs [13]). As mentioned above, of all the existing toolkits, we wish to highlight Wikipedia Revision Toolkit developed by Ferschke et al. [7]. The toolkit represents Wikipedia revisions in a compressed form by storing the edits, achieving a compression up to 98%. Effi- cient retrieval methods were implemented to retrieve the data of a particular revision from the compressed data dump. However, the compression and retrieval methods do not scale up with the current size of the dataset. Moreover, the authors did not discuss the theoretical analysis of choosing a fixed length of 1000. Given that Wikipedia’s size is increasing with time, fixing the interval length as 1000 may result in inefficient compression. Verma et al. [27] in their toolkit extended Ferschke’s compression method by emperically showing that the interval-length of √𝑛gives the ideal compression ratio. However, no thoretical analysis was provided.

3 PRELIMINARIES

Being a crowd-sourced portal, Wikipedia maintains each of its article’s development in terms of revision history (edit history)1. Chhabra et al. [4] describe the knowledge-building process in Wikipedia as a sequential process, where a single user’s contribution is added at a particular time-stamp. Wikipedia records all the edits of an article along with other details such as user ID, time-stamp, and

1These two terms are synonymous and essentially interchangeable

𝑑𝑟1 |{z} ⊕𝑑𝑟2 ⊕𝑑𝑟3 ⊕· · ·𝑑𝑟𝑖

= 𝑟1 ⊕𝑑𝑟2 | {z } ⊕𝑑𝑟3 ⊕· · ·𝑑𝑟𝑖

= 𝑟2 ⊕𝑑𝑟3 | {z } ⊕· · ·𝑑𝑟𝑖

...

= 𝑟𝑖 Moreover, the reconstruction time and compression ratio depend on the type of algorithm used to compute the diff between the two revisions. Much research has been conducted on developing effi- cient difference algorithms. However, both their runtime and the size of the resulting output are not feasible given the massive redun- dancy in Wikipedia’s articles’ revisions. For instance, Heckel’s [12] algorithm for computing difference is quick but provides inefficient output if related text exists in the inputs. Similarly, the algorithm provided by MacDonald [17] uses copy and insert operators to com- pute the difference. The copy operator is used to copy the text to the output whenever an exact match is found, which again is infeasible given the size and redundant text in Wikipedia. Arguably the best difference algorithm for our purpose is proposed by Mayer [21], which provides the difference between two texts as a set of inserts and deletes. The algorithm takes a greedy approach by maximizing the consumption of similar lines before making any change and preferring deletions over insertions when given a choice. This ap- proach allows the algorithm to detect redundant information while optimizing time complexity efficiently. Given two strings A and B, the algorithm takes O(𝑛𝑑) in time and space, where 𝑛is the sum of the lengths of A and B and 𝑑is the size of the minimum edit script for A and B. We use Mayer’s algorithm to compute the difference between two revisions. At any time, only 𝑟𝑘−1 is stored in the main memory while reconstructing 𝑟𝑘(2 ≤𝑘≤𝑛). In the worst case (retrieving the last revision), this method require O(𝑛𝑑+ (𝑚+ 𝑑)) in space, and

310

An Efficient Approach to Store and Access Wikipedia’s Revision History for Large-Scale Analysis HT ’24, September 10–13, 2024, Poznan, Poland

O(𝑛(𝑚+ 𝑑)) in time, where 𝑚is the maximum size of the revision in R and 𝑑is the maximum size of the difference revision in 𝑑R. This is because, the reconstruction of the text 𝑟𝑖+1 from 𝑟𝑖and 𝑑𝑟𝑖 would require O(||𝑟𝑖||+||𝑑𝑟𝑖||) in space and time, where ||·|| denote the size of the text (please refer to text reconstruction from diff patch [22]).

𝑘= 𝑛, the method reduces to storing only the difference revisions, as discussed in preliminaries, making this a general method. Based on our analysis, we now provide an efficient revision extraction algorithm for compressed Wikipedia dataset.

4.2 Variable-Interval Length Compression

The above method stores the difference between two consecutive revisions except for a few fixed intervals (𝑘). Although the above method reduces the overall compression ratio and the random revision retrieval time, the fixed interval length restricts us from optimal compression. We modify the above method by storing the full revisions at variable interval lengths. Our goal using the variable-length intervals is to store the difference only when there is a minor edit, in turn optimizing the overall compression. We translate this optimization problem into an ordered set partition problem. More specifically, for a Wikipedia article, we define 𝑆= {𝑠𝑖| 𝑠𝑖= ||𝑟𝑖||, 0 ≤𝑖≤𝑛} as an ordered set of revision sizes, where ||𝑟𝑖|| represents the text length of revision 𝑟𝑖∈R. For simplicity’s sake assume ||𝑟𝑖⊖𝑟𝑖−1|| = |𝑠𝑖−𝑠𝑖−1| (|.| is the absolute function), which means we can compute ||𝑑𝑟𝑖|| = |𝑠𝑖−𝑠𝑖−1| (we will relax this assumption later). Given a set 𝑆for a corresponding Wikipedia article, we define 𝑃as a partition of the set 𝑆such that:

4 WIKIPEDIA DATA COMPRESSION AND DECOMPRESSION: AN EFFICIENT WAY

This section provides an analysis of our approach for efficiently compressing and retrieving Wikipedia’s edit history. Based on our method, we provide algorithms to perform both random and full edit history extraction.

4.1 Fixed-Interval Length Compression

We develop a generalized model that calculates the interval length (𝑘) based on the input file, optimizing both the time and space complexity. Here, we modify the set𝑑R into ˜ 𝑑R, the set of difference between two consecutive revisions except at multiples of estimated 𝑘∈[1,𝑛]. Each element of ˜ 𝑑R, ˜ 𝑑𝑟𝑖, is defined as:

( 𝑟𝑖⊖𝑟𝑖−1 if 𝑖(mod 𝑘) ≠0 𝑟𝑖 if 𝑖(mod 𝑘) = 0

˜ 𝑑𝑟𝑖=

Out of 𝑛revisions, there are j𝑛

k number of revisions that are

stored as full revisions and 𝑛− j𝑛

k number as difference revisions. The decompression technique is same as described in the previous section except that ˜ 𝑑R is stored in the main memory instead of

𝑘

𝑑R, which makes it O 𝑛

𝑘𝑚+ 𝑛−𝑛

𝑑+ (𝑚+ 𝑑) in space and

𝑘

O(𝑘(𝑚+𝑑)) in time in the worst case (for retrieving any𝑖𝑡ℎrevision). We are able to achieve this by hashing the revisions stored as full revision, where keys are revision number and values are the text associated with it. As we increase the size of the interval length, 𝑘, the memory space decreases and the retrieval time increases. Hence, there is a trade-off in using extreme 𝑘values, giving us a chance to find the optimal 𝑘(in terms of both space and time combined). Using the above two expressions, given an XML dump of a Wikipedia article, we can compress the data with a value of 𝑘.

Theorem 4.1. For a given Wikipedia article with 𝑛(total number of revisions),𝑚(maximum size of the revision in R) and 𝑑(maximum

√︄

𝑛 𝑚−𝑑

size of the difference revision in 𝑑R), the optimal 𝑘is

𝑚+ 𝑑

Proof. Since for any given article we have 𝑛, 𝑚and 𝑑as con-

stants, the minima of the function 𝑓(𝑘) = 𝑛𝑚

𝑘 + 𝑛𝑑−𝑛𝑑

𝑘+ (𝑚+

𝑑) + 𝑘(𝑚+ 𝑑) needs to be calculated. Differentiating the function 𝑓(𝑘) with respect to 𝑘and equating it to zero, we get the desired 𝑘. It can be easily verified that the obtained 𝑘is the minima of 𝑓(𝑘).

□

If we let 𝑘= 1, then the compression method discussed above is the same as the XML dump of an article. On the other hand, if

• 𝑃= {𝑝1, 𝑝2, 𝑝3, . . . , 𝑝𝑁}, where 𝑁≤𝑛. • 𝑝𝑗(for some 𝑗) is either a singleton set or if 𝑠𝑙,𝑠𝑚∈𝑝𝑗and if 𝑙< 𝑚, then 𝑠𝑖∈𝑝𝑗∀𝑖∈(𝑙,𝑚).

• Given 𝑝𝑗= {𝑠𝑖| 𝑙≤𝑖≤𝑚}, we define function 𝑓−on 𝑝𝑗as

( 𝑠𝑖, if 𝑝𝑗is a singleton 𝑠𝑙+ Í𝑚−1 𝑖=𝑙 |𝑠𝑖+1 −𝑠𝑖|, otherwise

𝑓−(𝑝𝑗) =

• Given 𝑝𝑗= {𝑠𝑖| 𝑙≤𝑖≤𝑚}, we define function 𝑡on 𝑝𝑗as

𝑡(𝑝𝑗) = 

1, if 𝑝𝑗is a singleton

1 + 𝑚−1 Í



𝑖=𝑙 𝑠𝑖+ |𝑠𝑖+1 −𝑠𝑖|, otherwise

Given the partition and the function definition, the summation Í 𝑓−(𝑝𝑗), ∀𝑗∈𝑁represents the overall size of the set 𝑆(i.e. size of the Wikipedia article) after compression. Consider a simple example where a Wikipedia article contains only three revisions and their sizes are 𝑟1 = 1, 𝑟2 = 2, and 𝑟3 = 8. Given the size of each revision, we can represent the set 𝑆= {1, 2, 8}. If we partition this set 𝑆such that 𝑃= {{1}, {2, 8}} then Í 𝑓−(𝑝𝑗) will be 9, which we refer as the total space cost. But what about the revision retrieval time? As explained in section 3, given a revision 𝑟𝑖and the difference 𝑑𝑖= 𝑟𝑖⊖𝑟𝑖+1, retrieving the revision 𝑟𝑖+1 will take O(||𝑟𝑖|| + ||𝑑𝑟𝑖||) time. Which means that overall time cost for a given set 𝑆will be Í𝑡(𝑝𝑗), ∀𝑗∈𝑁(in the case of 𝑆= {1, 2, 8}, the time cost is 11, O(1) unit for 𝑟1 and 𝑟2, whereas O(2 + 6) for 𝑟3). Can we define a partition in this set 𝑆which minimizes the overall time cost and the space cost? Now provided a set 𝑆, the problem reduces to finding a partition 𝑃such that the overall time cost and the space cost are minimized. More specifically:

• Í 𝑓−(𝑝𝑗), ∀𝑗∈𝑁is minimized and, • Í𝑡(𝑝𝑗), ∀𝑗∈𝑁is minimized.

311

HT ’24, September 10–13, 2024, Poznan, Poland Amit Arjun Verma & Simran Setia

Table 1: Representation of difference between every two consecutive revisions. 𝑚𝑟𝑖and 𝑡𝑟𝑖represents the memory cost saved by storing the difference 𝑑𝑟𝑖and the time cost to retrieve the revision 𝑟𝑖using 𝑟𝑖−1 and 𝑑𝑟𝑖, respectively. 𝑙𝑖= ||𝑟𝑖|| represents the revision length of 𝑖𝑡ℎrevision and |.| represents the modulus function.

revisions 𝑙1 𝑙2 𝑙3 𝑙4 ... 𝑙𝑛−1 𝑟𝑛

differences 𝑑𝑙1 = |𝑙2 −𝑙1| 𝑑𝑙2 = |𝑙3 −𝑙2| 𝑑𝑙3 = |𝑙4 −𝑙3| ... 𝑑𝑙𝑛−1 = |𝑙𝑛−1 −𝑙𝑛−2| 𝑑𝑙𝑛−1 = |𝑙𝑛−𝑙𝑛−1| memory cost saved 𝑚𝑟1 = 𝑙2 −𝑑𝑙1 𝑚𝑟2 = 𝑙3 −𝑑𝑙2 𝑚𝑟3 = 𝑙4 −𝑑𝑙3 ... 𝑚𝑟𝑛−1 = 𝑙𝑛−1 −𝑑𝑙𝑛−1 𝑚𝑟𝑛−1 = 𝑙𝑛−𝑑𝑙𝑛−1 time cost 𝑡𝑟1 = 𝑙1 + 𝑑𝑙1 𝑡𝑟2 = 𝑙2 + 𝑑𝑙2 𝑡𝑟3 = 𝑙3 + 𝑑𝑙3 ... 𝑡𝑟𝑛−2 = 𝑙𝑛−2 + 𝑑𝑙𝑛−2 𝑡𝑟𝑛−1 = 𝑙𝑛−1 + 𝑑𝑙𝑛−1

However, the optimization function as the summation of space and time cost (Í 𝑓−(𝑝𝑗) + Í𝑡(𝑝𝑗), ∀𝑝𝑗∈𝑃) provides a solution other than the original arrangement of the set S, only if there exist at least two consecutive revisions having the difference precisely equal to 1 (please refer to the appendix of a detailed example2). Moreover, the solution is never unique. To overcome this challenge, we convert the optimization problem into a memory cost minimization problem based on a fixed time cost. More specifically, given a set 𝑆and a fixed time cost (as a function of 𝑛= |𝑆|), the optimization problem reduces to finding a partition 𝑃that minimizes the overall space cost. We first start with computing the differences between all the consecutive revisions. As illustrated in Table 1, we compute the memory cost saved as 𝑚𝑟𝑖= ||𝑑𝑟𝑖|| −||𝑟𝑖−1||, whereas the time cost represents the time units required to retrieve a specific revision. Given a fixed time cost, we aim to maximize the memory cost saved. It is easy to verify that this maximization problem can be translated into the 0/1 knapsack problem, where the time cost is the knapsack size, and the memory cost saved is the profit. We now formally define the 0/1 knapsack problem and show the reduction of our partitioning problem to the 0/1 knapsack problem.

Corollary 4.2. Given a set 𝑆of revision sizes and the optimal set of items 𝐼𝑜𝑝𝑡, the optimal partitioning 𝑃= {𝑝1, 𝑝2, ..., 𝑝𝑘} is per- formed such that ∀𝑖∈[𝑙+ 1,𝑚] ∋𝑙< 𝑚, 𝑝𝑗= {𝑠𝑖|𝑠𝑖∈𝐼𝑜𝑝𝑡}. Moreover, ∀𝑖∈[1,𝑛], 𝑠𝑖∈𝑝𝑗and 𝑠𝑖+1 ∈𝑝𝑗+1 for some 𝑗, iff 𝑠𝑖∈𝐼𝑜𝑝𝑡 and 𝑠𝑖+1 ∉𝐼𝑜𝑝𝑡.

The partitioning is performed based on the optimal set of items 𝐼𝑜𝑝𝑡computed based on the 0/1 knapsack solution. The recurrence relation of 0/1 knapsack problem guarantees to return the optimal set of items provided a fixed maximum cost. Therefore, deriving from the proof of knapsack optimization, the partitioning 𝑃per- formed using the set 𝐼𝑜𝑝𝑡is the optimal partitioning, minimizing the overall memory cost based on the given maximum time cost. Returning to our original problem, we now relax the assumption of ||𝑑𝑟𝑖|| = |𝑠𝑖−𝑠𝑖−1|. Instead of calculating the actual diff between two revisions as 𝑑𝑟𝑖= 𝑟𝑖⊖𝑟𝑖−1, we approximate the difference size as ||𝑑𝑟𝑖|| = 2.|𝑠𝑖−𝑠𝑖−1|3. The stated approximation allows us to calculate all the consecutive differences in linear time. It is easy to varify that even after relaxing the original assumption the algorithm returns the optimal partitioning. We experimently found that using the time cost as 𝑛2 the algorithm performes optimal compression.

4.2.1 0/1 knapsack definition. Given a set 𝐼of 𝑛items, with each item 𝑖∈[𝑛] having a cost 𝑐𝑖∈Z+ and a value 𝑣𝑖∈Z+ associated with it, find a subset 𝐼𝑜𝑝𝑡⊆𝐼of items whose cost 𝑐𝑜𝑠𝑡(𝐼𝑜𝑝𝑡) = Í 𝑖∈𝐼𝑜𝑝𝑡𝑐𝑖is smaller than a defined capacity 𝑊and whose value 𝑣𝑎𝑙𝑢𝑒(𝐼𝑜𝑝𝑡) ∈Í 𝑖∈𝐼𝑜𝑝𝑡𝑣𝑖is maximal. Apprantly the solution to the 0/1 knapsack problem is computed through a dynamic programming approach. More specifically, we define 𝑐[𝑖,𝑤] to be the maximum value that can be attained with capacity less than or equal to 𝑤using items up to 𝑖. We can define 𝑐[𝑖,𝑤] recursively as:



0, if 𝑖= 0|𝑤= 0, 𝑐[𝑖−1,𝑤], if 𝑤𝑖> 𝑤,

𝑐[𝑖,𝑤] =



𝑚𝑎𝑥(𝑣𝑖+𝑐[𝑖−1,𝑤−𝑤𝑖],𝑐[𝑖−1,𝑤]), if 𝑖> 0 & 𝑤≥𝑤𝑖

Similar to the 0/1 knapsack problem, we define our original set 𝑆 of revision sizes as the set of items. The time cost list represents the cost associated with each item, and memory cost saved list repre- sents each item’s value. Provided a fixed maximum time cost 𝐶, the optimal solution maximizing the memory cost saved (minimizing the overall memory cost) can be computed using the above recur- sive function. The optimum set of items 𝐼𝑜𝑝𝑡can be obtained from the final solution 𝑐[𝑛,𝑊].

2shorturl.at/emwEZ

Algorithm 1 Extract 𝑟𝑖, where 𝑖∈[𝑙,𝑙+ 𝑗]

Require: X, 𝑘≠0 or 𝑈= [𝑘1,𝑘2, ...,𝑘𝑁], 𝑙, and 𝑗

𝑝𝑟𝑒𝑣←𝑁𝑜𝑛𝑒 𝑐𝑢𝑟𝑒𝑣←𝑁𝑜𝑛𝑒 if 𝑋[𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒] = 𝑇𝑟𝑢𝑒then

𝛾←𝑘𝑞∋ 𝑚=𝑞 Í

𝑚=1 𝑘𝑚≤𝑙< 𝑚=𝑞+1 Í

𝑚=1 𝑘𝑚{Calculating the nearest full revision index}

𝛾← 𝑙

· 𝑘

else

𝑘

end if

if 𝑙mod 𝑘= 0 or 𝑚=𝑞 Í

𝑚=1 𝑘𝑚= 𝑙then

𝑝𝑟𝑒𝑣←X[𝛾] ⇐{if random revision is a full revision}

else

𝑝𝑟𝑒𝑣←X[𝛾] for 𝑡←(𝛾+ 1) 𝑡𝑜𝑙do

𝑝𝑎𝑡𝑐ℎ←𝑁𝑢𝑙𝑙 𝑐𝑢𝑟𝑒𝑣←X[𝑡] 𝑝𝑎𝑡𝑐ℎ←𝑝𝑟𝑒𝑣⊕𝑐𝑢𝑟𝑒𝑣⇐{sequential reconstruction of 𝑙𝑡ℎrevision} 𝑝𝑟𝑒𝑣←𝑐𝑢𝑟𝑒𝑣

end for

end if while 𝑡≠(𝑙+ 𝑗) + 1 do

𝑟𝑒𝑠𝑢𝑙𝑡←𝑝𝑟𝑒𝑣 𝑐𝑢𝑟𝑒𝑣←X[𝑡+ 1] 𝑟𝑒𝑠𝑢𝑙𝑡←𝑝𝑟𝑒𝑣⊕𝑐𝑢𝑟𝑒𝑣⇐{sequential retrieval of revisions from 𝑙to 𝑙+ 𝑗} 𝑝𝑟𝑒𝑣←𝑐𝑢𝑟𝑒𝑣

end while

3We emperically found that twice of the difference yields a good approximation.

312

An Efficient Approach to Store and Access Wikipedia’s Revision History for Large-Scale Analysis HT ’24, September 10–13, 2024, Poznan, Poland

Table 2: Number of articles sampled from each class

5 DATA AND EXPERIMENT

In this section, we describe the data, metrics, and experiments with different interval lengths (𝑘). Furthermore, we evaluate the performance of the proposed method with the baseline.

Class Number of Articles

Featured Articles 167 Good Articles 857 Class B 2349 Class C 6279

5.1 Dataset

We used KDAP to extract the full revision history of Wikipedia ar- ticles. Wikipedia articles are categorized into seven classes namely, Featured Articles (FA), Class A Articles, Good Articles (GA), Class B Articles, Class C Articles, Start Articles, and Stub Articles. To reproduce the original population distribution, we performed strat- ified sampling on four Wikipedia Quality classes: FA, GA, B, and C. We excluded Stub and Start class articles from our sampling as these articles comparatively have fewer revisions - meaning there is no potential requirement for compression. Moreover, Class A contains a small set of articles that we merged with the GA class. Since most of the Wikipedia articles with a number of revisions greater than 1000 fall into one of the mentioned categories, these four classes were chosen to cover the articles with more consider- able lengths. Similar sampling approaches have been taken to cover articles from various topics [1]. For each article in our sample, its complete editing history in Knol-ML format was collected between the article’s creation time to November 2023. The initial sampling resulted in 10000 articles. Among them, 348 articles had very few revisions (less than 100). These were excluded from the sampling, leaving the final data set of 9652 articles. Each Knol-ML document contains an article’s entire revision history with supporting information such as the contributor’s ID, time stamp, and comments. Each revision in a Knol-ML document has an ID tag, which always starts from one for the first instance. We leverage this information to perform random access on the compressed dataset. Table 2 presents the number of articles sampled from each class.

4.3 Efficient Revision Extraction

Our approach provides an efficient compression and extraction method, optimizing both the time and space complexity. However, extracting a bulk of consecutive revisions using random extrac- tion will be highly inefficient as it will require the computation of previous revisions multiple times. Similarly, extracting all the revisions in a single pass by processing one revision at a time may not be optimal when specific revisions (such as extracting revision at a particular timestamp) are required. We propose an optimized extraction algorithm by choosing the middle ground between the mentioned two approaches. Past literature involving the Wikipedia complete revision history analysis shows the usage of only specific segments of revisions. A few examples include extracting the edit history of, Featured Articles and Good Articles during the article nomination period [33], sampled articles during the timeline of the Black Lives Matter movement [26], and a category of articles during the 2016 U.S. presidential campaign [15]. The need to extract the specific series of edits from full revision history indicates a hybrid extraction algorithm’s importance. Algorithm 1 describes the hybrid approach of retrieving a set of consecutive revisions. As described, the algorithm takes a com- pressed full revision XML dump (X) as an input, where the docu- ment X is provided as a hash table of revision IDs. Without loss of generality, we can choose the hashed items to be IDs or revision timestamps4. The interval length (𝑘) or a set of partition lengths 𝑈= {𝑘𝑞|𝑘𝑞= ||𝑝𝑞||, ∀𝑞∈[𝑁]} (in case of variable length com- pression) and the required set of revision indices [𝑙,𝑙+ 𝑗] are also provided as input. Moreover, each document 𝑋has an extra tag value representing the type of compression used (variable or fixed). If 𝑗= 0, the above algorithm reduces to the random extraction, whereas, for 𝑙= 1 and 𝑗= 𝑛, the algorithm extracts all the revisions sequentially, making this a general method. For simplicity’s sake, we assume 𝑘represents the exact interval length in the case of fixed-interval compression and𝑘= 𝑚𝑎𝑥(𝑘1,𝑘2, ...,𝑘𝑁) in the case of variable-interval compression. Each 𝑙𝑡ℎrevision ex- traction requires O(𝑘(𝑚+ 𝑑)) in time, whereas the sequential ex- traction of revisions from indices [𝑙,𝑙+ 𝑗] requires O(𝑗(𝑚+ 𝑑)). The overall time complexity becomes O((𝑘+ 𝑗)(𝑚+ 𝑑)), which is a huge reduction from O(𝑘𝑗(𝑚+ 𝑑)), if only random extraction is used for all the required revisions. However, using only the se- quential revision extraction, the overall time complexity becomes O((𝑙+ 𝑗)(𝑚+ 𝑑)), which could be costly if 𝑗≪𝑛. The algorithm uses O 𝑛

𝑘𝑚+ 𝑛−𝑛

𝑑+ (𝑚+ 𝑑) of space as the compressed document is provided as an input.

𝑘

4Wikipedia revisions are always stored in the increasing order of timestamps

5.2 Experimental Setup

We use the sampled dataset as described in the previous subsection to evaluate our proposed method. We evaluate the performance of fixed-interval length and variable-interval length methods by comparing them with various interval lengths ranging from 𝑘= 2 to 𝑘= 𝑛−1, including the interval length proposed by Ferschke et al. [7]. Moreover, to evaluate the variable-interval length compres- sion method, we chose different 𝐶(maximum time cost) values. The reason behind choosing these interval lengths is to experimentally show that our method performs the optimal compression, mini- mizing both extraction time and space complexity. As described before, the random access of revisions is essential for various appli- cations; hence we perform the comparison based on the revision’s random access time and compressed to the original document ratio. We choose to evaluate our method based on the per-article com- pression ratio instead of the overall compression ratio. The reason behind choosing this parameter lies in the fact that one article’s compression is independent of another article. Since a single revi- sion’s random access time is minimal, we calculate the access time of 100 random revisions and take the aggregate. For each article in the dataset, we calculate the mentioned two parameters and present the mean and standard deviation.

313

HT ’24, September 10–13, 2024, Poznan, Poland Amit Arjun Verma & Simran Setia

Table 3: Comparison of compression methods using various interval lengths based on revision retrieval time and compression ratio. 𝐶represents the Maximum Time Cost for variable length compression.

Time (seconds) Memory Random Revision Extraction Original to Compressed Ratio

avg std avg std

Fixed Interval Length

𝑘= 2 0.012 0.073 0.421 0.120

𝑘= √︃

𝑛(𝑚−𝑑)

𝑚+𝑑 0.110 0.308 0.167 0.096

𝑘= √𝑛 0.153 0.194 0.138 0.167

𝑘= 1000 1.431 1.85 0.101 0.129

𝑘= 𝑛−1 2.660 7.346 0.93 0.188

Variable Interval Length

𝐶= 𝑙𝑜𝑔𝑛 0.008 0.028 0.603 0.093

𝐶= 𝑛 0.033 0.116 0.311 0.129

𝐶= 𝑛𝑙𝑜𝑔𝑛 0.079 0.265 0.128 0.117

𝐶= 𝑛𝑙𝑜𝑔𝑛2 0.093 0.278 0.102 0.143

𝐶= 𝑛√𝑛 0.803 0.481 0.077 0.117

We use the Python programming language to perform the ex- periments. We use a Linux-based machine with an Intel i7-9700F CPU and 8 GB of maximum working memory. Furthermore, we calculate each extraction time five times5 and take the average.

6 RESULTS

This section first presents the high-level descriptive statistics of comparing our method with the various interval lengths. We con- sider𝑘= 1000 as the baseline method and present a detailed descrip- tion of our method’s comparison with Ferschke et al.’s 𝑘= 1000 method. Although Verma et al. provided an online method to com- press the dataset by fixing the length 𝑘= √𝑛, the results are based on preliminary analysis. Hence we consider𝑘= 1000 as the baseline state-of-the-art method for our experiments. Table 3 shows the aggregate random retrieval time and com- pression ratio for different 𝑘values. Both of our proposed methods outperform the baseline method of 𝑘= 1000 (Ferschke et al. [7]) by a large margin. We achieve an optimal random revision extraction time without compromising the compression ratio for all 𝑘values. More precisely, using the fixed-length method, we achieve an aver- age random retrieval time of 0.110 seconds, which is 13 times and 1.3 times faster than the baseline 𝑘= 1000 and Verma’s 𝑘= √𝑛, respectively. Moreover, we achieve the average compression ratio of 0.167, a ratio only 1.65 times and 1.2 times more than the ratio observed using the baseline 𝑘= 1000 and Verma’s 𝑘= √𝑛, respec- tively. We achieve a comparatively low standard deviation in terms of random revisions extraction time, indicating our method’s stable performance over all the articles. However, in terms of compres- sion ratio, we achieve a larger standard deviation. A large standard deviation is mainly because our method estimates a comparatively smaller interval length for smaller articles (revisions less than 500), increasing the compression ratio. However, the results show that optimal compression is per- formed using the variable-interval length method. Moreover, we observe the optimal compression ratio and revision retrieval time

5For random access, each revision’s access time was calculated five times, whereas, full revision access time was calculated five times for each article

when we fix the maximum time cost (𝐶) to 𝑛𝑙𝑜𝑔𝑛. The variable- interval length method ( 𝐶= 𝑛𝑙𝑜𝑔𝑛) even outperforms the fixed- interval length method in terms of time (0.079 seconds on average) respecting the same compression ratio (ratio of 0.128 on average). The reason behind this optimality is the idea of collating all the consecutive minor edits into a single block. Furthermore, given a maximum time cost, the method guarantees the optimal compres- sion.

7 CONCLUSION AND FUTURE WORK

This article proposes an online algorithm to store and access Wikipedia articles’ edit history efficiently. Our method compresses the revi- sion history by storing only the differences except at multiples of 𝑘, using fixed and variable estimation. Although we present a de- tailed analysis of compressing the revision-history dataset using the fixed-interval length and the variable-interval length compres- sion, there are a few limitations to our approach. First, instead of compressing the whole English Wikipedia dataset or the set of most edited articles, we performed experiments on a sample of articles taken from various classes. However, the sampled articles provide a brief overview of the English Wikipedia, which would not be possible if a specific set of articles were taken. Secondly, the variable-interval length method relies on finding the optimal partitioning using the dynamic programming paradigm. Given the exponential number of solutions, the time complexity of finding the optimal partitioning is pseudo-polynomial in time [29]. However, the compression task is a one-time process and is easily scalable over the new future revisions. Moreover, there exist polynomial- time approximation algorithms to find the optimal partitioning. We evaluate our method on sampled Wikipedia articles and compare the results with previously established methods. The results show that our method outperforms the previously proposed state-of- the-art methods, without compromising much on the compression ratio. Based on our proposed method, we would like to a) develop a Python-based toolkit to access the revision edits of Wikipedia articles efficiently and b) provide an open dataset of compressed Wikipedia articles employing the state-of-the-art findings.

314

An Efficient Approach to Store and Access Wikipedia’s Revision History for Large-Scale Analysis HT ’24, September 10–13, 2024, Poznan, Poland

REFERENCES

other large-scale online communities. In Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems. 1–13.

[1] Ofer Arazy, Oded Nov, Raymond Patterson, and Lisa Yeo. 2011. Information quality in Wikipedia: The effects of group composition and task conflict. Journal of Management Information Systems 27, 4 (2011), 71–98.

[29] Wikipedia contributors. 2024. Knapsack problem — Wikipedia, The Free Encyclo- pedia. https://en.wikipedia.org/w/index.php?title=Knapsackproblem&oldid= 1014657879 [Online; accessed 8-April-2021].

[2] Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017. Enriching word vectors with subword information. Transactions of the Association for Computational Linguistics 5 (2017), 135–146.

[30] Wikipedia contributors. 2024. Wikipedia:Pruning article revisions — Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/wiki/Wikipedia:Pruning articlerevisions [Online; accessed 4-April-2024].

[3] Adriane Boyd. 2018. Using Wikipedia edits in low resource grammatical error correction. In Proceedings of the 2018 EMNLP Workshop W-NUT: The 4th Workshop on Noisy User-generated Text. 79–84.

[31] Diyi Yang, Aaron Halfaker, Robert Kraut, and Eduard Hovy. 2017. Identifying semantic edit intentions from revisions in wikipedia. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. 2000–2010.

[4] Anamika Chhabra and SRS Iyengar. 2017. How Does Knowledge Come By? arXiv preprint arXiv:1705.06946 (2017).

[32] Diyi Yang, Aaron Halfaker, Robert E Kraut, and Eduard H Hovy. 2016. Who Did What: Editor Role Identification in Wikipedia.. In ICWSM. 446–455.

[5] Si-Chi Chin, W Nick Street, Padmini Srinivasan, and David Eichmann. 2010. Detecting Wikipedia vandalism with active learning and statistical language models. In Proceedings of the 4th workshop on Information credibility. 3–10.

[33] Ark Fangzhou Zhang, Danielle Livneh, Ceren Budak, Lionel P Robert Jr, and Daniel M Romero. 2017. Crowd development: The interplay between crowd evaluation and collaborative dynamics in wikipedia. Proceedings of the ACM on Human-Computer Interaction 1, CSCW (2017), 1–21.

[6] Cristian Consonni, David Laniado, and Alberto Montresor. 2019. WikiLinkGraphs: A complete, longitudinal and multi-language dataset of the Wikipedia link net- works. In Proceedings of the International AAAI Conference on Web and Social Media, Vol. 13. 598–607.

[34] Haiyi Zhu, Robert E Kraut, and Aniket Kittur. 2014. The impact of membership overlap on the survival of online communities. In CHI. 281–290.

[7] Oliver Ferschke, Torsten Zesch, and Iryna Gurevych. 2011. Wikipedia revision toolkit: efficiently accessing Wikipedia’s edit history. In ACL. Association for Computational Linguistics, 97–102.

[8] Evgeniy Gabrilovich and Shaul Markovitch. 2006. Overcoming the brittleness bottleneck using Wikipedia: Enhancing text categorization with encyclopedic knowledge. In AAAI, Vol. 6. 1301–1306.

[9] Evgeniy Gabrilovich, Shaul Markovitch, et al. 2007. Computing semantic related- ness using wikipedia-based explicit semantic analysis.. In IJcAI, Vol. 7. 1606–1611.

[10] Jana Gallus and Sudeep Bhatia. 2020. Gender, power and emotions in the col- laborative production of knowledge: A large-scale analysis of Wikipedia editor conversations. Organizational Behavior and Human Decision Processes 160 (2020), 115–130.

[11] Aaron Halfaker. 2020. MediaWiki Utilities. Retrieved April 4, 2024 from https: //pythonhosted.org/mediawiki-utilities/

[12] Paul Heckel. 1978. A technique for isolating differences between files. Commun. ACM 21, 4 (1978), 264–268.

[13] Xuan Hu, Liangcai Gao, Xiaoyan Lin, Zhi Tang, Xiaofan Lin, and Josef B Baker. 2013. Wikimirs: a mathematical information retrieval system for wikipedia. In Proceedings of the 13th ACM/IEEE-CS joint conference on Digital libraries. 11–20.

[14] James Wayne Hunt and M Douglas MacIlroy. 1976. An algorithm for differential file comparison. Bell Laboratories Murray Hill.

[15] Brian C Keegan. 2019. The Dynamics of Peer-Produced Political Information During the 2016 US Presidential Campaign. Proceedings of the ACM on Human- Computer Interaction 3, CSCW (2019), 1–20.

[16] Aniket Kittur and Robert E Kraut. 2008. Harnessing the wisdom of crowds in wikipedia: quality through coordination. In Proceedings of the 2008 ACM conference on Computer supported cooperative work. ACM, 37–46.

[17] Josh MacDonald. 2000. File system support for delta compression. Ph. D. Dis- sertation. Masters thesis. Department of Electrical Engineering and Computer Science ....

[18] Márton Mestyán, Taha Yasseri, and János Kertész. 2013. Early prediction of movie box office success based on Wikipedia activity big data. PloS one 8, 8 (2013), e71226.

[19] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 (2013).

[20] David Milne and Ian H Witten. 2013. An open-source toolkit for mining Wikipedia. Artificial Intelligence 194 (2013), 222–239.

[21] Eugene W Myers. 1986. AnO (ND) difference algorithm and its variations. Algo- rithmica 1, 1-4 (1986), 251–266.

[22] Neil Fraser. 2006. Fuzzy Patch. https://neil.fraser.name/writing/patch/ [Online; accessed 1-April-2024].

[23] Adam Roberts, Colin Raffel, and Noam Shazeer. 2020. How much knowledge can you pack into the parameters of a language model? arXiv preprint arXiv:2002.08910 (2020).

[24] Shilad Sen, Toby Jia-Jun Li, WikiBrain Team, and Brent Hecht. 2014. Wikibrain: democratizing computation on wikipedia. In Proceedings of The International Symposium on Open Collaboration. 1–10.

[25] Tuan Tran and Tu Ngoc Nguyen. 2017. Hedera: scalable indexing and exploring entities in wikipedia revision history. arXiv preprint arXiv:1701.03937 (2017).

[26] Marlon Twyman, Brian C Keegan, and Aaron Shaw. 2017. Black Lives Matter in Wikipedia: Collective memory and collaboration around online social movements. In Proceedings of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing. 1400–1412.

[27] Amit Arjun Verma, SRS Iyengar, Simran Setia, and Neeru Dubey. 2021. An Open Source Toolkit to Parse and Analyze Online Crowdsourced Portals. (2021).

[28] Nicholas Vincent, Isaac Johnson, and Brent Hecht. 2018. Examining Wikipedia with a broader lens: Quantifying the value of Wikipedia’s relationships with

315