Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “sorting”

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.

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

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1988

Sort computation

Sorting has long been used to organize data in preparation for further computation, but sort computation allows some types of computation to be performed during the sort. Sort aggregation and sort distribution are the two basic forms of sort computation. Sort aggregation generates an accumulative or aggregate result for each group of records and places this result in one of the records. An aggregate operation can be any operation that is both associative and commutative, i.e., any operation whose result does not depend on the order of the operands or the order in which the operations are performed. Sort distribution copies the value from a field of a specific record in a group into that field in every record of that group.

Dorband, John E.↗
NASA NTRS1993

Parallel integer sorting with medium and fine-scale parallelism

Two new parallel integer sorting algorithms, queue-sort and barrel-sort, are presented and analyzed in detail. These algorithms do not have optimal parallel complexity, yet they show very good performance in practice. Queue-sort designed for fine-scale parallel architectures which allow the queueing of multiple messages to the same destination. Barrel-sort is designed for medium-scale parallel architectures with a high message passing overhead. The performance results from the implementation of queue-sort on a Connection Machine CM-2 and barrel-sort on a 128 processor iPSC/860 are given. The two implementations are found to be comparable in performance but not as good as a fully vectorized bucket sort on the Cray YMP.

Dagum, Leonardo↗
NASA NTRS1990

Derivation of sorting programs

Program synthesis for critical applications has become a viable alternative to program verification. Nested resolution and its extension are used to synthesize a set of sorting programs from their first order logic specifications. A set of sorting programs, such as, naive sort, merge sort, and insertion sort, were successfully synthesized starting from the same set of specifications.

Varghese, Joseph↗
NASA NTRS1992

Data parallel sorting for particle simulation

Sorting on a parallel architecture is a communications intensive event which can incur a high penalty in applications where it is required. In the case of particle simulation, only integer sorting is necessary, and sequential implementations easily attain the minimum performance bound of O (N) for N particles. Parallel implementations, however, have to cope with the parallel sorting problem which, in addition to incurring a heavy communications cost, can make the minimun performance bound difficult to attain. This paper demonstrates how the sorting problem in a particle simulation can be reduced to a merging problem, and describes an efficient data parallel algorithm to solve this merging problem in a particle simulation. The new algorithm is shown to be optimal under conditions usual for particle simulation, and its fieldwise implementation on the Connection Machine is analyzed in detail. The new algorithm is about four times faster than a fieldwise implementation of radix sort on the Connection Machine.

Dagum, Leonardo↗
NASA NTRS1978

Sorting on STAR

Timing comparisons are given for three sorting algorithms written for the CDC STAR computer. One algorithm is Hoare's (1962) Quicksort, which is the fastest or nearly the fastest sorting algorithm for most computers. A second algorithm is a vector version of Quicksort that takes advantage of the STAR's vector operations. The third algorithm is an adaptation of Batcher's (1968) sorting algorithm, which makes especially good use of vector operations but has a complexity of N(log N)-squared as compared with a complexity of N log N for the Quicksort algorithms. In spite of its worse complexity, Batcher's sorting algorithm is competitive with the serial version of Quicksort for vectors up to the largest that can be treated by STAR. Vector Quicksort outperforms the other two algorithms and is generally preferred. These results indicate that unusual instruction sets can introduce biases in program execution time that counter results predicted by worst-case asymptotic complexity analysis.

Stone, H. S.↗
NASA NTRS1987

Algorithm Sorts Groups Of Data

For efficient sorting, algorithm finds set containing minimum or maximum most significant data. Sets of data sorted as desired. Sorting process simplified by reduction of each multielement set of data to single representative number. First, each set of data expressed as polynomial with suitably chosen base, using elements of set as coefficients. Most significant element placed in term containing largest exponent. Base selected by examining range in value of data elements. Resulting series summed to yield single representative number. Numbers easily sorted, and each such number converted back to original set of data by successive division. Program written in BASIC.

Evans, J. D.↗
NASA NTRS2020

Using XRD to Characterize Sediment Sorting in a Mars Analog Glacio-Fluvio-Eolian Basaltic Sedimentary System in Iceland

The martian surface has a primarily basaltic composition and is dominated by sedimentary deposits. Ancient layered sedimentary rocks have been identified across the planet from orbit, have been studied in situ by the Mars Exploration Rovers and the Mars Science Laboratory rover, and will be studied by the Mars 2020 rover. These ancient sedimentary rocks were deposited in fluvial, lacustrine, and eolian environments during a warmer and wetter era on Mars. It is important to study the composition of sediments in Mars analog environments to characterize how minerals in basaltic sedimentary systems are sorted and/or aqueously altered. This information can help us better interpret sedimentary processes from similar deposits on Mars and derive information about the igneous source rocks. Sediment sorting has been studied extensively on Earth, but not typically in basaltic environments. Previous work has addressed sorting of basaltic sediments through experimental techniques and in modern eolian basaltic systems and aqueous alteration in subglacial and proglacial environments. We add to this body of research by studying sediment sorting and aqueous alteration in a glacio-fluvio-eolian basaltic system in southwest Iceland.

