Search

Retrieving points based on proximity in a high-dimensional vector space is a crucial step in information retrieval applications. The approximate nearest neighbor search (ANNS) problem, which identifies the $k$ nearest neighbors for a query (approximately, since exactly is hard), has been extensively studied in recent years. However, comparatively little attention has been paid to the related problem of finding all points within a given distance of a query, the range retrieval problem, despite its applications in areas such as duplicate detection, plagiarism checking, and facial recognition. In this paper, we present a set of algorithms for range retrieval on graph-based vector indices, which are known to achieve excellent performance on ANNS queries. Since a range query may have anywhere from no matching results to thousands of matching results in the database, we introduce a set of range retrieval algorithms based on modifications of the standard graph search that adapt to terminate quickly on queries in the former group, and to put more resources into finding results for the latter group. Due to the lack of existing benchmarks for range retrieval, we also undertake a comprehensive study of range characteristics of existing embedding datasets, and select a suitable range retrieval radius for eight existing datasets with up to 100 million points in addition to the one existing benchmark. We test our algorithms on these datasets, and find up to 100x improvement in query throughput over a naive baseline approach, with 5-10x improvement on average, and strong performance up to 100 million data points.

In this paper, we give theoretically and practically efficient implementations of Big Atomics, i.e., $k$-word linearizable registers that support the load, store, and compare-and-swap (CAS) operations. While modern hardware supports $k = 1$ and sometimes $k = 2$ (e.g., double-width compare-and-swap in x86), our implementations support arbitrary $k$. Big Atomics are useful in many applications, including atomic manipulation of tuples, version lists, and implementing load-linked/store-conditional (LL/SC). We design fast, lock-free implementations of big atomics based on a novel fast-path-slow-path approach we develop. We then use them to develop an efficient concurrent hash table, as evidence of their utility. We experimentally validate the approach by comparing a variety of implementations of big atomics under a variety of workloads (thread counts, load/store ratios, contention, oversubscription, and number of atomics). The experiments compare two of our lock-free variants with C++ std::atomic, a lock-based version, a version using sequence locks, and an indirect version. The results show that our approach is close to the fastest under all conditions and far outperforms others under oversubscription. We also compare our big atomics based concurrent hash table to a variety of other state-of-the-art hash tables that support arbitrary length keys and values, including implementations from Intel's TBB, Facebook's Folly, libcuckoo, and a recent release from Boost. The results show that our approach of using big atomics in the design of hash tables is a promising direction.

