Compressed Key Sort and Fast Index Reconstruction

In this paper we propose an index key compression scheme based on the notion of distinction bits by proving that the distinction bits of index keys are sufficient information to determine the sorted order of the index keys correctly. While the actual compression ratio may vary depending on the characteristics of datasets (an average of 2.76 to one compression ratio was observed in our experiments), the index key compression scheme leads to significant performance improvements during the reconstruction of large-scale indexes. Our index key compression can be effectively used in database replication and index recovery of modern main-memory database systems.

Introduction
Main-memory database systems have been widely used for many applications such as OLTP and OLAP, which are required to keep the latency low and the transaction throughput high. In such a main-memory database system, indexes are often deployed without on-disk representations [1,2,3,4]. By letting the indexes reside solely in memory, it can sustain the best attainable performance of the indexes, which are already critical to query and data processing performance, even in the presence of many updates. Insertions, deletions and updates made to a database table will be reflected to all the indexes associated with the table as well as the table itself. However, none of those update operations will incur any disk accesses for keeping the indexes up to date, because all the corresponding changes will only be applied to the table and the associated indexes residing in the main memory. The changes applied to the indexes will not even be written to the log or checkpointed to disk, as the most recent copy of each index can always be restored from its base table [5].
Since none of the index updates are propagated to disk, however, all the indexes have to be reconstructed from scratch when the database system restarts from a failure, an anti-cached table is loaded back from disk to memory, or an entire database is replicated from the master node to a slave node. For a table that has many indexes associated with it, the cost of loading the table may be significantly increased due to the additional cost of constructing the indexes from the rows of the table. Therefore, it is practically an important challenge to limit the cost of index reconstruction so that the database loading time and the restart time can be kept to its minimum. Table 1 shows the times taken to build a B-tree index for each of the six memory-resident tables. The times are broken down to two separate stages, namely, sort and build. Both the sort and build phases of index construction were performed by a single-core implementation. Just for the sake of comparison, the second column of the table shows the times taken to load the indexed columns from disk to memory. In all the six cases reported in Table 1, the cost of internal sort was approximately 90 percent of the total cost. Evidently, the internal sort was the dominant factor load index construction time of the B-tree index construction, and hence fast construction of memory resident B-tree indexes cannot be achieved without reducing the cost of internal sort drastically.
In this paper, we propose a new sort approach relying on the distinction bits among the keys. We call this method a compressed key sort, as utilizing only the distinction bits of the keys can be considered a kind of compressing the keys. The experimental evaluation demonstrates that the overall cost of B-tree construction can be reduced by 21-54 percent for real-world datasets. Our experiments also show that the compressed key sort is readily parallelizable for multi-core processors, yields near-linear speedup, and can actually build a B-tree index faster than loading its image from disk or even enterprise-class SSD.
The key question we pose in this paper is "What is the minimum amount of information required (in terms of the number of bits in the index keys) to determine the sorted order among the index keys correctly?" Whoever can determine it will extract the minimum number of bits from index keys and sort them still correctly but more efficiently. Once the keys are sorted, the B-tree index will be built by following the standard bulk-load procedure. This process is illustrated in Figure 1, where the top flow shows the conventional steps for index construction while the bottom one shows the proposed compressed key sort applied to index construction.
We now formally define the distinction bits of two index keys to be the most significant bits that are different between the keys. We will prove that the distinction bits of index keys are sufficient information to determine the sorted order of the index keys correctly. Consequently, we can extract only the distinction bits of index keys into compressed form and sort the compressed keys in order to construct a B-tree index quickly.
Index keys for database tables can be as short as a 4-byte word but they can also be longer than a few dozen bytes in business applications. Hence index trees and all related algorithms (sorting index keys, building the index, searching with a query key, etc.) should be able to handle long keys as well as short keys. Our compressed key sort approach assumes this wide range of index key sizes. To speed up the index construction process further, we exploit parallelism in building an index tree. This paper is organized as follows. In Section 2 we discuss related work. In Section 3 we introduce our compressed key sort. In Section 4 we describe the index key formats we use for various data types and present the metadata information to keep for efficient index rebuilding. In Section 5 we explain the procedure of rebuilding the index. Section 6 shows the results of our experiments, and we conclude in Section 7.

Related Work
There has been extensive research on efficient index structures for database tables, where efficiency measures are index size, search time, concurrency control, etc. Especially the following work focused on reducing index sizes and/or search time: Bayer [22]. See Graefe and Larson [23] and Graefe [24] for surveys.
Our work reduces the sizes of sort keys by compressing them, from which the speedups in sorting and index rebuilding are obtained. Hence our work is orthogonal to the previous work on efficient index structures, and it can be applied to many index structures. Compressing keys by distinction bits can also be applied to big data file formats. Popular self-described file formats such as ORC [25] and Parquet [26] adopt columnar storage structures to cope with read-heavy analytic workloads against large-scale distributed datasets. Compression by distinction bits can accelerate such common analytic tasks as sorting data and generating unique keys.
Kim et al.'s FAST [17] proposed a key compression technique which extracts bits of index keys in the bit positions where the index keys are not the same (which are called variant bits). We go one step further and use distinction bits to determine the sorted order of index keys correctly.
There has been research on order-preserving compression [27,28,29,30,31] which maps index keys into encoded values such that the order of index keys is the same as the order of encoded values. In order-preserving compression, index keys are replaced by encoded values. In our compression scheme, however, there is no encoding. We simply extract part of index keys (i.e., distinction bits) to speed up sorting and index building. The index tree built by our compression scheme will be a conventional B-tree index without any encoding of index keys.
For sorting in multi-core CPUs, there have recently been many results exploiting SIMD parallelism [32,33,34]. In our target applications which require a wide range of index key sizes, however, the size of index keys is too big to exploit SIMD parallelism. Thus we implemented our own parallel sorting algorithm called the row-column sort, which relies only on the operation of comparing two elements during sorting. The comparison operator is called a comparator. Therefore, the row-column sort works with any key sizes. (In contrast, sorting on SIMD needs quite different algorithmic techniques such as merging networks [32,33,34].) In our experiments we compared the row-column sort with GCC STL parallel sort [35], which is an available parallel sort code on multi-core CPUs in which a custom comparator can be used. Experiments show that the row-column sort shows a better speedup than GCC STL sort, and it is 31.4% faster than GCC STL sort when the number of cores is 16.

Compressed Key Sort
In this section we first prove that the distinction bits of index keys are sufficient information to determine the sorted order of the index keys correctly, and then present our compressed key sort based on distinction bits, which is the central idea in rebuilding main-memory indexes efficiently.

Definitions
We first introduce some terms to describe the compressed key sort. We consider key values as binary strings throughout this paper. Note that bit positions start with 0, and the bit of a key in bit position i will be called the (i + 1)-st bit of the key (i.e., the bit in bit position 0 is the first bit, the bit in bit position 1 is the second bit, etc.). The first bit (i.e., in bit position 0) is the most significant bit in the keys.
The distinction bit position of two keys is defined as the most significant bit position where the two keys differ (the bits themselves are called distinction bits). The name distinction bit 1 is from [8], but the main focus of this paper is sorting based on distinction bits 2 . Suppose that there are n+1 keys key 0 , key 1 , . . . , key n and they are in lexicographic order (sorted order), i.e., key 0 < key 1 < · · · < key n . The distinction bit position of two keys key i and key j is denoted by D-bit(key i , key j ). Let D i = D-bit(key i−1 , key i ) for 1 ≤ i ≤ n, i.e., the distinction bit position of two adjacent keys in sorted order. We prove that the set of distinction bit positions of all possible key pairs is the same as the set {D 1 , D 2 , . . . , D n }. First, we need a lemma.
Proof. We prove by induction on d = j − i. When d = 1, the lemma holds trivially. For induction hypothesis, assume that the lemma holds for d ≥ 1.
We now prove the lemma for d + 1. Let D = D-bit(key i , key j−1 ). Because (j − 1) − i = d, D = min i<k≤j−1 D k by induction hypothesis, which means that the first D bits of key i , key i+1 , . . . , key j−1 are the same. Consider D and D j (= D-bit(key j−1 , key j )).
• If D < D j , then D is D-bit(key i , key j ) because the (D + 1)-st bit of key j is the same as that of key j−1 which is different from that of key i , while the first D bits of key i , key i+1 , . . . , key j are the same. Since D = min i<k≤j−1 D k and D < D j , D = min i<k≤j D k .
• If D j < D, then D j is D-bit(key i , key j ) because the (D j + 1)-st bit of key j is different from that of key j−1 which is the same as that of key i , while the first D j bits of key i , key i+1 , . . . , key j are the same. Since D = min i<k≤j−1 D k and D j < D, D j = min i<k≤j D k .
For example, D-bit(key 1 , key 3 ) = 1 because D 2 = 1 < D 3 = 7, and D-bit(key 0 , key 2 ) = 1 because D 1 = 5 > D 2 = 1 in Figure 2 (a). Note that D cannot be equal to D j because we have only two possibilities, 0 and 1, in a bit position. Proof. Since adjacent key pairs are part of all key pairs, we have D adj ⊆ D all .
To prove D all ⊆ D adj , we show that the distinction bit position of any pair (say, key i and key j ) belongs to D adj . Without loss of generality, assume that i < j. By Lemma 1, D-bit(key i , key j ) = min i<k≤j D k . Since D k is in D adj , so is D-bit(key i , key j ). By Theorem 1, all possible distinction bit positions for n + 1 keys are D 1 , . . . , D n (i.e., there are at most n distinction bit positions), which is a crucial fact in our compressed key sort. Since some of D i values may be the same (e.g., D 1 = D 4 = 5 in Figure 2), the number of distinction bit positions can be much less than n. In Figure 2

