26838 research outputs found
Sort by
Variable strings for pangenomes
No full textThis dissertation investigates the computational foundations of sequence analysis in the context of pangenomics, a rapidly evolving field in computational biology. Classical string algorithms, originally developed for linear DNA sequences, encounter new challenges when extended to nonlinear, graph-like pangenome representations. To address this, we study variable strings—generalized models for representing sets of similar sequences compactly, including elastic-degenerate strings (ED strings), founder graphs, and weighted sequences. The thesis makes three core contributions. First, it explores exact and approximate pattern matching algorithms for variable strings, establishing tight upper and lower bounds. Second, it introduces novel methods for comparing pangenomic data structures, including algorithms for intersection detection, matching statistics, and distance-based comparisons. Third, it proposes space-efficient indexing strategies for weighted sequences, enabling probabilistic pattern queries under uncertainty
Adaptive cloud VR gaming optimized by gamer QoE models
Get PDFCloud Virtual Reality (VR) gaming offloads computationally intensive VR games to resourceful data centers. However, ensuring good Quality of Experience (QoE) in cloud VR gaming is inherently challenging as VR gamers demand high visual quality, short response time, and negligible cybersickness. In this article, we study the QoE of cloud VR gaming and build a QoE-optimized system in a few steps. First, we establish a cloud VR gaming testbed capable of emulating various network conditions. Using the testbed, we conduct comprehensive QoE evaluations using a user study to evaluate the influence of diverse factors, such as encoding settings, network conditions, and game genres, on gamer QoE scores. Second, we construct the very first QoE models for cloud VR gaming using our QoE evaluation results. Our QoE models achieve up to 0.93 (σ = 0.02) in Pearson Linear Correlation Coefficient (PLCC) and 0.92 (σ = 0.02) in Spearman Rank-Order Correlation Coefficient (SROCC), where σ stands for the standard deviation. Last, we leverage our QoE models for dynamically adapting encoding settings in our testbed. Extensive experiments revealed that, compared to the current practice, our adaptive cloud VR gaming system improves: (i) overall quality by 0.87 (σ = 0.44), (ii) visual quality by 0.61 (σ = 0.45), and (iii) interaction quality by 1.20 (σ = 0.48) on average in 5-point Mean Opinion Score (MOS)
Process mining on national health care data for the discovery of patient journeys of older adults
Get PDFObjective: Understanding the longitudinal patterns of health care utilization among older adults is crucial for designing effective patient journeys and enhancing care coordination across settings. This study aims to uncover the most common patient journeys of older adults. Design: This explorative study used process mining techniques to analyze national health care data from 2017 to 2019, focusing on patient care journeys of older adults (aged ≥65 years) in the Netherlands. Setting and Participants: Data were sourced from Statistics Netherlands, encompassing all residents aged ≥65 years as of January 1, 2017. Health care usage declarations from various care settings during 2017-2019 were included. Patient journeys were exclusively selected if their initiation points were certain. Methods: Data underwent rigorous preprocessing, merging, and filtering to create a single event log file suitable for process mining. Patients were categorized by age and medication use, and differences in patient journeys were analyzed. Process mining techniques generated visualizations illustrating the connections between care forms and the impact of changes in one form on others. Results: The study included 3,177,203 individuals aged 65 years and older, with 44% experiencing 1 or more patient journeys totaling 2,469,663 journeys in 2017-2019. Most care journeys for older adults were simple and short. The top 10 most frequent journeys had 4 or fewer care forms, with 95% of journeys for the 65+ population and 90% for the 85+ population having 4 or fewer care transitions. Long-term care forms, such as home care, personal care, and long-term care, accounted for the majority of time spent in the system. Conclusions and Implications: This pioneering study used process mining to show that most older adults tend to have a straightforward health care need, often involving the emergency department and hospitalizations. However, a smaller group among the population requires more complex and prolonged care, especially in the 85+ population. Reducing the number of transitions for this population, although impacting fewer people, might result in a larger effect on the overall system
Global vs. s-t vertex connectivity beyond sequential: Almost-perfect reductions and near-optimal separations
Get PDFA recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequential model. This raises a natural question: What is the relationship between s-t and global vertex connectivity in other computational models? In this paper, we demonstrate that the connection between global and s-t variants behaves very differently across computational models.
In parallel and distributed models, we obtain almost tight reductions from global to s-t vertex connectivity. In PRAM, this leads to a -work and -depth algorithm for vertex connectivity, improving over the 35-year-old -work -depth algorithm by [LLW FOCS'86], where is the matrix multiplication exponent and is the number of vertices. In CONGEST, the reduction implies the first sublinear-round vertex connectivity algorithm when the diameter is moderately small. This answers an open question in [JM STOC'23]. In contrast, we show that global vertex connectivity is strictly harder than s-t vertex connectivity in the two-party communication setting, requiring bits of communication. The s-t variant was known to be solvable in communication [BvdBEMN FOCS'22]. Our results resolve open problems raised by [MN STOC'20, BvdBEMN FOCS'22, AS SOSA'23]. At the heart of our results is a new graph decomposition framework we call common-neighborhood clustering, which can be applied in multiple models. Finally, we observe that global vertex connectivity cannot be solved without using s-t vertex connectivity by proving an s-t to global reduction in dense graphs in the PRAM and communication models
On uniqueness of power sum decomposition
Get PDFWe propose an algorithm to compute power sum decompositions, which are motivated by applications in algebraic statistics. Power sum decomposition entails writing forms of degree as a sum of th powers of -forms. We show that under certain assumptions, the power sum problem for -forms can be reduced to the classical case of power sums of linear forms. Semidefinite programming is used to perform this reduction. The semidefinite programming approach allows us to improve the currently best known rank bounds for the problem from to , in a typical case. An implementation of the algorithm is provided. We complement the theoretical analysis with numerical experiments
Single-copy stabilizer testing
Get PDFWe consider the problem of testing whether an unknown n-qubit quantum state is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using copies, and conversely prove that copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity
White paper - Toward practical anonymity: A white paper on privacy risk, metrics, and governance in synthetic data
No full textStructured synthetic data is presented as a maturing technology for privacy preservation that facilitates compliance with data protection regulations. The difficulty of defining when such data can be considered anonymous under existing legal frameworks is highlighted, given the absence of a universal standard, even as emerging best practices begin to provide guidance for privacy compliance. A comprehensive analysis is provided of the relevant legal and regulatory context, empirical methods for privacy risk evaluation, and adversarial threat modeling approaches. Privacy risk metrics and technical mitigation techniques are examined, and governance considerations for enterprise data management and compliance are addressed. Finally, the need for industry standard-setting initiatives is underscored, and a recommendation is made to pursue formal standards for privacy-preserving data synthesis
Still asking: How good are query optimizers, really?
Get PDFThis retrospective revisits our 2015 PVLDB paper How Good Are Query Optimizers, Really?, which challenged the prevailing notion that query optimization was a solved problem. By designing the Join Order Benchmark (JOB) and conducting a series of systematic experiments, we empirically disentangled the contributions of plan enumeration, cost modeling, and cardinality estimation. Our findings showed that cardinality estimation errors are widespread and often the dominant factor behind poor query plans, while cost models and enumeration strategies matter comparatively less. The benchmark and methodology helped refocus the community’s attention on cardinality estimation and led to a resurgence of research in this area, including learned and AI-based approaches. We reflect on the role of experiments and benchmarking in database research, survey developments in query optimization over the past decade, and discuss open challenges around robustness, adaptive execution, and realistic workloads
Optimal prefix-suffix queries with applications
No full textWe revisit the classic border tree data structure [Gu, Farach, Beigel, SODA 1994] that answers the following prefix-suffix queries on a string of length over an integer alphabet : for any return all occurrences of in . The border tree of can be constructed in time and answers prefix-suffix queries in time, where is the number of occurrences of in . Our contribution here is the following. We present a completely different and remarkably simple data structure that can be constructed in the optimal time and supports queries in the optimal time. Our result is based on a new structural lemma that lets us encode the output of any query in constant time andspace. We also show a new direct application of our result in pattern matching on node-labeled graphs
When Is String Reconstruction Using de Bruijn Graphs Hard?
Get PDFThe reduction of the fragment assembly problem to (variations of) the classical Eulerian trail problem [Pevzner et al., PNAS 2001] has led to remarkable progress in genome assembly. This reduction employs the notion of de Bruijn graph G = (V, E) of order k over an alphabet Σ. A single Eulerian trail in G represents a candidate genome reconstruction. Bernardini et al. have also introduced the complementary idea in data privacy [ALENEX 2020] based on z-anonymity. Let S be a private string that we would like to release, preventing, however, its full reconstruction. For a privacy threshold z > 0, we compute the largest k for which there exist at least z Eulerian trails in the order-k de Bruijn graph of S, and release a string S′ obtained via a random Eulerian trail. The pressing question is: How hard is it to reconstruct a best string from a de Bruijn graph given a function that models domain knowledge? Such a function maps every length-k string to an interval of positions where it may occur in the reconstructed string. By the above reduction to de Bruijn graphs, the latter function translates into a function c mapping every edge to an interval where it may occur in an Eulerian trail. This gives rise to the following basic problem on graphs: Given an instance (G, c), can we efficiently compute an Eulerian trail respecting c? Hannenhalli et al. [CABIOS 1996] formalized this problem and showed that it is NP-complete. Ben-Dor et al. [J. Comput. Biol. 2002] showed that it is NP-complete, even on de Bruin graphs with |Σ| = 4. In this work, we settle the lower-bound side of this problem by showing that finding a c-respecting Eulerian trail in de Bruijn graphs over alphabets of size 2 is NP-complete. We then shift our focus to parametrization aiming to capture the quality of our domain knowledge in the complexity. Ben-Dor et al. developed an algorithm to solve the problem on de Bruijn graphs in O(m · w1.54w) time, where m = |E| and w is the maximum interval length over all edges in E. Bumpus and Meeks [Algorithmica 2023] later rediscovered the same algorithm on temporal graphs, which highlights the relevance of this problem in other contexts. Our central contribution is showing how combinatorial insights lead to exponential-time improvements over the state-of-the-art algorithm. In particular, for the important class of de Bruijn graphs, we develop an algorithm parametrized by w(log w + 1)/(k − 1): for a de Bruijn graph of order k, it runs in O(mw · 2 k−1 ) time. Our w(log w+1) result improves on the state of the art by roughly an exponent of (log w + 1)/(k − 1). The existing algorithms have a natural interpretation for string reconstruction: when for each length-k string, we know a small range of positions it must lie in, string reconstruction can be solved in linear time. Our improved algorithm shows that it is enough when the range of positions is small relative to k. We then generalize both the existing and our novel FPT algorithm by allowing the cost at every position of an interval to vary. In this optimization version, our hardness result translates into inapproximability and the FPT algorithms work with a slight extension. Surprisingly, even in this more general setting, we extend the FPT algorithms to count and enumerate the min-cost Eulerian trails. The counting result has direct applications in the data privacy framework of Bernardini et al