Dynamic trees are a well-studied and fundamental building block of dynamic graph algorithms dating back to the seminal work of Sleator and Tarjan [STOC'81, (1981), pp. 114-122]. The problem is to maintain a tree subject to online edge insertions and deletions while answering queries about the tree, such as the heaviest weight on a path, etc. In the parallel batch-dynamic setting, the goal is to process batches of edge updates work efficiently in low ($\text{polylog}\ n$) span. Two work-efficient algorithms are known, batch-parallel Euler Tour Trees by Tseng et al. [ALENEX'19, (2019), pp. 92-106] and parallel Rake-Compress (RC) Trees by Acar et al. [ESA'20, (2020), pp. 2:1-2:23]. Both however are randomized and work efficient in expectation. Several downstream results that use these data structures (and indeed to the best of our knowledge, all known work-efficient parallel batch-dynamic graph algorithms) are therefore also randomized. In this work, we give the first deterministic work-efficient solution to the problem. Our algorithm maintains a dynamic parallel tree contraction subject to batches of $k$ edge updates deterministically in worst-case $O(k \log(1 + n/k))$ work and $O(\log n \log^{(c)} k)$ span for any constant $c$. This allows us to implement parallel batch-dynamic RC-Trees with worst-case $O(k \log(1 + n/k))$ work updates and queries deterministically. Our techniques that we use to obtain the given span bound can also be applied to the state-of-the-art randomized variant of the algorithm to improve its span from $O(\log n \log^* n)$ to $O(\log n)$.

The future Ricochet experiment aims to search for new physics in the electroweak sector by measuring the Coherent Elastic Neutrino-Nucleus Scattering process from reactor antineutrinos with high precision down to the sub-100 eV nuclear recoil energy range. While the Ricochet collaboration is currently building the experimental setup at the reactor site, it is also finalizing the cryogenic detector arrays that will be integrated into the cryostat at the Institut Laue Langevin in early 2024. In this paper, we report on recent progress from the Ge cryogenic detector technology, called the CryoCube. More specifically, we present the first demonstration of a 30~eVee (electron equivalent) baseline ionization resolution (RMS) achieved with an early design of the detector assembly and its dedicated High Electron Mobility Transistor (HEMT) based front-end electronics. This represents an order of magnitude improvement over the best ionization resolutions obtained on similar heat-and-ionization germanium cryogenic detectors from the EDELWEISS and SuperCDMS dark matter experiments, and a factor of three improvement compared to the first fully-cryogenic HEMT-based preamplifier coupled to a CDMS-II germanium detector. Additionally, we discuss the implications of these results in the context of the future Ricochet experiment and its expected background mitigation performance., Comment: 10 pages, 5 figures, 1 table

Approximate nearest-neighbor search (ANNS) algorithms are a key part of the modern deep learning stack due to enabling efficient similarity search over high-dimensional vector space representations (i.e., embeddings) of data. Among various ANNS algorithms, graph-based algorithms are known to achieve the best throughput-recall tradeoffs. Despite the large scale of modern ANNS datasets, existing parallel graph based implementations suffer from significant challenges to scale to large datasets due to heavy use of locks and other sequential bottlenecks, which 1) prevents them from efficiently scaling to a large number of processors, and 2) results in nondeterminism that is undesirable in certain applications. In this paper, we introduce ParlayANN, a library of deterministic and parallel graph-based approximate nearest neighbor search algorithms, along with a set of useful tools for developing such algorithms. In this library, we develop novel parallel implementations for four state-of-the-art graph-based ANNS algorithms that scale to billion-scale datasets. Our algorithms are deterministic and achieve high scalability across a diverse set of challenging datasets. In addition to the new algorithmic ideas, we also conduct a detailed experimental study of our new algorithms as well as two existing non-graph approaches. Our experimental results both validate the effectiveness of our new techniques, and lead to a comprehensive comparison among ANNS algorithms on large scale datasets with a list of interesting findings.

Coherent elastic neutrino-nucleus scattering (CE$\nu$NS) offers valuable sensitivity to physics beyond the Standard Model. The Ricochet experiment will use cryogenic solid-state detectors to perform a precision measurement of the CE$\nu$NS spectrum induced by the high neutrino flux from the Institut Laue-Langevin nuclear reactor. The experiment will employ an array of detectors, each with a mass of $\sim$30 g and a targeted energy threshold of 50 eV. Nine of these detectors (the "Q-Array") will be based on a novel Transition-Edge Sensor (TES) readout style, in which the TES devices are thermally coupled to the absorber using a gold wire bond. We present initial characterization of a Q-Array-style detector using a 1 gram silicon absorber, obtaining a baseline root-mean-square resolution of less than 40 eV., Comment: 18 pages, 8 figures

In the context of direct searches of sub-GeV Dark Matter particles with germanium detectors, the EDELWEISS collaboration has tested a new technique to tag ionizing events using NbSi transition edge athermal phonon sensors. The emission of the athermal phonons generated by the Neganov-Trofimov-Luke effect associated with the drift of electrons and holes through the detectors is used to tag ionization events generated in specific parts of the detector localized in front of the NbSi sensor and to reject by more than a factor 5 (at 90% C.L.) the background from heat-only events that dominates the spectrum above 3 keV. This method is able to improve by a factor 2.8 the previous limit on spin-independent interactions of 1 GeV/c2 WIMPs obtained with the same detector and data set but without this tagging technique., Comment: 13 pages, 11 figures

Evidence accumulation models (EAMs) are an important class of cognitive models used to analyze both response time and response choice data recorded from decision-making tasks. Developments in estimation procedures have helped EAMs become important both in basic scientific applications and solution-focussed applied work. Hierarchical Bayesian estimation frameworks for the linear ballistic accumulator model (LBA) and the diffusion decision model (DDM) have been widely used, but still suffer from some key limitations, particularly for large sample sizes, for models with many parameters, and when linking decision-relevant covariates to model parameters. We extend upon previous work with methods for estimating the LBA and DDM in hierarchical Bayesian frameworks that include random effects which are correlated between people, and include regression-model links between decision-relevant covariates and model parameters. Our methods work equally well in cases where the covariates are measured once per person (e.g., personality traits or psychological tests) or once per decision (e.g., neural or physiological data). We provide methods for exact Bayesian inference, using particle-based MCMC, and also approximate methods based on variational Bayesian (VB) inference. The VB methods are sufficiently fast and efficient that they can address large-scale estimation problems, such as with very large data sets. We evaluate the performance of these methods in applications to data from three existing experiments. Detailed algorithmic implementations and code are freely available for all methods., Comment: 92 pages including supplement, 29 figures, 6 tables

