This paper describes data structures and algorithms that allow disciplinary taxonomic experts to embed Formal Contexts within a graph of Archive Information Packages (AIP's). The AIP's are standardized objects that provide access to the Inventoried Objects (IO's) in an archive. For an archive containing Earth science data, IO's may be physical specimens or numerical data files. They are not just textual files that provide a corpora of keywork phrases. The graph serves as a Table of Contents for the archive's collection. A data user familiar with the discipline's taxonomy having a recognizable search target can navigate through the graph to identify and access the archive's IO's.
An archive containing Earth science data may contain physical objects or numerical data files. Its Inventoried Objects (IO’s) do not necessarily contain textual content. Thus, they may not provide keyword phrases chosen from their textual content. This paper’s algorithms assume that a disciplinary taxonomist develops an IO classification. To do this, the taxonomist creates vertices in a network. Each nonterminal vertex points to a unique Partitioned Formal Context (PFC). Each terminal vertex points to a unique IO.
The Archive Information Packages (AIP’s) described in the ISO standard
known as the Open Archive Information System (OAIS) Reference Model (RM)
[
This taxonomic approach markedly reduces the size of the Formal Contexts a FCA algorithm uses to create Formal Concepts from the PFC’s. The computed Formal Concepts guide the user’s navigation from AIC to AIC until the user finds an AIU with the target IO. The next section includes brief examples of the kinds of IO’s in archives of Earth science data. Then, it describes the way they enter the taxonomic network. Later sections include outlines of data structures for the network vertices and pseudo code for the key algorithms in this approach. c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 275{280, ISBN 978{2{7466{6566{8, Laboratory L3i, University of La Rochelle, 2013. Copying permitted only for private and academic purposes. 2
This section discusses the basis for creating a taxonomic classification network. The first subsection notes that a disciplinary taxonomist provides the a priori categories for the taxonomy. This subsection also provides examples of categories for two kinds of Earth science data. These categories depend on the disciplines providing the data. Thus, this paper treats them as axiomatic. The second subsection provides a formal discussion of the AIC and AIU data structures. The third subsection deals with a rough scaling analysis of a taxonomic network. 2.1
The a priori basis for creating a taxonomy for an archive’s collection lies in the scientific disciplines that produce the IO’s. As with the OAIS RM, we assume that the IO’s are atomic so they have no internal components that the archive records. In Earth science, IO’s may be physical objects, such as biological or geological specimens. They may include hand-written or printed observational records or technical reports. Finally, Earth science IO’s may be digital files, the bulk of which contain numerical values based on measurements from automated instruments.
A second axiomatic basis is the Formal Context (FC) formed by all the IO’s in the archive. The union of the IO’s forms the extent of this FC. Its intent is the union of all the IO attributes.
The NOAA Emergency Response Imagery Collection is an archive of digital
images taken by an automated camera mounted on an aircraft [
The ERI project provides a web site through which emergency responders, such as federal disaster coordinators or insurance adjustors can download IO’s. These users evaluate the storm damage and plan appropriate action based on the images. Altogether, the total collection probably contains about 60,000 IO’s. Each IO has an ID, a storm name, a data collection date, and a text storm centroid location. The high resolution and thumbnail gif’s have four latitude/longitude positions at the corners of each image. With eleven attributes for most of the files, there will be about 660,000 attributes (11 × 60, 000) in the Formal Context intent for this collection’s IO’s.
In the taxonomic network, the AIC’s that lie in the first level below the root refer to images from specific storms. Thus, these collections include images from storms such as Hurricanes Katrina, Ike, or Sandy. In the level below that, each storm AIC has two collections. One is an AIC for a collection of images in coarse geographic bins. Those images include the high-resolution gif images and the thumbnails. The second AIC is a collection of zipped files along the flight paths. The AIC’s that are children of each geographic bin AIC contain AIC’s with one high resolution image and one low-resolution image. The AIC’s below the one with the flight path collection contain AIU’s based on an individual flight path. The network replicates this layered AIC structure across the entire collection of IO’s. Even so, each PFC is unique.
For biological specie classification, the categories for the AIC’s are Kingdoms, Subkingdoms, Classes, Orders, Families, Genera, Species, and Races. The individual specimens in an archive’s biological specimen collection are the IO’s in the AIU’s. 2.2
A disciplinary taxonomist creates AIP’s and AIU’s. This is a familiar process
in biology. [
The AIC’s and AIU’s are vertices in a graph. The pseudo code in the Taxonomy Network Data Structure provides a pointer-based formalization of the relationship between the AIC’s and the AIU’s.
Taxonomy Network Data Structure type p PFC is access PFC Type; −− Pointer to a PFC type PFC Type(N O : in positive; N A : in positive)
is array(1 .. N O, 1 .. N A) of Boolean; type Type Of AIP is (Collection, IO); type p AIP is access AIP; −− Pointer to an AIP type AIP(AIP Type : Type Of AIP := Collection) is record
AIP Identifier : Bounded String; Parent AIP : p AIP; Next Sibling AIP : p AIP; case AIP Type is when Collection =>
PFC : p PFC;
First Child AIP : p AIP; when IO =>
Object Identifier : Bounded String; end case; end record;
If all of the PFC’s in the graph were diagonal, each object in the PFC would have only one unique attribute. The taxonomic graph would collapse to a tree. There would be a unique edge that linked each AIC to each of its children. When the parent PFC is not diagonal, the formal concepts formed from the PFC create a lattice that links parents to their children. For a taxonomic network, the lattice must provide a unique path from a parent to each of its children. 2.3
The number of children and the number of attributes for the PFC of a particular AIP can vary widely across the network. This variability makes it difficult to formulate simple scaling relationships for the work of computing formal concepts from the PFC’s. For example, the root PFC in the ERI example has about twenty storm objects. Each storm has three attributes: storm name, date, and centroid location name. Thus, for this PFC, NO = 20 and NA = 60. At the next level, the PFC’s have NO = 2 and NA = 2. The children of each PFC have only a coarse geographic bin collection and a flight path collection. At the level below this, the coarse bin PFC’s may have twenty to fifty objects. The flight path PFC’s have five to twenty objects. Clearly, the partitioning produces much smaller binary matrices than the unpartitioned Formal Context.
A rough approximation for scaling assumes that the graph reduces to a multiway tree. The number of children for each AIC is M . The number of levels is L. The total number of AIC nodes in the tree, N , is
N = 1 + M + M 2 + . . . + M L (1) If the number of attributes in each PFC is NA = aM , then the size of each PFC is (M, aM ). Both M and a are usually small compared with the dimensions of the Formal Context for the archive’s total collection. This approximation suggests that the computational work from the network partitioning can reduce that burden by several orders of magnitude.
The archive does not have to calculate the Formal Concepts for any of the PFC’s when it establishes the network. That calculation can occur when the user’s navigational search reaches an AIC. Under this simplifying assumption, a user with a successful navigation search will only select L formal contexts. The archive only needs to calculate Formal Concepts for each of the selected PFC’s. User attribute pruning to remove attributes the user regards as irrelevant will further reduce the computational load.
Disciplinary users familiar with a taxonomy form a much smaller community than the public using commercial search engines. For example, only about 1% to 2% of students entering U.S. colleges want to enter scientific or mathematical curricula. The reduction in computational burden and in user search requests should make the taxonomic partitioning approach computationally acceptable. 3
A disciplinary specialist, such as a research scientist or resource manager, spends a substantial amount of time learning a discipline’s taxonomy for classifying objects. Such a specialist is likely to have a specific target for a search. Thus, such a user seems highly likely to use the discipline’s taxonomy classification.
A biologist who has a new, unidentified plant would usually use a biological taxonomy to see if there were any previously identified specimen’s in an archive’s collection that matched her new one. Even if the biologist moved rapidly through the upper levels of the collection, she would eventually get to a level where she would need to match the attributes of her sample against the standard attributes that identify the particular specie within a probable Genus.
The search behavior of a disciplinary specialist differs markedly from that
of an individual with an unclear target for his or her search. A person browsing
needs a recommender site rather than a navigational one [
The taxonomic classification approach expects that a user can identify a useful IO based on the taxonomy network traversal. If the user obtains his or her goal, then the search terminates successfully. If the user recognizes that the search is not likely to reach the target, he or she can back up to a higher level and make different selections. Thus, we expect the user search to be iterative. In addition, the user can get tired of searching and terminate the interaction. The following pseudo code outlines the search algorithm.
The user-guided navigational search algorithm outlined in the pseudo code starts at the root AIP. The loop moves down the taxonomic AIP graph from the root at Level 0 to deeper levels where the user can find the desired target IO. The first step for the user is to prune the selected AIP attributes to create a pruned formal context. In pruning, the user removes attributes regarded as irrelevant to finding the target IO. Pruning the static Formal Context removes the irrelevant columns and thereby produces a smaller Formal Context. The pruning also removes any rows that contain no objects after removal of the attribute columns. The pseudo code for the NSN subalgorithm provides the logic for lines 5 and 6 of this listing.
Order Pruned Context objects into layers based on increasing number of attributes; Construct a directed graph with objects identified as vertices and edges that connect vertices to their immediate successors in the layer with the smallest increase in number of attributes; Construct a web site in which each page contains information on a single vertex and has links to the immediate successors; Search Successful := False; Done := False; Select page with the vertex that has no attributes and all objects; while not Done loop
User selects pages from the links on the current page; if selected page has only one IO then if IO is User Target then
Search Successful := True;
Done := True; else
Done := True; end if; end if; end loop;
This paper shows how a taxonomic classification with FCA can fit within the
OAIS RM’s standard structure for information packages in an Archive of Earth
science data. The scaling analysis of the computational load of user-guided
navigation and dynamic FCA needs refinement. Even so, it suggests that this
approach is affordable. [
The author gratefully acknowledges helpful discussions of this paper’s contents with Dr. Mike Folk, Ms. Beth Huffer, Dr. Nancy Hoebelheinrich, and Mr. Gustaf Barkstrom.