Rampe, E. B.↗
NASA NTRS2022

Galaxy Correlation Function and Local Density from Photometric Redshifts Using the Stochastic Order Redshift Technique (SORT)

The stochastic order redshift technique (SORT) is a simple, efficient, and robust method to improve cosmological redshift measurements. The method relies upon having a small (∼10 per cent) reference sample of high-quality redshifts. Within pencil- beam-like sub-volumes surrounding each galaxy, we use the precise dN/dz distribution of the reference sample to recover new redshifts and assign them one-to-one to galaxies such that the original rank order of redshifts is preserved. Preserving the rank order is motivated by the fact that random variables drawn from Gaussian probability density functions with different means but equal standard deviations satisfy stochastic ordering. This process is repeated for sub-volumes surrounding each galaxy in the survey. This results in every galaxy being assigned multiple ‘recovered’ redshifts from which a new redshift estimate is determined. An earlier paper applied SORT to a mock Sloan Digital Sky Survey at z 0.2 and accurately recovered the two-point correlation function (2PCF) on scales > 4 h−1Mpc. In this paper, we test the performance of SORT in surveys spanning the redshift range 0.75 < z < 2.25. We used two mock surveys extracted from the Small MultiDark–Planck and Bolshoi–Planck N-body simulations with dark matter haloes that were populated by the Santa Cruz semi-analytic model. We find that SORT overall improves redshift estimates, accurately recovers the redshift-space 2PCF ξ (s) on scales > 2.5 h−1Mpc, and provides improved local density estimates in regions of average or higher density, which may allow for improved understanding of how galaxy properties relate to their environments.

James Kakos↗
NASA NTRS1978

Efficient searching and sorting applications using an associative array processor

The purpose of this paper is to describe a method of searching and sorting data by using some of the unique capabilities of an associative array processor. To understand the application, the associative array processor is described in detail. In particular, the content addressable memory and flip network are discussed because these two unique elements give the associative array processor the power to rapidly sort and search. A simple alphanumeric sorting example is explained in hardware and software terms. The hardware used to explain the application is the STARAN (Goodyear Aerospace Corporation) associative array processor. The software used is the APPLE (Array Processor Programming Language) programming language. Some applications of the array processor are discussed. This summary tries to differentiate between the techniques of the sequential machine and the associative array processor.

Pace, W.↗
NASA NTRSDate not supplied

Design of an AI Trash Sorting Machine for Use on the Moon and Mars

As NASA prepares for Mars colonization, resource conservation will be critical for survival. Artificial Intelligence (AI) powered waste sorting technologies, already emerging on Earth, offer promising solutions for recycling and material recovery. These systems use advanced sensors and machine learning algorithms to identify and separate materials with remarkable accuracy. On Mars, where every item has significant value, efficient recycling will be essential to reduce resupply needs and support closed-loop life support systems. This paper explores how terrestrial AI-based trash sorting technologies can be adapted for Martian conditions, focusing on challenges such as the harsh surface environment, minimizing system mass, power, volume, and estimating waste composition. Addressing these issues will be key to enabling sustainable operations on the Red Planet.

Sorting↗
NASA NTRSDate not supplied

Design of an AI Trash Sorting Machine for Use on the Moon and Mars

As NASA prepares for Mars colonization, resource conservation will be critical for survival. Artificial Intelligence (AI) powered waste sorting technologies, already emerging on Earth, offer promising solutions for recycling and material recovery. These systems use advanced sensors and machine learning algorithms to identify and separate materials with remarkable accuracy. On Mars, where every item has significant value, efficient recycling will be essential to reduce resupply needs and support closed-loop life support systems. This paper explores how terrestrial AI-based trash sorting technologies can be adapted for Martian conditions, focusing on challenges such as the harsh surface environment, minimizing system mass, power, volume, and estimating waste composition. Addressing these issues will be key to enabling sustainable operations on the Red Planet.

AI↗
NASA NTRS1993

Order-sorting filter transmittance measured with an array detector

The simultaneous measurement of the spectrally and spatially variant transmittance of a linear variable order-sorting filter in a manner that closely resembles its conditions of actual use is described. The transmittance of a prototype order-sorting filter was measured in the 400- to 880-nm wavelength region by illuminating it with the output beam of a spectrophotometer while the filter was attached to the front of a 30 x 32 pixel silicon array detector. The filter was designed to be used in the output beam of a grating spectrometer to prevent the dispersal of higher diffracted orders onto an array detector. Areas of the filter that were spatially matched to the corresponding detector pixel column had measured peak transmittances of about 90 percent that were uniform to within +/- 1.5 percent along a given column. Transmittances for incident wavelengths shorter than the desired bandpass, corresponding to the order overlap region, were measured in the 0.003 range. Line spread function measurements made with the array detector indicated no significant beam spreading caused by inserting the filter into the beam.

Heaney, James B.↗
NASA NTRS2010

Mechanism for Particle Transport and Size Sorting via Low-Frequency Vibrations