Multiversioning is widely used in databases, transactional memory, and concurrent data structures. It can be used to support read-only transactions that appear atomic in the presence of concurrent update operations. Any system that maintains multiple versions of each object needs a way of efficiently reclaiming them. We experimentally compare various existing reclamation techniques by applying them to a multiversion tree and a multiversion hash table. Using insights from these experiments, we develop two new multiversion garbage collection (MVGC) techniques. These techniques use two novel concurrent version list data structures. Our experimental evaluation shows that our fastest technique is competitive with the fastest existing MVGC techniques, while using significantly less space on some workloads. Our new techniques provide strong theoretical bounds, especially on space usage. These bounds ensure that the schemes have consistent performance, avoiding the very high worst-case space usage of other techniques., Comment: Full version of a paper appearing in PPoPP'23

The performance of today's in-memory indexes is bottlenecked by the memory latency/bandwidth wall. Processing-in-memory (PIM) is an emerging approach that potentially mitigates this bottleneck, by enabling low-latency memory access whose aggregate memory bandwidth scales with the number of PIM nodes. There is an inherent tension, however, between minimizing inter-node communication and achieving load balance in PIM systems, in the presence of workload skew. This paper presents PIM-tree, an ordered index for PIM systems that achieves both low communication and high load balance, regardless of the degree of skew in the data and the queries. Our skew-resistant index is based on a novel division of labor between the multi-core host CPU and the PIM nodes, which leverages the strengths of each. We introduce push-pull search, which dynamically decides whether to push queries to a PIM-tree node (CPU -> PIM-node) or pull the node's keys back to the CPU (PIM-node -> CPU) based on workload skew. Combined with other PIM-friendly optimizations (shadow subtrees and chunked skip lists), our PIM-tree provides high-throughput, (guaranteed) low communication, and (guaranteed) high load balance, for batches of point queries, updates, and range scans. We implement the PIM-tree structure, in addition to prior proposed PIM indexes, on the latest PIM system from UPMEM, with 32 CPU cores and 2048 PIM nodes. On workloads with 500 million keys and batches of one million queries, the throughput using PIM-trees is up to 69.7x and 59.1x higher than the two best prior methods. As far as we know these are the first implementations of an ordered index on a real PIM system.

The future Ricochet experiment aims at searching for new physics in the electroweak sector by providing a high precision measurement of the Coherent Elastic Neutrino-Nucleus Scattering (CENNS) process down to the sub-100 eV nuclear recoil energy range. The experiment will deploy a kg-scale low-energy-threshold detector array combining Ge and Zn target crystals 8.8 meters away from the 58 MW research nuclear reactor core of the Institut Laue Langevin (ILL) in Grenoble, France. Currently, the Ricochet collaboration is characterizing the backgrounds at its future experimental site in order to optimize the experiment's shielding design. The most threatening background component, which cannot be actively rejected by particle identification, consists of keV-scale neutron-induced nuclear recoils. These initial fast neutrons are generated by the reactor core and surrounding experiments (reactogenics), and by the cosmic rays producing primary neutrons and muon-induced neutrons in the surrounding materials. In this paper, we present the Ricochet neutron background characterization using $^3$He proportional counters which exhibit a high sensitivity to thermal, epithermal and fast neutrons. We compare these measurements to the Ricochet Geant4 simulations to validate our reactogenic and cosmogenic neutron background estimations. Eventually, we present our estimated neutron background for the future Ricochet experiment and the resulting CENNS detection significance., Comment: 14 pages, 14 figures, 1 table