Key Compression
Extended distinction bit positions mean all distinction bit positions plus some other (zero or more) bit positions. Let Compress(key i ) be the concatenation of the bits of key i in extended distinction bit positions. The distinction bit slice (or D-bit slice) is defined as the set {Compress(key 0 ), . . . , Compress(key n )}. See Figure 2 (b). The distinction bit slice is simply a set of Compress(key i )'s, not necessarily sorted by Compress(key i ).
Theorem 2. The distinction bit slice is sufficient information to determine the sorted order of the keys.
Proof. We first prove the theorem for the distinction bit positions. We prove that the following relation holds: for all i and j. Let D = D-bit(key i , key j ). Since the first D bits of key i and key j are the same, the order of key i and key j is determined by the bits in bit position D. By Lemma 1, bits in bit position D are in Compress (and thus in the distinction bit slice). Hence, the order between key i and key j is determined by the order between Compress(key i ) and Compress(key j ). Due to the relation above, we can correctly determine the sorted order of the keys by the distinction bit slice. Similarly, we can prove the theorem for extended distinction bit positions.
When we maintain an index for a database table, index keys may be inserted, deleted, or updated by database operations. Then distinction bit positions may be changed at runtime. For example, if key 3 is deleted in Figure 2, position 7 is no longer a distinction bit position (but it is still a variant bit position). If key 0 is also deleted, distinction bit positions don't change, but position 7 becomes an invariant bit position. If an index key is inserted, a new distinction bit position may be added. It is quite expensive to maintain the distinction bit positions accurately when delete operations are allowed. Theorem 2 allows us to lazily update distinction bit positions without affecting the correctness of sorting by letting some invalidated bit positions stay.
The scheme of extracting distinction bits of key i into Compress(key i ) for all i and sorting Compress(key i )'s rather than sorting full key values is called compressed key sort. In order to extract compressed keys from index keys, we need to keep only (extended) distinction bit positions as a bitmap. Compressed key sort is the main reason for the speedup of index reconstruction.

Remark 1.
To build an index, the sorting of index keys is necessary, which requires O(n log n) time. To compute distinction bit positions additionally, our compressed key sort needs O(n) time to compare adjacent keys in sorted order. However, our key compression is not optimal in terms of the number of bit positions if an unlimited time is allowed. For the given keys in Figure 3, our key compression selects bit positions 0, 1, and 3 as distinction bit positions, but the bit slice in bit positions 2 and 3 can correctly determine the sorted order of the keys, and this is the

