dataesr/scientific-paragraphs-categorization huggingface dataset:
Datasets and aggregation functions Aggregations are operations that provide us information on the population of a random variable through the use of multiple samples. We model datasets here as multisets denoted  = (, ) where  is the set of distinct data values observed and the multiplicity function  ∶  → N + denotes the number of times the multiset contains each value in. We also define the sum operator to represent the merging of two datasets as 𝑀 𝑖 + 𝑀 𝑗 = (𝐴 𝑖 , 𝑚 𝑖 ) + (𝐴 𝑗 , 𝑚 𝑗 ) = (𝐴 ′ , 𝑚 ′ ) = 𝑀 ′ such that: 𝐴 ′ = 𝐴 𝑖 ∪ 𝐴 𝑗 and ∀𝑥 ∈ 𝐴 ′ , 𝑚 ′ (𝑥) = ⎧ ⎪ ⎨ ⎪ ⎩ 𝑚 𝑖 (𝑥), if 𝑥 ∉ 𝐴 𝑗 𝑚 𝑗 (𝑥), if 𝑥 ∉ 𝐴 𝑖 𝑚 𝑖 (𝑥) + 𝑚 𝑗 (𝑥), otherwise Notice that merging two datasets is an anonymous operation since values in  ′ does not indicate whether it comes from   or. Thus, it is impossible to identify the original and individual datasets when looking (only) at the resulting merge.
We assume here that all datasets have a set of descriptive attributes. Take for example the dataset of parking sensors deployed in Melbourne to monitor available parking spots  1. This dataset includes geographical location of more than a thousand sensors that monitor bays of multiple parking lots. We say that a function  ∶  →  preserves the sum operation of multisets iif  ( (  ) +  (  )) =  (  +   ). Commutative and associative functions satisfy such a preservation of the result. Thus, applying such a function to merged or unmerged inputs (and whatever their ordering) does not change the final value. We say that a function is an aggregation function if it preserves the sum operation and also conserves the cardinality of the resulting dataset. An aggregation function also decreases the level of details to enable k-anonymity: the cardinality remains constant after the aggregation.
More specifically, for a given aggregation function  and a set of  input datasets  1 ,  2 , … ,   such that, for easier notation, ∑ 𝑛 𝑖  𝑖 =  = (𝐴, 𝑚) and 𝑓 () = (𝐴 ′ , 𝑚 ′ ) ∑ 𝑥∈𝐴 𝑚(𝑥) = ∑ 𝑦∈𝐴 ′ 𝑚 ′ (𝑦) 𝑎𝑛𝑑 |𝐴| ≥ |𝐴 ′ | (1) Average, maximum and minimum are simple statistical functions that match this aggregation with  1  illustrates different aggregation functions with two datasets 1 and 2. The multiplicity functions resulting from the minimum () and average () functions indicate the number of input samples used as required in Eq. (  1 ). Thus, they increase privacy since the individual contributions of each producer is more complex to be inferred. For the average function, a single value is produced, whatever the number of samples. |𝐴 ′ | = 1. Such operations result in a multiset with a single value, i.
Formally:  () ≠  ( + ), for any dataset . Some functions such as the min and max functions are not sensitive to repeated values. However, the average and histogram functions are examples of functions which are sensitive. The result of such aggregations is biased to the values which are repeated. For these examples, the more values are repeated, the more bias the result will be. Any aggregation structure must account for such sensitivity, which is why trees are used to aggregate values distributively. In this work, and in order to remain as general as possible, we prefer to assume that the aggregation functions in use are sensitive to this issue.
Privacy by aggregation Applying an aggregation function to datasets removes details from the resulting dataset as the operation replaces information on individual samples with information on the population of samples (|| ≥ | ′ |). These operations can be exploited in order to provide levels of privacy similar to that of anonymous datasets. Anonymous data strategies rely on a tradeoff between utility and risk: reinforcing the aggregation decreases the level of information. However, it makes the de-anonymization harder. In other words, there is no upper bound on how much data can be aggregated together  [48]. We consider that sufficiently aggregated data is private enough to be disseminated into the network. Peering border routers are not authorized to forward data directly: they must first aggregate data to enforce the privacy requirements of the producers.
We denote () as the minimum aggregation requirement of each producer  ∈. Thus, a border router needs to achieve ()-anonymity by aggregation. When a dataset is composed of several producers, a border router must respect the highest privacy requirement among all of them. Let  be a set of producers part of a dataset, all border routers must respect the following minimum aggregation requirement: 𝑟𝑒𝑞(𝑃 ) = 𝑀𝑎𝑥 𝑝∈𝑃 (𝑟𝑒𝑞(𝑝)) (2) It is worth noting that respecting the minimum aggregation requirements creates constraints on the forwarding scheme. In particular, a producer may specify a very high minimum aggregation requirement, that prevents any peering domain to aggregate it. In conclusion the topology of domains must be sufficiently dense, and/or the minimum aggregation requirement sufficiently low to enable a global dissemination.
Properties This paper focuses on creating valid aggregations in a multi-domain environment. The following three properties must be preserved when computing aggregated data: P1 Only data of interest must be involved: Subscribers describe their interest in a query, with a collection of criteria. Our subscription scheme must identify the relevant Matching Producers (MP), i. e. , the metadata of these producers match the criteria of the query. P2 Enforce non-intersecting datasets: the aggregation is applied recursively to form a stream. Obviously, the same producer must not appear several times in this aggregation. Else, considering the same sample value multiple times leads to bias. P3 Aggregation requirements must be preserved: the aggregation must respect the minimum privacy requirement of each producer.
Publication and subscription of aggregated data Our proposal builds on top of a NDN architecture. While our previous work  [16]  assumed the domains form physically a tree topology, we propose here a publish/subscribe mechanism able to detect overlaps, and to construct globally consistent streams. Our publish/subscribe scheme proceeds in two phases: 1. Publication: routers disseminate the valid combinations of producers. Each combination forms a dataset that respects the minimum privacy requirement of each producer; 2. Subscription: the consumer constructs a query that defines its interest, and sends it to a border router of its domain. This border router is in charge of identifying the producers that match the query. It will subscribe to a subset of the matching producers, such that the privacy requirements are respected.
Creation of producer IDs Border routers propagate offers during the publication phase, with the dataset, and their metadata. Then, during the subscription, they parse the offers it received in order to identify those that match the interest of the consumer. To avoid using the same data twice in the aggregation, we need to identify the producers. More precisely, we need to identify that a data which is part of several offers is generated by the same producer. Our method maintains correct aggregation through the use of producer IDs that are used by border routers to identify the data used in aggregations. To maintain the privacy, a border router should not be able to identify the actual producer behind a producer ID. It should just use this ID to detect overlaps in the aggregation, and thus, to prevent this kind of situation.
Metadata similarities When a border router has to construct the list of datasets to publish, it must merge/aggregate some of them, else, the number of offers would increase exponentially. We propose to merge datasets that contain similar producers. More precisely, we define the metadata similarities as the distance in the descriptive space. Such distances are easy to measure for continuous attributes (e. g. , geolocation in Fig. 3 )). For categorical attributes (e. g. , device types), we need another quantification function  [49]. We assume here a similarity function  exists, that quantifies the similarity between two datasets. In Fig. 1 , domains 1, 2, and 3 produce data with metadata containing their geolocation, as well as the measurement and sensor type, its accuracy, etc. Domains 1 and 2 have very similar metadata: a border router will merge preferentially domains 1 and 2.
Publication phase Each border router has to identify the datasets it can publish, i. e. , share with its peers. An aggregation offer is a pair  = (, ) where Aggregation Set (AS) denotes the set of producer IDs that are being offered in offer  and  denotes the minimum requirement of these producers in offer. Such an offer denotes that any combination of producers  ⊆  may be enabled as an aggregated stream as long as it is compliant with the minimum requirement, i. e. , || ≥. On a high level, publication consists in filtering and/or transforming aggregation offers from incoming neighbors (input offers) and exporting aggregation offers to outgoing neighbors (output offers). Let us consider Fig. 4 , a slightly modified version of the use case described in Fig. 1. A producer domain generates data (with the corresponding producer ID), that is exported through its border router.
Completing offers to respect privacy requirements Producers initially disclose their dataset as an offer with an AS containing only their ID and  being their own (individual) requirement (see Fig. 4(a) ). Such offer naturally has a requirement larger than the available number of producers (|| = 1 < ). They correspond to what we name incomplete offers. Analogously, a complete offer respects the minimum requirement (|| ≥ ). When a border router receives an input offer which is complete, it can forward it unchanged to its peers, in the output offers. Oppositely, incomplete offers cannot be disseminated: they do not respect the privacy constraints of some producers. Border router must extend these incomplete offers before publishing them. However, a border router can merge only non-intersecting input offers.
Identification of non-intersecting offers The challenge is then to identify offers that do not intersect, and such that their union maximizes the number of producers. Indeed, we cannot have intersecting offers in the combination, else, the data from the same producer may be aggregated several times, creating statistical bias (property P2). We have first to compute the set of matching producers (i. e. , their metadata matches the query). Then, we try to identify a union of offers that: (i) contain matching producers; (ii) respect the privacy requirement of each offer; (iii) are disjoint (i. e. , do not intersect). Maximizing the number of producers in this combination allows the consumer to collect a richer dataset. Similarly to the publication problem, we must find maximal cliques in the conflict graph in order to maximize the number of producers offered to the consumer.
Exploration algorithm for subscription 1. The border router identifies the set  that match the metadata criteria defined in the query  (lines 1 and 2). We denote as () the set of metadata of the dataset offered by producer. If the number of matching producers is inferior to the minimum required in the query, we must discard it since we are certain that no answer is valid (line 3); 2. We identify the set of matching ID combinations ( * , line 5). They correspond to combinations of producers available from offers which are contained in the Matching Producers (MP) (property P3). To simplify our pseudocode, we use the   function to denote all valid combinations from offer  = (, ), i. e. ,   () = { ⊂  | || ≥ }. In our actual implementation, we do not generate all possible combinations of producers.
It is worth noting that the domain ID of the border router that actually aggregates data is unknown: inter-domain interests are forwarded hop by hop based on the offers received from the peers. In that way, privacy is preserved. Inter-domain interests may comprise a large set of producer IDs. Ideally, these IDs would be added (sorted) to the name being queried to directly rely on the NDN's default cache engine: in that way, the NDN caching features can be used without any modification. However, NDN's routing tables would use very long names, increasing significantly the lookup times. For instance, if domains use the MD5 hash function, their IDs would be fixed at 16 bytes each. A large number of IDs would be prejudicial since NDN names are assumed to be a few dozen bytes in total  [52, 53].
To avoid such an issue, we propose to use the application parameter field of interest packets. This application field will piggyback the sorted list of producer IDs. Thus, the name in the interest can be composed of an hash of this list; for example, a inter-domain interest name would typically be like /PeeringDomain/hash(ProducerIDs)/type, where PeeringDomain is the domain ID of the peer from which the offer was issued, and type is the type of data of interest (e. g. , temperature, electricity consumption/production). Such a naming convention allows for re-using the caching strategy of NDN: if the same list of producer IDs is mentioned, the cached data may be offered in response. If nothing exists in the cache, the peering border router will extract the list of producer IDs in the application parameter field and search for a peer that advertised such offer to forward the matching interest.
Similarly, intra-domain interests must include the selection criteria (aka metadata of the queries). We assume that these criteria are implemented as logical expressions on data, similarly to SQL and SPARQL queries  [54]. These expressions can be encoded as the final name component of intra-domain interests. Again, NDN's cache engine must be extended to consider this type of criteria. In our previous work  [16]  we have discussed how NDN's cache engine can be extended for hierarchical criteria. Our extensions allow the proposed inter-domain architecture to identify partially processed data in cache and apply missing processing functions in order to answer novel queries.
We denote  this set of bootstrappers. For each simulation, we generate 30 random graphs composed of two types of vertices: 1. 30 border routers (brokers) belonging to a strongly connected graph. We generate an Erdös-Rényi graph  [55]  such that each edge has a probability of 0. 15% to exist. We discard the graph if it is not strongly connected, to generate another Erdös-Rényi graph; 2. 170 producer border routers are attached to the graph of brokers (that are also border routers). More precisely, we generate 170 random locations for the producers. Then, we connect each producer to its 3 closer border routers (in space). This way, border routers offer data of similar producers according to the metadata considered. At subscription time, we generate 50 queries randomly while we set the combination exploration limit   of our scheme to 100 (i.
e. , we limit to 100 the number of combinations of offers to explore, cf. Alg. 2). Each query is generated by a border router randomly selected in the graph. Each query selects the producers located in a random rectangular area of interest. In practice, the query selects for the evaluation the | | producers (by default 50) closest to a randomly picked location. This mimics well a geographical query. Generally speaking, all the parameters used in our simulations are listed in 6 return   rather on privacy for inter-domain routing. Our solution disseminates offers in the meshed topology of border routers, that aggregate data to respect privacy constraints. In particular, the border routers are able to detect overlaps in the datasets, and to construct distributively a valid aggregation. Thus, we decided to compare the two following approaches: 1.
Metrics We compute the following metrics for each combination of parameters: Normalized answer dataset size: the number of matching producers that can be aggregated in response to a specific query by using available aggregation offers. Larger is better: the subscriber can acquire larger datasets than expected as long as the set of producers matches the query (it may be included in a larger compliant set). This value is normalized by the number of producers matching the query issued (| |). We plot distributions in the form of violin plots with our publish-subscribe algorithm. The unlimited walk algorithm does not exhibit a large variability as observed with our heuristic. Offer table size: the number of IDs in the offers available at each border router. Assuming that each ID is stored as a hash, we calculate how many bytes would be required to store all available offers.
We compute this sum using hash sizes for the md5 functions. Processing time: amount of time taken by our algorithm. For the publication stage, we measure how long each message exchanging round takes. For the subscription stage, we measure how long it takes to find the set of offers to use to answer the query. Size of enabled aggregation sets: number of producers whose data have been aggregated in a stream. We measure, at subscription time, the number of producers in the (enabled) aggregation sets to answer some query. This metric tries to quantify anonymity: individual measurements are more and more complex to de-anonymize when they regroup many values. Our figures display these metrics through the use of violin plots. These plots show the distribution of values in the vertical axis. Additionally, our plots include a mini box plot in the middle of each violin to indicate the mean, quantiles and whisker intervals.
Boundaries imposed by aggregation requirements We first use the random walk algorithm (Alg. 3) to verify the limits of achievable aggregation. Indeed, respecting the minimum requirements limits the possibilities for the aggregation. A producer cannot export data if not enough data can be collected to construct a compliant aggregation (|| > ()). We measure the normalized answer dataset size (Fig. 6 ). With a large set of matching producers, a border router can combine data from a large set of producers. The probability is higher than enough matching producers are attached to a given border router. Thus, they can aggregate all the matching producers to construct a valid offer. When the query matches 25 producers (Fig. 6 (a)), the subscriber can recursively construct a valid aggregation tree with all the matching producers (normalized answer set = 100%).
Convergence of the publication step The centralized random walk can respect any privacy requirement, and it reaches a 100% normalized answer dataset size (Fig. 7(a) ). Its convergence is immediate since it assumes a centralized, complete knowledge. Even if a producer has a very high privacy requirement, an attached border router can collect an offer that has been generated very far in the network, to aggregate it with the local producer. However, this border router relies on a complete knowledge of the topology, which creates privacy and scalability issues. For our pubsub scheme, we study the convergence of the publication phase, by measuring the average size of the answer aggregation set at the end of each round (Fig. 7(a) ). Observe that the answer is on average empty with less than 1 round: a router cannot aggregate the data of local and distant producers because of the privacy constraints.
In that case, the answer may be empty. In practice, we quantify the execution and subscription times only for non empty answers, in particular Figs. with less than 1 round. However, our system converges quickly: the normalized size of the answered dataset grows fast and quickly reaches its maximum. We observe that after only 4 rounds, the border router of the consumer is able to construct an answer aggregation set that respects the privacy constraints with almost 90% of the matching producers. We do not reach a 100% answered dataset size in all the cases since a few producers have too strict privacy requirements: our pub-sub scheme cannot satisfied them. The number of rounds depends both on the eccentricity of the graph and the minimum aggregation requirement, that may generate a larger set of incomplete offers.
While it increases slightly at the beginning since the subscriber has more offers to filter, it converges fast for the same reason as for the publication. After 4 rounds, the computation time tends to decrease since the number of offers increases. Indeed, more offers are available, and a border router can efficiently find offers to aggregate the data of all the matching producers. Thus, our subscription algorithm is efficient to construct a privacy-aware set of producers matching the query. A few dozens of milliseconds are at most required to identify which offers to combine to construct a valid dataset.
Anonymization We measure the level of aggregation that our proposed pub-sub scheme reaches (Fig. 8 ). We measure how many producers are actually aggregated compared to the requirements of each of the producers whose data is aggregated in the enabled stream. Obviously, the minimum requirement is respected: the size of enabled aggregated sets is at least equal to the requirements of each producer (the size of the aggregated set is always larger than the producer's privacy requirement). However, it is worth noting that on average, much larger aggregated sets are constructed: with a privacy requirement of 2, the aggregated sets comprise the data from more than 6 different producers. In that way, we reinforce the privacy, making the de-anoymization particularly complex. Indeed, the aggregated set is constrained by the strictest producer.
Impact of the privacy requirements We now measure the impact of the privacy requirement defined by the producers (Fig. 9 ). We only report the metrics at the end of the last round, after the system has converged. We first focus on the dataset size (Fig. 9(a) ), we see the behavior that we initially saw with our upper bound resources (sec 5. 3). Imposing larger requirements, statistically reduces the achievable answer aggregation set. Indeed, we create probabilistically more privacy constraints, and we restrict the number of producers from which the subscriber can collect data. However, even with very strict constraints, the consumer can subscribe to a significant set of producers, that have probabilistically a smaller minimum aggregation requirement. Thus, our system is robust to heterogeneous privacy constraints.
Let us focus now on the size of the offers' table for each border router (Fig. 9(b) ). The number of offers is very small when privacy is straightforward (  = 2): any border router is able to combine one or two local producers. Thus, no incomplete offer exists, border routers do not need to explore and construct complex sets of offers. A few offers for each couple of attached producers is sufficient to cover the whole dataset. More privacy means a larger number of offers to mutually combine at first. Inversely, a very high privacy implies that incomplete offers at some point cannot be combined, and are not announced. The number of offers present in the table decreases.
Impact of bootstrapping producers Let us now focus on the impact of presence of bootstrapping producers, i. e. , producers without any privacy requirement (() = 1). They  can be used by any border router to complete their incomplete offers, to allow later the subscriber to select a larger dataset. The bootstrappers reduce the number of offers (Fig. 11(a) ). Indeed, a border router does not need to generate a very large set of offers: combining one incomplete offer with a bootstrapping producer is sufficient. Mechanically, it reduces also the computation time (Fig. 11(b )), by almost 50% with 60 bootstrapping producers (one third of the producers). It is worth noting that this complexity reduction does not impact the accuracy. Indeed, the normalized answer dataset size remains unchanged (and thus not plotted): the subscriber can still use the same dataset for the answer, which is less restrictive than those without bootstrapping producers.