More Like this

1. The Geometry of Tree-Based Sorting

   Blelloch, Guy E.; Dobson, Magdalen (May 2023, Dagstuhl Repository)

   We study the connections between sorting and the binary search tree (BST) model, with an aim towards showing that the fields are connected more deeply than is currently appreciated. While any BST can be used to sort by inserting the keys one-by-one, this is a very limited relationship and importantly says nothing about parallel sorting. We show what we believe to be the first formal relationship between the BST model and sorting. Namely, we show that a large class of sorting algorithms, which includes mergesort, quicksort, insertion sort, and almost every instance-optimal sorting algorithm, are equivalent in cost to offline BST algorithms. Our main theoretical tool is the geometric interpretation of the BST model introduced by Demaine et al. [18], which finds an equivalence between searches on a BST and point sets in the plane satisfying a certain property. To give an example of the utility of our approach, we introduce the log-interleave bound, a measure of the information-theoretic complexity of a permutation π, which is within a lg lg n multiplicative factor of a known lower bound in the BST model; we also devise a parallel sorting algorithm with polylogarithmic span that sorts a permutation π using comparisons proportional to its log-interleave bound. Our aforementioned result on sorting and offline BST algorithms can be used to show existence of an offline BST algorithm whose cost is within a constant factor of the log-interleave bound of any permutation π. 

   more » « less
2. The Graph Based Benchmark Suite (GBBS)

   https://doi.org/10.1145/3398682.3399168  

   Dhulipala, Laxman; Shi, Jessica; Tseng, Tom; Blelloch, Guy E.; Shun, Julian (June 2020, GRADES-NDA'20: Proceedings of the 3rd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA))

   null (Ed.)
3. The frontier of simulation-based inference

   https://doi.org/10.1073/pnas.1912789117  

   Cranmer, Kyle; Brehmer, Johann; Louppe, Gilles (May 2020, Proceedings of the National Academy of Sciences)

   Many domains of science have developed complex simulations to describe phenomena of interest. While these simulations provide high-fidelity models, they are poorly suited for inference and lead to challenging inverse problems. We review the rapidly developing field of simulation-based inference and identify the forces giving additional momentum to the field. Finally, we describe how the frontier is expanding so that a broad audience can appreciate the profound influence these developments may have on science. 

   more » « less
4. The Fast and the Private: Task-based Dataset Search

   Huang, Zezou; Liu, Jiaxiang; Wang, Haonan; Wu, Eugene (January 2024, Conference on Innovative Data Systems Research)

   Recent platforms utilize ML task performance metrics, not metadata keywords, to search large data corpus. Requesters provide an initial dataset, and the platform searches for additional datasets that augment---join or union---requester's dataset to most improve the model (e.g., linear regression) performance. Although effective, current task-based data searches are stymied by (1) high latency which deters users, (2) privacy concerns for regulatory standards, and (3) low data quality which provides low utility. We introduce Mileena, a fast, private, and high-quality task-based dataset search platform. At its heart, Mileena is built on pre-computed semi-ring sketches for efficient ML training and evaluation. Based on semi-ring, we develop a novel Factorized Privacy Mechanism that makes the search differentially private and scales to arbitrary corpus sizes and numbers of requests without major quality degradation. We also demonstrate the early promise in using LLM-based agents for automatic data transformation and applying semi-rings to support causal discovery and treatment effect estimation. 

   more » « less
5. Can Host-Based SDNs Rival the Traffic Engineering Abilities of Switch-Based SDNs?

   Lei, Yunsen; Lanson, Julian P.; Kaldawy, Remy M.; Estrada, Jeffrey; Shue, Craig A. (October 2020, IEEE Network of the Future (NoF))

   The software-defined networking (SDN) paradigm offers significant flexibility for network operators. However, the SDN community has focused on switch-based implementations, which pose several challenges. First, some may require significant hardware costs to upgrade a network. Further, fine-grained flow control in a switch-based SDN results in well-known, fundamental scalability limitations. These challenges may limit the reach of SDN technologies. In this work, we explore the extent to which host-based SDN agents can achieve feature parity with switch-based SDNs. Prior work has shown the potential of host-based SDNs for security and access control. Our study finds that with appropriate preparation, a host-based agent offers the same capabilities of switch-based SDNs in the remaining key area of traffic engineering, even in a legacy managed-switch network. We find the approach offers comparable performance to switch-based SDNs while eliminating the flow table scalability and cost concerns of switch-based SDN deployments. 

   more » « less