Index Key Format
The B+ tree and its variants are widely used as indexes in modern DBMSs to enable fast access to data with a search key. If an index is defined on columns A 1 , . . . , A k of a table, its key can be represented as a tuple of column values, of the form (a 1 , . . . , a k ) [37]. The ordering of the tuples is the lexicographic ordering. When k = 2, for example, the order of two tuples (a 1 , a 2 ) and (b 1 , b 2 ) is determined as follows: In this section we describe how to make actual index keys from the tuples of column values so as to keep the lexicographic ordering of the tuples. We first explain how to make index keys from different data types and then explain how to make an index key from multiple columns.
For each data type (int, float, decimal, string, etc.), its index key format can be defined so that a lexicographic binary comparison in the index key format is equivalent to a comparison of original data values. For the mappings of data types int and float to index key formats, we refer readers to [20]. Here we describe the mappings of decimal and string to index key formats.
A. decimal: A decimal number x is represented by a 1-byte header and a decimal part. The last bit of the header is the sign of the decimal number (1 for negative), and the second-to-last bit indicates whether the entry is null or not (0 for null). The decimal part contains a binary number corresponding to x in log 2 (x + 1)/8 bytes. The location of the decimal point is stored in the metadata of the column. For mapping, if the sign bit is 1 (i.e., x is negative), toggle the sign bit and all bits of the decimal part; otherwise, toggle the sign bit only. Then the order of the mapped values corresponds to that of the decimal numbers. See Figure 4, where decimal(m, n) means m total digits, of which n digits are to the right of the decimal point. B. fixed-size string: We use a fixed-size string as it is. C. variable-size string with maximum length: A variable-size string with maximum length n is denoted by varchar(n). We assume that the null character (denoted by ∅) is not allowed in the variable-size string. (In the case that null characters are allowed, we need to use some (15)  encoding of characters so that the encoded string doesn't have null characters.) We attach one null character at the end of the variable-size string to make the index key value. Then the lexicographic order of index key values corresponds to that of variable-size strings as follows.
If two index keys have the same lengths, the order between them is trivially the order of the strings. If two index keys have different lengths (let k be the length of the shorter key) and their first k − 1 bytes have different values, their order is determined by the first k − 1 bytes. If two keys have different lengths and their first k − 1 bytes have the same values, the shorter one is smaller in lexicographic order because it has a null character in the k-th byte and the longer one has a non-null character in the k-th byte. For instance, if two keys are AB∅ and ABA∅, then AB∅ is smaller than ABA∅ due to the 3rd bytes and this is the lexicographic order between two strings AB and ABA. Furthermore, the distinction bit position takes place in the null character of the shorter key.
In each data type, the order between two index keys can be determined by a lexicographic binary comparison of them. We now explain how to make an index key from multiple columns. An index key on multiple columns is defined as the concatenations of index keys from the multiple columns. Suppose that an index key is defined on the following five columns: PART (int), NAME (varchar(30)), XXX (int), YYY (int), and ZZZ (varchar (15)). Example column values in some rows are shown in Figure 5 (a), and the index keys of the three rows are in Figure 5 The distinction bit positions in Section 3.1 are defined on these full index keys. If the data types of index columns have fixed lengths (as in int, float, decimal, and fixed-size string), the column values are aligned in the index keys, and the order between index keys are determined by the lexicographic order of the column values.
If the data types of index columns have variable lengths (as in variable-size string), however, the column values may not be aligned in the index keys, as shown in Figure 5 (b). Still we define distinction bit positions on these full index keys. If two rows have variable-size strings of different lengths in a column (e.g., column NAME in Figure 5), the distinction bit position takes place in that column as described above if previous columns have the same values as in Figure 5, and the order between the two index keys are determined by the lexicographic order of the variable-size strings in that column.
To compare two index keys, we make a binary comparison (by word sizes) of the two keys. If

Index Tree and DS-metadata
Although our compressed key sort can work with any variant of the B+ tree index structure, available codes for indexes have a small and fixed length for index keys (4 bytes for FAST [38] and CSB+ tree [39], and 4 or 8 bytes for k-ary search tree [14]) or some restrictions in building indexes (e.g., no parallel index building for ART [20]). Therefore, we use a full-fledged index tree which is being used in SAP HANA database system, and apply our compressed key sort to it. Figure 6 shows the structure of the index tree, which is a variant of the partial-key B+ tree [9]. To define partial keys on key values key 0 , key 1 , . . . , key n in sorted order, a parameter pk is introduced. The partial key of key i is the pk bits following the distinction bit position D i [9]. In Figure 2, the partial key of key 1 when pk = 4 is 1010, because D 1 = 5. The distinction bit position D i is also called the offset of the partial key of key i [9].
We describe the structure of the index tree in Figure 6 which is relevant to this paper. A leaf node of the index tree contains a list of entries, one for each index key, plus a pointer to the next node. An entry in a leaf node consists of a partial key, a distinction bit position, an index key length, and a record ID. The header of a leaf node contains a pointer to the last (i.e., highest) index key of the entries in the leaf node. A non-leaf node contains a list of entries, one for each child. The index key corresponding to an entry is the highest index key in the descendant leaves of the child corresponding to the entry. An entry in a non-leaf node consists of a partial key, a distinction bit position, an index key length, a pointer to the child node, and a pointer to the highest index key (where the partial key and the index key length are those of the highest index key, and the distinction bit position is that of the highest index key against the highest index key of the previous entry).
In addition, we keep the following information persistently for each index tree, which will be called the DS-metadata (DS stands for D-bit Slice). Note that we use extended distinction bit positions to define the D-bitmap. We maintain the variant bitmap and a reference key value in order to obtain partial keys when we rebuild our index tree. If partial keys are not needed in an index, the variant bitmap and a reference key value are not necessary, and we need only maintain the D-bitmap, which is the main information to keep for efficient index rebuilding.

Search and Update Operations
We describe how to perform search/insert/delete operations with the index tree and DSmetadata.
• Search: Given a search key value K, we search down the index tree for K as follows.
In a non-leaf node, we need to compare K with an index key in a non-leaf node entry. Since the entry has a pointer to the highest index key (say, A), we make a binary comparison of two full key values K and A.
A leaf node contains a list of partial keys, and thus we need to compare search key K with a list of partial keys. The procedure to compare K with a list of partial keys is the same as the one described in Bohannon et al. [9].
• Insert: Given an insert key value K, insert K into the index tree as follows.
1. Search down the index tree with K and find the right place for insertion (say, between two keys A and B). • Delete: Given a delete key value K, delete K from the index tree as follows.
We delete K as a usual deletion is done in the index tree, and simply leave the D-bitmap and the variant bitmap without changes. We need to show that the D-bitmap is valid after deleting K. Let A and B be the previous key value and the next key value of K, respectively. After An update operation is done by a delete operation followed by an insert operation. Note that if there are only insert operations (i.e., no delete operations), the D-bitmap represents the distinction bit positions exactly.
As the data in a database table change, the DS-metadata is updated incrementally as above. When an insertion occurs, at most one distinction bit position is added to the D-bitmap, and some variant bit positions may be added to the variant bitmap. This operation never reverts even if there is a delete or rollback, because implementing the revert exactly is quite expensive. Hence there may be positions in the D-bitmap whose values are 1, but which are not distinction bit positions. Also the variant bitmap may have positions whose values are 1, but which are not variant bit positions. However, they do not affect the correctness as shown in Theorem 2. Such bit positions can be removed by scanning the index and computing the DS-metadata occasionally. If we rebuild the index anew, then certainly there will be no such bit positions.
With the current DS-metadata, we can rebuild the index tree (which will be described in the next section) when it is lost or unavailable. Even after the index tree is rebuilt, we may use the current DS-metadata as the DS-metadata. However, index rebuilding is an opportune time to compute the DS-metadata anew. We compute the new DS-metadata from the current DS-metadata as follows.
1. D-bitmap: Extract compressed keys from index keys by the current D-bitmap, sort the compressed keys, and compute the distinction bit positions between adjacent compressed keys (all three steps are part of index reconstruction), which make the new D-bitmap. Note that the bit positions where the current D-bitmap had 0 remain 0 in the new D-bitmap. 2. Reference key value: Take an arbitrary index key as the reference key value. 3. Variant bitmap: Initially the variant bitmap is all 0, and we take index keys one by one (say, K) and do the following. Perform a bitwise XOR on K and the reference key value, followed by a bitwise OR on the variant bitmap and the result of the bitwise XOR (as in the insert operation above).
If we build an index tree for the first time (i.e., there is no DS-metadata at all), then we compute the D-bitmap as above, but with full index keys rather than compressed keys.

Remark 2.
Our key compression per se requires O(n) time to compute the DS-metadata initially (other than sorting) and O(1) time to update the DS-metadata for an insertion (other than O(log n) search time to find the right place to insert). Note that sorting is needed anyway to build an index tree and a search is needed anyway to find the place to insert. For the optimal algorithm described in Remark 1, finding the minimum number of bit positions after an insertion is very expensive. Any practical compression scheme should have low complexities in computing compression information such as the DS-metadata and updating the information.

Index Reconstruction
We now describe how to build the index tree in parallel from a database table loaded in memory by using the DS-metadata on the fly. We extract only the bits from the index key values whose positions are set in the D-bitmap. Figure 7 shows the overall procedure of parallel index reconstruction.
1. To collect index keys in parallel, data pages of the target table are evenly distributed to the cores. 2. Each core scans the assigned data pages and extracts compressed keys and corresponding record IDs. A pair of a compressed key and the corresponding record ID makes a sort key. The record ID is included in the sort key so that each pair of a compressed key and a record ID can be directly used to fill its corresponding leaf node entry without causing many cache misses. 3. Sort the pairs of compressed key and record ID by a parallel sorting algorithm. 4. Build the index tree in a bottom-up fashion.

Extracting Compressed Keys
Sort key compression can be done by extracting the bits in the positions which have value 1 in the D-bitmap. We now describe how to get compressed keys from index keys. (Though the examples in Figure 8 are shown in the big endian format for readability, the actual implementation was done in the little endian format due to Intel processors.) 1. Separate one-word long (8 bytes) masks from the D-bitmap. The first mask starts from the byte which contains the first 1 in the bitmap, and it is 8 bytes long. The second mask starts from the byte which contains the first 1 after the first mask, and it is 8 bytes long, and so on. In the example of Figure 8, we get three masks from the D-bitmap. See Figure 8 (c). 2. By BMI instruction PEXT [40] (which copies selected bits from the source to contiguous low-order bits of the destination), extract bits from an index key which are located in the positions where the masks have value 1. See Figure 8

Parallel Sorting
In our target applications which require a wide range of index key sizes, the size of sort keys is usually too big to exploit SIMD parallelism. Thus we implemented our own parallel sorting algorithm called the row-column sort, which is a comparison sort [41] (i.e., it relies only on the operation of comparing two elements during sorting; the comparison operator is called a comparator ). Hence the row-column sort works for any key sizes. The details of the row-column sort are described in Appendix.

Parallel Index Construction
Once the pairs of compressed index key and record ID are sorted in lexicographic order, the index tree can be built in a bottom-up fashion. First, we build leaf nodes from the sorted compressed keys and record IDs. To compute distinction bit positions, we make an array D-offset[i] from the D-bitmap, which stores the position of the (i+1)-st 1 in the D-bitmap. Then the distinction bit position of key i and key i+1 is D-offset[D-bit(Compress(key i ), Compress(key i+1 ))]. Next, we build nonleaf nodes in a bottom-up fashion. For two adjacent entries in a non-leaf node whose highest keys are key i and key j , the distinction bit position is D-offset[D-bit(Compress(key i ), Compress(key j ))].
In the case of our index tree, the leaf nodes and non-leaf nodes contain partial keys of a predefined length pk. Given the offset (i.e., distinction bit position) of a partial key and the predefined partial key length pk, the bits of the partial key are determined as follows.
A. If a bit position of the partial key is included in the compressed key, the bit value can be directly copied from the compressed key. B. If a bit position is a position which has value 0 in the variant bitmap (i.e., an invariant bit position), the bit value can be copied from the reference key value. C. Otherwise (i.e., a bit position which has value 0 in the D-bitmap and value 1 in the variant bitmap), we have two options. a) Add the bits required for partial key construction (pk bits following the distinction bit position) to the compressed key and use them here for index construction. b) Since the record ID is also contained in the sort key, necessary bits can be copied from the record, for which a dereferencing is required. To build an index, we maintain two parameters: max fanout and a fill factor. Each (leaf or non-leaf) node is of size 256B, and it has a header (24B). A leaf node also has a pointer to the next node (8B). Since each entry in a leaf node takes 16B, the max fanout (i.e., maximum number of entries) in a leaf node is (256 − 32)/16 = 14. Since each entry in a non-leaf node takes 24B, the max fanout in a non-leaf node is 9. The fill factor is defined for each index during index building, and leaf and non-leaf nodes are filled up to max fanout × fill factor [41]. Given the number of records, the max fanouts, and the fill factor (default value is 0.9), the height of the index tree can be determined.
Index construction can be parallelized by partitioning the sorted pairs of index key and record ID and constructing subtrees in parallel. That is, n sort keys are divided into p blocks of n p sort keys each, and one block is assigned to a thread (which is the situation at the end of the row-column sort). Thread i (1 ≤ i ≤ p) constructs a subtree consisting of all sort keys in the i-th block. When all the subtrees are constructed, they are merged into one tree such that the height of the resulting tree can be minimized. Since the fanouts of the root nodes of the subtrees can be much less than the max fanout, just linking the root nodes of the subtrees may increase the height of the whole tree unnecessarily. Hence we remove the root nodes of the subtrees, and build the top layers of the whole tree by linking the children of the root nodes of the subtrees. In this way the height of the whole tree can be minimized.

Experimental Settings
We conduct experiments to measure the performance improvements due to our compressed key sort. In the experiments we compare the compressed key sort against the full key sort with respect to the time for sorting and index building. We use five real datasets and one TPC-H dataset: a database table in SAP HANA that records items in sales documents (which we call INDBTAB), a complete EST (expressed sequence tag) database of Human Chromosome 14 from Genome Assembly Gold-standard Evaluations [42], Wikipedia titles [43], external links of DBpedia [44], Wikipedia links of DBpedia [44], and Part load full key sort -sort full key sort -build compressed key sort -extract compressed key sort -sort compressed key sort -build The computer used in our experiments is equipped with four Intel R Xeon R E7-8880 v4 (2.20GHz) processors, each of which contains 22 cores. The computer has 1TB DRAM memory. (Since we used no more than 16 cores in our experiments of parallelization, the experiments were done in a single processor.) Table 2 presents the basic statistics of the six datasets such as the sizes of each database table and its index tree as well as a few important characteristics and measurements relevant to our proposed scheme. The full sort key refers to the combination of an uncompressed key taken from a dataset and the corresponding record ID. The record ID is 8 bytes long, and either the whole or only the variant bits of a record ID can be used as part of a sort key. In the latter case, the variant bitmap in the DS-metadata should be expanded to include the variant bits of the record IDs. The compressed sort key consists of distinction bits in a key and variant bits in the corresponding record ID. Table 2 also shows the number of keys in a dataset, the lengths of the shortest, average, and longest keys, the number of bits in a full key, the number of distinction bits in keys, the number of variant bits in record IDs, the size of full sort keys (i.e., full key + record ID), the size of compressed sort keys (i.e., distinction bits in key + variant bits in record ID). The length of a sort key -full or compressed -is presented in the unit of 8B because sort keys are stored in words.