Many modern programming languages are shifting toward a functional style for collection interfaces such as sets, maps, and sequences. Functional interfaces offer many advantages, including being safe for parallelism and providing simple and lightweight snapshots. However, existing high-performance functional interfaces such as PAM, which are based on balanced purely-functional trees, incur large space overheads for large-scale data analysis due to storing every element in a separate node in a tree. This paper presents PaC-trees, a purely-functional data structure supporting functional interfaces for sets, maps, and sequences that provides a significant reduction in space over existing approaches. A PaC-tree is a balanced binary search tree which blocks the leaves and compresses the blocks using arrays. We provide novel techniques for compressing and uncompressing the blocks which yield practical parallel functional algorithms for a broad set of operations on PaC-trees such as union, intersection, filter, reduction, and range queries which are both theoretically and practically efficient. Using PaC-trees we designed CPAM, a C++ library that implements the full functionality of PAM, while offering significant extra functionality for compression. CPAM consistently matches or outperforms PAM on a set of microbenchmarks on sets, maps, and sequences while using about a quarter of the space. On applications including inverted indices, 2D range queries, and 1D interval queries, CPAM is competitive with or faster than PAM, while using 2.1--7.8x less space. For static and streaming graph processing, CPAM offers 1.6x faster batch updates while using 1.3--2.6x less space than the state-of-the-art graph processing system Aspen., Comment: This is a preliminary version of a paper that will appear at the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2022)

Safe memory reclamation (SMR) schemes are an essential tool for lock-free data structures and concurrent programming. However, manual SMR schemes are notoriously difficult to apply correctly, and automatic schemes, such as reference counting, have been argued for over a decade to be too slow for practical purposes. A recent wave of work has disproved this long-held notion and shown that reference counting can be as scalable as hazard pointers, one of the most common manual techniques. Despite these tremendous improvements, there remains a gap of up to 2x or more in performance between these schemes and faster manual techniques such as epoch-based reclamation (EBR). In this work, we first advance these ideas and show that in many cases, automatic reference counting can in fact be as fast as the fastest manual SMR techniques. We generalize our previous Concurrent Deferred Reference Counting (CDRC) algorithm to obtain a method for converting any standard manual SMR technique into an automatic reference counting technique with a similar performance profile. Our second contribution is extending this framework to support weak pointers, which are reference-counted pointers that automatically break pointer cycles by not contributing to the reference count, thus addressing a common weakness in reference-counted garbage collection. Our experiments with a C++-library implementation show that our automatic techniques perform in line with their manual counterparts, and that our weak pointer implementation outperforms the best known atomic weak pointer library by up to an order of magnitude on high thread counts. All together, we show that the ease of use of automatic memory management can be achieved without significant cost to practical performance or general applicability.

Coherent elastic neutrino-nucleus scattering (CE$\nu$NS) is a process in which neutrinos scatter on a nucleus which acts as a single particle. Though the total cross section is large by neutrino standards, CE$\nu$NS has long proven difficult to detect, since the deposited energy into the nucleus is $\sim$ keV. In 2017, the COHERENT collaboration announced the detection of CE$\nu$NS using a stopped-pion source with CsI detectors, followed up the detection of CE$\nu$NS using an Ar target. The detection of CE$\nu$NS has spawned a flurry of activities in high-energy physics, inspiring new constraints on beyond the Standard Model (BSM) physics, and new experimental methods. The CE$\nu$NS process has important implications for not only high-energy physics, but also astrophysics, nuclear physics, and beyond. This whitepaper discusses the scientific importance of CE$\nu$NS, highlighting how present experiments such as COHERENT are informing theory, and also how future experiments will provide a wealth of information across the aforementioned fields of physics., Comment: contribution to Snowmasss 2021. Contact authors: P. S. Barbeau, R. Strauss, L. E. Strigari

The EDELWEISS collaboration reports on the search for Dark Matter (DM) particle interactions via Migdal effect with masses between $32$ MeV$\cdot$c$^{-2}$ to $2$ GeV$\cdot$c$^{-2}$ using a $200$ g cryogenic Ge detector sensitive to simultaneously heat and ionization signals and operated underground at the Laboratoire Souterrain de Modane in France. The phonon signal was read out using a Transition Edge Sensor made of a NbSi thin film. The detector was biased at $66$ V in order to benefit from the Neganov-Trofimov-Luke amplification and resulting in a resolution on the energy of electron recoils of $4.46$ eV$_{ee}$ (RMS) and an analysis threshold of $30$ eV$_{ee}$. The sensitivity is limited by a dominant background not associated to charge creation in the detector. The search constrains a new region of parameter space for cross-sections down to $10^{-29}$ cm$^2$ and masses between $32$ and $100$ MeV$\cdot$c$^{-2}$. The achieved low threshold with the NbSi sensor shows the relevance of its use for athermal-phonon sensitive devices for low-mass DM searches., Comment: 10 pages, 9 figures

