Proteus: A Self-Designing Range Filter

• URL: http://arxiv.org/abs/2207.01503v1
• Date: Thu, 30 Jun 2022 22:43:34 GMT
• Title: Proteus: A Self-Designing Range Filter
• Authors: Eric R. Knorr, Baptiste Lemaire, Andrew Lim, Siqiang Luo, Huanchen Zhang, Stratos Idreos, Michael Mitzenmacher
• Abstract summary: Proteus is a novel self-designing approximate range filter. It unifies the probabilistic and deterministic design spaces of state-of-the-art range filters. Proteus is able to improve end-to-end performance by as much as 5.3x over more brittle state-of-the-art methods.
• Score: 29.998915706012642
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce Proteus, a novel self-designing approximate range filter, which configures itself based on sampled data in order to optimize its false positive rate (FPR) for a given space requirement. Proteus unifies the probabilistic and deterministic design spaces of state-of-the-art range filters to achieve robust performance across a larger variety of use cases. At the core of Proteus lies our Contextual Prefix FPR (CPFPR) model - a formal framework for the FPR of prefix-based filters across their design spaces. We empirically demonstrate the accuracy of our model and Proteus' ability to optimize over both synthetic workloads and real-world datasets. We further evaluate Proteus in RocksDB and show that it is able to improve end-to-end performance by as much as 5.3x over more brittle state-of-the-art methods such as SuRF and Rosetta. Our experiments also indicate that the cost of modeling is not significant compared to the end-to-end performance gains and that Proteus is robust to workload shifts.

Related papers

• Adversarial Transform Particle Filters [11.330617592263744]
  The particle filter (PF) and the ensemble Kalman filter (EnKF) are widely used for approximate inference in state-space models. We propose the Adversarial Transform Particle Filter (ATPF), a novel filtering framework that combines the strengths of the PF and the EnKF through adversarial learning.
  arXiv  Detail & Related papers  (2025-02-10T05:31:35Z)
• Proteus: Preserving Model Confidentiality during Graph Optimizations [5.44122875495684]
  This paper presents Proteus, a novel mechanism that enables model optimization by an independent party. Proteus obfuscates the protected model by partitioning its computational graph into subgraphs. To our knowledge, Proteus is the first work that tackles the challenge of model confidentiality during performance optimization.
  arXiv  Detail & Related papers  (2024-04-18T21:23:25Z)
• Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation [84.0621253654014]
  We propose a framework, called BALLET, which adaptively filters for a high-confidence region of interest. We show theoretically that BALLET can efficiently shrink the search space, and can exhibit a tighter regret bound than standard BO.
  arXiv  Detail & Related papers  (2023-07-25T09:45:47Z)
• Robust Feature Inference: A Test-time Defense Strategy using Spectral Projections [12.807619042576018]
  We propose a novel test-time defense strategy called Robust Feature Inference (RFI) RFI is easy to integrate with any existing (robust) training procedure without additional test-time computation. We show that RFI improves robustness across adaptive and transfer attacks consistently.
  arXiv  Detail & Related papers  (2023-07-21T16:18:58Z)
• Filter Pruning for Efficient CNNs via Knowledge-driven Differential Filter Sampler [103.97487121678276]
  Filter pruning simultaneously accelerates the computation and reduces the memory overhead of CNNs. We propose a novel Knowledge-driven Differential Filter Sampler(KDFS) with Masked Filter Modeling(MFM) framework for filter pruning.
  arXiv  Detail & Related papers  (2023-07-01T02:28:41Z)
• Optimization for truss design using Bayesian optimization [1.5070398746522742]
  The shape of the truss is a dominant factor in determining the capacity of load it can bear. At a given parameter space, our goal is to find the parameters of a hull that maximize the load-bearing capacity and also don't yield to the induced stress. We rely on finite element analysis, which is a computationally costly design analysis tool for design evaluation.
  arXiv  Detail & Related papers  (2023-05-27T10:28:27Z)
• Alternating Objectives Generates Stronger PGD-Based Adversarial Attacks [78.2700757742992]
  Projected Gradient Descent (PGD) is one of the most effective and conceptually simple algorithms to generate such adversaries. We experimentally verify this assertion on a synthetic-data example and by evaluating our proposed method across 25 different $ell_infty$-robust models and 3 datasets. Our strongest adversarial attack outperforms all of the white-box components of AutoAttack ensemble.
  arXiv  Detail & Related papers  (2022-12-15T17:44:31Z)
• FAMLP: A Frequency-Aware MLP-Like Architecture For Domain Generalization [73.41395947275473]
  We propose a novel frequency-aware architecture, in which the domain-specific features are filtered out in the transformed frequency domain. Experiments on three benchmarks demonstrate significant performance, outperforming the state-of-the-art methods by a margin of 3%, 4% and 9%, respectively.
  arXiv  Detail & Related papers  (2022-03-24T07:26:29Z)
• Progressive-Scale Boundary Blackbox Attack via Projective Gradient Estimation [26.16745376395128]
  Boundary based blackbox attack has been recognized as practical and effective, given that an attacker only needs to access the final model prediction. We show that such efficiency highly depends on the scale at which the attack is applied, and attacking at the optimal scale significantly improves the efficiency. We propose Progressive-Scale enabled projective Boundary Attack (PSBA) to improve the query efficiency via progressive scaling techniques.
  arXiv  Detail & Related papers  (2021-06-10T21:13:41Z)
• Adversarial Robustness by Design through Analog Computing and Synthetic Gradients [80.60080084042666]
  We propose a new defense mechanism against adversarial attacks inspired by an optical co-processor. In the white-box setting, our defense works by obfuscating the parameters of the random projection. We find the combination of a random projection and binarization in the optical system also improves robustness against various types of black-box attacks.
  arXiv  Detail & Related papers  (2021-01-06T16:15:29Z)
• Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
  We study a variant of the linear bandit problem wherein we optimize a linear objective function but rewards are accrued only to an unknown subspace. In particular, at each round, the learner must choose whether to query the objective or the protected subspace alongside choosing an action. Our algorithm, derived from the OFUL principle, uses some of the queries to get an estimate of the protected space.
  arXiv  Detail & Related papers  (2020-11-02T14:59:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.