Evaluation with Real and Synthetic Datasets
The compression ratio and the sort key ratio are computed by the following formulas: compression ratio = # full key bits / # distinction bits in keys sort key ratio = full sort key size / compressed sort key size.
The compression ratio of our key compression scheme is 2.76 on average for the six datasets. (The percentage of distinction bit positions in full index keys is 39.8% on average.) The sort key ratio is 2.34 on average for the six datasets. (The word comparison ratio will be explained in the next subsection.) In all the experiments, comparison of two sort keys is made in the unit of 8-byte words.
Thus, for example, if two sort keys are 24B long, at most three word-comparisons will be required. Figure 9 shows the performance results from all the six datasets. The execution times of the full key sort and the compressed key sort are summarized in three bars for each dataset in the figure.
The first bar (in the white color) of each group shows the time taken to load the key column of each database table from disk. The load time is common to both sort methods and is included in the figure to show how the I/O cost is compared with the sort cost. The second and third bars of each group represent the total cost of building an index, excluding the load time, required by the  full key sort and the compressed key sort, respectively. While the second bar is broken down to two phases, sort and build, the third bar is broken down to three phases, extract, sort, and build. This is because the extract phase is needed only for the compressed key sort to obtain compressed keys by extracting bits from full keys in positions of 1s in the D-bitmap. Despite the extra phase of bit extraction, however, as is shown clearly in Figure 9, our compressed key sort reduced the total index building time substantially by expediting both the sort and build phases. The improvement ratio was 34.0% on average for the six datasets. Note that all the measurements in the figure are normalized to the same scale for the ease of presentation and comparison. The total time of building an index by the full key sort is 4.59, 21.12, 5.68, 17.63, 19.36, and 0.70 seconds for INDBTAB, Human, Wikititle, ExURL, WikiURL, and Part, respectively.
To better understand the performance differential, we looked into the distribution of distinction bit positions. Table 3 shows the distinction bit positions of INDBTAB, where distinction bit positions are set by 1. As is shown in the table, the distinction bit positions are distributed widely over many bytes of full index keys, and extracting distinction bits into a compressed key can make it shorter and improve the performance of sorting and index building. In the case of full key sort, a single key comparison will have to examine up to 22 bytes of each key (i.e., sort by distinguishing prefixes), because the last distinction bit position is in the 22nd byte in the table. In the case of compressed key sort, however, a single key comparison can be done by examining no more than 7 bytes, because there are only 56 distinction bits, which can be stored in 7 bytes. Although a compressed sort key is actually 16 bytes long due to the 27 variant bits in the record IDs, a comparison of two compressed sort keys finishes in one word-comparison because all distinction bits belong to the first word of a compressed sort key.

