SEARCH · Search NASA

Results for “data structures”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2

All sources NASA NTRS DOE OSTI

DOE OSTI2022

NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20

The C++ Standard Library is a valuable collection of generic algorithms and data structures that improves the usability and reliability of C++ software. Graph algorithms and data structures are notably absent from the standard library, and previous attempts to fill this gap have not gained widespread adoption. In this paper we show that the richness of graph algorithms and data structures can in fact be captured by straightforward composition of existing C++ mechanisms. Generic programming is algorithm-oriented. Accordingly, we apply a systematic approach to analyzing a broad set of graph algorithms, “lift” unnecessary constraints from them, and organize the resulting set of minimal common type requirements, i.e., concepts, for defining their interfaces. By using the newly available ranges and concepts in C++20, the type requirements for generic graph algorithms can be succinctly expressed. The generic algorithms and data structures resulting from our analysis are realized in NWGraph, in a modern, composable, and extensible C++ library.

graphs and networks, programming language, C++20↗

NASA NTRS1987

Local concurrent error detection and correction in data structures using virtual backpointers

A new technique, based on virtual backpointers, for local concurrent error detection and correction in linked data structures is presented. Two new data structures, the Virtual Double Linked List, and the B-tree with Virtual Backpointers, are described. For these structures, double errors can be detected in 0(1) time and errors detected during forward moves can be corrected in 0(1) time. The application of a concurrent auditor process to data structure error detection and correction is analyzed, and an implementation is described, to determine the effect on mean time to failure of a multi-user shared database system. The implementation utilizes a Sequent shared memory multiprocessor system operating on a shared databased of Virtual Double Linked Lists.

Li, C. C.↗

NASA NTRS1983

Algorithms and data structures for adaptive multigrid elliptic solvers

Adaptive refinement and the complicated data structures required to support it are discussed. These data structures must be carefully tuned, especially in three dimensions where the time and storage requirements of algorithms are crucial. Another major issue is grid generation. The options available seem to be curvilinear fitted grids, constructed on iterative graphics systems, and unfitted Cartesian grids, which can be constructed automatically. On several grounds, including storage requirements, the second option seems preferrable for the well behaved scalar elliptic problems considered here. A variety of techniques for treatment of boundary conditions on such grids are reviewed. A new approach, which may overcome some of the difficulties encountered with previous approaches, is also presented.

Vanrosendale, J.↗

DOE OSTI2019

Concurrent data structures in the ATLAS offline software

In preparation for Run 3 of the LHC, the ATLAS experiment is modifying its offline software to be fully multithreaded. An important part of this is data structures that can be concurrently accessed from many threads both efficiently and safely. A standard way of achieving this is through mutual exclusion; however, the overhead from this can sometimes be excessive. Fully lockless implementations are known for some data structures; however, they are typically complex, and the overhead they require can sometimes be larger than that required for locking implementations. An interesting compromise is to allow lockless access only for reading but not for writing. This often allows the data structures to be much simpler, while still giving good performance for read-mostly access patterns. This proceeding shows some examples of this strategy in data structures used by the ATLAS offline software. It also gives examples of synchronization strategies inspired by read-copy-update, as well as helpers for memorizing values in a multithreaded environment.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

DOE OSTI2020

Performance and usability enhancements for continuous subgraph matching queries on graph-structured data

A query graph, which includes vertices and edges, represents a query on graph-structured data. The query graph is decomposed into query subgraphs. A network analysis tool performs continuous subgraph matching queries to facilitate analysis of computer network traffic, social media events, or other streams of data represented as a dynamic data graph (graph-structured data). This can help identify emerging trends in the data. Some features of the network analysis tool enhance performance by effectively utilizing distributed computing resources (including processing cores and memory at different nodes of a cluster) to speed up the process of updating the dynamic data graph and detecting matches of query subgraphs. Features of a query graph building tool enhance usability by providing intuitive ways to specify query graphs and their subgraphs. Features of a results visualization tool enhance usability by providing an intuitive way to present the results of continuous subgraph matching queries.

Choudhury, Sutanay↗

NASA NTRS1982

Conversion of raster coded images to polygonal data structures

A method is presented for converting polygons coded in raster data structures into conventional vector structures to allow the output of scanner-based data collection systems to be input directly to conventional geographic information systems. The method relies on topological principles to (1) uniquely label each polygon in the image and produce an output image in which each pixel is described by the label of the polygon to which it belongs; (2) create line segment components of polygon boundaries, with nodes labeled and the two adjacent polygons identified; and (3) traverse the polygon boundaries by connecting the appropriate adjacent line segments. The conversion capability makes it possible to design systems which automatically convert to the data structure most appropriate for a particular application.