There is a need for effective sample handling tools to deliver and sort particles for analytical instruments that are planned for use in future NASA missions. Specifically, a need exists for a compact mechanism that allows transporting and sieving particle sizes of powdered cuttings and soil grains that may be acquired by sampling tools such as a robotic scoop or drill. The required tool needs to be low mass and compact to operate from such platforms as a lander or rover. This technology also would be applicable to sample handling when transporting samples to analyzers and sorting particles by size.

Sherrit, Stewart↗
NASA NTRS2013

Shape-induced Gravitational Sorting of Saharan Dust During Transatlantic Voyage: Evidence from CALIOP Lidar Depolarization Measurements

Motivated by the physical picture of shape-dependent air resistance and, consequently, shape-induced differential sedimentation of dust particles, we searched for and found evidence of dust particle asphericity affecting the evolution and distribution of dust-scattered light depolarization ratio (delta). Specifically, we examined a large data set of Cloud-Aerosol Lidar with Orthogonal Polarization (CALIOP) observations of Saharan dust from June to August 2007. Observing along a typical transatlantic dust track, we find that (1) median delta is uniformly distributed between 2 and 5 km altitudes as the elevated dust leaves the west coast of Africa, thereby indicating uniformly random mixing of particle shapes with height; (2) vertical homogeneity of median delta breaks down during the westward transport: between 2 and 5 km delta increases with altitude and this increase becomes more pronounced with westward progress; (3) delta tends to increase at higher altitude (greater than 4 km) and decrease at lower altitude (less than 4 km) during the westward transport. All these features are captured qualitatively by a minimal model (two shapes only), suggesting that shape-induced differential settling and consequent sorting indeed contribute significantly to the observed temporal evolution and vertical stratification of dust properties. By implicating particle shape as a likely cause of gravitational sorting, these results will affect the estimates of radiative transfer through Saharan dust layers.

CALIPSO↗
NASA NTRS2020

Sediment Sorting and Rounding in a Basaltic Glacio-Fluvio-Aeolian Environment: Ϸhórisjökull Glacier, Iceland

Sediments and sedimentary rocks preserve a rich history of environment and climate. Identifying these signals requires an understanding of the physical and chemical processes that have affected sedimentary deposits [1]. Such processes include sorting and rounding during transport and chemical alteration through weathering and diagenesis. Although these processes have long been studied in quartz-dominated sedimentary systems [2], a lack of studies of basaltic sedimentary systems limits our interpretations of the environment and climate where mafic source rocks dominate, such as on Mars [3,4]. As part of the SAND-E: Semi-Autonomous Navigation for Detrital Environments project [5], which uses robotic operations to examine physical and chemical changes to sediments in basaltic glacio-fluvialaeolian environments, this research studies changes in sorting and rounding of fluvial-aeolian sediments along a glacier-proximal-to-glacier-distal transect in the outwash-plain of the Ϸόrisjökull glacier in SW Iceland (Fig. 1)

Mason, K. G.↗
NASA NTRS2021

A Simulation Study of Bin-and-Sort Policies in a Distributed System for Flights Scheduling

This is a report on the results of a simulation experiment conducted on an automated distributed system for scheduling flights in a shared airspace. The scheduling is carried out by computer systems owned by the private operators of the flights, which interface through a centralized independent server. The scheduling requires determining which of the group of flights at hand (whether owned by the same operator or different ones) are to have the advantage of being scheduled before the others. A chosen method of grouping and prioritizing flights must: have the ability to schedule a flight promptly, prevent scheduling conflicts between pairs of overlapping flight routes, and be computationally feasible. Scheduling flights one by one is the First Come First Served policy. Scheduling too many at a time is infeasible. The type of scheduling policy proposed herein, called bin-and-sort, is an attempt to reach a compromise between these two extremes. Bin-and-sort allows for each operator to choose its criteria for prioritizing its flights, and for the centralized component to use different arbitration criteria. A number of these criteria are used in the simulation presented herein. The results of each criterion choice are reported and analyzed.

flight scheduling↗
NASA NTRS2021

A Simulation Study of Bin-and-Sort Policies in a Distributed System for Flights Scheduling

This is a report on the results of a simulation experiment conducted on an automated distributed system for scheduling flights in a shared airspace. The scheduling is carried out by computer systems owned by the private operators of the flights, which interface through a centralized independent server. The scheduling requires determining which of the group of flights at hand (whether owned by the same operator or different ones) are to have the advantage of being scheduled before the others. A chosen method of grouping and prioritizing flights must: have the ability to schedule a flight promptly, prevent scheduling conflicts between pairs of overlapping flight routes, and be computationally feasible. Scheduling flights one by one is the First Come First Served policy. Scheduling too many at a time is infeasible. The type of scheduling policy proposed herein, called bin-and-sort, is an attempt to reach a compromise between these two extremes. Bin-and-sort allows for each operator to choose its criteria for prioritizing its flights, and for the centralized component to use different arbitration criteria. A number of these criteria are used in the simulation presented herein. The results of each criterion choice are reported and analyzed.

flight scheduling↗