Search for: All records

Storing tabular data to balance storage and query efficiency is a long-standing research question in the database community. In this work, we argue and show that a novel {\em DeepMapping} abstraction, which relies on the impressive {\em memorization} capabilities of deep neural networks, can provide better storage cost, better latency, and better run-time memory footprint, all at the same time. Such unique properties may benefit a broad class of use cases in capacity-limited devices. Our proposed DeepMapping abstraction transforms a dataset into multiple key-value mappings and constructs a multi-tasking neural network model that outputs the corresponding \textit{values} for a given input \textit{key}. To deal with memorization errors, DeepMapping couples the learned neural network with a lightweight auxiliary data structure capable of correcting mistakes. The auxiliary structure design further enables DeepMapping to efficiently deal with insertions, deletions, and updates even without retraining the mapping. We propose a multi-task search strategy for selecting the hybrid DeepMapping structures (including model architecture and auxiliary structure) with a desirable trade-off among memorization capacity, size, and efficiency. Extensive experiments with a real-world dataset, synthetic and benchmark datasets, including TPC-H and TPC-DS, demonstrated that the DeepMapping approach can better balance the retrieving speed and compression ratio against several cutting-edge competitors. 

DNA has shown great biocompatibility, programmable mechanical properties, and precise structural addressabil- ity at the nanometer scale, rendering it a material for constructing versatile nanorobots for biomedical applica- tions. Here, we present the design principle, synthesis, and characterization of a DNA nanorobotic hand, called DNA NanoGripper, that contains a palm and four bendable fingers as inspired by naturally evolved human hands, bird claws, and bacteriophages. Each NanoGripper finger consists of three phalanges connected by three rotat- able joints that are bendable in response to the binding of other entities. NanoGripper functions are enabled and driven by the interactions between moieties attached to the fingers and their binding partners. We demonstrate that the NanoGripper can be engineered to effectively interact with and capture nanometer-scale objects, includ- ing gold nanoparticles, gold NanoUrchins, and SARS-CoV-2 virions. With multiple DNA aptamer nanoswitches programmed to generate a fluorescent signal that is enhanced on a photonic crystal platform, the NanoGripper functions as a highly sensitive biosensor that selectively detects intact SARS-CoV-2 virions in human saliva with a limit of detection of ~100 copies per milliliter, providing a sensitivity equal to that of reverse transcription quanti- tative polymerase chain reaction (RT-qPCR). Quantified by flow cytometry assays, we demonstrated that the NanoGripper-aptamer complex can effectively block viral entry into the host cells, suggesting its potential for in- hibiting virus infections. The design, synthesis, and characterization of a sophisticated nanomachine that can be tailored for specific applications highlight a promising pathway toward feasible and efficient solutions to the de- tection and potential inhibition of virus infections. 

We prove a new generalization bound that shows for any class of linear predictors in Gaussian space, the Rademacher complexity of the class and the training error under any continuous loss ℓ can control the test error under all Moreau envelopes of the loss ℓ . We use our finite-sample bound to directly recover the “optimistic rate” of Zhou et al. (2021) for linear regression with the square loss, which is known to be tight for minimal ℓ2-norm interpolation, but we also handle more general settings where the label is generated by a potentially misspecified multi-index model. The same argument can analyze noisy interpolation of max-margin classifiers through the squared hinge loss, and establishes consistency results in spiked-covariance settings. More generally, when the loss is only assumed to be Lipschitz, our bound effectively improves Talagrand’s well-known contraction lemma by a factor of two, and we prove uniform convergence of interpolators (Koehler et al. 2021) for all smooth, non-negative losses. Finally, we show that application of our generalization bound using localized Gaussian width will generally be sharp for empirical risk minimizers, establishing a non-asymptotic Moreau envelope theory