Sensitivity Analysis
We conduct a sensitivity analysis to see how our sort key compression scheme performs under various circumstances. The main parameters that affect the performance are the sort key ratio defined in the previous section and the word comparison ratio defined as follows: where wcc f ull is the average count of word comparisons required by a single full key comparison, and wcc comp is the average count of word comparisons required by a single compressed key comparison. We used Zipf distribution [46] to generate synthetic datasets of various configurations. Each dataset is generated by a custom function, denoted by Zipf(s, n, m), so that it contains 10 million keys of n bytes each, the first m bytes of each 8 byte word in a key have the same arbitrary ASCII value, and the remaining 8 − m bytes of each word have lower case ASCII characters following the Zipf distribution Zipf (s, 26). The parameter s is the value of the exponent characterizing the Zipf distribution. For example, Zipf(s, 16, 3) generates keys of type aaaZZZZZ aaaZZZZZ, where a is an arbitrary fixed character and Z is a byte having one of 'a' to 'z' by the Zipf distribution (s, 26).    Table 4 shows the statistics of the synthetic datasets used in the sensitivity analysis. As can be seen in the table, the datasets are generated such that they conform to the default parameter settings: word comparison ratio = 1.30 and sort key ratio = 2.00 or 3.00. In datasets 1-9, the word comparison ratio is fixed to 1.30 and the sort key ratio changes as the key size changes. In datasets 10-14 (resp. 15-20), the sort key ratio is fixed to 2.00 (resp. 3.00) and the word comparison ratio changes as m changes in Zipf(s, n, m). Figure 10 shows the index construction times by the compressed key sort in comparison with those by the full key sort. The measurements are the ratio of the former to the latter. So, the higher the ratio is, the larger the margin of improvement is by the compressed key sort. In datasets 1-9, as the sort key ratio increases, the advantage of our compressed key sort scheme grows proportionally. This is because the size of compressed sort keys gets smaller, which leads to a smaller amount of work in sorting and index building.
In datasets 10-14 (also in datasets 15-20) the number of distinction bits in each dataset is about the same, and thus the sort key ratios are identical. However, as m in Zipf(1.5, 40, m) increases, the distinction bits are more widely spread in full keys. Hence, our compression scheme has the effect of compacting widely spread distinction bits in full keys into compressed keys, which leads to a smaller number of word-comparisons in a comparison of two compressed keys. As m increases, therefore, the word comparison ratio gets bigger, which results in an improvement especially in sorting time, even though the sort key ratios remain the same. Therefore, our compression scheme improves the performance of index building in two ways: 1. by making compressed keys shorter than full keys, which leads to a smaller amount of work in sorting and index building, and 2. by compacting distinction bits in full keys into compressed keys, which leads to a smaller number of word-comparisons in a comparison of two compressed keys.
For example, whereas the sort key ratio of WikiURL is smaller than that of INDBTAB (in Table 2), the improvement of WikiURL is larger than that of INDBTAB (in Figure 9) because the word comparison ratio of WikiURL is larger than that of INDBTAB. Finally, we compare the sensitivity analysis to the experimental results with the six datasets with respect to (sort key ratio, word comparison ratio, total time ratio

Parallelization and Loading
In Section 6.2, we have shown that our compressed key sort can reduce times for both sort and index-build phases considerably. Nonetheless, the sort time still remains as the dominant portion of total index reconstruction time. In this section, we show that the sort time could be further full key sort -sort full key sort -build compressed key sort -extract compressed key sort -sort compressed key sort -build  reduced by parallelizing it on a multi-core computing platform. The choice of our sort algorithm was the row-column sort. Refer to Appendix A for the detailed description of the algorithm. Table 5 shows the detailed performance measurements from the full key sort and the compressed key sort with a varying number of cores used. Figure 11 presents the speedups observed in this experiment in the log-log scale. It clearly shows near-linear speedup in all measurements from both the full key sort and compressed key sort except for the index-building time with 16 cores, in which the speedup deteriorated because memory write (390MB in Table 2) became dominant and was not accelerated by using multiple cores. When sixteen cores were used, the speedups in the total index reconstruction time were 13.3 and 13.8 for the full key sort and the compressed key sort, respectively.
In the case of sixteen cores, the tree index of INDBTAB was reconstructed from the preloaded database table in just 0.207 seconds. Given that the memory footprint of the index tree of INDBTAB is 390MB (see Table 2), this is approximately equivalent to 1.88 GB/sec bandwidth. This level of bandwidth is higher than the peak bandwidth of enterprise class magnetic disk drives and most commodity solid state drives. We present this result as an evidence that a tree index can be reconstructed from the pre-loaded database table on the fly much more efficiently than loading the materialized image from disk.

Conclusion
We have defined the notion of distinction bit positions and proved that the bit slices of index keys in distinction bit positions are sufficient information to determine the sorted order of the index keys correctly. Consequently, utilizing only those bit slices is in effect equivalent to compressing keys losslessly in regard to sorting the keys. The key compression ratio achieved by the proposed method was 2.76:1 on average in our experiment.
We have then proposed the compressed key sort based on the distinction bit positions in order to expedite the reconstruction of a tree index from the base table in memory. The compressed key sort reduced the index reconstruction time by 34.0% on average in our experiment carried out on a single core platform. The proposed method based on distinction bit positions is essentially a lightweight key compression scheme. Thus it can be adopted in any application that involves sorting keys longer than the word size and is expected to deliver significant performance benefit. 4 28 11 15 24 16 17 29 26 31 3 22 19 2 0 23 25 18 13 8 5 21 7 12 14 20 27 6 10 1 30 9   4 28 11 15 24 16 17 29   26 31 3 22 19 2 0 23   25 18 13 8 5 21 7 12   14 20 27 6 10 1 30 9   4 11 15 16 17 24 28 29   0 2 3 19 22 23 26 31   5 7 8 12 13 18 21 25   1 6 9 10 14 20 27 30   4 11 15 16 17 24 28  n: number of elements (i.e., sort keys) p: number of threads e: size of an element (in bytes) C: last level cache size (in bytes) per thread (i.e., available L3 cache size / number of threads in our experiments) For the dataset of INDBTAB in Section 6, for instance, n is 16.39 million, and e is 48 bytes for full sort keys. Typically in our target applications, the size of sort keys is too big to exploit SIMD parallelism. Hence, the row-column sort does not rely on SIMD instructions, but it is a comparison sort [41] (i.e., it relies on the operation of comparing two elements). Algorithm 1 shows the pseudo-code of the row-column sort. The details of the algorithm are as follows.
1. (lines 2-3) Compute two parameters which are used in the algorithm: c is the number of elements that can be included in C bytes, and t is set such that n tpc ≈ tp in order to balance the workloads of line 13 and line 18. In Figure 12, n = 32 and p = 4. For simplicity, we assume in this toy example that e = 1 and c = 2. Then t is set to 1.  Figure 12. For simplicity of presentation, we assume that n tp , n tpc , and n p are integers. In Algorithm 1, each block is represented by the first position and the last position in its array (but in actual implementation only one of the first and last positions is necessary because the whole array is partitioned into blocks without overlaps). For example, init block [1] is represented by (1, n tp [1..n] by the following basic sort. The basic sort is essentially Quicksort with insertion sort as the recursion base. The Quicksort partitions around the median of the medians of three samples, each of three elements (also called the pseudo-median of 9 elements) [49]. This basic sort is fast when all the input elements are within the last level cache [49,50].

The row-column sort uses two arrays
sorting times of GCC STL sort and the row-column sort for full sort keys of INDBTAB, and Figure 13 shows the speedups of the two sorting algorithms with multiple cores. The row-column sort shows a better speedup than GCC STL sort, and it is 31.4% faster than GCC STL sort when the number of cores is 16.


TRENDNERT: A Benchmark for Trend and Downtrend Detection in a Scientific Domain

Computational analysis and modeling of the evolution of trends is an important area of research in Natural Language Processing (NLP) because of its socio-economic impact. However, no large publicly available benchmark for trend detection currently exists, making a comparative evaluation of methods impossible. We remedy this situation by publishing the benchmark TRENDNERT, consisting of a set of gold trends and downtrends and document labels that is available as an unrestricted download, and a large underlying document collection that can also be obtained for free. We propose Mean Average Precision (MAP) as an evaluation measure for trend detection and apply this measure in an investigation of several baselines.

Introduction
Science changes and evolves rapidly: novel research areas emerge, while others fade away. Keeping pace with these changes is challenging. Therefore, recognizing and forecasting research trends is of great importance for researchers and academic publishers as well as for funding agencies, companies and journalists. The task of trend detection is often solved by domain experts who use special tools to investigate the data and get useful insights from it, e.g., through data visualization. However, manual analysis of large amounts of data can be time-consuming, and domain experts are expensive. Also, the overall increase of research publications (e.g., on Google Scholar, PubMed, DBLP) in the past decade makes an approach based on human domain experts increasingly difficult whereas automated approaches become a more desirable solution for the task of trend detection (Kontostathis et al. 2004).
At its inception, a new research topic often does not attract a lot of attention from the scientific community and is represented by just a few publications. He and Chen (2018) attribute the emergence of a trend to some triggering event, e.g., the publication of an article in a high-impact journal. Then the research topic starts to grow faster and becomes a trend (He and Chen 2018). We adopt this as our definition of trend in this paper: a trend is a research topic that has Copyright c 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. a strongly increasing number of publications in a particular time interval. We define a downtrend as the converse: a downtrend is a research topic that has a strongly decreasing number of publications in a particular time interval. Downtrends can be as important to detect as trends, e.g., for a funding agency that is planning its budget.
There has been a lot of work on detecting trends in textual data, both in NLP and machine learning. However, despite the overall importance of trend analysis, no large publicly available benchmark for trend detection currently exists, making a comparative evaluation of methods impossible. Most of the prior work has used proprietary data or small datasets; or evaluation measures were not directly tied to the objectives of trend detection (Gollapalli and Li 2015).
We remedy this situation by publishing the benchmark TRENDNERT. 1 The benchmark consists of the following: 1. A set of gold trends compiled based on an extensive analysis of the metaliterature; 2. A set of labeled documents, where each document is assigned to a trend, a downtrend or to a third class, the flat topics; 3. An evaluation script to compute Mean Average Precision as the measure for the accuracy of trend detection algorithms; We make the benchmark available as an unrestricted download. 2 The underlying research corpus can be obtained for free from Semantic Scholar (Ammar et al. 2018). 3

Outline and Contributions
In this work, we address the challenge of benchmark creation for (down)trend detection. This paper is structured as follows: Section 2 discusses related work. Section 3 introduces our model for corpus creation and its components. In Section 4, we present the crowdsourcing procedure for labeling the benchmark. Section 5 introduces our evaluation measure. Section 6 describes the proposed baseline for trend detection, our experimental setup, and final results. Finally, we present the details of the distributed benchmark in Section 7 and conclude in Section 8. Our contributions are as follows: • TRENDNERT is the first publicly available benchmark for (down)trend detection.
• TRENDNERT is based on a collection of more than a million documents. It is among the largest that has been used for trend detection and therefore offers a realistic setting for developing trend detection algorithms.
• TRENDNERT addresses the task of detecting both trends and downtrends. To the best of our knowledge, the task of downtrend detection has not been addressed before.

Related Work
In addition to growth, two other characteristics of trends that have been proposed are novelty and utility, and some prior work has used this more narrow definition of trend (Tu and Seng 2012;Small, Boyack, and Klavans 2014;Rotolo, Hicks, and Martin 2015;He and Chen 2018). Unfortunately, novelty and utility are much harder to quantify automatically than growth. For this reason, we define trends in terms of growth only in this paper, i.e., a trend is a research topic that has a strongly increasing number of publications in a particular time interval. Prior work on analyzing topics and their evolution over time can be classified according to the primary source of information it employs: text, citations and key phrases.
Text-based analysis: There has been a great deal of prior work on text-based analysis for trend detection and evolution (Blei and Lafferty 2006;Wang and McCallum 2006;Hall, Jurafsky, and Manning 2008;Gollapalli and Li 2015;Gupta et al. 2018;Schein et al. 2019). However, our focus in this paper is not to develop new algorithms or models, but instead to create a benchmark. We have therefore selected a simple baseline text-based analysis method for trend detection.
Citation-based analysis is the second popular direction that is considered to be effective for trend identification (Le, Ho, and Nakamori 2005;Small 2006;He et al. 2009;Shibata et al. 2008;Shibata, Kajikawa, and Takeda 2009). This method assumes that citations in their various forms (bibliographic citations, co-citation networks, citation graphs) indicate meaningful relationships between topics and uses citations to model the topic evolution in the scientific domain. Nie and Sun (2017) utilize this approach along with Latent Dirichlet Allocation (LDA) and k-means clustering to identify research trends. The authors first use LDA to extract features and determine the optimal number of topics. Then they use k-means to obtain thematic clusters, and finally, they compute citation functions to identify the changes of clusters over time. Though the main drawback of citationbased analysis is that there are many trend detection scenarios (e.g., research news articles or research blog posts) in which citations are not available and the approach is therefore not applicable.
Keyphrase-based analysis: This approach is based on keyphrase information extracted from research papers. A keyphrase is interpreted as a representative for a single research topic. For example, Asooja et al. (2016) utilize the Saffron system (Monaghan et al. 2010) to extract keywords from LREC proceedings and then forecast trends based on regression models. A potential problem with this approach is that there is no clear correspondence between topics and keyphrases. Keyphrases are noisy, ambiguous (e.g., Java as an island vs. Java as a programming language), and many topics may not correspond to a single keyphrase because there are several equivalent names for a topic.

Corpus Creation
In this section, we describe the methodology we use to create the TRENDNERT benchmark.

Underlying Data
We use a subset of the Open Research Corpus provided by Semantic Scholar. It contains more than one million papers published mostly between 2000 and 2015 in about 5000 computer science journals and conference proceedings. 4 Each document in the collection consists of title, keyphrases, abstract and other metadata (e.g., venue, year).

Stratification
The distribution of papers over time in the underlying dataset is skewed: years before 2000 have less than 1000 documents per year (see Figure 1). 5 During our experiments, we found that clustering the entire collection or a random sample does not support high-quality identification of (down)trend candidates, because more weight is given to later years than to earlier years (see Section 6.2). Therefore, the first step in the benchmark creation was the generation of a stratified sample of the original document collection. To this end, we randomly select 10, 000 documents for each year between 2000 and 2015 for an overall sample size of 160, 000.

Document Representations & Clustering
As we mentioned before, our main focus in this paper is not to develop new algorithms or models, but instead to create a benchmark. We have therefore selected an algorithm based on k-means clustering as a simple baseline method for trend detection. In traditional document clustering (Manning, Raghavan, and Schütze 2008), documents are usually represented as bag-of-words (BOW) feature vectors that however have a major weakness: they ignore the semantics of words (Le and Mikolov 2014). Still, the recent work in representation learning and in particular doc2vec -the method proposed by Le and Mikolov (2014) -can provide representations to document clustering that overcome this weakness. The doc2vec 6 algorithm is inspired by techniques for learning word vectors (Mikolov et al. 2013) and is able to capture semantic regularities in document collections. It is an unsupervised approach for learning continuous distributed vector representations for pieces of text (i.e., paragraphs, documents). This approach maps texts into a vector space such that semantically similar documents are assigned similar vector representations (e.g., an article about genomics is closer to an article about gene expression than to an article about fuzzy sets). Other work has already successfully applied this type of document representations for topic modeling, combining them with both LDA and clustering approaches ( In our work we run doc2vec on the stratified sample of 160, 000 papers and represent each document as a lengthnormalized vector (i.e., as a document embedding). These vectors are then clustered into k = 1000 clusters using the scikit-learn 7 implementation of k-means (MacQueen 1967) with default parameters. The combination of document representations with a clustering algorithm is conceptually simple and interpretable. Also, the comprehensive comparative evaluation of topic modeling methods utilizing document embeddings performed by Curiskis et al. (2019) showed that doc2vec feature representations with k-means clustering outperform several other methods 8 on three evaluation measures (Normalized Mutual Information, Adjusted Mutual Information, and Adjusted Rand Index).
We run 10 trials of stratification and clustering, resulting in 10 different clusterings. We do this to protect against the variability of clustering and because we do not want to rely on a single clustering for proposing (down)trends for the benchmark. 6 We use the implementation provided by Gensim: https:// radimrehurek.com/gensim/models/doc2vec.html 7 https://scikit-learn.org/stable/ 8 hierarchical clustering, k-medoids, NMF and LDA

Trend & Downtrend Estimation
Recall our definitions of trend and downtrend. A trend (resp. downtrend) is a research topic that has a strongly increasing (resp. decreasing) number of publications in a particular time interval. Linear regression is a widely used technique in trend analysis (Hess, Iyer, and Malm 2001) that can identify changes over time in a variable. It correlates the measurements of the variable to the times at which they occurred. Here, we use linear regression to identify trend and downtrend candidates in a given set of clusters. We count the number of documents per year for a cluster and then estimate the slope of the best fitting line. Clusters are then ranked according to the resulting slope and the n = 150 clusters with the largest (resp. smallest) slope are selected as trend (resp. downtrend) candidates. Thus, our definition of a singleclustering (down)trend candidate is a cluster with extreme ascending or descending slope. Figure 2 gives two examples of (down)trend candidates.

(Down)trend Candidate Validation
We run ten rounds of clustering (see. Section 3.3), resulting in ten different clusterings. We then estimate the (down)trend candidates according to the procedure described in Section 3.4, so that for each of the ten clusterings, we obtain 150 trend and 150 downtrend candidates.
For our benchmark, among all the (down)trend candidates across the ten clusterings, we want to keep only those that are consistent across clusterings. To obtain such consistent (down)trend candidates, we employ the Jaccard coefficient. We define an equivalence relation ∼ R : two candidates (i.e., clusters) are equivalent if their Jaccard coefficient is ≥ τ ∼ , where τ ∼ = 0.5. We compute the equivalence classes of ∼ R over the ten clusterings. Finally, we define an equivalence class as an equivalence class trend candidate (resp. equivalence class downtrend candidate) if it contains trend (resp. downtrends) candidates in at least half of the clusterings. This procedure gave us in total 110 equivalence class trend candidates and 107 equivalence class downtrend candidates that we then annotate for our benchmark. 9

Benchmark Annotation
To annotate the equivalence class (down)trend candidates obtained from our model we used the Figure-Eight 10 platform. It provides an integrated quality-control mechanism and a training phase before the actual annotation (Kolhatkar, Zinsmeister, and Hirst 2013), which helps disqualify poorly performing annotators.
We design our annotation task as follows. A worker is shown a descriptor of a particular candidate along with the list of possible (down)trend tags (i.e., "curated" names). The descriptors of candidates are obtained through the following procedure: • First, we examine the papers assigned to a candidate cluster.
• Then we extract keywords and titles of the papers assigned to the cluster. Semantic Scholar provides keywords and titles as a part of the metadata in the underlying collection (see Section 3.1).
• Finally, we compute the top 15 most frequent keywords and randomly pick 15 titles. These keywords and titles are the descriptor of the candidate shown to crowd-workers.
We create the (down)trend tags as follows. Based on keywords, titles and metadata such as publication venue, cluster candidates are manually labeled by graduate employees (i.e., domain experts in the computer science domain). Examples of (down)trend tags created this way are "XML" and "Sentiment and Emotion Analysis (using Social Media Channels)".
In the crowdsourcing interface, the descriptor of a (down)trend candidate is shown on the right. The (down)trend tags are shown on the left. They are mixed and presented in random order. The temporal presentation order of candidates (i.e., descriptors) is also random. The worker is asked to pick from the list of (down)trend tags the tag that 9 Note that the overall number of 217 refers to the number of the (down)trend candidates and not to the number of documents. Each candidate contains hundreds of documents. 10 formerly called CrowdFlower matches the descriptor best. Even if there are several tags that are a possible match, the worker must choose one. If there is no matching tag, the worker can select the option other. Three different workers evaluate each (down)trend candidate (i.e., descriptor), and the final label is the majority label. If there is no majority label, we present the (down)trend candidate repeatedly to the workers until there is a majority.

Inter-annotator Agreement
To measure the quality of annotation, we compute the interannotator agreement -a measure of how well two (or more) annotators agree. We use two measures of inter-annotator agreement: Krippendorff's α and the Figure-Eight Internal Agreement Rate.
Krippendorff's α is a reliability coefficient developed to measure the agreement between observers (i.e., annotators) (Krippendorff 2011). We choose Krippendorff's α as an inter-annotator agreement measure because it -unlike other specialized coefficients -is a generalization of several reliability criteria and applies to situations like ours where we have more than two annotators and a given annotator only annotates a subset of the data (i.e., we have to deal with missing values). For our gold standard, Krippendorff's α for the 217 annotated down(trend) candidates (represented as descriptors) is α = 0.798. According to Landis and Koch (1977), this value corresponds to a substantial level of agreement.  Figure-Eight provides an agreement score c for each annotated unit u, which is based on the majority vote of the trusted workers. The score has been proven to perform well compared to classic metrics (Kolhatkar, Zinsmeister, and Hirst 2013). For our gold standard, the average c for the 217 annotated (down)trend candidates is 0.799.
Since both Krippendorff's α and the Figure-Eight Internal Agreement Rate are quite high, we consider the obtained annotations for the benchmark to be of good quality.

Gold Trends
We then compiled a list of computer science trends for the year 2016 based on our analysis of twelve survey publications (Augustin 2016;Frot 2016;Brooks 2016;Reese 2015;Markov 2015;Zaino 2016;Rivera 2016;Harriet 2015;IEEE Computer Society 2016;Nessma 2015;Meyerson and Mariette 2016;Ankerholz 2016). We identified a total of 31 trends; see Table 1. Since there is variation as to the name of a specific trend, we created a standard name for each. Of the 31 trends, 28 (90%) were found as trend candidates during crowdsourcing 11 . We searched for the three missing trends using a variety of techniques: inspection of non-trends/downtrends; random browsing of documents not assigned to trend candidates; and keyword searches. Two of the missing trends do not seem to occur in the collection at all: Human Augmentation and Food and Water Technology. The third missing trend is Cryptocurrency and Cryptography; it does occur in the collection, but the occurrence rate is very small (ca. 0.0001). We do not consider these three trends in the rest of the paper.
In summary, based on our analysis of the meta-literature, we identified 28 gold trends that also occur in our collection. We will use them as the gold standard that trend detection algorithms should aim to discover.

Evaluation Measure for Trend Detection
Whether something is a trend is a graded notion. For this reason, we adopt an evaluation measure that is based on a ranking of trend candidates: Mean Average Precision (MAP). The score represents the average of the precision values of ranks of correctly identified (and non-redundant) trends.
We define trend detection as computing a ranked list of sets of documents (i.e., papers), where each set is a trend candidate. We refer to documents as trendy, downtrendy or flat depending on which category they are assigned to in our benchmark. A trend candidate is called trendy, downtrendy or flat, depending on which of the three classes constitutes the plurality of documents. We count a trend candidate c as a correct recognition of gold trend t if it meets the following conditions: • c is trendy; • t is the largest trend in c; • |t ∩ c|/|c| ≥ ρ, where ρ is a coverage parameter; • t was not earlier recognized in the list.
This criterion give us a true positive (recognition of a gold trend) or false positive (otherwise) for each position of the ranked list, and a precision score for each trend that was found. Precision for a trend that was not found is 0. We then compute MAP; see Table 2 for an example.

Trend Detection Baselines
In this section, we investigate the impact of four different configuration choices on the performance of trend detection by way of ablation.

Configuration Choices
Abstracts vs. Full text. Our subset of data collection 12 contains both abstracts and full text documents. Our initial expectation was that the full text of a document contains more information than the abstract and should be a better basis for trend detection. This is one of the configuration choices we test in the ablation. We apply our proposed method on full text (document content without abstract) and abstract (only abstract) collections separately and observe the results.
Measure of Growth: Length L t of Interval. Clusters are ranked by trendiness, and the resulting ranked list is evaluated. To measure the trendiness or growth of topics over time we fit a line to an interval {(i, n i }|i 0 ≤ i < i 0 + L t } by linear regression, where L t is the length of the interval, i is one of the 16 years (2000, . . . , 2015) and n i is the number of documents that were assigned to cluster c in that year.
As a simple default baseline, we apply the regression to half the entire interval, i.e., L t = 8. There are nine such intervals in our 16-year period. As the final measure of growth for the cluster, we take the max of the nine individual slopes.
To determine how much this configuration choice affects our results, we also test a linear regression over the entire time span, i.e., L t = 16. In this case, there is a single interval.
Clustering Method. We consider Gaussian Mixture Models (GMM) and k-means. We use GMM with spherical covariance, where each component has the same variance. For both, we proceed as described in Section 3.3.

Experimental Setup and Results
We conducted experiments on the Semantic Scholar corpus and evaluated a ranked list of trend candidates against the benchmark. We used MAP as the primary evaluation measure. As a secondary evaluation measure, we compute recall at 50 (R@50), which estimates the percentage of gold trends found in the list of 50 highest-ranked trend candidates. We found that the configuration (0) in Table 3 works best. We then conducted ablation experiments to determine the importance of the configuration choices.
Comparing (0) and (1), 13 we see that abstracts (A) are a better representation for our trend detection baseline than full text (F ). This can be explained by the fact that an abstract is a summary of a scientific paper that covers only the central points, and thus it is semantically very concise and rich. In contrast, the full text contains many parts that are secondary (e.g., future work, related work) and thus may be an inferior representation of the overall meaning of the document.
Comparing (0) and (2), we observe that stratification (y) clearly improves results compared to the setting with unstratified data (n), i.e., randomly sampled data. We would   expect the effect of stratification to be even stronger for collections in which the distribution of documents over time is more skewed than in ours.
Comparing (0) and (3), the length of the interval is an important configuration choice: as we expected, the 16 year interval is too long and the 8 year interval seems to be a better choice, especially if one aims to find short-term trends.
Comparing (0) and (4), we see that topics obtained from k-means and from GMM have similar performance. How-ever, GMM, which takes variance into account and estimates a soft assignment, performs slightly better.

Benchmark Description
We now describe the contents of the TRENDNERT benchmark. It contains the following components.
1. Two files containing information about documents, one for documents assigned to (down)trends and one for documents assigned to flat topics, i.e., topics that are neither trends nor downtrends; 2. A script for generating document hash codes; 3. A file mapping hash codes to our internal IDs; 4. A script for computing MAP for a list of (down)trend candidates (default setting is ρ = .25); The two files containing information about documents give the following information for each document. • Paper ID: the internal ID we use for documents in the Semantic Scholar collection; • Cluster ID: unique ID of the equivalence class in which the document occurs; • Label: (down)trend tag assigned by crowd-workers (e.g., Cyber Security, Fuzzy Sets and Systems); • Type of (down)trend candidate: trend (T ), downtrend (D) or flat topic (F ); • Hash ID 14 of each paper from the Semantic Scholar collection;

Conclusion
With this work we release TRENDNERT -the first publicly available benchmark for (down)trend detection that offers a realistic setting for evaluating trend detection algorithms.
(  TRENDNERT also supports downtrend detection -an important problem that was not addressed before. We evaluate a number of baselines for trend detection on TREND-NERT. We find that, for these baselines, stratification improves trend detection if the distribution of documents is skewed and that abstract-based representations perform better than fulltext representations for the models included in our experiments.


extfieldsofstudy:
Computer Science
Mathematics

text:
ADER: Adaptively Distilled Exemplar Replay Towards Continual Learning for Session-based Recommendation

Session-based recommendation has received growing attention recently due to the increasing privacy concern. Despite the recent success of neural session-based recommenders, they are typically developed in an offline manner using a static dataset. However, recommendation requires continual adaptation to take into account new and obsolete items and users, and requires"continual learning"in real-life applications. In this case, the recommender is updated continually and periodically with new data that arrives in each update cycle, and the updated model needs to provide recommendations for user activities before the next model update. A major challenge for continual learning with neural models is catastrophic forgetting, in which a continually trained model forgets user preference patterns it has learned before. To deal with this challenge, we propose a method called Adaptively Distilled Exemplar Replay (ADER) by periodically replaying previous training samples (i.e., exemplars) to the current model with an adaptive distillation loss. Experiments are conducted based on the state-of-the-art SASRec model using two widely used datasets to benchmark ADER with several well-known continual learning techniques. We empirically demonstrate that ADER consistently outperforms other baselines, and it even outperforms the method using all historical data at every update cycle. This result reveals that ADER is a promising solution to mitigate the catastrophic forgetting issue towards building more realistic and scalable session-based recommenders.

The major challenge of continual learning is catastrophic forgetting [6,23]. That is, a neural model updated on new data distributions tends to forget old distributions it has learned before. A naive solution is to retrain the model using all historical data every time. However, it suffers from severe computation and storage overhead in large-scale recommendation applications.
To this end, we propose to store a small set of representative sequences from previous data, namely exemplars, and replay them each time when the recommendation model needs to be trained on new data. Methods using exemplars have shown great success in different continual learning [3,29] and reinforcement learning [2,32] tasks. In this paper, we propose to select representative exemplars of an item using an herding technique [29,36], and its exemplar size is proportional to the item frequency in the near past. To enforce a stronger constraint on not forgetting previous user preferences, we propose a regularization method based on the well-known knowledge distillation technique [12]. We propose to apply a distillation loss on the selected exemplars to preserve the model's knowledge. The distillation loss is further adaptively interpolated with the regular cross-entropy loss on the new data by considering the difference between new data and old ones to flexibly deal with different new data distributions.
Altogether, (1) we are the first to study the practical continual learning setting for the session-based recommendation task; (2) we propose a method called Adaptively Distilled Exemplar Replay (ADER) for this task, and benchmark it with state-of-the-art continual learning techniques; (3) experiment results on two widely used datasets empirically demonstrate the superior performance of ADER and its ability to mitigate catastrophic forgetting. 1

Session-based Recommendation
Session-based recommendation (SR) can be formulated as a sequence learning problem to be solved by recurrent neural networks (RNNs). The first work (GRU4Rec, [11]) uses a gated recurrent unit (GRU) to learn session representations from previous clicks. Based on GRU4Rec, [10] proposes new ranking losses on relevant sessions, and [34] proposes to augment training data. Attention operation is first used by NARM [18] to pay attention to specific parts of the sequence.
Base on NARM, [20] proposes STAMP to model users' general and short-term interests using two separate attention operations, and [30] proposes RepeatNet to predict repetitive actions in a session. Motivated by the recent success of Tansformer [35] and BERT [5] for language model tasks, [16] proposed SASRec using Transformer, and [33] proposed BERT4Rec to model bi-directional information. Despite the broad exploration and success, the above methods are all studied in a static and offline manner. Recently, the incremental and steaming nature of SR is pointed out by [9,27].
Besides neural approaches, several non-parametric methods have been proposed. [15] proposed SKNN to compare the current session with historical sessions in the training data. Lately, variations [8,21] of SKNN have been proposed to consider the position of items in a session or the timestamp of a past session. [7,[24][25][26] applies a non-parametric structure called context tree. Although these methods can be efficiently updated, the realistic continual learning setting and the corresponding forgetting issue remain to be explored.

Continual Learning
The major challenge for continual learning is catastrophic forgetting [6,23]. Methods designed to mitigate catastrophic forgetting fall into three categories: regularization [17,19,38], Exemplar Replay [3,4,29] and dynamic architectures [22,31]. Methods using dynamic architectures increase model parameters throughout the training process, which leads to an unfair comparison with other methods. In this work, we focus on the first two categories. Regularization methods add specific regularization terms to consolidate knowledge learned before. [19] introduces knowledge distillation [12] to penalize model logit change, and it is widely employed by [3,14,29,37,39]. [1,17,38] propose to penalize changes on parameters that are crucial to old knowledge according to various importance measures.

METHODOLOGY
In this section, we first introduce some background in Section 3.1 and a formulation of the continual learning setup in Section 3.2. In Section 3.3, we propose our method called "Adaptively Distilled Exemplar Replay" (ADER).

Background on Neural Session-based Recommenders
A user action in SR is a click or view on an item, and the task is to predict the next user action based on a sequence of user actions in the current web-browser session. Existing neural models f (θ ) typically contain two modules: an feature extractor ϕ(x) to compute a compact sequence representation of the sequence x of previous user actions, and an output layer ω(ϕ(x)) to predict the next user action. Various recurrent neural networks [10,11] and attention mechanisms [16,18,20] have been proposed for ϕ, and the common choices for the output layer ω is fully-connect layers [11] or bi-linear decoders [16,18]. In this paper, we base our comparison on SASRec [16], and we refer readers to model details in the original paper to avoid verbosity. Nevertheless, the techniques proposed and compared in this paper are agnostic to f (θ ), therefore, a more thorough comparison using different f (θ ) are left for interesting future work.

Formulation of Continual Learning for Session-based Recommendation
In this section, we formulate the continual learning setting for the session-based recommendation task to simulate the realistic use cases of training a recommendation model continually. To be specific, at an update cycle t, the recommendation model f (θ t −1 ) obtained until the last update cycle t − 1 needs to be updated with new incoming data the incoming data D t +1 before the next update cycle t + 1. A visualization of the continual learning setup is illustrated in Fig. 1, where a recommendation model is continually trained and tested upon receiving data in sequential update cycles.

Proposed Solution: Adaptively Distilled Exemplar Replay (ADER)
3.3.1 Exemplar Replay. To alleviate the widely-recognized catastrophic forgetting issue in continual learning, the model needs to preserve old knowledge it has learned before. To this end, we propose to store past samples,a.k.a Algorithm 1 ADER: ExemplarSelection at cycle t Train θ t with loss in Eq. (4) end while Compute E t using Algorithm 1 with θ t and M t computed by Eq. (1) Output: updated θ t and new exemplar set E t exemplars, and replay them periodically to preserve previous knowledge. To maintain a manageable memory footprint, we only store a fixed total number of exemplars throughout the entire continual learning process. Two decisions need to be made at each cycle t: (1). how many exemplars should be stored for each item/label? (2). what is the criterion for selecting exemplars of an item/label? First, we design the number of exemplars of each appeared item in I t (i.e. the set of appeared items until cycle t) to be proportional to its appearance frequency. In other words, more frequent and popular items contribute a larger portion of selected exemplars to be replayed to the next cycle. Suppose we store N exemplars in total, the number of exemplars m t,i at cycle t for a item i ∈ I t is: where the second term is the probability that item i appears in the current update cycle, as well as in the exemplars E t −1 we kept from the last cycle. Therefore, the exemplar sizes of different items to be select in the cycle t can be encoded as Second, we need to decide which samples to select as exemplars for each item. We propose to use a herding technique [29,36] to select the most representative sequences of an item in an iterative manner based on the distance to the mean feature vector of the item. In each iteration, one sample from D t ∪ E t −1 that best approximates the average feature vector (µ) over all training examples of this item (y) is selected to E t . The details are presented in Algorithm 1.

Adaptive Distillation on Exemplars.
The number of exemplars should be reasonably small to reduce memory overhead. As a consequence, the constraint to prevent the recommender forgetting previous user preference patterns is not strong enough. To enforce a stronger constrain on not forgetting old user preference patterns, we propose to use a knowledge distillation loss [12] on exemplars to better consolidate old knowledge At a cycle t, the set of exemplars to be replayed is E t −1 and the set of items till the last cycle is I t −1 , the proposed knowledge distillation (KD) loss is written as: where [p 1 , . . . ,p |I t −1 | ] is predicted distribution (softmax of logits) over I t −1 generated by f (θ t −1 ), and [p 1 , . . . , is the prediction of f (θ t ) over I t −1 . L K D measures the difference between the outputs of the previous model and the current model on exemplars, and the idea is to penalize prediction changes on items in previous update cycles. L K D defined above is interpolated with a regular cross-entropy (CE) loss computed w.r.t. D t defined below: In practice, the size of incoming data and the number of new items varies in different cycles, therefore, the degree of need to preserve old knowledge varies. To this end, we propose an adaptive weight λ t to combine L K D with L C E : In general, λ t increases when the ratio of the number of old items to that of new items increases, and when the ratio of the exemplar size to the current data size increases. The idea is to rely more on L K D when the new cycle contains fewer new items or fewer data to be learned. The overall training procedure of ADER is summarized in Algorithm 2.
As in [11,16,18,20], we remove sessions of length 1 and items that appear less than 5 times. To simulate the continual learning scenario, we split the model update cycle of DIGINETICA by weeks and YOOCHOOSE by days as its volume is much larger. Different time spans also resemble model update cycles at different granulates. In total, 16 update cycles are used to continually train the recommender on both datasets. 10% of the training data of each update cycle is randomly selected as a validation set. Statistics of split datasets are summarized in Table 1. We can see that YOOCHOOSE is less dynamic, indicated by the tiny fraction of actions on new items, that is, old items heavily reappear.

Evaluation Metrics
Two commonly used evaluation metrics are used: (1)

Baseline Methods
Several widely adopted baselines in continual learning literature are compared: • Finetune: At each cycle, the recommender trained till the last task is trained with the data from the current task.
• Dropout [28]: Dropout [13] is recently found by [28] that it effectively alleviates catastrophic forgetting. Based on Finetune, we applied dropout to every self-attention and feed-forward layer. • EWC [17]: It is a well-known method to alleviate forgetting by regularizing parameters important to previous data estimated by the diagonal of a Fisher information matrix computed w.r.t. exemplars.
• ADER (c.f. Algorithm 2): The proposed method using adaptively distilled exemplars in each cycle with dropout.
• Joint: In each cycle, the recommender is trained (with dropout) using data from the current and all historical cycles. This is a common performance "upper bound" for continual learning.
The above methods are applied on top of the state-of-the-art base SR recommender SASRec [16] using 150 hidden units and 2 stacked self-attention blocks. During continual training, we set the batch size to be 256 on DIGINETICA and 512 on YOOCHOOSE. We use Adam optimizer with a learning rate of 5e-4. A total of 100 epochs are trained, and early stop is applied if validation performance (Recall@20) does not improve for 5 consecutive epochs. Other hyper-parameters are tuned to maximize Recall@20. The dropout rate of Dropout, ADER, and Jointis set to 0.3; 30,000 exemplars are used by default for EWC and ADER; λ base of ADER is set to 0.8 on DIGINETICA and 1.0 on YOOCHOOSE.

Overall Results on Two Datasets
Results averaged over 16 update cycles are presented in Table 2, and several interesting observations can be noted: • Finetune already works reasonably well, especially on the less dynamic YOOCHOOSE dataset. The performance gap between Finetune and Joint is less significant than typical continual learning setups [14,19,29,37]. The reason is that catastrophic forgetting is not severe since old items can frequently reappear in recommendation tasks.
• EWC only outperforms Finetune marginally, and it performs worse than Dropout.
• Dropout is effective, and it notably outperforms Finetune, especially on the more dynamic DIGINETICA dataset.
• ADER significantly outperforms other methods, and the improvement margin over other methods is larger on the more dynamic DIGINETICA dataset. Furthermore, it even outperforms Joint. This result empirically reveals that ADER is a promising solution for the continual recommendation setting by effectively preserving user preference patterns learned before.
Detailed disentangled performance at each update cycle is plotted in Figure 2. We can see that the advantage of ADER is significant on the more dynamic DIGINETICA dataset. On the less dynamic YOOCHOOSE dataset, the gain of ADER mainly comes from the more dynamic starting cycles with relatively more actions on new items. At later stable cycles with few new items, different methods show comparable performance, including the vanilla Finetune.

In-depth Analysis
In following experiments, we conducted an in-depth analysis of the results on the more dynamic DIGINETICA dataset.  4 5 6 7 8 9 10 11 12 13 14 15  using 30k exemplars, we tested using only 10k/20k exemplars, and results are shown in Table 3. We can see that the performance of ADER only drops marginally as exemplar size decreases from 30k to 10k. This result reveals that ADER is insensitive to the number of exemplars, and it works reasonably well with smaller number of exemplars.

Ablation Study.
In this experiment, we compared ADER to several simplified versions to justify our design choices. (i). ER her dinд : A vanilla exemplar replay different from ADER by using a regular L C E , rather than L K D , on exemplars. (ii). ER r andom : It differs from ER her dinд by selecting exemplars of an item at random. (iii). ER loss : It differs from ER her dinд by selecting exemplars of an item with smallest L C E . (iv). ADER equal : This version differs from ADER by selecting equal number of exemplars for each item, that is, the assumption that more frequent items should be stored more is removed. (v). ADER f ix : This version differs from ADER by not using the adaptive λ t in Eq. (4), but a fixed λ.
Comparison results are presented in Table 4, and several observations can be noted: (1). Herding is effective to selected exemplars, indicated by the better performance of ER her dinд over ER r andom and ER loss . (2). The distillation loss in Eq. (2) is helpful, indicated by the better performance of three versions of ADER over three vanilla ER methods.
(3). Selecting exemplars proportional to item frequency is helpful, indicated by the better performance of ADER over ADER equal . (4). The adaptive λ t in Eq. (2) is helpful, , indicated by the better performance of ADER over ADER f ix .

CONCLUSION
In this paper, we studied the practical and realistic continual learning setting for session-based recommendation tasks.
To prevent the recommender forgetting user preferences learned before, we propose ADER by replaying carefully chosen exemplars from previous cycles and an adaptive distillation loss. Experiment results on two widely used datasets empirically demonstrate the promising performance of ADER. Our work may inspire researchers working from similar continual learning perspective for building more robust and scalable recommenders.