More Like this

1. Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors

   https://doi.org/10.4230/LIPIcs.SEA.2023.8  

   Afshar, Ramtin; Dillencourt, Michael; Goodrich, Michael T; Ozel, Evrim (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Georgiadis, Loukas (Ed.)

   We provide and study several algorithms for sorting an array of n comparable distinct elements subject to probabilistic comparison errors. In this model, the comparison of two elements returns the wrong answer according to a fixed probability, p_e < 1/2, and otherwise returns the correct answer. The dislocation of an element is the distance between its position in a given (current or output) array and its position in a sorted array. There are various algorithms that can be utilized for sorting or near-sorting elements subject to probabilistic comparison errors, but these algorithms are not data oblivious because they all make heavy use of noisy binary searching. In this paper, we provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. In addition, we experimentally compare our algorithms and other sorting algorithms. 

   more » « less
2. Sorting in Memristive Memory

   https://doi.org/10.1145/3517181  

   Alam, Mohsen Riahi; Najafi, M. Hassan; TaheriNejad, Nima (February 2022, ACM Journal on Emerging Technologies in Computing Systems)

   Sorting data is needed in many application domains. Traditionally, the data is read from memory and sent to a general-purpose processor or application-specific hardware for sorting. The sorted data is then written back to the memory. Reading/writing data from/to memory and transferring data between memory and processing unit incur significant latency and energy overhead. In this work, we develop the first architectures for in-memory sorting of data to the best of our knowledge. We propose two architectures. The first architecture is applicable to the conventional format of representing data, i.e., weighted binary radix. The second architecture is proposed for developing unary processing systems, where data is encoded as uniform unary bit-streams. As we present, each of the two architectures has different advantages and disadvantages, making one or the other more suitable for a specific application. However, the common property of both is a significant reduction in the processing time compared to prior sorting designs. Our evaluations show on average 37 × and 138 × energy reduction for binary and unary designs, respectively, compared to conventional CMOS off-memory sorting systems in a 45nm technology. We designed a 3 × 3 and a 5 × 5 Median filter using the proposed sorting solutions, which we used for processing 64 × 64 pixel images. Our results show a reduction of 14 × and 634 × in energy and latency, respectively, with the proposed binary, and 5.6 × and 152 × 10 3 in energy and latency with the proposed unary approach compared to those of the off-memory binary and unary designs for the 3 × 3 Median filtering system. 

   more » « less
3. Spatial Sorting and Inequality

   https://doi.org/10.1146/annurev-economics-051420-110839  

   Diamond, Rebecca; Gaubert, Cecile (August 2022, Annual Review of Economics)

   The spatial segregation of college-educated and non-college-educated workers between commuting zones in the United States has steadily grown since 1980. We summarize prior work on sorting and location and document new descriptive patterns on how sorting and locations have changed over the past four decades. We find that there has been a shift in the sorting of college-educated workers from cities centered primarily around production in 1980 to cities centered around consumption by 2017. We develop a spatial equilibrium model to understand these patterns and highlight key places where further research is needed. Our framework helps understand the causes and consequences of changes in spatial sorting; their impact on inequality; and how they respond to, and feed into, the changing nature of cities. 

   more » « less
4. Sorting out microtubule-based transport

   https://doi.org/10.1038/s41580-020-00320-y  

   Yildiz, Ahmet (February 2021, Nature Reviews Molecular Cell Biology)
5. Versatile phenotype-activated cell sorting

   https://doi.org/10.1126/sciadv.abb7438  

   Lee, Jihwan; Liu, Zhuohe; Suzuki, Peter H.; Ahrens, John F.; Lai, Shujuan; Lu, Xiaoyu; Guan, Sihui; St-Pierre, François (October 2020, Science Advances)

   null (Ed.)

   Unraveling the genetic and epigenetic determinants of phenotypes is critical for understanding and re-engineering biology and would benefit from improved methods to separate cells based on phenotypes. Here, we report SPOTlight, a versatile high-throughput technique to isolate individual yeast or human cells with unique spatiotemporal profiles from heterogeneous populations. SPOTlight relies on imaging visual phenotypes by microscopy, precise optical tagging of single target cells, and retrieval of tagged cells by fluorescence-activated cell sorting. To illustrate SPOTlight’s ability to screen cells based on temporal properties, we chose to develop a photostable yellow fluorescent protein for extended imaging experiments. We screened 3 million cells expressing mutagenesis libraries and identified a bright new variant, mGold, that is the most photostable yellow fluorescent protein reported to date. We anticipate that the versatility of SPOTlight will facilitate its deployment to decipher the rules of life, understand diseases, and engineer new molecules and cells. 

   more » « less