A universal method to compare parts from STEP files

Model Based Definition (MBD) captures the complete specification of a part in digital form and leverages (at least) the universal “Standard for the Exchange of Product” (STEP) file format. MBD has revolutionized manufacturing due to time and cost savings associated with containing all engineering data within a single digital source. This work presents a novel method to transform digital definitions in any given STEP file into a tensor-like structure that is unique for each part and can be used to regenerate the original STEP file completely. Resulting STEP tensors are amenable to part comparison based on various part specifications in a general and straightforward manner. Here, part similarity is evaluated among sets of parts according to specific geometry, material composition, and design intent. Importantly, specification similarity can be quantified using only the tensors’ structure. As such, this approach is not limited to families of geometric shapes, part types, or fabrication methods; nor does it require any prior knowledge about the parts being compared.

Introduction
Model Based Definition (MBD) represents a comprehensive information source for the entire manufacturing chain across the enterprise (Alemanni et al., 2011) and is essential for achieving the smart manufacturing paradigm. MBD can specify all requirements for manufacturing part(s). In addition to the geometric information defining the part/ assembly, it contains Product and Manufacturing Information (PMI) that includes Geometric Dimensions & Tolerances (GD&T), surface finish, material specifications data, and the like. This unification of data improves overall efficiency and eliminates redundancies, such as conversion to 2D draw- Micro & Nano Technology Section, Lawrence Livermore National Laboratory, 7000 East Ave, Livermore, CA 94550, USA ings, feeding PMI in manufacturing softwares and using multiple data formats. MBD in the form of ISO 10303 defined STEP file standard (ISO, 2021) is a widely used neutral product data format. STEP files serve as a fileexchange format, which is compatible with most of the computer aided designed (CAD) software packages, opensourced (such as FreeCAD, OpenSCAD, SALMONE, etc.), or proprietary (Autodesk, SOLIDWORKS, CATIA, Creo, etc.). It provides data exchange compatibility across the entire manufacturing chain, starting from design using CAD, analysis using computer-aided engineering, manufacturing using computer-aided manufacturing and inspection using Coordinate measuring machines. Due to its universality and versatility, STEP files are used for part specification for any type of manufacturing approach, e.g., traditional, additive, and/or advance manufacturing systems, and at all manufacturing scales.
The success of manufacturing process planning depends on how reliably a part can be fabricated and inspected using a series of production steps. Developing these production sequences for a new part or product can be a time intensive and expensive process. The starting place for this development generally involves investigating prior examples with similar geometries, materials, etc. and using what is learned as a guide. Current approaches to part comparison/similarity evaluation use only the geometry of parts. The underly-ing methods being used for this evaluation include global feature-based, graph-based, hint-based, hybrid, volumetric decomposition, and machine learning-based methods. The Literature Review section below elaborates on each of these methods and the corresponding references. Collectively, these methods suffer from a combination of insufficient degrees of robustness and generalization and may also incur significant computational costs. This works aims to overcome these challenges by leveraging the information present in MBD in STEP format and hence further increasing the production utility of STEP files. A major highlight of this work is how information embedded within the STEP file can be extracted systematically and combined into a form amenable to computationally inexpensive matrix operations. As such, part similarity can be determined from various specification types, e.g., geometric data, material properties, GD&T, and combinations thereof. This paper takes a novel approach of encoding the information of MBD in STEP format into a tensor-like structure, termed a "STEP tensor." This information is embedded in STEP files through a nested structure of keywords and user-specified arguments for those keywords. By traversing through this root-branch-leaf hierarchy, this data is populated into STEP tensor. STEP tensor is unique for each part and contains all necessary details to reconstruct the STEP file. Using these characteristics of STEP tensors, the paper demonstrates the value of this novel encoding in context of manufacturing. By applying computationally inexpensive matrix operations to STEP tensors, the similarity evaluation of a new part with prior parts in the database is conducted. For this assessment, comparison of geometry and material of parts are performed in this work. The application of this approach in manufacturing process design is presented in this paper with simple examples. However, this can be applied to complex processes and even to other domains such as part design and inventory management as well.