Nichols, D. A.↗

DOE OSTI2022

Supply Chain Risk Management: Data Structuring

Supply chain risk management (SCRM) is an area of research that addresses both logistics concepts to maximize efficiency, reliability, and revenue as well as risk features, such as potential weak points, break points, and vulnerabilities within the supply chain. SCRM is used to find risks introduced at each node in a supply chain and how these risks can impact a company’s products, individuals, customers, and reputation. SCRM is a relatively new field, so standardized processes including data structuring are not fully documented. This paper explains the importance of a standard data structuring methodology and how it can enhance current SCRM efforts. Data ingest, structuring, and analysis are predominantly managed by humans. Automating some of the less complex steps can positively impact SCRM by allowing human analysts to focus on more strategic analyses. Types of data to be collected and structured are collected via publicly available information related to hardware, software, and corporate entities. After the data has been collected, the information is formatted in a specific manner, conforming to a schema, to allow for more effective and efficient ingest for further analysis. This paper outlines data structures used by Pacific Northwest National Laboratory for SCRM research and analysis purposes. These structures have been used for hundreds of analyses and have been successful in developing a common baseline. Data structuring is one of the first steps in data standardization, which will further mature and enhance the SCRM research area.

supply chain risk management, data structuring, re↗

DOE OSTI2019

BCL: A Cross-Platform Distributed Data Structures Library

One-sided communication is a useful paradigm for irregular parallel applications, but most one-sided programming environments, including MPI's one-sided interface and PGAS programming languages, lack application-level libraries to support these applications. We present the Berkeley Container Library, a set of generic, cross-platform, high-performance data structures for irregular applications, including queues, hash tables, Bloom filters and more. BCL is written in C++ using an internal DSL called the BCL Core that provides one-sided communication primitives such as remote get and remote put operations. The BCL Core has backends for MPI, OpenSHMEM, GASNet-EX, and UPC++, allowing BCL data structures to be used natively in programs written using any of these programming environments. Along with our internal DSL, we present the BCL ObjectContainer abstraction, which allows BCL data structures to transparently serialize complex data types while maintaining efficiency for primitive types. We also introduce the set of BCL data structures and evaluate their performance across a number of high-performance computing systems, demonstrating that BCL programs are competitive with hand-optimized code, even while hiding many of the underlying details of message aggregation, serialization, and synchronization.

Brock, Benjamin↗

NASA NTRS1987

Investigation of candidate data structures and search algorithms to support a knowledge based fault diagnosis system

The focus of this research is the investigation of data structures and associated search algorithms for automated fault diagnosis of complex systems such as the Hubble Space Telescope. Such data structures and algorithms will form the basis of a more sophisticated Knowledge Based Fault Diagnosis System. As a part of the research, several prototypes were written in VAXLISP and implemented on one of the VAX-11/780's at the Marshall Space Flight Center. This report describes and gives the rationale for both the data structures and algorithms selected. A brief discussion of a user interface is also included.

Bosworth, Edward L., Jr.↗

NASA NTRS1986

Advanced data structures for the interpretation of image and cartographic data in geo-based information systems

A growing need to usse geographic information systems (GIS) to improve the flexibility and overall performance of very large, heterogeneous data bases was examined. The Vaster structure and the Topological Grid structure were compared to test whether such hybrid structures represent an improvement in performance. The use of artificial intelligence in a geographic/earth sciences data base context is being explored. The architecture of the Knowledge Based GIS (KBGIS) has a dual object/spatial data base and a three tier hierarchial search subsystem. Quadtree Spatial Spectra (QTSS) are derived, based on the quadtree data structure, to generate and represent spatial distribution information for large volumes of spatial data.

Peuquet, D. J.↗

DOE OSTI2021

NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1997

Querying Semi-Structured Data

The amount of data of all kinds available electronically has increased dramatically in recent years. The data resides in different forms, ranging from unstructured data in the systems to highly structured in relational database systems. Data is accessible through a variety of interfaces including Web browsers, database query languages, application-specic interfaces, or data exchange formats. Some of this data is raw data, e.g., images or sound. Some of it has structure even if the structure is often implicit, and not as rigid or regular as that found in standard database systems. Sometimes the structure exists but has to be extracted from the data. Sometimes also it exists but we prefer to ignore it for certain purposes such as browsing. We call here semi-structured data this data that is (from a particular viewpoint) neither raw data nor strictly typed, i.e., not table-oriented as in a relational model or sorted-graph as in object databases. As will seen later when the notion of semi-structured data is more precisely de ned, the need for semi-structured data arises naturally in the context of data integration, even when the data sources are themselves well-structured. Although data integration is an old topic, the need to integrate a wider variety of data- formats (e.g., SGML or ASN.1 data) and data found on the Web has brought the topic of semi-structured data to the forefront of research. The main purpose of the paper is to isolate the essential aspects of semi- structured data. We also survey some proposals of models and query languages for semi-structured data. In particular, we consider recent works at Stanford U. and U. Penn on semi-structured data. In both cases, the motivation is found in the integration of heterogeneous data.

