共找到 20 条结果
Nim is a well-known combinatorial game with several variants, e.g., Delete Nim and Variant Delete Nim. In Variant Delete Nim, the player deletes one of the two heaps of stones and splits the other heap on his/her turn. In this paper, we discuss generalized Variant Delete Nim, which generalizes the number of stone heaps to three or more, All-but-one-delete Nim, Half-delete Nim, No-more-than-half-delete Nim, and Single-delete Nim. We study the win-loss conditions for each of these games.
LSM-trees are featured by out-of-place updates, where key deletion is handled by inserting a tombstone to mark its staleness instead of removing it in place. This defers actual removal to compactions with greatly reduced overhead. However, this classic strategy struggles with another fundamental operator--range deletes--which removes all keys within a specified range, requiring the system to insert numerous tombstones and causing severe performance issues. To address this, modern LSM-based systems introduce range tombstones that record the start and end keys to avoid per-key tombstones. Although this achieves impressive range delete efficiency, such a solution is incompatible with lookups. In particular, our experiments show that point lookup latency can increase by 30% even with just 1% range deletions in workloads. Further to our surprise, this issue has not been raised before, though the range tombstone solution has been employed for more than five years. To address this critical performance issue, we propose GLORAN, an efficient range delete method that can be integrated into modern LSM-based systems and offers desirable range deletion performance without compromising point loo
Graph unlearning has emerged as a pivotal method to delete information from a pre-trained graph neural network (GNN). One may delete nodes, a class of nodes, edges, or a class of edges. An unlearning method enables the GNN model to comply with data protection regulations (i.e., the right to be forgotten), adapt to evolving data distributions, and reduce the GPU-hours carbon footprint by avoiding repetitive retraining. Existing partitioning and aggregation-based methods have limitations due to their poor handling of local graph dependencies and additional overhead costs. More recently, GNNDelete offered a model-agnostic approach that alleviates some of these issues. Our work takes a novel approach to address these challenges in graph unlearning through knowledge distillation, as it distills to delete in GNN (D2DGN). It is a model-agnostic distillation framework where the complete graph knowledge is divided and marked for retention and deletion. It performs distillation with response-based soft targets and feature-based node embedding while minimizing KL divergence. The unlearned model effectively removes the influence of deleted graph elements while preserving knowledge about the re
Automated content moderation for collaborative knowledge hubs like Wikipedia or Wikidata is an important yet challenging task due to multiple factors. In this paper, we construct a database of discussions happening around articles marked for deletion in several Wikis and in three languages, which we then use to evaluate a range of LMs on different tasks (from predicting the outcome of the discussion to identifying the implicit policy an individual comment might be pointing to). Our results reveal, among others, that discussions leading to deletion are easier to predict, and that, surprisingly, self-produced tags (keep, delete or redirect) don't always help guiding the classifiers, presumably because of users' hesitation or deliberation within comments.
Is it possible to comprehensively destroy a piece of quantum information, so that nothing is left behind except the memory of whether one had it at one point? For example, various works, most recently Morimae, Poremba, and Yamakawa (TQC 2024), show how to construct a signature scheme with certified deletion where a user who deletes a signature on m cannot later produce a signature for m. However, in all of the existing schemes, even after deletion the user is still able keep irrefutable evidence that m was signed, and thus they do not fully capture the spirit of deletion. In this work, we initiate the study of certified deniability in order to obtain a more comprehensive notion of deletion. Certified deniability uses a simulation-based security definition, ensuring that any information the user has kept after deletion could have been learned without being given the deleteable object to begin with; meaning that deletion leaves no trace behind! We define and construct two non-interactive primitives that satisfy certified deniability in the quantum random oracle model: signatures and non-interactive zero-knowledge arguments (NIZKs). As a consequence, for example, it is not possible to
Over 500 million tweets are posted in Twitter each day, out of which about 11% tweets are deleted by the users posting them. This phenomenon of widespread deletion of tweets leads to a number of questions: what kind of content posted by users makes them want to delete them later? %Are all users equally active in deleting their tweets or Are users of certain predispositions more likely to post regrettable tweets, deleting them later? In this paper we provide a detailed characterization of tweets posted and then later deleted by their authors. We collected tweets from over 200 thousand Twitter users during a period of four weeks. Our characterization shows significant personality differences between users who delete their tweets and those who do not. We find that users who delete their tweets are more likely to be extroverted and neurotic while being less conscientious. Also, we find that deleted tweets while containing less information and being less conversational, contain significant indications of regrettable content. Since users of online communication do not have instant social cues (like listener's body language) to gauge the impact of their words, they are often delayed in em
The classic game of Nim has been well-known for many years, inspiring numerous variations. One such variant is Delete Nim, where players take turns eliminating one pile of stones and splitting the remaining pile into two smaller piles. In this paper we generalize the game to include the case of n piles. On each turn, a player eliminates one pile and splits one of the remaining piles into two smaller piles. We specifically analyze the case where n=4, deriving the conditions for a winning strategy.
Stack Overflow is the most popular CQA for programmers on the web with 2.05M users, 5.1M questions and 9.4M answers. Stack Overflow has explicit, detailed guidelines on how to post questions and an ebullient moderation community. Despite these precise communications and safeguards, questions posted on Stack Overflow can be extremely off topic or very poor in quality. Such questions can be deleted from Stack Overflow at the discretion of experienced community members and moderators. We present the first study of deleted questions on Stack Overflow. We divide our study into two parts (i) Characterization of deleted questions over approx. 5 years (2008-2013) of data, (ii) Prediction of deletion at the time of question creation. Our characterization study reveals multiple insights on question deletion phenomena. We observe a significant increase in the number of deleted questions over time. We find that it takes substantial time to vote a question to be deleted but once voted, the community takes swift action. We also see that question authors delete their questions to salvage reputation points. We notice some instances of accidental deletion of good quality questions but such question
Drug discovery is a highly complicated process, and it is unfeasible to fully commit it to the recently developed molecular generation methods. Deep learning-based lead optimization takes expert knowledge as a starting point, learning from numerous historical cases about how to modify the structure for better drug-forming properties. However, compared with the more established de novo generation schemes, lead optimization is still an area that requires further exploration. Previously developed models are often limited to resolving one (or few) certain subtask(s) of lead optimization, and most of them can only generate the two-dimensional structures of molecules while disregarding the vital protein-ligand interactions based on the three-dimensional binding poses. To address these challenges, we present a novel tool for lead optimization, named Delete (Deep lead optimization enveloped in protein pocket). Our model can handle all subtasks of lead optimization involving fragment growing, linking, and replacement through a unified deleting (masking) strategy, and is aware of the intricate pocket-ligand interactions through the geometric design of networks. Statistical evaluations and ca
Data-intensive applications fueled the evolution of log structured merge (LSM) based key-value engines that employ the out-of-place paradigm to support high ingestion rates with low read/write interference. These benefits, however, come at the cost of treating deletes as a second-class citizen. A delete inserts a tombstone that invalidates older instances of the deleted key. State-of-the-art LSM engines do not provide guarantees as to how fast a tombstone will propagate to persist the deletion. Further, LSM engines only support deletion on the sort key. To delete on another attribute (e.g., timestamp), the entire tree is read and re-written. We highlight that fast persistent deletion without affecting read performance is key to support: (i) streaming systems operating on a window of data, (ii) privacy with latency guarantees on the right-to-be-forgotten, and (iii) en masse cloud deployment of data systems that makes storage a precious resource. To address these challenges, in this paper, we build a new key-value storage engine, Lethe, that uses a very small amount of additional metadata, a set of new delete-aware compaction policies, and a new physical data layout that weaves the s
Users are more aware than ever of the importance of their own data, thanks to reports about security breaches and leaks of private, often sensitive data in recent years. Additionally, the GDPR has been in effect in the European Union for over three years and many people have encountered its effects in one way or another. Consequently, more and more users are actively protecting their personal data. One way to do this is to make of the right to erasure guaranteed in the GDPR, which has potential implications for a number of different fields, such as big data and machine learning. Our paper presents an in-depth analysis about the impact of the use of the right to erasure on the performance of machine learning models on classification tasks. We conduct various experiments utilising different datasets as well as different machine learning algorithms to analyse a variety of deletion behaviour scenarios. Due to the lack of credible data on actual user behaviour, we make reasonable assumptions for various deletion modes and biases and provide insight into the effects of different plausible scenarios for right to erasure usage on data quality of machine learning. Our results show that the
Red-black (RB) trees are one of the most efficient variants of balanced binary search trees. However, they have always been blamed for being too complicated, hard to explain, and not suitable for pedagogical purposes. In the pioneering work of Guibas & Sedgewick (1978), both 2-3 and 2-3-4 variants of RB trees had been considered, but further study of the former had been abandoned due to the higher number of rotations in the insert algorithm. Sedgewick (2008) proposed a variant of 2-3 RB trees, viz. left-leaning red-black (LLRB) trees, in which red links are restricted to left children and proposed concise recursive insert and delete algorithms. However, the top-down deletion algorithm of LLRB is still very complicated and highly inefficient. In this paper, we reconsider 2-3 red-black trees in which both children of a node cannot be red. We propose a parity-seeking delete algorithm with the basic idea of making the deficient subtree on a par with its sibling: either by fixing the deficient subtree or by turning the sibling deficient as well, ascending deficiency to the parent node. Interestingly, the proposed parity-seeking delete algorithm works for 2-3-4 RB trees as well. Our
In this paper, we study an impartial game called Delete Nim. In this game, there are two heaps of stones. The player chooses one of the heaps and delete the other heap. Next, she takes away one stone from the chosen heap and optionally splits it into two heaps. We show the way to calculate the G-value of this game by using the OR operation and 2-adic valuation.
We firstly suggest new cache policy applying the duty to delete invalid cache data on Non-volatile Memory (NVM). This cache policy includes generating random data and overwriting the random data into invalid cache data. Proposed cache policy is more economical and effective regarding perfect deletion of data. It is ensure that the invalid cache data in NVM is secure against malicious hackers.
Deploying reinforcement learning policies in the real world requires adapting to time-varying environments. We study this problem in the contextual Markov Decision Process (cMDP) framework, where a family of environments is indexed by a low-dimensional context unknown at test time. The standard approach decomposes the problem: train a so-called "universal policy" which assumes knowledge of the true context, then pair it with a context estimator which approximates context using the observed trajectory. We identify a simple, counterintuitive trick that substantially improves the estimator: randomly delete a fraction of the training buffer after each round. This works because data is collected across multiple rounds using progressively better policies, and older trajectories come from a different distribution than what the estimator will face at deployment time; random deletion creates an implicit exponential decay on older data while preserving diversity without requiring any explicit identification of which samples are stale. This reduces robustness gap by 30% for MLPs and by 6% on average for recurrent networks. Strikingly, it allows a narrow MLP with 5x fewer parameters to outperf
Pati and Braunstein defined a deleting machine and showed the impossibility of deleting one of two identical copies of an unknown quantum state. So far, no one has defined two non-identical copies of a quantum state, of course no one has discussed the impossibility of deleting one of two non-identical copies of an unknown quantum state. In this paper, we define $u|ψ>$ and $U|ψ>$, where $u$ and $U$ are any unitary operators, as two unitary copies of a quantum state $|ψ>$, and show that it is impossible to delete one of two unitary copies of an unknown state.
In this paper, we consider the Levenshtein's sequence reconstruction problem in the case where the transmitted codeword is chosen from $\{0,1\}^n$ and the channel can delete up to $t$ symbols from the transmitted codeword. We determine the minimum number of channel outputs (assuming that they are distinct) required to reconstruct a list of size $\ell-1$ of candidate sequences, one of which corresponds to the original transmitted sequence. More specifically, we determine the maximum possible size of the intersection of $\ell \geq 3$ deletion balls of radius $t$ centered at $x_1, x_2, \dots, x_{\ell}$, where $x_i \in \{0,1\}^n$ for all $i \in \{1,2,\dots,\ell\}$ and $x_i eq x_j$ for $i eq j$, with $n \geq t+ \ell-1$ and $t \geq 1$.
We consider binary input deletion/substitution channels, which model certain types of synchronization errors encountered in practice. Specifically, we focus on the regime of small deletion and substitution probabilities, and by extending an approach developed for the deletion-only channel, we obtain an asymptotic characterization of the channel capacity for independent and identically distributed (i.i.d.) deletion/substitution channels. To do so, given a target probability of successful decoding, we first develop an upper bound on the codebook size for arbitrary but fixed numbers of deletions and substitutions, and then extend the result to the case of random deletions and substitutions to obtain a bound on the channel capacity. Our final result is: The i.i.d. deletion/substitution channel capacity is approximately \(1 - H(p_d) - H(p_s)\), for \(p_d, p_s \approx0\), where \(p_d\) and \(p_s\) are the deletion and substitution probabilities, respectively.
Unlearning algorithms aim to remove deleted data's influence from trained models at a cost lower than full retraining. However, prior guarantees of unlearning in literature are flawed and don't protect the privacy of deleted records. We show that when users delete their data as a function of published models, records in a database become interdependent. So, even retraining a fresh model after deletion of a record doesn't ensure its privacy. Secondly, unlearning algorithms that cache partial computations to speed up the processing can leak deleted information over a series of releases, violating the privacy of deleted records in the long run. To address these, we propose a sound deletion guarantee and show that the privacy of existing records is necessary for the privacy of deleted records. Under this notion, we propose an accurate, computationally efficient, and secure machine unlearning algorithm based on noisy gradient descent.
In a world of information overload, understanding how we can most effectively manage information is crucial to success. We set out to understand how people view deletion, the removal of material no longer needed: does it help by reducing clutter and improving the signal to noise ratio, or does the effort required to decide to delete something make it not worthwhile? How does deletion relate to other strategies like filing; do people who spend extensive time in filing also prune their materials too? We studied the behaviour of 51 knowledge workers though a series of questionnaires and interviews to evaluate a range of tactics they used aimed at organizing, filing, and retrieving digital resources. Our study reveals that deletion is consistently under-adopted compared to other tactics such as Filing, Coverage, Ontology, and Timeliness. Moreover, the empirical data indicate that deletion is actually detrimental to retrieval success and satisfaction. In this paper, we examine the practice of deletion, review the related literature, and present detailed statistical results and clustering outcomes that underscore its adverse effects.