Literature review
Solid models are represented predominantly in three representations, namely constructive solid geometry (CSG), boundary representation (BRep), and spatial subdivision (Homann & Rossignac, 1996). Most CAD systems use BRep representation for representing solid models. In BRep representation, an object is defined by the hierarchal connection of topological entities, such as vertex, edge, face, solid, etc. These topological entities contain information of geometrical entities, such as point, curve and surface etc. (Perzylo et al., 2015). STEP file is a neutral CAD format, which uses BRep representation. ISO 10303-42:2019(ISO, 2019 defines the geometric and topological representation in a STEP file. Using this hierarchical and geometric information, researchers have proposed various approaches to identify the similarity of features and even compare three-dimensional shapes. The applications of feature recognition or 3D shape comparison span multiple disciplines such as computer vision (Büker et al., 2001), artifact comparison (Koutsoudis et al., 2012) and molecular biology (Firdaus-Raih et al., 2014). In the field of manufacturing, feature recognition has immense potential applications such as, extraction of manufacturing features such as holes (for machining tool path generation), extraction of tolerance specifications (for machine selection required for manufacturing) and extraction of similar part from a database for manufacturing process design. This prior organizational knowledge reuse is a key step to reduce a new product development time and associated cost.
Current approaches for similarity comparison transform the 3D CAD object to a shape descriptor metric or "signature" of the object, and then distinguish the objects by a dissimilarity measure which computes the distance between a pair of descriptors (Tangelder & Veltkamp, 2008). Comprehensive reviews of the different approaches for 3D shape comparison have been presented (Shah et al., 2001;Iyer et al., 2005;Babic et al., 2008). The shape searching methods are broadly classified into following categories: Global feature-based methods, graph-based methods, hint-based methods, hybrid methods, volumetric decomposition methods and machine learning based methods. Global feature-based methods use global properties of the 3D model such as moments (Elad et al., 2001), Fourier descriptors (Kazhdan et al., 2003) and geometry parameters such as surface to volume ratio. These methods capture the averaged global description of shapes. However, they fail to discriminate among locally dissimilar shapes. Graph-based methods represent a part by relational data structure such as attributed adjacency graph (AAG). This data structure contains a detail in multiple levels and facilitates comparison of local geometry (Joshi & Chang, 1988). However, the pattern searching for a real-world part is computationally expensive. Also, complex forms where two or more features interact cannot be detected using these methods. Hint-based method (Vandenbrande & Requicha, 1994) attempts to identify the interacting feature by defining "a presence rule which asserts that a feature and its associated machining operation should leave a trace in the part boundary even when features intersect". The presence of rules sacrifices the generality of the method, as they are feature specific (Shah et al., 2001). Hybrid methods are a combination of graph and hint-based methods (Gao & Shah, 1998). However, these methods still rely on predefined rules and hence cannot be generalized.
Volume decomposition methods are also capable of identifying interacting features. In these methods, the overall removable volume is identified by subtracting the part model from the stock model. This volume is decomposed into unit volumes, which are merged into macro volumes based on common faces. The feature identification then reduces into classifying these macro volumes (Han et al., 2000). These methods are computationally intensive. This is because of the effect of local geometry getting cascaded globally across the part, which increases the cell decomposition complexity (Shah et al., 2001).
Machine learning based methods for feature recognition enable dynamic approach of knowledge acquisition, leading to performace improvement. Babić et al. (2011) presents a review of Artificial neural network (ANN) techniques and other works use convolutional neural networks (Zhang et al., 2018) and  for feature recognition. All these approaches convert CAD models into a format suited for input to the machine learning techniques, based on methods such as, graph-based methods, contoursyntactic methods and heat persistence map etc. However, these machine learning techniques have some drawbacks while being used for feature recognition, such as challenges associated with identification of complex features and substantial resource required to train the models. Some recent studies, such as (Shi et al., , 2022 are focussing on the identification of intersecting features and reducing the training resources to overcome these challenges. In manufacturing arena, reserchers have mainly focused on converting low level entities present in 3D models such as points, curves etc. to high levels features such as holes and pockets. The purpose of these studies is to use the extracted features to design the manufacturing process for the part. Bhandarkar and Nagi (2000) presented a feature extraction approach using STEP AP203. Using a rule-based methodology, this approach extracts the geometrical data within the STEP file and then translate this data into manufacturing features such as holes, pockets in STEP AP224 format. STEP Manufacturing team demonstrated milling of a part using STEP AP203 as input (Hardwick et al., 2013). They used FB Mach system (Feature-Based Machining Husk) for feature extraction to convert AP 203 to AP 224, and generated tool path required for milling. Bickel et al. (2021) have presented a machine learning based method to extract most similar part to a given input part from a database using similarity search. However, in addition to the complexity associated with this method, the comparison uses geometrical entities only. CAD data in form of a neutral format such as STEP files contain other information such as material property, Geometric dimensions and tolerancing and user defined notes related to mechanical or thermal requirement of the part. This work introduces an approach to channel this enormous unexplored information within the CAD data by converting it to a machine-readable format termed the STEP tensor. A holistic comparison of parts (geometrical and material property data) is performed using this STEP tensor.

Method
STEP files embed all specifications within an ASCII readable format. The encoding mechanism of STEP file is defined in ISO 10303-21 (ISO, 2016) with a schema written in EXPRESS language, defined in ISO 10303-11 (ISO, 2004). Specifically STEP 242 ("Managed Model based 3D engineering") (ISO, 2020) has been used in this work. This ISO Application Protocol (AP) converges and replaces the earlier used AP 203 and AP 214 standards, with the addition of extended functionalities such as, 3D GD&T at assembly level and 3D shape quality. It captures both requirement data and metadata for a given part or assembly of parts. Requirement data, such as geometric, material, or other specifications, are mapped by a nested structure of keywords and user-specified arguments for those keywords that captures everything. Root keywords exist at the top of nested hierarchy of keyword(s). Underneath this root keyword are other keywords, termed as branch or leaf keywords, as well as arguments for those keywords. Leaf keywords have no branch associated with them but may still have arguments. For instance, the entire geometric specifications for an arbitrary part stem from the "MECHANICAL_DESIGN_GEOMETRIC_PRE-SENTATION_REPRESENTATION" keyword. These keywords are defined in ISO 10303-11. Along this root-branchleaf hierarchy, the information related to the faces and their orientation, edge lengths, vertex points, etc. is captured by keyword(s) and arguments within a STEP file. This relationship can be represented as a tree-like structure, termed as a STEP tree. This STEP tree and the associated arguments are used to compare the parts in this work.

STEP file structure
A STEP file may contain up to five sections (ISO, 2016) which, listed chronologically, are the Header, Anchor, Reference, Data, and Signature sections. The Header and Data sections are mandatory sections and the others are optional. Figure 1 depicts the content and purpose of each section in a STEP file. The Header section has the information regarding the context of the STEP file such as timestamp, file schema used, author's name and organization, etc. The Anchor section contains the definition of external names for instances so that they can be referenced by other files. The Reference section defines instance names whose definitions are present in external files. The Signature section is placed at the end of a STEP file and indicates that the content is verified by that signee. The Data section contains the core information of part/assembly. The topological and geometrical entities are defined in this section and this work demonstrates how the Data section is analyzed in order to compare STEP files in a systematic and universal manner. Organization of a STEP file: STEP files have five sections, whose contents are labeled here. In this work, we focus on information in Data section, which contains the topological and geometrical information of the part

Generating STEP tensors
This section describes how to convert a STEP file, specifically everything contained in the Data section, into a tensor-like structure. The resulting "STEP tensor" contains all necessary details to reconstruct the standard ASCII format of the originating Data section. In this format, STEP tensors are amenable to matrix and other analytical operations that can be used to readily compare STEP files and extract salient information contained within the Data section. The STEP tensor is unique for each part. It is straightforward to populate a database of STEP tensors of parts relevant to a manufacturing operation. This database can then be used as a tool to plan the manufacturing process for a given new part, discussed in details in Sect. 4.
A CAD model is a digital representation of a part that contains information required for defining a part's geometry. It can be exported as a STEP file. The Data section of a STEP file contains the topological and geometrical information of the part. This information is organized into many lines called instances. Each instance has a unique numerical name such as "#123 = ", followed by keyword(s) and associated argument(s) of each keyword. The arguments contain the keyword definition and typically contains references to many additional instances. The total number of these instances (present in arguments) scales with the complexity of part. The instance to the left of "=" sign is referred as a root and the instances to the right either as branches or leaves.
This hierarchy can be explained readily using an example of STEP file of a hemispherical shell with a hole punch shown in Fig. 2a. Since the entire STEP file contains 378 instances, only a small subset of instance lines is shown in Fig. 2b for clarity. For this object, the geometry is specificized by the following instance with the CLOSED_SHELL keyword whose arguments are in parenthesis, e.g. 'Hemisphere',(#137,#138,#139,#140). In Equation 1, the instance #141 is a root and the subordinate instances #137, #138, #139, and #140 are its branches. Continuing along this tree in this example, the instance #196 #196 = D I R EC T I O N ( re f _axis , 1., 0., 0.); (2) calls keyword DIRECTION with arguments 'ref_axis' and (1.,0.,0.) and, since no subsequent instance is called, #196 is one leaf of many in this tree structure. The entire hierarchy that stems from instance root #141 is mapped into a network graph in Fig. 2c. Each node in the graph labeled with its a unique instance number. The arrows point to subordinate branches or leaves, which can be invoked by multiple times by other branches within the tree. Furthermore, many unique root-branch-leaf structures exist within a given STEP file, stemming from different keyword instances. As such, these network diagrams can be very information dense and thus admittedly difficult to represent in a figure. However, though specific instance names referring to the same feature can vary between STEP files, the hierarchy and sets of nested keywords remain the same. Thus, instance labels within the plots are less important than the shape and structure of the network graphs.
Despite the inherent complexity of network diagrams, they still can be interpreted for similarity, at least on a qualitative basis. Figure 2d demonstrates this with trees derived from Fig. 2 Generating a database of STEP trees using STEP files for different parts. STEP trees for different objects, e.g. hemispherical object, cone, cylinder, or any object, are distinct. Part comparisons can be made using the structures of STEP trees to reveal the most similar part to a given new part two other example parts, namely a cone and a cylinder. Each of the "CLOSED_SHELL" trees are generated via the same methodology as described above. Since the geometric specifications contained within the respective STEP files for these parts are different, the resulting trees are distinct. By evaluating these graph visualizations, the structure of this instance offers a means of comparing similarity between various parts. To gain quantitative insights of part similarity along with other information within the Data section, STEP tensors can be constructed from the network graphs. A STEP tensor is analogous to an adjacency matrix that maps the connectivity of keywords, while also storing information about arguments for the keywords. STEP tensors of the parts are all unique trees in a given Data. A Python based code is developed for generating STEP tensor and identifying the most similar part from a database.
The procedure for generating the STEP tensor data structure consists of two tasks. In the first task, the information within each instance in the Data section of the STEP file is extracted using parsing techniques. The keywords and their associated arguments are extracted. The root-branchleaf hierarchy within the STEP file is also captured. Figure 3 walks through the process wherein the hierarchy of instances within Data section is parsed and (possibly nested) keywords and arguments are captured by the STEP tensor. For clarity, Fig. 3a and b show a subset of a Data section and resulting STEP tree, respectively. For the ease of understanding, colors have been used to show the root-branch-leaf relationship. Dashed arrows indicate subordinate sections of the tree, which are left out for clarity.
The second task, shown in Fig. 3c, consists of forming the STEP tensor, where the extracted parsed data of the previous step is stored. The STEP tensor stores a count of keyword connections of root with branches or leaves. According to the ISO standard, there exists an exhaustive set of 2997 different keywords within the STEP schema. In our code, these keywords are stored in a row vector and the position or index number of the keyword in the vector is taken as the keyword index number. Therefore, all STEP tensors are arrays of size 2997 × 2997 and each entry, whose position is defined by [row index, column index], is a list. The data in the row corresponds to the keyword index number of root and the data in the columns correspond to the keyword index number of associated branches or leaves. The diagonal elements of this array contain the count of occurrences of the roots, a list of instance names, followed by lists of associated arguments. Therefore, the off-diagonal elements contain the count of connections of roots with branches or leaves. Figure 3c walks through an example of how this formation of the STEP tensor is performed on the instance given by Eq. (1). In this work, keyword indexes are assigned in the order they appear in the ISO standard. However, the actual ordering is arbitrary in the same way elementary matrix operations allow row switching. That said, analysis, comparison, etc. among a set of STEP tensors requires a consistent assignment schema. The index number for the keyword index "CLOSED_SHELL" is 659 and for "ADVANCED_FACE" is 428. Here, the root keyword index 659 is connected to four branches of the keyword index 428. Hence, in the row keyword index 659 of the STEP tensor, the number 4 is stored in column keyword index 428 and root's data "1, ["141"] [['Hemisphere'], []]" is stored in the column index 659. For this example keyword, the last entry is a blank list, i.e. there is no floating number associated with this keyword. Another instance of this STEP file in Fig. 3c To build the entire STEP tensor, the STEP file is systematically combed with the initial root as "MECHANI-CAL_DESIGN_GEOMETRIC_ PRESENTATION_REPRE-SENTATION" keyword and then navigating through its branches and leaves present in its argument and so on. During this process, the information present in each root is extracted and populated into the STEP tensor. This process gradually builds up the STEP tensor and is complete when there are no branches left and the information present in all leaves are extracted.

Generating forest matrix
STEP tensor contains all information necessary to reconstruct the Data section of a STEP file in form of keywords and arguments, and root-branch-leaf tree structural relations between them. The Data section comprises of many "trees," each tree starting with an instance and its connected downstream network of instances. To assimilate the richness of information present in the STEP file and hence in STEP tensor, it is useful to work with condensed data structures derived from all STEP tensors. A lower dimensional (2997×2997×1) "forest matrix" can be created using the first element of each list of the STEP tensor, i.e. the number of times each keyword is used in a given STEP files. A forest matrix offers rapid qualitative insights, as it readily can be represented as an image. Figure 3d shows the forest matrix corresponding to the STEP tensor in Fig. 3c. Each (row, column) entry is color-coded by the frequency Fig. 3 Data structure of STEP tensor: The structure of a STEP file a can be mapped into a STEP tree (b). c A STEP tensor contains a frequency count of the topological connections between different keywords and geometrical information of the part. d A STEP matrix, which comprises only frequency counts, is represented visually for qualitative analysis count of keyword connections. Typically, STEP files do not make use of all possible keywords in which case the resulting forest matrices will be sparse due to all-zero rows/columns corresponding to unused keywords. Hence for clarity in visualization, the unused keywords are removed while plotting the forest matrix for rest of the paper. Using the plot of Forest matrices, an operator can quickly compare the parts quantitatively, as discussed in the next section.

Extracting material property
The build material(s) of a part plays an important role in determining its manufacturing process. Along with geometrical specifications, a STEP file also specifies the type and density of a part's material. Equation (4) presents the instance lines that store the material name of the part.
This information of the material is extracted by combing with "PROPERTY_DEFINITION_REPRESENTATION" as the root and navigating through its branch and leaf keywords namely, "PROPERTY_DEFINITION", "REPRESENT-ATION" and "DESCRIPTIVE_REPRESENTATION_ ITEM". In this example, the extracted material name is 'Steel'. The value of density can be extrated by traversing through extra keywords namely, "MEASURE _REPRESEN-TATION_ITEM" and "DERIVED_UNIT_ELEMENT". This information supplements with an extra dimension to the comparison of parts, besides the geometric comparison described earlier.

Results and discussions
STEP tensors and hence Forest matrices can be built from STEP files using the procedure described in the Method section. This section demonstrates their utility in evaluating parts similarity according to geometry and material specification through several examples. These examples illustrate simple yet effective approach which can be implemented in manufacturing workflow and support in leveraging prior experiential manufacturing process information. Forest matrices of two parts can be compared directly to reveal similarity between them, as demonstrated in Fig. 4. To illustrate this, a hemispherical shell and truncated pyramid are shown in Fig. 4a1 and b1, respectively. According to the procedure detailed in Fig. 3, their respective STEP forest matrices are generated in Fig. 4a2, b2, where unused keywords (whose row and column counts sum to zero) are hidden for clarity. Since the full (2997 × 2997) forest matrices have the same dimensions, they can be subtracted from each other, which is represented graphically in Fig. 4c. One key feature of this method is that the computational complexity and memory requirements are independent of the complexity of parts/assembly. For each case, the size of STEP tensor is always 2997 × 2997. The parts/assembly differ based on the value and location of the integer value stored in this tensor. The sparsity of the difference of forest matrices is directly proportional to the similarity between the parts. Furthermore, it is straightforward to derive a quantitative metric of the sim-ilarity. In general, two Forest matrices, e.g. F 1 and F 2 , can be subtracted from each other in an element-by-element fashion to compute the squared difference Equation (5) provides a numerical value of the (dis)similarity between objects. For two identical objects, d 2 (F 1 , F 1 ) ≡ 0. For the objects in Fig. 4a1, b1, the squared difference via Eq. (5) is d 2 =14750.
When evaluating Eq. (5) among a set of distinct objects, the most similar pair would return the smallest value. This property can be exploited for interrogating a database of STEP tensors (and associated forest matrices) to extract important production trends and design insights. For instance, a pairwise comparison between a new part's STEP tensor can be performed with all entries within this database to identify the most similar part(s) within the database. This has immense applications in manufacturing domain, especially in terms of organizing the manufacturing process data and in defining a starting point to manufacture the new part.
The identification of "the most similar part" can occur using a variety of specification(s) within each STEP file. Figure 5 illustrates the process of evaluating a database of parts for geometric similarity. While Fig. 5a1 shows this example using a set of five unique objects, the number and type of geometries is arbitrary, i.e. the technique is scalable and general. That is, for each part in the database, a STEP tensor is generated, as shown in Fig. 5a2 using the respective Forest matrices. These tensors (or subcomponents thereof) can be manipulated using standard matrix operations, e.g. Figure 4 and Eq. (5). After adding a new part (a hemisphere with a hole punch) to the database and computing its STEP tensor in Fig. 5b1, b2, the squared difference can be computed in a pairwise fashion with all other STEP tensors. When using only the portion of the STEP tensor that accounts for the geometric requirements, the object that returns the lowest squared difference value, d 2 min , exhibits the most similar geometry to the new part. Figure 5c1, c2 shows intuitively that a hollow hemisphere with d 2 min = 7248 is the most similar part. This can inform the manufacturing design process in developing the production sequence of the new part by leveraging the prior experiential process knowledge of similar parts.
As just demonstrated, a comparison that uses only the geometric portion of the forest matrix, while powerful, may be too coarse for objects with the same overall geometry with different dimensions. This can have profound consequences in a manufacturing setting since fabricating the same object at different scales, e.g. 1 cm 3 versus 1 m 3 , or different materials may require entirely different techniques. For instance, STEP

Fig. 4
Comparisons between between two objects (a1, b1) can be made by subtracting their STEP file-derived forest matrices, represented graphically (a2, b2) by removing unused keywords. c The resulting difference matrix offers rapid qualitative insights on similarity when viewed graphically, i.e. very similar objects yield a sparse difference matrix. Similarity also can be quantified via the the squared sum of every element of the difference matrix per Eq. (5) Fig. 5 Interrogating only the portion of the STEP file that defines geometric requirements of objects shown in (a1, b1) and pictorial representations of this portion of the Forest matrices (a2, b2), reveals the most similar object pairs (c1) via the most sparse difference matrix (c2) with the minimum squared difference value for the entire database, i.e. d 2 min = 7248 tensors contain information about the material properties of the parts, too. Consider two identical ingots made of steel and copper. Using the keywords described in Sect. 3.4, the 'Steel' and 'Copper' are extracted as the material name and so are the corresponding density values of 8 g/cm 3 and 8.94 g/cm 3 that live within the STEP files. This, or any, vital specification information can be used to make part families or select manufacturing processes to fabricate the parts. Thus, a more fine-tuned comparison that incorporates additional information in the STEP tensor is straightforward. Continuing with the example above that used the topological (tree hierarchy) connection data to compare objects, assume additional hemispherical objects with a hole punch were to be fabricated that each had a different shell thickness. Since these hypothetical objects all have the same parameterized geometry, the difference matrices as computed with Fig. 6 Comparison of hemispheres of different internal diameter (I.D.) using STEP tensors. The parts (Part 1 to Part 4) are compared to a reference part of I.D. = 20. Square differences clearly show the quantitative departure from the reference part Fig. 7 Investigating the capture of design intent of an example part, shown in (a), using different modeling steps, shown in (b)-(d). The squared difference shows that the design intent is not captured by the STEP file the forest matrices all return identical d 2 = 0 values. For this example, Fig. 6 illustrates a refined comparison by quantifying similarity using the information present in the STEP tensor. Again, squared difference is used when comparing the reference part (first column) to other parts arranged by increasing shell thickness. The summary table shows the most similar object to be Part 3, which has a shell thick-ness most approximate to the reference part and thus smallest non-zero squared difference, d 2 min = 42. Also, it is to be noted that the squared difference of the reference part compared to itself to equals 0 by definition. This demonstration shows that a STEP-file derived similarity quantification is functional for manufacturing environments where minute part design iterations are frequent. As such, the refined analy-sis in Fig. 6 can be useful in the rapid prototyping stage or in boutique manufacturing settings that leverage additive manufacturing platforms. Admittedly, Figs. 5 and 6 are proof-of-principle demonstrations using simple geometries, but the overall workflow of (1) performing a part comparison over an entire production data base to motivate a (2) more refined geometry-specific comparison is widely applicable due to its adaptability. For complex geometrical entities, e.g. defined by splines, further work needs to be done, which may leverage the complementary techniques detailed in Sect. 2.
Finally, the STEP tensor is used to investigate the modeling steps used to design a part. In keeping with the example part in Figs. 5, 6, and 7 compares four different design methods to create the same hemispherical shell with a hole punch. Figure 7b and c shows a wireframe that is revolved about its central axis that does and does not require a hole removed from the top, respectively. Figure 7d conducts a shell operation on a full sphere that is split into half by a central plane before cutting a hole. Figure 7e splits a hollow sphere in half before cutting a hole from the top. Four forest matrices are generated from these STEP files and compared to the reference object. With the exception of Fig. 7c, this analysis reveals all methods are geometrically equivalent. In Fig. 7c, two additional vertex points are generated and their specification within the resulting STEP tensor is detected via non-zero d 2 value. From this, it can be concluded that the STEP file captures only the connections between the geometrical entities and not the steps followed to model the part. Since the modeling steps may inform the motivation behind a given part's design and aid in downstream manufacturing activities, further work is required to capture this information. Fortunately, this new and powerful methodology can be adapted to probe the modeling steps of a part by taking advantage of various other STEP formats, e.g. (Ref: ISO 10303-55) (ISO, 2005).
While this work focuses on STEP 242 file formats for the reasons described in the Introduction section, there are many options to choose from. Some of the file formats, such as QIF, JT and IGES, can be amenable to our approach. In these cases, a simple modification to text parsing is required, after which the matrix operations we leverage in the manuscript should be applicable. Other file formats, such as STL, AMF, ACIS and Parasolid, lack data content to support MBD or are proprietary, and thus not inherently universally used.

Conclusions/future works
Model Based Definition (MBD) captures the complete specification of a part in digital form and leverages (at least) the universal "STandard for the Exchange of Product" (STEP) file format. MBD has revolutionized manufacturing due to time and cost savings associated with containing all engineer-ing data within a single digital source. This work presents a novel method of comparing parts using STEP 242, a neutral file format. Following are the contributions of this work.

A novel method of encoding the information present in
the STEP 242 into called STEP tensors, is introduced.
These tensors contain all the information present in the STEP files and are unique to a given part. 2. STEP tensors (or subcomponents thereof) can be manipulated using standard matrix operations. STEP tensors offer computationally cheap intercomparison among any set of parts in a general manner. 3. Intercomparison of parts can be used to leverage the prior knowledge of manufacturing process of similar parts. Additionally, the development of tools and analysis methods like those presented in this work can further leverage this data to improve the design and manufacturing processes. Increased focus on data collection, processing and utilization is a trend in the manufacturing community. This paper focuses primarily on geometry as a similarity metric, but STEP files contain a wealth of information about a given product.
Future work in this space could explore new applications of the STEP tensor (beyond part intercomparison), exploring new ways to integrate this tool into the design and manufacturing workflow. The STEP tensor could also be extended to include more PMI, such as GD&T and surface finish data. The natural extensibility of this method to include any information present in STEP file is a natural strength of the approach.


Robots Still Outnumber Humans in Web Archives, But Less Than Before

To identify robots and humans and analyze their respective access patterns, we used the Internet Archive's (IA) Wayback Machine access logs from 2012 and 2019, as well as Arquivo.pt's (Portuguese Web Archive) access logs from 2019. We identified user sessions in the access logs and classified those sessions as human or robot based on their browsing behavior. To better understand how users navigate through the web archives, we evaluated these sessions to discover user access patterns. Based on the two archives and between the two years of IA access logs (2012 vs. 2019), we present a comparison of detected robots vs. humans and their user access patterns and temporal preferences. The total number of robots detected in IA 2012 is greater than in IA 2019 (21% more in requests and 18% more in sessions). Robots account for 98% of requests (97% of sessions) in Arquivo.pt (2019). We found that the robots are almost entirely limited to"Dip"and"Skim"access patterns in IA 2012, but exhibit all the patterns and their combinations in IA 2019. Both humans and robots show a preference for web pages archived in the near past.

Introduction
The web has become ingrained in our lives, influencing our daily activities and preserving the web through web archives is more important than before. With over 686 billion web pages archived [26] dating back to 1996, the Internet Archive (IA) is the largest and oldest of the web archives. The Wayback Machine, which can replay past versions of websites, is a public service provided by IA. Arquivo.pt [21,16] has been archiving millions of files from the Internet since 1996. This paper is an extended version of the paper accepted for publication at TPDL 2022 arXiv:2208.12914v1 [cs.DL] 27 Aug 2022 Both web archives contain information in a variety of languages and provide public search capabilities for historical content.
Our study is an extension of a previous study by AlNoamany et al. [7] that examined access patterns for robots and humans in web archives based on a web server log sample from 2012 from the Wayback Machine. By using several heuristics including browsing speed, image to HTML ratio, requests for robots.txt, and User-Agent strings to differentiate between robot and human sessions, Al-Noamany et al. determined that in the IA access logs in 2012, humans were outnumbered by robots 10:1 in terms of sessions, 5:4 in terms of raw HTTP accesses, and 4:1 in terms of megabytes transferred. The four web archive user access patterns defined in the previous study are Dip (single access), Slide (the same page at different archive times), Dive (different pages at roughly the same archive time), and Skim (lists of what pages are archived, i.e., TimeMaps).
We revisit the work of AlNoamany et al. by examining user accesses to web archives using three different datasets from anonymized server access logs: 2012 Wayback Machine (IA2012), 2019 Wayback Machine (IA2019), and 2019 Arquivo.pt (PT2019). Using these datasets, we identify human and robot access, identify important web archive access patterns, and discover the temporal preference for web archive access. We add to the previous study's criteria for distinguishing robots from humans by making a few adjustments. These heuristics will be discussed in detail in Section 3.4.
The following are the primary contributions of our study: 1. We used a full-day's worth of three web archive access logs datasets (IA2012, IA2019, PT2019) to distinguish between human and robot access. The total number of robots detected in IA2012 is greater than IA2019 (21% more in requests and 18% more in sessions). Robots account for 98% of requests (97% of sessions) in PT2019. 2. We looked at different access patterns exhibited by web archive users (humans and robots). We found out that the robots are almost entirely limited to Dip and Skim in IA2012, but exhibit all the established patterns and their combinations in IA2019. 3. We explored human and robot users' temporal preferences for web archive content. The majority of requests were for mementos that were near to the date-time of each access log dataset, suggesting a preference for the archived content in the recent past.
In this paper, we are attempting to understand who accesses the web archives. To be clear, we are not making any value judgments about robots because we recognize that not all bots are bad. For example, there are services like Internet Archive Scholar [9], ArchiveReady [10], TMVis [36], and MemGator [3] which are built on top of web archives that benefit users.

Background and Related Work
Extracting useful data from web server logs and analyzing user navigation activity is referred to as web usage mining [46,50,41]. Numerous studies have been conducted for analyzing different web usage mining techniques as well as to identify user access patterns on the Internet [47,38,35]. Web usage mining is used to increase the personalization of web-based applications [42,40]. Mobasher et al. [39] developed an automatic personalization technique using multiple web usage mining approaches. Web usage mining is also applied in user profiling [23,15], web marketing initiatives [11], and enhancing learning management systems [51,51].
In this work, we look at web archive server access logs and perform web usage mining in the context of web archives. There has been past work in how users utilize and behave in web archives [22,17,25,20,18,6], including the 2013 study [7] that we revisit. Web archives maintain their web server access logs as plain text files that record each request to the web archive. Most HTTP servers use the standard Common Log Format or the extended Combined Log Format to record their server access logs [8]. An example access log entry from Arquivo.pt web archive is shown in Figure 1. A single log entry consists of the IP address of the client, user identity, authenticated user's ID, date and time, HTTP method, request path, HTTP version, HTTP status code, and size of the response in bytes, referrer, and User-Agent (left to right). The client IP address is anonymized in the access log datasets for privacy reasons. Alam has implemented an HTTP access log parser [1], with exclusive features for web archive access logs, which can be used to process such web archive access logs.
Web servers usually operate on the Hypertext Transfer Protocol (HTTP) [19]. Web clients (such as a web browser or web crawler) make HTTP requests to web servers using a set of defined methods, such as GET, HEAD, POST, etc. to interact with resources [2]. Web servers respond using a set of defined HTTP status codes, headers, and payload (if any). The goal of web archives is to capture and preserve original web resources (URI-Rs). Each capture, or memento (URI-M), is a version of a URI-R that comes from a fixed moment in time (Memento-Datetime). The list of mementos for a particular URI-R is called a TimeMap (URI-T). All of these notions are outlined in the Memento Protocol [49].
AlNoamany et al.'s previous work [7] in 2013 set the groundwork for this study. In addition to their analysis of the prevalence of robot and human users in the Internet Archive, they also proposed a set of basic user access patterns for users of web archives: In a separate study, AlNoamany et al. looked into the Wayback Machine's access logs to understand who created links to URI-Ms and why [5,6]. They found that web archives were used to visit pages no longer on the live web (as opposed to prior versions of pages still on the web), and much of the traffic came from sites like Wikipedia.
Alam et al. [4] describe archival voids or portions of URI spaces that are not present in a web archive. They created multiple Archival Void profiles using Arquivo.pt access logs, and while doing so, they identified and reported access patterns, status code distributions, and issues such as Soft-404 (when a web server responds with an HTTP 200 OK status code for pages that are actually error pages [37]) through Arquivo.pt server logs. While their research is very similar to ours, the mentioned access patterns differ from ours. Their study looks at which users are accessing the archive and what they request, whereas we explain how a user (robot or human) might traverse through an archive.

Methodology
In this work, we leverage cleaned access logs after pre-processing raw access logs to identify user sessions, detect robots, assess distinct access patterns used by web archive visitors, and finally check for any temporal preferences in user accesses. The steps of our analysis are shown in Figure 2. The code [28] and visualizations [27] are published and each step is explained in detail in this section.

Dataset
In this study, we are using three full-day access log datasets from two different web archives: February 2, 2012 access logs from the Internet Archive (IA2012) and February 7, 2019 access logs from Internet Archive (IA2019) and Arquivo.pt (PT2019). We chose the first Thursday of February for our datasets to align with the prior analysis performed on a much smaller sample (2 million requests representing about 30 minutes) from the Wayback access logs from February 2, 2012 [7].
The characteristics of the raw datasets are listed in Table 1. We show the frequency of HTTP request methods and HTTP response codes, among other features. HTTP GET is the most prevalent request method (>98%) present in all three datasets, while the HTTP HEAD method accounts for less than 1% of requests.
Due to the practice of web archives redirecting from the requested Memento-Datetime to the nearest available memento, IA2012 and IA2019 have numerous 3xx requests. About 20% of requests are 3xx in PT2019, due to the same behavior. IA2019 has the highest number of requests to embedded resources (63%) followed by IA2012 (44%) whereas PT2019 has only 20%. From IA2012 to IA2019, the number of requests with a null referrer field has decreased by more than half. There is an increase in self-identified robots (SI robots) from IA2012 to IA2019. The percentage of SI robots in PT2019 is as twice that in IA2019. We used some of these features (HEAD requests, embedded resources, and SI robots) in the bot identification process (covered in Section 3.4).

Data Cleaning
An overview of our data cleaning process is shown in Figure 2. In the Stage 1 data cleaning (S1), we removed the log entries that were either invalid or irrelevant to the analysis. We only kept legitimate requests to web archive content (mementos and TimeMaps) and requests to the web archive's robots.txt at the end of S1 data cleaning. The robots.txt requests were preserved since they will be utilized as a bot detection heuristic later on in our process. After S1 data cleaning, we identified user sessions in each of our three datasets (Section 3.3) and conducted bot identification (Section 3.4). Stage 2 data cleaning (S2) takes place only after the requests were flagged as human or robot. Our study's ultimate goal was to detect user access patterns of robots and humans in our datasets, and to do so, we must ensure that the refined datasets only included requests that a user would make. As a result, in S2 we purged log items that were unrelated in terms of user behavior. This includes the browser's automatic requests for embedded resources, any requests using a method other than HTTP GET, and requests generating responses with status codes other than 200, 404, and 503. Several of these requests, including embedded resources and HEAD requests, were necessary during the bot detection phase. Thus, we had to follow a two-step data cleaning approach. Table 2 shows the number of requests for each dataset after each cleaning stage. The percentages are based on the raw dataset's initial number of requests. PT2019 had a higher percentage of requests remaining after S2 compared to IA2012 and IA2019. This could be related to the raw dataset's low percentage of embedded resources (20%) in the PT2019 dataset (Table 1).

Session Identification
After S1 data cleaning, the next phase in our study was session identification ( Figure 2). A session can be defined as a set of interactions by a particular user with the web server within a given time frame. We split the requests into different user sessions after S1 data cleaning. First, we sorted all of the requests by IP and User-Agent, then identified the user sessions based on a 10-minute timeout threshold similar to the prior study's process [7]. That is, if the interval between two consecutive requests with the same IP and User-Agent is longer than 10 minutes, the second request is considered as the start of the next session for that user.

Bot identification
As the next step in our process, we employed a heuristic-based strategy to identify robot requests (Figure 2). We incorporated a few new adjustments to the original heuristics used in prior work [7] to improve the performance of the robot detection. The following sub-sections will go through each heuristic in detail. The real-world examples for each heuristic taken from the web archive access logs is shown in the appendices.

Known bots
We created a list of User-Agents that are known to be used by bots. We first constructed U A l , a list of all User-Agent strings from our three datasets. From this list, we compiled U A m by filtering for User-Agent strings that contained robot keywords, such as "bot", "crawler", "spider", etc. We compiled a separate bot User-Agent list U A d by running our full list U A l through DeviceDetector [13], a parser that filters on known bot User-Agent strings. Our final list [29] of bot User-Agents U A K b was constructed by combining U A d with our keyword set U A m . Any request with a User-Agent found in U A K b was classified as a robot. Appendix A provides a real-world example where the "bot" keyword is available on the User-Agent itself.
Type of HTTP request method Web browsers, which are assumed to be humans, send GET requests for web pages. As a result, we used HEAD requests as an indication of robot behavior. If the request made is a HEAD request, it is considered a robot request, and the session to which it belongs is counted as a robot session. Appendix B provides a real-world example where HEAD requests are made.
Number of User-Agent per IP (UA/IP) There are robots that repeatedly change their User-Agent (UA) between requests to avoid being detected. The previous study [7] found that a threshold of 20 UAs per IP was effective in distinguishing robots from humans. This allows for some human requests behind a proxy or NAT that may have the same IP address but different User-Agents, representing different users sharing a single IP. As discussed in Section 3.3, we sorted the access logs from the three datasets based on IP first and then User-Agent. We marked any requests from IPs that update their User-Agent field more than 20 times as robots. Appendix C provides a real-world example where the IP address is changed for each request.
Requests to robots.txt file A robots.txt [32,52] file contains information on how to crawl pages on a website. It helps web crawlers control their actions so that they do not overburden the web server or crawl web pages that are not intended for public viewing. As a result, a request for the robots.txt file can be considered an indication of a robot request. We identified any user who made a request for robots.txt (including query strings) as a robot. Appendix D provides a real-world example where requests are made to the robots.txt file.
Browsing Speed (BS) We used browsing speed as a criterion to distinguish robots from humans. Robots can navigate the web far faster than humans. Castellano et al. [14] found that a human would only make a maximum of one request for a new web page every two seconds. Similar to the previous study [7], we classified any session with a browsing speed faster than one HTML request every two seconds (or, BS >= 0.5 requests per second) as a robot. Appendix E provides a real-world example where we can see so many requests in a single second which is unusual for human behavior.
Image-to-HTML Ratio (IH) Robots tend to retrieve only HTML pages, therefore requests for images can be regarded as a sign of a human user. A ratio of 1:10 images to HTML was proposed by Stassopoulou and Dikaiakos [48] and used in the prior study [7] as a threshold for distinguishing robots from humans. We flagged a session requesting less than one image file for every 10 HTML files as a robot session. IH was found to have the largest effect in detecting robots in the prior study's dataset, and this holds true for our three datasets as well.
Appendix F provides a real-world example where a session is marked as a robot using the IH ratio.
We used the aforementioned heuristics on our three datasets to classify each request as human or robot. If a request/session has been marked as a robot at least by one of the heuristics, we have classified it as a robot. After bot identification but before reporting the final results, we performed S2 as described in Section 3.2.

Results and Analysis
In order to investigate the data further after S2 data cleaning, we divided the dataset into two subsets, human sessions, and bot sessions. For each dataset, we used these two subsets to determine user access patterns and compare them to robot access patterns. Finally, we conducted a temporal analysis of the requests in both subsets for each dataset. Table 3 reports the number of detected robots for each dataset based on the total number of sessions and the total number of requests. We counted the number of requests classified as robots based on each heuristic independently (as mentioned earlier, the heuristics are not mutually exclusive, so these numbers across a column do not need to add to exactly 100%). The final row in the table represents the total number of sessions and requests that are marked as robots after applying all the heuristics together.

Robots vs. Humans
The Image-to-HTML ratio (IH) had the largest effect on detecting robots across all three datasets. The impact of IH was ≈85-90% in IA2012 but only around ≈ 55 − 65% in IA2019. In PT2019, ≈ 80 − 96% of robots were detected using the IH ratio, which is higher compared to IA2019. In PT2019, we were able to detect almost all the robots through this one heuristic, IH. We found that ≈ 90% of requests were robots in IA2012, ≈ 70% of requests were robots in IA2019, and ≈ 98% of requests were robots in PT2019.
The reason for this increase in human sessions in 2019 than in 2012 could be the increase in awareness of web archives among human users. In addition, headless browsers, such as Headless Chromium [12], PhantomJS [24], and Selenium [44], that provide automated web page control have become popular in recent years. Their functionality simulates a more human-like behavior that may not be caught easily by bot detection techniques. For instance, applications like the work of Ayala [43] and tools like the oldweb.today [33,34], DSA Toolkit [30,31], TMVis [36], and Memento-Damage service [45] that replicate human behavior make things challenging for detection algorithms. Between IA2019 and PT2019, PT2019 has ≈ 30% more robots present. Based on our PT2019 dataset, only 2% of all requests coming into the Arquivo.pt are potential human requests.

Discovering Access Patterns
Upon distinguishing robots from humans, we divided all three of our datasets into human and bot subdatasets (IA2012_H, IA2012_B, IA2019_H, IA2019_B, PT2019_H, PT2019_B). We used these datasets to identify different access patterns that are followed by both human and robot sessions. Upon distinguishing robots from humans, we divided all three of our datasets into human and bot subdatasets (IA2012_H, IA2012_B, IA2019_H, IA2019_B, PT2019_H, PT2019_B). As introduced in Section 2, there were four different user access patterns established by AlNoamany et al. [7]. We looked into each of these patterns and identified their prevalence in our three datasets. We discovered the prevalence of sessions that followed each of the four patterns (Dip, Dive, Slide, Skim), as well as sessions that followed a hybrid of those patterns ("Dive and Slide", "Dive and Skim", "Skim and Slide", and "Dive, Slide, and Skim"). We categorized requests that do not fall into any pattern as Unknown. Figure 3 shows a chart for each subdataset. The horizontal (x) axis represents the different patterns or a hybrid of patterns and the vertical (y) axis represents the percentage of the number of requests. The percentages are based on the total number of requests for each subdataset. According to AlNoamany et al.'s findings based on the IA2012 dataset, Dips were the most common pattern in both human and robot sessions. However in our IA2012 dataset (full-day), Dive and Dip account for about the same percentage of human sessions, although Skim is the most common pattern among robot sessions. Dip is the most common pattern in IA2019, followed by Dive, Slide for both human and robot sessions. The human Dips have more than doubled from IA2012 (22%) to IA2019 (50%) indicating that more humans are accessing web archives to access a single URI-M or URI-T. There are a high number of robot Skims in IA2012 compared to IA2019. In IA2012 robot sessions, it is over 90% Skims. We could see that the long-running robot sessions that request URI-Ts account for most of the Skim percentage. In contrast to IA2019, PT2019 humans exhibit a higher percentage of Dive and Slide (45%) than Dips (29%). Even in robot sessions, Dive (70%) and Dive and Slide (24%) percentage is higher than Dip (6%).
In IA2012, robots almost always access TimeMaps (95%) and humans access mementos (82%). However, in IA2019, humans and robots almost always access mementos (96%), whereas only 4% of those accesses are to TimeMaps. When looking at the hybrid patterns, PT2019 bot sessions only have a maximum of two patterns while the rest have a small percentage of all three patterns (Dive, Skim, and Slide). For each dataset in IA, there is a very small percentage of requests (4.22% in IA2019, 0.97% in IA2012) that do not belong to any of the patterns. We were able to identify all the different patterns in the PT2019 dataset. The percentage of human requests falling under the Unknown category in IA2012 (4.02%) is higher compared to the IA2012 robot requests (0.2%), IA2019 human requests (0.85%), and IA2019 robot requests (0.12%).

Identifying Temporal Preferences
We also explored the requested Memento-Datetime in our subdatasets to see if there was any temporal preference by web archive users. Figure 4 illustrates the temporal preference of robots and humans in our datasets. The x-axis represents the number of years prior, meaning the number of years passed relative to the datetime of the access logs (e.g., for IA2012, 2 years prior is 2010) and the y-axis represents the number of requests. Note that the y-axis in each chart is different.
It is evident that the majority of the requests are for mementos that are close to the datetime of each access log sample and gradually diminish as we go further back in time. There is no significant difference in temporal preference  in IA2012 and IA2019. IA2019 humans, IA2019 bots, and PT2019 bots exhibit the same trend however, it is difficult to see a trend in PT2019 humans due to the fewer number of humans in the dataset. For PT2019 humans, there is a spike around 4-5 years prior which implies PT human accesses were mostly for mementos around 2015-2016. There is an advantage to knowing the temporal preferences of web archive users. Web archives can prioritize or store data in memory for the most recent years to speed up disk access.

Future Work
AlNoamany et al. [7] observed four different user access patterns in 2013. In our datasets combined, 0.35% of requests were outside of any of these patterns or their combinations. One may look into if the percentage of requests that fell into the Unknown category have any other generally applicable patterns, or if they are completely random.
The overall number of robots identified in IA2019 is much lower than in IA2012. We would like to repeat this study on more distinct full-day datasets to see if the reduction in robots is a general behavior from 2012 to 2019 or specific to the day we chose. Additionally, the IH [48] and BS thresholds [14] in our bot identification heuristics are based on the behavior of conventional web servers; however, it remains to be determined if the same thresholds apply to web archival replay systems, as the dynamics of web archival replay systems differ (e.g., the Wayback Machine is typically slower than a typical web server).

Conclusions
We used a full-day access logs sample of Internet Archive's (IA) Wayback Machine from 2012 and 2019, as well as Arquivo.pt's from 2019, to distinguish between robot and human users in web archives. In IA2012, the overall number of robots discovered was higher than in IA2019 (21% more in requests and 18%t more in sessions). We discovered that robot accesses account for 98% of requests (97% of sessions) based on 2019 server logs from Arquivo.pt. We also discovered that in IA2012, the robots were almost exclusively limited to Dip and Skim, but that in IA2019, they exhibit all of the patterns and their combinations. Regardless of whether it is a robot or a human user, the majority of requests were for mementos that are close to the date-time of each access log dataset, demonstrating a preference for the recent past.

Acknowledgements
We thank Mark Graham, director of the Wayback Machine, for sharing access log data from the Wayback Machine at the Internet Archive. We are grateful to Daniel Gomes and Fernando Melo of Arquivo.pt for sharing access log data from the Arquivo.pt web archive with us.

Appendix C Number of User-Agents per IP (UA/IP)
There are robots that repeatedly change their User-Agent (UA) between requests to avoid being detected. We marked any requests from IPs that update their User-Agent field more than 20 times as robots. Below is an example where the IP address is changed for each request. Section 3.4 discusses this heuristic in more detail.


Deep Learning-based approaches for automatic detection of shell nouns and evaluation on WikiText-2

In some areas, such as Cognitive Linguistics, researchers are still using traditional techniques based on manual rules and patterns. Since the definition of shell noun is rather subjective and there are many exceptions, this time-consuming work had to be done by hand in the past when Deep Learning techniques were not mature enough. With the increasing number of networked languages, these rules are becoming less useful. However, there is a better alternative now. With the development of Deep Learning, pre-trained language models have provided a good technical basis for Natural Language Processing. Automated processes based on Deep Learning approaches are more in line with modern needs. This paper collaborates across borders to propose two Neural Network models for the automatic detection of shell nouns and experiment on the WikiText-2 dataset. The proposed approaches not only allow the entire process to be automated, but the precision has reached 94% even on completely unseen articles, comparable to that of human annotators. This shows that the performance and generalization ability of the model is good enough to be used for research purposes. Many new nouns are found that fit the definition of shell noun very well. All discovered shell nouns as well as pre-trained models and code are available on GitHub.

Introduction
The concept of the shell noun was first introduced by linguist Schmid, H. J. in 1997 [1]. He defines a shell noun as a functionally defined abstract noun used to convey or refer to complex content in a specific context. Such a noun needs to be identified based on its behavior in a sentence, not based on an inherent meaning. Its actual meaning needs to be determined in context, and because of this, it has an important role to play in the understanding of language. Here are a few examples, with the bold underlined word being the shell noun.
(1) The fact that a major label hadn't been at liberty to exploit and repackage the material on CD meant that prices on the vintage LP market were soaring. (2) The issue that this country and Congress must address is how to provide optimal care for all without limiting access for the many. (3) Living expenses are much lower in rural India than in New York, but this fact is not fully captured if prices are converted with currency exchange rates. In Schmid's study, he suggests 670 words that can be used as shell nouns, while also pointing out that giving an exhaustive list is not possible, as more shell nouns can be found in the right context [1].
There are already some previous researches in attempting to automate the shell noun detection process. Kolhatkar, V.
proposed a syntax-based approach to doing Pattern Recognition and achieved accuracies of 62% to 83% [2]. However, their approach is based on sentence structure rather than semantics and function and does not identify shell nouns better in poorly structured sentences. Also, as the handwritten patterns are limited, which is the same limitation as Schmid's, they cannot enumerate all the sentence patterns in which shell nouns occur, so the scope of application is limited [1]. It is also mentioned in their paper that it should be possible to reduce such limitations through a robust Machine Learning approach.
Similar rules and patterns were proposed by Roussel, A. in German [3]. Their work focused more on precision than recall, achieving 56.4% precision but only 26.2% recall. Such accuracy, precision and recall are far from adequate for practical use.
Researchers in Cognitive Linguistics need a more accurate and flexible way of tackling this long-standing task, which is what this paper aims to do. Another task in this paper is to use our proposed model to discover more shell nouns in a more up-to-date dataset and to verify them to test the validity and usefulness of the model.

Part-Of-Speech tagging
The task of shell noun detection is like the task of Part-Of-Speech tagging in linguistics. The difference between these two tasks is that Part-Of-Speech tagging focuses more on the overall lexical classification and does not distinguish carefully whether a noun is a shell noun or not. Shell noun detection, on the other hand, focuses on separating shell nouns from other words without regard to lexicality.
The task of Part-Of-Speech tagging has seen more solutions using Deep Learning techniques in addition to the traditional pattern-based approach. In the field of Natural Language Processing, both Part-Of-Speech tagging and Named Entity Recognition can be handled by the same token classification task. For example, Akbik, A., Blythe, D., and Vollgraf, R. used Long Short-Term Memory Neural Network for language sequence modelling and achieved an F1 score of 98.19% on Part-Of-Speech tagging [4]. Their work, therefore, provides a good basis for our research.

Token classification
Shell noun detection is also a Natural Language Processing task. When it comes to Natural Language Processing, an architecture that cannot be avoided is Transformer, a new network architecture based entirely on attention mechanisms, proposed by Vaswani, A. et al. in 2017 [5]. Later Conneau, A. et al. used a dataset of more than 2 TB for pre-training the model, resulting in the XLM-RoBERTa family of models [6].
These models are well suited for language-related tasks, as they take full advantage of the knowledge gained during the pre-training period and require only a small amount of data fine-tuning to achieve good performance. Data for shell noun annotation is very scarce and the subjective nature of the definitions makes data collection more difficult. Fine-tuning a pre-trained model is a better option. Our research will also build on their work.

Annotated shell noun corpus
Data is important for any Deep Learning approach. The annotated shell noun corpus by Simonjetz, F., and Roussel, A. uses a part of the English-German parallel text from Europarl, manually annotated by multiple annotators with rounding [7]. The Europarl corpus is a parallel corpus extracted from the proceedings of the European Parliament by Koehn, P. and was originally intended for the development of Machine Translation system [8].
Due to the subjective nature of the definition of shell noun, the annotated corpus will use to train models directly without annotating them by us. The work in this paper focuses more on English, although the corpus is a parallel corpus, the corresponding German part is ignored. This corpus provides all the data for training, validation and testing. The other dataset mentioned below was used only for the practical application of shell noun detection.
Some statistics for this corpus are shown in Table 1 below.

WikiText-2 dataset
The WikiText-2 dataset is a corpus of verified, excellent and selected articles from Wikipedia by Merity, S., Xiong, C., Bradbury, J., and Socher, R. [9]. The dataset consists of many complete articles, preserving original cases, punctuation and numbers. It is available under CC BY-SA. It was chosen for shell noun detection because it is of moderate size, with about 2.5 million words; and relatively new, the dataset having been published in 2016. This gives a higher probability of finding more eligible shell nouns.
In addition, Wikipedia is a website that many people use, and the text on it should be closer to the text that people can see in their daily lives. The Europarl corpus from the proceedings of the European Parliament, on the other hand, is less relevant to the general public.
The difference in statistics between WikiText-2 and the corpus mentioned in 3.1 is shown in Table 2 below.

Review of the traditional approach
There are two main steps in shell noun detection using the traditional method: (1) Lexico-grammatical analysis and labelling of the components of each word using relevant software. (2) Matching against the patterns proposed by Hans Schmid and later researchers [1]. Noun-be-to Noun-wh Noun-be-that Noun-of Noun-be-wh th-Noun Noun-to th-be-Noun Noun-that Sub-be-Noun This approach relies on lexico-grammatical analysis, and the accuracy of identifying shell nouns also relies on the accuracy of component annotation. Nowadays Part-Of-Speech tagging based on Deep Learning is well established and the Part-Of-Speech tagging model proposed by Akbik, A. et al. is used to reproduce Kolhatkar, V.'s algorithm [2,4]. Even though the accuracy of Part-Of-Speech tagging is very high, their algorithm still does not perform well on our test set, as can be seen in Chapter 6.2 of this paper.
The reason for this is explained by themselves. Since it is impossible to exhaust all patterns of occurrence of shell nouns, some words fit the definition but not the pattern. And the reason why this approach does not work well is that it relies entirely on lexical and grammatical usage. The role of a shell noun is to convey or refer to a particular piece of information in the context. A better way to address this type of problem requires consideration of the underlying semantics of the words.

Our LSTM-based approach
Long Short-Term Memory (LSTM) Neural Networks are a very practical type of network for sequence data processing [10]. Articles are sequences made up of many words and are therefore also suitable for processing using LSTM. Our proposed LSTM-based model is built using Flair and PyTorch, and the general architecture is shown in Figure 1. The model uses three different sets of word vectors as input, GloVe, Flairnews-forward and Flair-news-backward [11]. They go into an LSTM and linear module, respectively, and are then combined. It is then connected to a larger LSTM module and a linear module. Eventually, it will pass through the Viterbi and the Conditional Random Field to get the final output [12,13]. Unlike the Transformer-based model below, the LSTMbased model is commonly used to deal with language problems by using the word vector corresponding to each word as input. Three different word vectors are used to give the model more information. GloVe uses co-occurrence matrices to obtain features of words both locally and as a whole, while the word vectors starting with Flair-news obtain features by allowing the language model to predict words forwards and backwards respectively. Doing so also enhances the robustness of the model, as these word vectors are constructed differently and use different training data.
When reasoning on a larger dataset, words will likely appear that have never been seen in the training data. And the scenario of dropping certain words with some probability to let the model infer it from other words is like the model encountering words it has never seen before. So, the interspersed dropout layer acts as a regularization to suppress the overfitting of the model and improve generalization.
As with many other language tasks, the current word alone is not sufficient to infer whether it is a shell noun, so the Viterbi algorithm and Conditional Random Field are used to find more likely correspondences. Both techniques are also frequently used in Automatic Speech Recognition and Natural Language Processing.

Our Transformer-based approach
Since the Transformer architecture was proposed in 2017, it has been successful in areas such as Natural Language Processing and Computer Vision. In our proposed Transformer-based approach, a RoBERTa model is used to replace the word vectors in the LSTM-based approach [14]. All LSTM modules are removed so that the model is informed only by the features extracted by RoBERTa. The model uses the XLM-RoBERTa-base hosted on Hugging Face's Model Hub [15]. Its architecture is shown in Figure 2. As all word vectors and LSTM modules are replaced by a RoBERTa and linear module, this approach is much cleaner in terms of process. One of the advantages of this approach is that the word vectors generated by Transformer are strongly contextdependent, i.e., the word vectors for the same word in different contexts are different. GloVe, for example, has a fixed word vector for each word after training, and therefore cannot be better adapted to changing contexts.
Another advantage is that, due to resource constraints, we cannot provide a huge dataset for the LSTM-based model to be trained. In contrast, the XLM-RoBERTa family of models are pre-trained on a 2 TB dataset. If only fine-tune it at a very low learning rate, the knowledge learned by the model during pre-training will be retained, which is one of the reasons why pre-trained language models are useful. And this may be even more useful for the model to discover shell nouns in passages that have never been seen before.
Since the Transformer-based model has a higher number of parameters than the LSTM-based model, it is less efficient on short inputs. However, when the input sequence becomes longer, the Transformer is more efficient than the LSTM. This is because Transformer's operations are performed in parallel at the sequence level, whereas LSTM is serial. As the WikiText-2 dataset has over 2 million words, Transformer will be more efficient on data of this size, as longer input lengths can be used.

The loss functions
The simplest loss function to solve this task is the crossentropy loss, which will optimize the prediction loss for each word individually. If the prediction loss for each word is small enough, the model will naturally achieve good performance. In this scenario, what the model learns is the probability of each word being a shell noun in the corresponding context. The focus is on the words themselves. Cross-entropy loss has been applied to several different tasks and its formula will be set out again below for comparison purposes.
However, this ignores the information about the regularity between words. So, there is a better way, which is to use a Conditional Random Field, as in the paper by Huang, Z., Xu, W., and Yu, K. [16]. After introducing CRF to the model, it is no longer possible to use cross-entropy as a loss function. This is because the focus when training the model will no longer be on each word itself, but on the transition probabilities between different states. Specifically, it is the transition probability between whether the words of this sentence are shell nouns or not in our task. In the process of forwarding inference, the sequence with the highest overall probability needs to be found, and this can be solved using the Viterbi algorithm. This is the reason why the Viterbi module is used.
As the loss of each word is now no longer optimized separately, but rather the loss of transition probabilities, a new loss function needs to be used. It is generally referred to as the Viterbi loss or CRF loss and here is its formula. (2) In our specific task, ( | −1 ) in Formula (2) above denotes the transition probability of the state of the i th word given the state of the (i-1) th word.
( | ) denotes the emission probability of the state of the i th word given its word in the corresponding context. Both transition probabilities and emission probabilities are trainable parameters in CRF.

Is POS lexical information necessary?
In the traditional pattern-based approach, it is necessary to determine whether a word is a shell noun based on the results of lexical annotation, so this is where lexical information is necessary. When using a Deep Learning-based approach, the text itself can be input and the probability that each word is a shell noun can be output directly. In this case, is it still necessary to retain lexical information? Relevant experiments are designed to answer this question.
The experimental results in Chapter 6 show that, both in LSTM and Transformer, when the Viterbi and CRF are used, the inclusion of lexical information will, on the contrary, degrade the performance of the model. However, if the Viterbi and CRF are not used, the addition of lexical information improves the performance of the model. However, the lexical information provides a limited improvement, and the gain is not comparable to that of CRF.
Lexicality, as additional information about the text, could give more supervisory information to help the model achieve better performance when the model itself is not good enough. However, with CRF, the model itself is already good enough. Adding further lexical information would instead distract the model from the single task of whether it is a shell noun or not. Therefore, in our final model, CRF instead of lexical information is used to obtain better performance.

Is the Viterbi module and CRF necessary?
The Viterbi and CRF are used for tasks such as Part-Of-Speech tagging, because the occurrence of words is conditional, also known as the probability of state transfer. Most of the relevant tasks use CRF, but is the Transformer model powerful enough to perform well without using it? Or does the removal of CRF help the model? Experiments are also designed to investigate this question by replacing CRF with a cross-entropy loss, as described in Chapter 4.4.
However, the experimental results in Chapter 6.2 show that in most cases, removing CRF harms the model, especially in the Transformer-based model. A Transformer-based model without CRF performs even worse than an LSTM-based model that also does not use CRF. This may also reflect the fact that although both LSTM and Transformer are good at working with sequential data, their respective strengths are different.
Given this, even a strong Transformer model needs to use traditional tools such as the Viterbi and CRF to achieve better performance when encountering certain problems, such as Part-Of-Speech tagging and shell noun detection. For this reason, these two modules are used in both of our proposed models. In the training set, the use of lexical information brings a boost to performance for both LSTM-based and Transformerbased models. This suggests that it helps to help the model fit better on the training set. Furthermore, using the Viterbi and CRF in the LSTM model leads to performance degradation in the training set, while its use in the Transformer model leads to a boost. The traditional pattern-based approach is reimplemented in the testing set. Even with the very powerful POS tagging model, the recall and precision of the traditional approach are only about 55%. This shows that it is not the accuracy of the lexical annotation that limits the traditional approach but the patterns themselves.

Performance on the testing set
For both of our proposed models, the best versions of each use the Viterbi and CRF, and the comparison of the F1 scores shows that CRF reduces the degree of overfitting of the model and enhances generalization. Lexical information, on the other hand, negatively affects the performance of the model, both in the LSTM-based model and the Transformer-based model. Considering that this information is very useful in the training set, it affects the generalization ability of the model. Language is uncertain, so the words that each annotator considers to be shell nouns are not the same. The confusion matrix for annotators is given in Simonjetz, F. and Roussel, A.'s paper and can be used to work out how well human annotators perform [7]. This is how the data for #10 in Table 6 is calculated.

Comparison with the traditional approach and human
As can be seen, our proposed LSTM model has a 30% performance improvement over the traditional approach, and our proposed Transformer model has a 33% improvement. This directly improves the F1 score of the model in the testing set from around 55% to around 88%, reaching a practical level.
Affected by a lower recall, the F1 score of the model is below the human level. However, our Transformer-based model's precision on the testing set has narrowly outperformed that of the human annotator. This is a height that no previous work has achieved. Our test platform uses an RTX 3070 Laptop. As can be seen from Table 7 above, our LSTM model is a relatively lightweight model, with only about 64 million parameters, requiring little video memory. However, due to its serial computing nature, it performs poorly in terms of efficiency on long passages, processing only about 700 words per second. The Transformer model has a relatively large number of parameters, 278 million, but this is a small number of parameters compared to common language models. Moreover, due to its parallel computing nature, the processing efficiency on long passages is much better than that of LSTM, exceeding 7800 words per second. Our proposed Transformer-based model with the highest F1 score is taken to inference on WikiText-2, and the results are shown in Table 8. The model found a total of 21,021 shell nouns in this dataset, representing 0.85% of all nouns. This proportion is lower compared to the training data. However, given that the model has a recall of around 83%, approximately 1.02% of the nouns in this dataset should be shell nouns. This may be because Wikipedia uses more usual simple language, as opposed to the more formal style of the proceedings of the European Parliament.

Overall statistics
Our model also found 522 new shell nouns that were not among Schmid, H. J.'s 670 words, but also qualify as shell nouns [1]. The full list of 959 shell nouns in WikiText-2 can be found on our GitHub repository. Below are 10 selected new words with the highest frequency of occurrence for manual verification. Above are 10 examples of the most frequently occurring shell nouns newly discovered by our proposed model, all samples were randomly extracted from the WikiText-2 dataset. Words underlined in bold are shell nouns, while those in italics are the part of the message they refer to or convey, i.e., the shell content. Manual verification can be used as a gold standard. The 10 randomly selected examples all meet the functional definition of shell noun, and all refer to or convey contextspecific information. This means that the model does have the ability to discover new shell nouns in texts that have never been seen before, and the performance is as expected.

Conclusion
This paper investigates the practical application of two classical neural network architectures, Long Short-Term Memory and Transformer, to the task of shell noun detection in the traditional field of Cognitive Linguistics. A new model based on LSTM, and another based on Transformer are proposed. Its performance is improved by 30% to 33% over the traditional pattern-based approach, while also automating the entire process. The probability of each word being a shell noun is obtained by simply entering the text. The impact of lexical information, the Viterbi and Conditional Random Fields on this task was also investigated. Shell noun detection was evaluated on the WikiText-2, where a total of 522 new shell nouns were found that met the requirements but had not been previously proposed, and the 10 with the highest frequency were manually validated.
The code for the new model proposed in this paper and the 959 shell nouns with their frequency statistics are publicly available at https://github.com/ycd2016/shellnouns. The trained models have also been uploaded to Google Drive and the link can be found on the GitHub page above. This work not only brings new Deep Learning-based solutions to the field but also brings more researchable content. For example, revisiting models written by previous researchers as well as exploring new words discovered by the models. We look forward to more collaborations across knowledge domains to promote the joint development of different disciplines.