We introduce the game of Cat Herding, where an omnipresent herder slowly cuts down a graph until an evasive cat player has nowhere to go. The number of cuts made is the score of a game, and we study the score under optimal play. In this paper, we begin by deriving some general results, and then we determine the precise cat number for paths, cycles, stars, and wheels. Finally, we identify an optimal Cat and Herder strategy on complete graphs, while providing both a recurrence and closed form for cat ( K n ) .

Lazy burning is a recently introduced variation of burning where only one set of vertices is chosen to burn during the first round. In hypergraphs, lazy burning spreads when all but one vertex in a hyperedge is burned. The lazy burning number is the minimum number of initially burned vertices that eventually burn all vertices. We give several equivalent characterizations of lazy burning on hypergraphs using matchings and zero forcing, and then apply these to establish new bounds and complexity results. We prove that the lazy burning number of a hypergraph H equals its order minus the maximum cardinality of a certain matching on its incidence graph. Using this characterization, we give a formula for the lazy burning number of a dual hypergraph and give new bounds on the lazy burning number based on various hypergraph parameters. We show that the lazy burning number of a hypergraph may be characterized by a maximal subhypergraph that results from iteratively deleting vertices in singleton hyperedges. We prove that lazy burning on a hypergraph is equivalent to zero forcing on its incidence graph and show an equivalence between skew zero forcing on a graph and lazy burning on its neighborhood hypergraph. As a result, we show that the decision problem of computing the lazy burning number of a hypergraph is NP-complete, which solves an open problem in [12] . By applying the results found for lazy burning, we show that the decision problem of computing the skew zero forcing number for bipartite graphs is NP-complete. We finish with open problems.

Abstract. We extend a recent breakthrough result relating expectation thresholds and actual thresholds to include some rainbow versions.

General anomaly detection techniques have always received a lot of attention. Current detection methods usually focus solely on representation learning or anomaly judgment. This paper proposes a Multi-Subspace Deviation Network (MSDN) framework to build a model combining feature learning with anomaly score learning under the condition that a small number of labeled anomalies can be observed. Concretely, our framework combines a feature learner with two specific projectors: a self-supervised projector and an anomaly score learner. We utilize random affine transformations to map the raw data to multiple subspaces and train a classifier to predict the transformation label in the self-supervised module. Anomaly scores are then obtained directly from a deviation network, where the contrastive loss is used to amplify the gap in the anomaly scores between normal objects and anomalies. Extensive experiments on eight datasets show that our proposed method achieves higher detection accuracy than previous schemes with fewer observed anomalies.

The performance of query processing has always been a concern in the field of information retrieval. Dynamic pruning algorithms have been proposed to improve query processing performance in terms of efficiency and effectiveness. However, a single pruning algorithm generally does not have both advantages. In this work, we investigate the performance of the main dynamic pruning algorithms in terms of average and tail latency as well as the accuracy of query results, and find that they are complementary. Inspired by these findings, we propose two types of hybrid dynamic pruning algorithms that choose different combinations of strategies according to the characteristics of each query. Experimental results demonstrate that our proposed methods yield a good balance between both efficiency and effectiveness.

Load balance is one of the major issues in large-scale search engines. A commonly used load balancing approach in search engine datacenters is to reassign index shards among machines. However, reassigning shards within stringent resource environments is challenging due to transient resource constraints (during reassignment, some resources are consumed simultaneously by a shard on the initial machine and its copy on the target machine).

In cloud storage, remote data auditing is designed to verify the integrity of cloud data on behalf of cloud users. The audit is performed by a third-party auditor (TPA) according to auditing protocols such as proof of retrievability and provable data possession. However, the TPA-based auditing framework leads to single-point failures, opaque audit processes and undetected mistakes. In this paper, we propose a decentralized auditing system in which the audit is performed by multiple auditors and the audit result is reached in a collaborative and transparent way. Auditors are selected for each audit randomly from the set of cloud users via modified cryptographic sortition; auditing procedures are implemented using a smart contract, and auditing records are published on a blockchain; an incentive mechanism is provided to regulate the behavior of system participants. We implement a prototype system and demonstrate that the proposed system is reliable and technically feasible.