Many low-threshold experiments observe sharply rising event rates of yet unknown origins below a few hundred eV, and larger than expected from known backgrounds. Due to the significant impact of this excess on the dark matter or neutrino sensitivity of these experiments, a collective effort has been started to share the knowledge about the individual observations. For this, the EXCESS Workshop was initiated. In its first iteration in June 2021, ten rare event search collaborations contributed to this initiative via talks and discussions. The contributing collaborations were CONNIE, CRESST, DAMIC, EDELWEISS, MINER, NEWS-G, NUCLEUS, RICOCHET, SENSEI and SuperCDMS. They presented data about their observed energy spectra and known backgrounds together with details about the respective measurements. In this paper, we summarize the presented information and give a comprehensive overview of the similarities and differences between the distinct measurements. The provided data is furthermore publicly available on the workshop's data repository together with a plotting tool for visualization., Comment: 44 pages, 20 figures; Editors: A. Fuss, M. Kaznacheeva, F. Reindl, F. Wagner; updated copyright statements and funding information

This paper presents a new and practical approach to lock-free locks based on helping, which allows the user to write code using fine-grained locks, but run it in a lock-free manner. Although lock-free locks have been suggested in the past, they are widely viewed as impractical, have some key limitations, and, as far as we know, have never been implemented. The paper presents some key techniques that make lock-free locks practical and more general. The most important technique is an approach to idempotence -- i.e. making code that runs multiple times appear as if it ran once. The idea is based on using a shared log among processes running the same protected code. Importantly, the approach can be library based, requiring very little if any change to standard code -- code just needs to use the idempotent versions of memory operations (load, store, LL/SC, allocation, free). We have implemented a C++ library called Flock based on the ideas. Flock allows lock-based data structures to run in either lock-free or blocking (traditional locks) mode. We implemented a variety of tree and list-based data structures with Flock and compare the performance of the lock-free and blocking modes under a variety of workloads. The lock-free mode is almost as fast as blocking mode under almost all workloads, and significantly faster when threads are oversubscribed (more threads than processors). We also compare with several existing lock-based and lock-free alternatives., Comment: This is the full version of the paper appearing in PPoPP 2022

We present a randomized approach for wait-free locks with strong bounds on time and fairness in a context in which any process can be arbitrarily delayed. Our approach supports a tryLock operation that is given a set of locks, and code to run when all the locks are acquired. A tryLock operation, or attempt, may fail if there is contention on the locks, in which case the code is not run. Given an upper bound $\kappa$ known to the algorithm on the point contention of any lock, and an upper bound $L$ on the number of locks in a tryLock's set, a tryLock will succeed in acquiring its locks and running the code with probability at least $1/(\kappa L)$. It is thus fair. Furthermore, if the maximum step complexity for the code in any lock is $T$, the attempt will take $O(\kappa^2 L^2 T)$ steps, regardless of whether it succeeds or fails. The attempts are independent, thus if the tryLock is repeatedly retried on failure, it will succeed in $O(\kappa^3 L^3 T)$ expected steps, and with high probability in not much more.

Non-volatile random access memory (NVRAM) offers byte-addressable persistence at speeds comparable to DRAM. However, with caches remaining volatile, automatic cache evictions can reorder updates to memory, potentially leaving persistent memory in an inconsistent state upon a system crash. Flush and fence instructions can be used to force ordering among updates, but are expensive. This has motivated significant work studying how to write correct and efficient persistent programs for NVRAM. In this paper, we present FliT, a C++ library that facilitates writing efficient persistent code. Using the library's default mode makes any linearizable data structure durable with minimal changes to the code. FliT avoids many redundant flush instructions by using a novel algorithm to track dirty cache lines. The FliT library also allows for extra optimizations, but achieves good performance even in its default setting. To describe the FliT library's capabilities and guarantees, we define a persistent programming interface, called the P-V Interface, which FliT implements. The P-V Interface captures the expected behavior of code in which some instructions' effects are persisted and some are not. We show that the interface captures the desired semantics of many practical algorithms in the literature. We apply the FliT library to four different persistent data structures, and show that across several workloads, persistence implementations, and data structure sizes, the FliT library always improves operation throughput, by at least $2.1\times$ over a naive implementation in all but one workload.

