RH Logo

All
My Hubs

Data Structures & Algorithms

Trending
Today
All
Papers
Posts
Hypotheses

Sign in to discover all of the research papers you care about, live as they're published.

6
Date Added: Oct 31, 2020
Date Added: Oct 31, 2020
Lock-free shared data structures implement distributed objects without the use of mutual exclusion, thus providing robustness and reliability. We present a new lock-free implementation of singly-linked lists. We prove that the worst-case amortized cost of the operations on our linked lists is linear in the length of the list plus the contention, which is better than in previous lock-free implementations of this data structure. Our implementation uses backlinks that are set when a node is deleted so that concurrent operations visiting the deleted node can recover. To avoid performance problems that would arise from traversing long chains of backlink pointers, we introduce flag bits, which indicate that a deletion of the next node is underway. We then give a lock-free implementation of a skip list dictionary data structure that uses the new linked list algorithms to implement individual levels. Our algorithms use the single-word C&S synchronization primitive.
7
Date Added: Mar 23, 2021
Date Added: Mar 23, 2021
Geomagnetic substorms are a global magnetospheric reconfiguration, during which energy is abruptly transported to the ionosphere. Central to this are the auroral electrojets, large-scale ionospheric currents that are part of a larger three-dimensional system, the substorm current wedge. Many, often conflicting, magnetospheric reconfiguration scenarios have been proposed to describe the substorm current wedge evolution and structure. SuperMAG is a worldwide collaboration providing easy access to ground based magnetometer data. Here we show application of techniques from network science to analyze data from 137 SuperMAG ground-based magnetometers. We calculate a time-varying directed network and perform community detection on the network, identifying locally dense groups of connections. Analysis of 41 substorms exhibit robust structural change from many small, uncorrelated current systems before substorm onset, to a large spatially-extended coherent system, approximately 10 minutes after onset. We interpret this as strong indication that the auroral electrojet system during substorm expansions is inherently a large-scale phenomenon and is not solely due to many meso-scale wedgelets.
5
Date Added: Mar 22, 2021
Date Added: Mar 22, 2021
Optimizing the impact on the economy of control strategies aiming at containing the spread of COVID-19 is a critical challenge. We use daily new case counts of COVID-19 patients reported by local health administrations from different Metropolitan Statistical Areas (MSAs) within the US to parametrize a model that well describes the propagation of the disease in each area. We then introduce a time-varying control input that represents the level of social distancing imposed on the population of a given area and solve an optimal control problem with the goal of minimizing the impact of social distancing on the economy in the presence of relevant constraints, such as a desired level of suppression for the epidemics at a terminal time. We find that with the exception of the initial time and of the final time, the optimal control input is well approximated by a constant, specific to each area, which contrasts with the implemented system of reopening ‘in phases’. For all the areas considered, this optimal level corresponds to stricter social distancing than the level estimated from data. Proper selection of the time period for application of the control action optimally is important: depending on the particular MSA this period should be either short or long or intermediate. We also consider the case that the transmissibility increases in time (due e.g. to increasingly colder weather), for which we find that the optimal control solution yields progressively stricter measures of social distancing. We finally compute the optimal control solution for a model modified to incorporate the effects of vaccinations on the population and we see that depending on a number of factors, social distancing measures could be optimally reduced during the period over which vaccines are administered to the population.
24
Date Added: Dec 2, 2020
Date Added: Dec 2, 2020
The advent of stablecoins offers new and innovative ways to improve financial inclusion, reduce transaction costs, and increase the efficiency of the global financial system. The following paper explores the assets and process necessary for creating a central bank digital currency (CBDC) on the Celo platform, as well as the potential impact on the financial system. Perhaps most importantly, the paper also introduces the idea that current technological advancements allow for a better understanding of the velocity of money, and may afford central banks the ability to influence money velocity, thus potentially creating a new transmission channel for monetary policy.
3
Date Added: Dec 19, 2020
Date Added: Dec 19, 2020
Cyber security is vital to the success of today’s digital economy. The major security threats are coming from within, as opposed to outside forces. Insider threat detection and prediction are important mitigation techniques. This study addresses the following research questions: 1) what are the research trends in insider threat detection and prediction nowadays? 2) What are the challenges associated with insider threat detection and prediction? 3) What are the best-to-date insider threat detection and prediction algorithms? We conduct a systematic review of 37 articles published in peer-reviewed journals, conference proceedings and edited books for the period of 1950–2015 to address the first two questions. Our survey suggests that game theoretic approach (GTA) is a popular source of insider threat data; the insiders’ online activities are the most widely used features in insider threat detection and prediction; most of the papers use single point estimates of threat likelihood; and graph algorithms are the most widely used tools for detecting and predicting insider threats. The key challenges facing the insider threat detection and prediction system include unbounded patterns, uneven time lags between activities, data nonstationarity, individuality, collusion attacks, high false alarm rates, class imbalance problem, undetected insider attacks, uncertainty, and the large number of free parameters in the model. To identify the best-to-date insider threat detection and prediction algorithms, our meta-analysis study excludes theoretical papers proposing conceptual algorithms from the 37 selected papers resulting in the selection of 13 papers. We rank the insider threat detection and prediction algorithms presented in the 13 selected papers based on the theoretical merits and the transparency of information. To determine the significance of rank sums, we perform “the Friedman two-way analysis of variance by ranks” test and “multiple comparisons between groups or conditions” tests.
2
Date Added: Mar 4, 2021
Date Added: Mar 4, 2021
The model of cylindrical anisotropy in the inner core (IC) states that seismic rays traveling parallel to the Earth's rotational axis travel faster than those parallel to the equator. There have been continuing discrepancies in estimates of the strength and orientation of anisotropy, with some evidence suggesting that such a model may not be supported by available data. Here, we scrutinize the radial dependence of anisotropy within the IC, where the nature of anisotropy has been shown to change anywhere between a 300 and 800 km radius. We use recent travel time data from the International Seismological Centre in conjunction with the neighborhood algorithm to provide a robust means of testing this idea, through examination of an ensemble of models that satisfactorily fit the data. This can be done with no explicit regularization and without the need for subjective choices associated with binning of phase data. In addition, uncertainty bounds are calculated for anisotropic parameters using a likelihood ratio approach. We find evidence to suggest that commonly employed spatial averaging (binning) methods may be detrimental to obtaining reliable results. We conclude that there is no significant change in the strength of anisotropy with depth in the IC. Instead, we find a change in the slow direction of anisotropy to 54° within the innermost IC at an ∼650 km radius with fast direction parallel to the Earth's rotational axis.
12
Date Added: Oct 29, 2020
Date Added: Oct 29, 2020
Linearizability is the gold standard of correctness conditions for shared memory algorithms, and historically has been considered the practical equivalent of atomicity. However, it has been shown that replacing atomic objects with linearizable implementations can affect the probability distribution of execution outcomes in randomized algorithms. Thus, linearizable objects are not always suitable replacements for atomic objects. A stricter correctness condition called strong linearizability has been developed and shown to be appropriate for randomized algorithms in a strong adaptive adversary model[16]. We devise several new lock-free strongly linearizable implementations from atomic registers. In particular, we give the first strongly linearizable lock-free snapshot implementation that uses bounded space. This improves on the unbounded space solution of Denysyuk and Woelfel[14]. As a building block, our algorithm uses a lock-free strongly linearizable ABA-detecting register. We obtain this object by modifying the wait-free linearizable ABA-detecting register of Aghazadeh and Woelfel [5], which, as we show, is not strongly linearizable. Aspnes and Herlihy[8] identified a wide class of types that have wait-free linearizable implementations. These types require that any pair of operations either commute, or one overwrites the other. Aspnes and Herlihy gave a general wait-free linearizable implementation of such types, employing an atomic snapshot object. We show that this implementation is strongly linearizable, proving that all types in this class have a lock-free strongly linearizable implementation from atomic registers.