More Like this

1. Heuristic AND/OR Search for Solving Influence Diagram

   https://doi.org/10.1609/SOCS.V11I1.18523  

   Lee, Junkyu; Marinescu, Radu; Dechter, Rina (May 2020, Proceedings of the International Symposium on Combinatorial Search)

   An influence diagram is a graphical representation of sequential decision-making under uncertainty, defining a structured decision problem by conditional probability functions and additive utility functions over discrete state and action variables. The task of finding the maximum expected utility of influence diagrams is closely related to the cost-optimal probabilistic planning, stochastic programmings, or model-based reinforcement learning. In this position paper, we address the heuristic search for solving influence diagram, where we generate admissible heuristic functions from graph decomposition schemes. Then, we demonstrate how such heuristics can guide an AND/OR branch and bound search. Finally, we briefly discuss the future directions for improving the quality of heuristic functions and search strategies. 

   more » « less
2. Verifying concurrent multicopy search structures

   https://doi.org/10.1145/3485490  

   Patel, Nisarg; Krishna, Siddharth; Shasha, Dennis; Wies, Thomas (October 2021, Proceedings of the ACM on Programming Languages)

   Multicopy search structures such as log-structured merge (LSM) trees are optimized for high insert/update/delete (collectively known as upsert) performance. In such data structures, an upsert on keyk, which adds (k,v) wherevcan be a value or a tombstone, is added to the root node even ifkis already present in other nodes. Thus there may be multiple copies ofkin the search structure. A search onkaims to return the value associated with the most recent upsert. We present a general framework for verifying linearizability of concurrent multicopy search structures that abstracts from the underlying representation of the data structure in memory, enabling proof-reuse across diverse implementations. Based on our framework, we propose template algorithms for (a) LSM structures forming arbitrary directed acyclic graphs and (b) differential file structures, and formally verify these templates in the concurrent separation logic Iris. We also instantiate the LSM template to obtain the first verified concurrent in-memory LSM tree implementation. 

   more » « less
3. Learning Explainable Templated Graphical Model

   Embar, Varun; Srinivasan, Sriram; Getoor, Lise (August 2022, Uncertainty in artificial intelligence)

   Templated graphical models (TGMs) encode model structure using rules that capture recurring relationships between multiple random variables. While the rules in TGMs are interpretable, it is not clear how they can be used to generate explanations for the individual predictions of the model. Further, learning these rules from data comes with high computational costs: it typically requires an expensive combinatorial search over the space of rules and repeated optimization over rule weights. In this work, we propose a new structure learning algorithm, Explainable Structured Model Search (ESMS), that learns a templated graphical model and an explanation framework for its predictions. ESMS uses a novel search procedure to efficiently search the space of models and discover models that trade-off predictive accuracy and explainability. We introduce the notion of relational stability and prove that our proposed explanation framework is stable. Further, our proposed piecewise pseudolikelihood (PPLL) objective does not require re-optimizing the rule weights across models during each iteration of the search. In our empirical evaluation on three realworld datasets, we show that our proposed approach not only discovers models that are explainable, but also significantly outperforms existing state-out-the-art structure learning approaches. 

   more » « less
4. Efficient Graph Reconstruction and Representation Using Augmented Persistence Diagrams

   Fasy, Brittany Terese; Micka, Samuel; Millman, David L.; Schenfisch, Anna; Williams, Lucy (August 2022, Canadian Conference on Computational Geometry (CCCG))

   Persistent homology is a tool that can be employed to summarize the shape of data by quantifying homological features. When the data is an object in R d , the (augmented) persistent homology transform ((A)PHT) is a family of persistence diagrams, parameterized by directions in the ambient space. A recent advance in understanding the PHT used the framework of reconstruction in order to find finite a set of directions to faithfully represent the shape, a result that is of both theoretical and practical interest. In this paper, we improve upon this result and present an improved algorithm for graph— and, more generally one-skeleton—reconstruction. The improvement comes in reconstructing the edges, where we use a radial binary (multi-)search. The binary search employed takes advantage of the fact that the edges can be ordered radially with respect to a reference plane, a feature unique to graphs. 

   more » « less
5. Time- and Space-Efficient Aggregate Range Queries over Encrypted Databases

   https://doi.org/10.56553/popets-2022-0128  

   Espiritu, Zachary; Markatou, Evangelia Anna; Tamassia, Roberto (October 2022, Proceedings on Privacy Enhancing Technologies)

   We present ARQ, a systematic framework for creating cryptographic schemes that handle range aggregate queries (sum, minimum, median, and mode) over encrypted datasets. Our framework does not rely on trusted hardware or specialized cryptographic primitives such as property-preserving or homomorphic encryption. Instead, ARQ unifies structures from the plaintext data management community with existing structured encryption primitives. We prove how such combinations yield efficient (and secure) constructions in the encrypted setting. We also propose a series of domain reduction techniques that can improve the space efficiency of our schemes against sparse datasets at the cost of small leakage. As part of this work, we designed and implemented a new, open-source, encrypted search library called Arca and implemented the ARQ framework using this library in order to evaluate ARQ’s practicality. Our experiments on real-world datasets demonstrate the efficiency of the schemes derived from ARQ in comparison to prior work. 

   more » « less