Cloud gaming has been increasing in popularity recently, but issues relating to maintaining low interaction delay for users to guarantee satisfactory gaming experience is still prevalent. Interaction delays caused by server-side processing are heavily influenced by how the processes partition the resources. However, finding the optimal partitioning policy that minimizes the response delay is complicated by several critical challenges. In this paper, we propose Themis, a system that enables efficient and adaptive online resource partitioning for reducing response delay in cloud gaming. Briefly, Themis employs machine learning technology to build a performance model which is able to capture the complex relationships between resource partition and system performance. With this model, Themis divides the processes into disjoint groups and partitions resources among process groups, which greatly simplifies the resource partition problem while ensuring high partitioning effectiveness. To tackle dynamic workload changes, Themis leverages reinforcement learning to learn how different partitioning actions affect system performance in an online manner, and adaptively choose the best actions for minimizing response delay in real time. We evaluate Themis in a real cloud gaming environment using several real games. The experimental results show that Themis can reduce the response delay by 17% to 36% compared to a system without resource partitioning, and outperforms other resource partitioning policies significantly. To the best of our knowledge, this is the first work to optimize response delay in cloud gaming through resource partitioning.

We define a cover of a Latin square to be a set of entries that includes at least one representative of each row, column and symbol. A cover is minimal if it does not contain any smaller cover. A partial transversal is a set of entries that includes at most one representative of each row, column and symbol. A partial transversal is maximal if it is not contained in any larger partial transversal. We explore the relationship between covers and partial transversals. We prove the following: (1) The minimum size of a cover in a Latin square of order n is $$n+a$$ if and only if the maximum size of a partial transversal is either $$n-2a$$ or $$n-2a+1$$ . (2) A minimal cover in a Latin square of order n has size at most $$\mu _n=3(n+1/2-\sqrt{n+1/4})$$ . (3) There are infinitely many orders n for which there exists a Latin square having a minimal cover of every size from n to $$\mu _n$$ . (4) Every Latin square of order n has a minimal cover of a size which is asymptotically equal to $$\mu _n$$ . (5) If $$1\leqslant k\leqslant n/2$$ and $$n\geqslant 5$$ then there is a Latin square of order n with a maximal partial transversal of size $$n-k$$ . (6) For any $$\varepsilon >0$$ , asymptotically almost all Latin squares have no maximal partial transversal of size less than $$n-n^{2/3+\varepsilon }$$ .

In the era of cloud computing, the over-occupancy of data center resources (CPU, memory, disk) and subsequent machine failure have resulted in great loss to users and enterprises. So it makes sense to anticipate the server workload in advance. Previous research on server workloads has focused on trend analysis and time series fitting. We propose an approach to forecast the workloads of servers based on machine learning. And our data comes from a database-based data center that is real, large-scale, and enterprise-class. We use the servers' historical monitoring data for our models to predict future workloads and hence provide the ability to automatically warn overload and reallocate resources. We calculate the failure detection rate and false alarm rate of our overload detection models, as well as put forward an evaluation based on the overload processing cost. Experimental results show that machine learning methods especially Random Forest can better predict the server load than traditional time series analysis method. We use the forecast results to propose some scheduling strategies to prevent server overload, achieve intelligent operation and maintenance, and failure prediction. Compared with the traditional time series analysis method, our method uses less data and lower dimensions, and yields more accurate predictions.

Intel's Optane SSD recently came to the market as the pioneer of 3D XPoint based commercial devices. They have much lower latency (about 14 μs) and better parallelism properties than traditional SSDs, and as such are set to replace NAND flash SSD in commercial settings. To best serve cloud and enterprise data centers' higher performing storage demands, it is necessary to know the performance characteristics of the new devices in both virtualized cloud environments and traditional non-virtualized environments. In this paper, we present an analysis of Optane SSDs based on a large number of experiments. We use several micro-benchmarks to gain knowledge of Optane's basic performance metrics. We also discuss the impact of state-of-the-art storage stacks on the performance of Optane SSDs. By analyzing the test results, we provide configuration suggestions for storage I/O applications using Optane SSDs. Lastly, we evaluate the real-world performance of Optane SDDs by running MySQL database based experiments. All the experiments are performed in non-virtualized and virtualized environments (Linux and QEMU) with a comparison study between the Optane SSD and a SATA NAND flash-based SSD.