We present a general technique for garbage collecting old versions for multiversion concurrency control that simultaneously achieves good time and space complexity. Our technique takes only $O(1)$ time on average to reclaim each version and maintains only a constant factor more versions than needed (plus an additive term). It is designed for multiversion schemes using version lists, which are the most common. Our approach uses two components that are of independent interest. First, we define a novel range-tracking data structure which stores a set of old versions and efficiently finds those that are no longer needed. We provide a wait-free implementation in which all operations take amortized constant time. Second, we represent version lists using a new lock-free doubly-linked list algorithm that supports efficient (amortized constant time) removals given a pointer to any node in the list. These two components naturally fit together to solve the multiversion garbage collection problem--the range-tracker identifies which versions to remove and our list algorithm can then be used to remove them from their version lists. We apply our garbage collection technique to generate end-to-end time and space bounds for the multiversioning system of Wei et al. (PPoPP 2021)., Comment: This is the full version of the paper appearing in the International Symposium on Distributed Computing (DISC 2021)

Self-adjusting computation is an approach for automatically producing dynamic algorithms from static ones. The approach works by tracking control and data dependencies, and propagating changes through the dependencies when making an update. Extensively studied in the sequential setting, some results on parallel self-adjusting computation exist, but are either only applicable to limited classes of computations, such as map-reduce, or are ad-hoc systems with no theoretical analysis of their performance. In this paper, we present the first system for parallel self-adjusting computation that applies to a wide class of nested parallel algorithms and provides theoretical bounds on the work and span of the resulting dynamic algorithms. As with bounds in the sequential setting, our bounds relate a "distance" measure between computations on different inputs to the cost of propagating an update. However, here we also consider parallelism in the propagation cost. The main innovation in the paper is in using Series-Parallel trees (SP trees) to track sequential and parallel control dependencies to allow propagation of changes to be applied safely in parallel. We show both theoretically and through experiments that our system allows algorithms to produce updated results over large datasets significantly faster than from-scratch execution. We demonstrate our system with several example applications, including algorithms for dynamic sequences and dynamic trees. In all cases studied, we show that parallel self-adjusting computation can provide a significant benefit in both work savings and parallel time.

Model comparison is the cornerstone of theoretical progress in psychological research. Common practice overwhelmingly relies on tools that evaluate competing models by balancing in-sample descriptive adequacy against model flexibility, with modern approaches advocating the use of marginal likelihood for hierarchical cognitive models. Cross-validation is another popular approach but its implementation has remained out of reach for cognitive models evaluated in a Bayesian hierarchical framework, with the major hurdle being prohibitive computational cost. To address this issue, we develop novel algorithms that make variational Bayes (VB) inference for hierarchical models feasible and computationally efficient for complex cognitive models of substantive theoretical interest. It is well known that VB produces good estimates of the first moments of the parameters which gives good predictive densities estimates. We thus develop a novel VB algorithm with Bayesian prediction as a tool to perform model comparison by cross-validation, which we refer to as CVVB. In particular, the CVVB can be used as a model screening device that quickly identifies bad models. We demonstrate the utility of CVVB by revisiting a classic question in decision making research: what latent components of processing drive the ubiquitous speed-accuracy tradeoff? We demonstrate that CVVB strongly agrees with model comparison via marginal likelihood yet achieves the outcome in much less time. Our approach brings cross-validation within reach of theoretically important psychological models, and makes it feasible to compare much larger families of hierarchically specified cognitive models than has previously been possible., Comment: 35 pages, 8 figures

We present a randomized $O(m \log^2 n)$ work, $O(\text{polylog } n)$ depth parallel algorithm for minimum cut. This algorithm matches the work bounds of a recent sequential algorithm by Gawrychowski, Mozes, and Weimann [ICALP'20], and improves on the previously best parallel algorithm by Geissmann and Gianinazzi [SPAA'18], which performs $O(m \log^4 n)$ work in $O(\text{polylog } n)$ depth. Our algorithm makes use of three components that might be of independent interest. Firstly, we design a parallel data structure that efficiently supports batched mixed queries and updates on trees. It generalizes and improves the work bounds of a previous data structure of Geissmann and Gianinazzi and is work efficient with respect to the best sequential algorithm. Secondly, we design a parallel algorithm for approximate minimum cut that improves on previous results by Karger and Motwani. We use this algorithm to give a work-efficient procedure to produce a tree packing, as in Karger's sequential algorithm for minimum cuts. Lastly, we design an efficient parallel algorithm for solving the minimum $2$-respecting cut problem., Comment: This is the full version of the paper appearing in the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021