DATA MANAGEMENT↗

NASA NTRS1989

Local concurrent error detection and correction in data structures using virtual backpointers

A new technique, based on virtual backpointers, for local concurrent error detection and correction in linked data strutures is presented. Two new data structures, the Virtual Double Linked List, and the B-tree with Virtual Backpointers, are described. For these structures, double errors can be detected in 0(1) time and errors detected during forward moves can be corrected in 0(1) time. The application of a concurrent auditor process to data structure error detection and correction is analyzed, and an implementation is described, to determine the effect on mean time to failure of a multi-user shared database system. The implementation utilizes a Sequent shared memory multiprocessor system operating on a shared database of Virtual Double Linked Lists.

Li, Chung-Chi Jim↗

NASA NTRS1990

Supporting shared data structures on distributed memory architectures

Programming nonshared memory systems is more difficult than programming shared memory systems, since there is no support for shared data structures. Current programming languages for distributed memory architectures force the user to decompose all data structures into separate pieces, with each piece owned by one of the processors in the machine, and with all communication explicitly specified by low-level message-passing primitives. A new programming environment is presented for distributed memory architectures, providing a global name space and allowing direct access to remote parts of data values. The analysis and program transformations required to implement this environment are described, and the efficiency of the resulting code on the NCUBE/7 and IPSC/2 hypercubes are described.

Koelbel, Charles↗

DOE OSTI2019

iEEG-BIDS, extending the Brain Imaging Data Structure specification to human intracranial electrophysiology

he Brain Imaging Data Structure (BIDS) is a community-driven specification for organizing neuroscience data and metadata with the aim to make datasets more transparent, reusable, and reproducible. Intracranial electroencephalography (iEEG) data offer a unique combination of high spatial and temporal resolution measurements of the living human brain. To improve internal (re)use and external sharing of these unique data, we present a specification for storing and sharing iEEG data: iEEG-BIDS.

Science & Technology - Other Topics↗

NASA NTRS1993

Certification trails for data structures

Certification trails are a recently introduced and promising approach to fault detection and fault tolerance. The applicability of the certification trail technique is significantly generalized. Previously, certification trails had to be customized to each algorithm application; trails appropriate to wide classes of algorithms were developed. These certification trails are based on common data-structure operations such as those carried out using these sets of operations such as those carried out using balanced binary trees and heaps. Any algorithms using these sets of operations can therefore employ the certification trail method to achieve software fault tolerance. To exemplify the scope of the generalization of the certification trail technique provided, constructions of trails for abstract data types such as priority queues and union-find structures are given. These trails are applicable to any data-structure implementation of the abstract data type. It is also shown that these ideals lead naturally to monitors for data-structure operations.

Sullivan, Gregory F.↗

NASA NTRS1984

Advanced Data Structure and Geographic Information Systems

The current state of the art in specified areas of Geographic Information Systems GIS technology is examined. Study of the question of very large, efficient, heterogeneous spatial databases is required in order to explore the potential application of remotely sensed data for studying the long term habitability of the Earth. Research includes a review of spatial data structures and storage, development of operations required by GIS, and preparation of a testbed system to compare Vaster data structure with NASA's Topological Raster Structure.

Peuquet, D.↗

NASA NTRS1990

Sphere quadtrees - A new data structure to support the visualization of spherically distributed data

The concept of the sphere quadtree (SQT) is introduced to enable the structuring of spherically distributed data to be consistent with its geometry and facilitate mapping of the data onto a flat file system. The SQT is based on the recursive subdivision of the spherical triangles that result from the projection of the faces of an icosahedron onto a sphere. The SQT concept is insensitive to the distortions that occur far from the equator in spherically distributed data sets. Geographic data can be shown at several levels and at any resolution, allowing a system of referencing between data sets of different resolutions as well as data that are not geographically registered. SQTs are found to facilitate the search for particular spherically distributed data sets and improve the efficiency of surface rendering algorithms.

Fekete, Gyorgy↗