dataesr/scientific-paragraphs-categorization huggingface dataset:
Lucene answers conjunctive queries, like CAS queries, by evaluating each predicate on the appropriate index. The indexes return sorted postings lists that must be intersected to see if a document matches all predicates of a conjunctive query. Since the lists are sorted, the intersection can be performed efficiently. However, the independent evaluation of the predicates may yield large intermediate results, making the approach non-robust. To scale to large datasets, Lucene implements techniques that are similar to LSM trees  [32]  (cf. Section 6). The problem with separate CAS-indexing is that it is not robust. If at least one predicate of a CAS query is not selective, separate indexing approaches generate large intermediate results. This is inefficient if the final result is small. Since the predicates are evaluated on different indexes, we cannot use the more selective predicate to prune the search space.
Combined CAS indexing integrates paths and values in one index. A well-known and mature technology are composite indexes, which are used, e. g. , in relational databases to index keys that consist of more than one attribute. Composite indexes concatenate the indexed attributes according to a specified ordering. In CAS indexing, there are two possible orderings of the paths and values: the P V -ordering orders the paths before the values, while the V P -ordering orders the values first. The ordering determines what queries a composite index can evaluate efficiently. Composite indexes are only efficient for queries that have a small selectivity for the attribute appearing first. In our experiments we use the composite B+ tree of Postgres as the reference point for an efficient and scalable implementation of composite indexes.
Data Representation We use composite keys to represent the paths and values of data items in semi-structured hierarchical data. Definition 1 (Composite Key) A composite key k is a twodimensional key that consists of a path k. P and a value k. V , and each key stores a reference k. R as payload that points to the corresponding data item in the database. Given a dimension D ∈ {P, V } we write k. D to access k's path (if D = P ) or value (if D = V ). Composite keys can be extracted from popular semi-structured hierarchical data formats, such as JSON and XML. In the context of SWH we use composite keys k to represent that a file with path k. P is modified (i. e. , added, changed, or deleted) at time k. V in revision k. R. We represent paths and values as byte strings that we access byte-wise. We visualize them with one byte ASCII characters for the path dimension and italic hexadecimal numbers for the value dimension, see Table  1.
Theorem 3 Given a query Q (with ς P and ς V ) and its complementary query Q ′ (with ς ′ P = ς V and ς ′ V = ς P ), there is no interleaving that has a smaller variability than the dynamic interleaving with a perfectly alternating vector ϕ DY , i. e. , ∀ϕ ∶ | Ĉ(o, h, ϕ DY , ς P , ς V ) -Ĉ(o, h, ϕ DY , ς ′ P , ς ′ V )| ≤ | Ĉ(o, h, ϕ, ς P , ς V ) -Ĉ(o, h, ϕ, ς ′ P , ς ′ V )|. Similar to the results for the average performance, Theorem 3 can be generalized to the set of all queries. Note that in practice the search structure is not a complete tree and the fraction ς P and ς V of children that are traversed at each node is not constant. We previously evaluated the cost model experimentally on real-world datasets  [42]  and showed that the estimated and true cost of a query are off by a factor of two on average, which is a good estimate for the cost of a query.
Robust and Scalable CAS (RSCAS) Index Data-intensive applications require indexing techniques that make it possible to efficiently index, insert, and query large amounts of data. The SWH archive, for example, stores billions of revisions and every day millions of revisions are crawled from popular software forges. We propose the Robust and Scalable Content-And-Structure (RSCAS) index to provide support for querying and updating the content and structure of big hierarchical data. For robustness, the RSCAS index uses our dynamic interleaving to integrate the paths and values of composite keys in a trie structure. For scalability, RSCAS implements log-structured merge trees (LSM trees) that combine a memory-optimized trie with a series of disk-optimized tries (see Figure  5 ). Example 13 Figure  4  shows the RSCAS trie for keys K 1.
As soon as R i is complete, we replace R M 0 with R M ′ 0 and R 0 ,. , R i-1 with R i. In practice neither insertions nor queries stall as long as the insertion rate is bounded. If the insertion rate is too high and R M ′ 0 overflows before we finish bulkloading R i , we block and do not accept more insertions. This does not happen in the SWH archive since with our default of M = 10 8 keys (about 8 GB memory) trie R M ′ 0 overflows every ten days and bulk-loading the trie on our biggest dataset takes about four hours.
Query Algorithm Algorithm 1 shows the pseudocode for evaluating a CAS query on a RSCAS trie. It takes the following parameters: the current node n (initially the root node of the trie), a query path q, and a range [v l , v h ] for the value predicate. Furthermore, we need two buffers buff P and buff V (initially empty) that hold, respectively, all path and value bytes from the root to the current node n. Finally, we require state information s to evaluate the path and value predicates (we provide details as we go along) and an answer set W to collect the results. Algorithm 1: CasQuery(n, q, [v l , v h ], buff V , buff P , s, W ) 1 UpdateBuffers(n. s V , n. s P , buff V , buff P ) 2 if n is an inner node then 3 match V ← MatchValue(buff V , v l , v h , s, n) 4 match P ← MatchPath(buff P , q, s, n) 5 if match V ≠ MISMATCH ∧ match P ≠ MISMATCH then 6 for each matching child c of n do 7 CasQuery(c, q, [v l , v h ], buff V , buff P , 11 match V ← MatchValue(buff V , v l , v h , s, n) 12 match P ← MatchPath(buff P , q, s, n) 13 if match V = MATCH ∧ match P = MATCH then 14 W ← W ∪ {t.
Total I/O Overhead During Bulk-Loading The I/O overhead is the number of page I/Os without reading the input and writing the output. We use N , M , and B for the number of input keys, the number of keys that fit into memory, and the number of keys that fit into a page, respectively  [4]. We analyze the I/O overhead of Algorithm 4 for a uniform data distribution with a balanced RSCAS and for a maximally skewed distribution with an unbalanced RSCAS. The ψ-partitioning splits a partition into equally sized partitions. Thus, with a fixed fanout f the ψ-partitioning splits a partition into f , 2 ≤ f ≤ 2 8 , partitions. For maximally skewed data RSCAS deteriorates to a trie whose height is linear in the number of keys in the dataset.
Setup Environment. We use a Debian 10 server with 80 cores and 400 GB main memory. The machine has six hard disks, each 2 TB big, that are configured in a RAID 10 setup. The code is written in C++ and compiled with g++ 8. 3. 0. Datasets. We use three real-world datasets and one synthetic dataset. Table  6  provides an overview. -GitLab. The GitLab data from SWH contains archived copies of all publicly available GitLab repositories up to 2020-12-15. The dataset contains 914 593 archived repositories, which correspond to a total of 120 071 946 unique revisions and 457 839 953 unique files. For all revisions in the GitLab dataset we index the commit time and the modified files (equivalent to "commit diffstats" in version control system terminology). In total, we index 6. 9 billion composite keys similar to Table  1.
-ServerFarm. The ServerFarm dataset  [42]  mirrors the file systems of 100 Linux servers. For each server we installed a default set of packages and randomly picked a subset of optional packages. In total there are 21 million files. For each file we record the file's full path and size. -Amazon. The Amazon dataset  [18]  contains hierarchically categorized products. For each product its location in the hierarchical categorization (the path) and its price in cents (the value) are recorded. For example, the shoe 'evo' has path /sports/outdoor/running/evo and its price is 10 000 cents. -XMark. The XMark dataset  [39]  is a synthetic dataset that models a database for an internet auction site. It contains information about people, regions (subdivided by continent), etc. We generated the dataset with scale factor 500 and we index the numeric attribute 'category'.
Impact of Datasets on RSCAS's Structure In Figure  10  we show how the shape (depth and width) of the RSCAS trie adapts to the datasets. Figure  10a  shows the distribution of the node depths in the RSCAS trie for the GitLab dataset. Because of its trie-based structure not every root-to-leaf path in RSCAS has the same length (see also Figure  4 ). The average node depth is about 10, with 90% of all nodes occurring no deeper than level 14. The expected depth is log f ⌈ N τ ⌉ = log 8 ⌈ 6. 9B 100 ⌉ = 8. 7, where N is the number of keys, τ is the partitioning threshold that denotes the maximum size of a leaf partition, and f is the average fanout. The actual average depth is higher than the expected depth since the GitLab dataset is skewed and the expected depth assumes a uniformly distributed dataset.
In the Git-Lab dataset the average key length is 80 bytes, but the average node depth is 10, meaning that RSCAS successfully extracts common prefixes. Figure  10b  shows how the fanout of the nodes is distributed. Since RSCAS ψ-partitions the data at the granularity of bytes, the fanout of a node is upperbounded by 2 8 , but in practice most nodes have a smaller fanout (we cap the x-axis in Figure  10b  at fanout 40, because there is a long tail of high fanouts with low frequencies). Nodes that ψ-partition the data in the path dimension typically have a lower fanout because most paths contain only printable ASCII characters (of which there are about 100), while value bytes span the entire available byte spectrum. The shape of the RSCAS tries on the ServerFarm and Amazon datasets closely resemble that of the trie on the Git-  Lab dataset, see the second and third row in Figure  10.
This is to be expected since all three datasets contain a large number of unique paths and values, see Table  6. As a result, the data contains a large number of discriminative bytes that are needed to distinguish keys from one another. The paths in these datasets are typically longer than the values and contain more discriminative bytes. In addition, as seen above, the discriminative path bytes typically ψ-partition the data into fewer partitions than the discriminative value bytes. As a consequence, the RSCAS trie on these three datasets is narrower and deeper than the RSCAS trie on the XMark dataset, which has only seven unique paths and about 390k unique values in a dataset of 60M keys. Since the majority of the discriminative bytes in the XMark dataset are value bytes, the trie is flatter and wider on average, see the last row in Figure  10.
Query Performance Table  7  shows twelve typical CAS queries with their query path q and the value range [v l , v h ]. We show for each query the final result size and the number of keys that match the individual predicates. In addition, we provide the selectivities of the queries. The selectivity σ (σ P ) [σ V ] is computed as the fraction of all keys that match the CAS query (path predicate) [value predicate]. A salient characteristic of the queries is that the final result is orders of magnitude smaller than the results of the individual predicates. Queries Q 1 through Q 6 on the GitLab dataset increase in complexity. Q 1 looks up all revisions that modify one specific file in a short two-hour time frame. Thus, Q 1 is similar to a point query with very low selectivity in both dimensions.
The remaining queries have a higher selectivity in at least one dimension. Q 2 looks up all revisions that modify one specific file in a one-month period. Thus, its path selectivity is low but its value selectivity is high. Query Q 3 does the opposite: its path predicate matches all changes to GPU drivers using the ** wildcard, but we only look for revisions in a very narrow one-day time frame. Q 4 mixes the * and ** wildcards multiple times and puts them in different locations of the query path (in the middle and towards the end). Q 5 looks for changes to all Makefiles, using the ** wildcard at the front of the query path. Similarly, Q 6 looks for all changes to files named inode (all file extensions are accepted with the * wildcard). The remaining six queries on the other three datasets are similar.
Likewise, the composite PV index must traverse large parts of the index because the keys are ordered first by the paths and in the index. The VP index can use the value predicate to prune subtrees that do not match the value predicate before looking at the path predicate. RSCAS uses the value predicate to prune subtrees when the path predicate does not prune anymore because of wildcards and therefore delivers the best query runtime. In Figure  12  we show the runtime of queries Q 7 ,. Q 12 on the remaining three datasets (again on cold caches). The absolute runtimes are lower because the datasets are considerably smaller than the GitLab dataset, see Table  6 , but the relative differences between the approaches are comparable to the previous set of queries, see Figure  11. We repeat the same experiments on warm caches, see Figure  13  (the y-axis shows the query runtime in milliseconds).
Calibration We start out by calibrating the partitioning threshold τ , i. e. , the maximum number of suffixes in a leaf node. We calibrate τ in Figure  14  on a 100 GB subset of the GitLab dataset. Even on the 100 GB subset, bulk-loading RSCAS with τ = 1 takes more than 12 hours, see Figure  14a. When we increase τ , the recursive bulk-loading algorithm terminates earlier (see lines 15-21 in Algorithm 4), hence fewer partitions are created and the runtime improves. Since the bulk-loading algorithm extracts from every partition its longest common prefixes and stores them in a new node, the number of nodes in the index also decreases as we increase τ , see Figure  14b. As a result, leaf nodes get bigger and store more uninterleaved suffixes. This negatively affects the query performance and the index size, see Figures  14c  and 14d , respectively.
We give the systems 8 GB of main memory. For a fair comparison, we set the fill factor of the composite B+ trees in Postgres to 100% to make them read-optimized and as compact as possible since disk-based RSCAS tries are read-only. We compare the systems for our biggest dataset, the GitLab dataset, in Figure  15. The GitLab dataset contains 6. 9 billion keys and has a size of 550 GB. Figure  15a  confirms that bulk-loading RSCAS takes roughly the same time as bulk-loading the PV and VP composite indexes in Postgres (notice that RSCAS and the PV composite index have virtually the same runtime, thus PV's curve is barely visible). The runtime and disk I/O of all algorithms increase linearly in Figure  15a , which means it is feasible to bulk-load these indexes efficiently for very large datasets.
Insertion Performance New keys are first inserted into the in-memory trie R M 0 before they are written to disk when R M 0 overflows. We evaluate insertions into R M 0 in Figure  16a  and look at the insertion speed when R M 0 overflows in Figure  16b. For the latter case we compare RSCAS's on-disk insertion performance to Lucene's and Postgres'. Since R M 0 is memory-based, insertions can be performed quickly, see Figure  16a. For example, inserting 100 million keys takes less than three minutes with one insertion taking 1. 7µs, on average. In practice, the SWH archive crawls about one million revisions per day and since a revision modifies on average about 60 files in the GitLab dataset, there are 60 million insertions into the RSCAS index per day, on average. Therefore, our RSCAS index can easily keep up with the ingestion rate of the SWH archive.
Evaluating the Cost Model We evaluate the cost model from Lemma 5 that measures the I/O overhead of our bulk-loading algorithm for a uniform data distribution and compare it to the I/O overhead of bulk-loading the real-world GitLab dataset. The I/O overhead is the number of page transfers to read/write intermediate results during bulk-loading. We multiply the I/O overhead with the page size to get the number of bytes that are transferred to and from disk. The cost model in Lemma 5 has four parameters: N , M , B, and f (see Section 5. 4). We set fanout f = 10 since this is the average fanout of a node in RSCAS for the GitLab dataset, see Figure  10a. The cost model assumes that M (B) keys fit into memory (a page). Therefore, we set B = ⌈ 16 KB  80 B ⌉ = 205, where 16 KB is the page size and 80 is the average key length (see Section 8.
2). Similarly, if the memory size is 8 GB we can store M = ⌈ 8 GB 80 B ⌉ = 100 million keys in memory. In Figure  17a  we compare the actual and the estimated I/O overhead to bulk-load RSCAS as we increase the number of keys N in the dataset, keeping the memory size fixed at M = 100 million keys. The estimated and actual cost are close and within 15% of each other. In Figure  17b  we vary the memory size and fix the full GitLab dataset as input. The estimated cost is constant from M = 100 to M = 400 million keys because of the ceiling operator in log f ⌈ N M ⌉ to compute the number of levels of the trie in Lemma 5. If we increase M to 800 million keys, the trie in the cost model has one level less before partitions fit entirely into memory and therefore the I/O overhead decreases and remains con-stant thereafter since only the root partition does not fit into main memory.
), after 2M insertions R 1 (400 mil. ), and after 3M insertions again R 0 (200 mil. ) for a total of 800 million bulk-loaded keys. For M = 300 we create only two tries: after M insertions R 0 (300 mil. ) and after M insertions R 1 (600 mil. ) for a total of 900 million bulk-loaded keys. Figure  19  shows the size of the RSCAS, Lucene, and Postgres indexes for our four datasets. The RSCAS index is between 30% to 80% smaller than the input size (i. e. , the size of the indexed keys). The savings are highest for the XMark dataset because it has only seven unique paths and therefore the RSCAS trie has fewer nodes since there are fewer dis-criminative bytes. But even for a dataset with a large number of unique paths, e. g. , the GitLab dataset, RSCAS is 43% smaller than the input. RSCAS's size is comparable to that of the other indexes since all the indexes require space linear in the number of keys in the input.
We evaluate RSCAS experimentally on three real-world datasets and one synthetic data. Our experiments show that the RSCAS index outperforms state-of-the-art approaches by several orders of magnitude on real-world and synthetic datasets. We show-case RSCAS's scalability by indexing the revisions (i. e. , commits) of all public GitLab repositories archived by Software Heritage, for a total of 6. 9 billion modified files in 120 revisions. In our future work we plan to support deletions. In the in-memory RSCAS trie we plan to delete the appropriate leaf node and efficiently restructure the trie if necessary. To delete keys from the disk-resident RSCAS trie we plan to flag the appropriate leaf nodes as deleted to avoid expensive restructuring on disk. As a result, queries need to filter flagged leaf nodes.
8 ⋅ 10 -5 ) 112 037 140 (1. 6 ⋅ 10 -2 ) 10 932 756 (1. 6 ⋅ 10 -3 ) Q6 / ** /ext * /inode. * 07/08/18 29/08/18 5080 (7. 4 ⋅ 10 -7 ) 529 875 (7. 7 ⋅ 10 -5 ) 70 971 382 (1. 0 ⋅ 10 -2 ) Dataset: ServerFarm (the values are the file sizes in bytes) Q7 /usr/lib/ ** 0 kB 1 kB 512 497 (2. 4 ⋅ 10 -2 ) 2 277 518 (1. 1 ⋅ 10 -1 ) 8 403 809 (3. 9 ⋅ 10 -1 ) Q8 /usr/share/doc/ ** /README 4 kB 5 kB 521 (2. 4 ⋅ 10 -5 ) 24 698 (1. 2 ⋅ 10 -3 ) 761 513 (3. 6 ⋅ 10 -2 ) Dataset: Amazon (the values are product prices in cents) Q9 /CellPhones&Accessories/ ** 100 $ 200 $ 2758 (4. 1 ⋅ 10 -4 ) 291 625 (4. 3 ⋅ 10 -2 ) 324 272 (4. 8 ⋅ 10 -2 ) Q10 /Clothing/Women/ * /Sweaters/ ** 70 $ 100 $ 239 (3. 6 ⋅ 10 -5 ) 4654 (6. 9 ⋅ 10 -4 ) 269 936 (4. 0 ⋅ 10 -2 ) Dataset: XMark (the values denote the numeric attribute category) Q11 /site/people/ ** /interest 0 50000 1 910 524 (3.
com). The probe sequences for each gene used in this study have been deposited at Zenodo (Zenodo: https://doi. org/10. 5281/zenodo. 6592760) and is publicly available as of the date of publication. The following sequence was added to the 5 0 end of each 20 nucleotide (nt) probe: CCTCCTAAGTTTCGAGCTGGACTCAGTG, which is the reverse complement of the X flap sequence (CACTGAGTCCAGCTCGAAACTTAGGAGG) used in  (Tsanov et al. , 2016). The 5 0 -extened primary probe sets were synthesized by Integrated DNA Technologies (IDT), using 25 nmole synthesis scale, standard desalting, and at 100 mM in nuclease-free H2O. The X flap sequence, 5 0 and -3 0 end-labeled with Quasar 570, is synthesized by Biosearch Technologies. Fluorophore-labeled probe sets are prepared as described in  (Tsanov et al. , 2016) , by hybridizing the fluorophore-labeled X Flap sequence and 5 0 -extented primary probe sets.
smFISH analysis See also smFISH analysis source code in the Key resources table. Each Lin A/15 cell was segmented in 3D in ImageJ/Fiji  (Rueden et al. , 2017; Schindelin et al. , 2012; Schneider et al. , 2012) , using the LimeSeg plugin  (Machado et al. , 2019) , on the GFP channel, with the following parameters: D_0$4-6, F pressure = 0. 01, Z_scale = 6. 8, Range in d0 units$4-6, Number of integration step = À1, real XY pixel size = 50. For subsequent analysis, each segmented cell was exported into a separate ply file which was then imported in MATLAB as a point cloud (The Math Works, Inc. ). The original stacks were imported in Matlab using the Bio-Formats toolbox (https:// www. openmicroscopy. org/bio-formats/downloads/). These stacks were then cropped around each cell using the point clouds generated by individual cell segmentation with LimeSeg.
The mRNA spots were detected in 3D, in the mRNA channel of these cropped stacks, using the method described by  (Raj et al. , 2008). In short, the spots were identified computationally by running a Matlab image processing script that runs the raw data through a filter (Laplacian of a Gaussian) designed to enhance spots of the correct size and shape while removing the slowly varying background. The filtered stacks are then thresholded to disregard remaining background noise. In order to choose an optimal threshold, all possible thresholds are computed. The thresholds were always chosen manually and close to the plateau. A 'check File stack' for each cell was generated in order to visualize the accuracy of the spot detection for a given threshold. In most of our samples, common thresholds were chosen for all the cells of a given Lin A/15.
However, specific thresholds were occasionally chosen for some cells. The parameters that gave the best visual detection of mRNA spots in our datasets-check files were generated were as follow: width of the Gaussian filter = 5; variance of the Gaussian filter = 0. 25 ; threshold = 0. 11 for jim, 0. 08 for chinmo, 0. 15 for mamo, 0. 09 for br, 0. 29 for nvy and 0. 15 for oli. The detected spots in each cell had a normal distribution of diameters with a mean of 0. 25 +/-0. 05 micrometers and their maximum intensities displayed a unimodal distribution, arguing that the detected spots are mostly individual molecules. A custom Matlab routine transformed the point clouds corresponding to segmented cell volumes obtained from the LimeSeg plugin into an alpha shape (critical radius = 100) and then returned the number of mRNA contained in this cell volume using the Matlab function inShape.