9607 research outputs found
Sort by
Building a Data Management System for the Cloud: Lessons Learned and Future Directions
No full textThe paper discusses the lessons learned from building Snowflake, a data management system for the cloud. Given the need for systems that can scale to handle large data volumes, provide expressive programming interfaces, and leverage the benefits of cloud computing, it describes the architecture of a cloud-based data management system and optimization techniques specific to the cloud. Key techniques include pruning large file sets at both compile time and query runtime, optimizing data layouts in the background, and, more generally, the importance of performing maintenance tasks in the background, which is enabled by cloud resources. The paper also explains the need for using immutable files and the implications for data modification queries. Finally, it highlights the operational aspects of building and maintaining a data management system that functions as an online cloud service. The paper concludes by outlining future directions for cloud-based data management systems
The Eighth Rhetoric of Play
No full textTo Brian Sutton-Smith’s catalogue of seven play rhetorics in his influential work, The Ambiguity of Play, the author adds an eighth category—the rhetoric of computational play, connecting the research field of game studies with other forms of play studies. By proposing this rhetoric, Sicart seeks to consolidate the relation between game studies and play studies
No Silver Bullet:Towards Demonstrating Secure Software Development for Small and Medium Enterprises in a Business-to-Business Model
Get PDFSoftware developing small and medium enterprises (SMEs) play a crucial role as suppliers to larger corporations and public administration. It is therefore necessary for them to be able to demonstrate that their products meet certain security criteria, both to gain trust of their customers and to comply to standards that demand such a demonstration. In this study we have investigated ways for SMEs to demonstrate their security when operating in a business-to-business model, conducting semi-structured interviews (N=16) with practitioners from different SMEs in Denmark and validating our findings in a follow-up workshop (N=6). Our findings indicate five distinctive security demonstration approaches, namely: Certifications, Reports, Questionnaires, Interactive Sessions and Social Proof. We discuss the challenges, benefits, and recommendations related to these approaches, concluding that none of them is a one-size-fits all solution and that more research into relative advantages of these approaches and their combinations is needed
The Churns and Turns of HCI: Which CHI Papers Make the Most Impact in an Ever-growing Sea of HCI Publications
No full textThe ACM Conference on Human Factors in Computing Systems (CHI) is the premier venue for research in Human-Computer Interaction (HCI). 11,290 full papers have been published and collectively cited almost one million times. Highly cited papers undoubtedly represent influential work, affecting the creation of review standards and conference submission and acceptance practices within and beyond CHI. However, the factors contributing to high citation counts and what constitutes a highly cited CHI paper remain largely unclear. In this panel discussion, we will engage the CHI community in exploring the relationship between paper characteristics, citation numbers, and effective impact on HCI as a discipline, and on HCI as an influential endeavour in technology design and development. To ground this discussion, we present findings from a literature review of the 100 most cited CHI full papers, looking at past and present fields and subfields of influence. We will also share insights from HCI experts. Our goals are to shed light on the meaning of impactful work at CHI and in HCI more broadly, to reflect on key trends in HCI over the years, and to discuss themes that have driven pivotal shifts in HCI research. We will lead the conversation toward a deeper understanding of citation practices, the role of citations in focusing and driving HCI research, and the implications of citation when it comes to shaping what is considered impactful HCI
Maximum List r-Colorable Induced Subgraphs in kP₃-Free Graphs.
No full textWe show that, for every fixed positive integers r and k, Max-Weight List r-Colorable Induced Subgraph admits a polynomial-time algorithm on kP3-free graphs. This problem is a common generalization of Max-Weight Independent Set, Odd Cycle Transversal and List r-Coloring, among others. Our result has several consequences. First, it implies that, for every fixed r ≥ 5, assuming P ≠ NP, Max-Weight List r-Colorable Induced Subgraph is polynomial-time solvable on H-free graphs if and only if H is an induced subgraph of either kP3 or P5 + kP1, for some k ≥ 1. Second, it makes considerable progress toward a complexity dichotomy for Odd Cycle Transversal on H-free graphs, allowing to answer a question of Agrawal, Lima, Lokshtanov, Rzążewski, Saurabh, and Sharma [ACM Trans. Algorithms 2025]. Third, it gives a short and self-contained proof of the known result of Chudnovsky, Hajebi, and Spirkl [Combinatorica 2024] that List r-Coloring on kP3-free graphs is polynomial-time solvable for every fixed r and k. We also consider two natural distance-d generalizations of Max-Weight Independent Set and List r-Coloring and provide polynomial-time algorithms on kP3-free graphs for every fixed integers r, k, and d ≥ 6
Estimating affective polarization on a social network
Get PDFConcerns about polarization and hate speech on social media are widespread. Affective polarization, i.e., hostility among partisans, is crucial in this regard as it links political disagreements to hostile language online. However, only a few methods are available to measure how affectively polarized an online debate is, and the existing approaches do not investigate jointly two defining features of affective polarization: hostility and social distance. To address this methodological gap, we propose a network-based measure of affective polarization that combines both aspects – which allows them to be studied independently. We show that our measure accurately captures the relation between the level of disagreement and the hostility expressed towards others (affective component) and whom individuals choose to interact with or avoid (social distance component). Applying our measure to a large-scale Twitter data set on COVID-19, we find that affective polarization was low in February 2020 and increased to high levels as more users joined the Twitter discussion in the following months
Instance-Optimal Imprecise Convex Hull.
No full textImprecise measurements of a point set P = (p₁, …, p_n) can be modelled by a family of regions F = (R₁, …, R_n), where each imprecise region R_i ∈ F contains a unique point p_i ∈ P. A retrieval models an accurate measurement by replacing an imprecise region R_i with its corresponding point p_i. We construct the convex hull of an imprecise point set in the plane, by determining the cyclic ordering of the convex hull vertices of P as efficiently as possible. Efficiency is interpreted in two ways: (i) minimising the number of retrievals, and (ii) the computation time to determine the set of regions that must be retrieved. Previous works focused on only one of these two aspects: either minimising retrievals or optimising algorithmic runtime. Our contribution is the first to simultaneously achieve both. Let r(F, P) denote the minimal number of retrievals required by any algorithm to determine the convex hull of P for a given instance (F, P). For a family F of n constant-complexity polygons, our main result is a reconstruction algorithm that performs Θ(r(F, P)) retrievals in O(r(F, P) log³ n) time. Compared to previous approaches that achieve optimal retrieval counts, we improve the runtime per retrieval from polynomial to polylogarithmic. We extend the generality of previous results to simple k-gons, to pairwise disjoint disks with radii in [1,k], and to unit disks where at most k disks overlap in a single point. Our runtime scales linearly with k
A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees.
No full textIndexing data is a fundamental problem in computer science. The input is a set S of n distinct integers from a universe U. Indexing queries take a value q ∈ U and return the membership, predecessor or rank of q in S. A range query takes two values q, r ∈ U and returns the set S ∩[q, r]. Recently, various papers study a special case where the the input data behaves in an approximately piece-wise linear way. Given the sorted (rank,value) pairs, and given some constant ε, one wants to maintain a small number of axis-disjoint line-segments such that, for each rank, the value is within ±ε of the corresponding line-segment. Ferragina and Vinciguerra (VLDB 2020) observe that this geometric problem is useful for solving indexing problems, particularly when the number of line-segments is small compared to the size of the dataset. We study the dynamic version of this geometric problem. In the dynamic setting, inserting or deleting just one data point may cause up to three line-segments to be merged, or one line-segment to be split at most three-way. To determine and compute this, we use techniques from dynamic maintenance of convex hulls, and provide new algorithms with worst-case guarantees, including an O(log n) algorithm to compute a separating line between two non-intersecting convex hulls – an operation previously missing from the literature. We then use our fully-dynamic geometry-based subroutine in an indexing data structure, combining it with a natural hashing technique. The resulting indexing data structure has theoretically efficient worst-case guarantees in expectation. We compare its practical performance to the solution of Ferragina and Vinciguerra, which was shown to perform better in certain structured settings [Sun, Zhou, Li VLDB 2023]. Our empirical analysis shows that our solution supports more efficient range queries in the special case where the update sequence contains many deletions
Local Density and Its Distributed Approximation.
No full textThe densest subgraph problem is a classic problem in combinatorial optimisation. Graphs with low maximum subgraph density are often called “uniformly sparse”, leading to algorithms parameterised by this density. However, in reality, the sparsity of a graph is not necessarily uniform. This calls for a formally well-defined, fine-grained notion of density. Danisch, Chan, and Sozio propose a definition for local density that assigns to each vertex v a value ρ*(v). This local density is a generalisation of the maximum subgraph density of a graph. I.e., if ρ(G) is the subgraph density of a finite graph G, then ρ(G) equals the maximum local density ρ*(v) over vertices v in G. They present a Frank-Wolfe-based algorithm to approximate the local density of each vertex with no theoretical (asymptotic) guarantees. We provide an extensive study of this local density measure. Just as with (global) maximum subgraph density, we show that there is a dual relation between the local out-degrees and the minimum out-degree orientations of the graph. We introduce the definition of the local out-degree g*(v) of a vertex v, and show it to be equal to the local density ρ*(v). We consider the local out-degree to be conceptually simpler, shorter to define, and easier to compute. Using the local out-degree we show a previously unknown fact: that existing algorithms already dynamically approximate the local density for each vertex with polylogarithmic update time. Next, we provide the first distributed algorithms that compute the local density with provable guarantees: given any ε such that ε−1 ∈ O(poly n), we show a deterministic distributed algorithm in the LOCAL model where, after O(ε−2 log2 n) rounds, every vertex v outputs a (1 + ε)-approximation of their local density ρ*(v). In CONGEST, we show a deterministic distributed algorithm that requires poly(log n, ε−1) · 2O(√log n) rounds, which is sublinear in n. As a corollary, we obtain the first deterministic algorithm running in a sublinear number of rounds for (1 + ε)-approximate densest subgraph detection in the CONGEST model
Solving Polynomial Equations Over Finite Fields
Get PDFWe present a randomized algorithm for solving low-degree polynomial equation systems over finite fields faster than exhaustive search. In order to do so, we follow a line of work by Lokshtanov, Paturi, Tamaki, Williams, and Yu (SODA 2017), Björklund, Kaski, and Williams (ICALP 2019), and Dinur (SODA 2021). In particular, we generalize Dinur’s algorithm for F2 to all finite fields, in particular the “symbolic interpolation” of Björklund, Kaski, and Williams, and we use an efficient trimmed multipoint evaluation and interpolation procedure for multivariate polynomials over finite fields by Van der Hoeven and Schost (AAECC 2013). The running time of our algorithm matches that of Dinur’s algorithm for F2 and is significantly faster than the one of Lokshtanov et al. for q > 2.We complement our results with tight conditional lower bounds that, surprisingly, we were not able to find in the literature. In particular, under the strong exponential time hypothesis, we prove that it is impossible to solve n-variate low-degree polynomial equation systems over Fq in time O((q −ε) n). As a bonus, we show that under the counting version of the strong exponential time hypothesis, it is impossible to compute the number of roots of a single n-variate low-degree polynomial over Fq in time O((q − ε)n); this generalizes a result of Williams (SOSA 2018) from F2 to all finite fields