On-line multiversion database concurrency control

This paper presents a new model for studying the concurrency vs. computation time tradeoffs involved in on-line multiversion database concurrency control. The basic problem that is studied in our model is the following: Given:a current database system state which includes information such as which transaction previously read a version from which other transaction; which transaction has written which versions into the database; and the ordering of versions previously written; anda set of read and write requests of requesting transactions. Question: Does there exist a new database system state in which the requesting transactions can be immediately put into execution (their read and write requests satisfied, or in the case of predeclared writeset transactions, write requests are guaranteed to be satisfied) while preserving consistency under a given set of additional constraints? (The amount of concurrency achieved is defined by the set of additional constraints). In this paper we derive “limits” of performance achievable by polynomial time concurrency control algorithms. Each limit is characterized by a minimal set of constraints that allow the on-line scheduling problem to be solved in polynomial time. If any one constraint in that minimal set is omitted, although it could increase the amount of concurrency, it would also have the dramatic negative effect of making the scheduling problem NP-complete; whereas if we do not omit any constraint in the minimal set, then the scheduling problem can be solved in polynomial time. With each of these limits, one can construct an efficient scheduling algorithm that achieves an optimal level of concurrency in polynomial computation time according to the constraints defined in the minimal set.     

From the Happened-Before Relation to the Causal Ordered Set Abstraction

Several works in distributed systems have been designed based on the Happened-Before Relation (HBR). Most of these works intend to be efficient in their implementation by identifying and ensuring dependency constraints among single events. Even when the minimal causal dependencies among events have been clearly identified, the evolution of systems, which may involve a high number of processes and a high volume of transmitted data, calls for the need to design even more efficient approaches. This paper proposes the Causal Ordered Set Abstraction (CAOS) where the causally related events are arranged in sets that are strictly causally ordered. As for single events, CAOS establishes that any pair of resultant sets can be, and can only be, causally or concurrently related. We claim that our ordered set abstraction can be used to design more efficient algorithms based on the HBR principle. This assertion is based on two main properties. First, CAOS attains a consistent compact representation of a distributed computation. Second, as a consequence of the causal ordering of the events in the resultant sets, it is sufficient to verify only a pair of single events, one per each set, in order to determine whether these sets are causally or concurrently related, regardless of the cardinality of the sets.     

Speed-Ups by changing the order in which sets are enumerated

The purpose of this paper is to show that there are sets for which really large improvements in enumeration times can only be achieved by programs which change the order in which the sets are enumerated and not by programs which merely speed up the enumeration times without changing the order in which the sets are enumerated. We do this by proving, in a suitably general context, the following analogue of the Blum speedup theorem: There are some infinite sets which are so difficult to enumerate that, given any order for enumerating the set, there is some other order and someone method of enumerating the set in this second order which is much faster thanany method of enumerating the set in the first ordering. The proof itself is one of the first nontrivial applications of priority methods to questions of computational complexity. (See also [8], [6], and [3] for more such applications.)Supported by NSF Research Grant No. GP 6120 and GJ—27127. Preliminary version presented at the First Annual ACM Symposium on the Theory of Computing, May, 1969.     

Efficient symmetry breaking formulations for the job grouping problem

The job grouping problem consists of assigning a set of jobs, each with a specific set of tool requirements, to machines with a limited tool capacity in order to minimize the number of machines needed. Traditionally, a formulation has been used that assigns jobs to machines. However, such a formulation contains a lot of symmetry since the machines are identical and they can be permuted in any feasible solution. We propose a new formulation for this problem, based on the asymmetric representatives formulation (ARF) idea. This formulation eliminates the symmetry between the identical machines. We further propose various symmetry breaking constraints, including variable reduction and lexicographic ordering constraints, which can be added to the traditional formulation. These formulations are tested on a data set from the literature and newly generated data sets using a state-of-the-art commercial solver, which includes symmetry breaking features.     

一种基于ATMS的求解所有极小冲突集的新方法

在Reiter算法的基础上，本文提出一种基于ATMS的求解所有极小冲突集的新方法。其中，对每个元件模型最多调用一次就可求出所有的极小冲突集，防止了ATMS的多次调用，因而能够提高效率。本文提出了极小依赖集的概念，并据此对ATMS求得的极小冲突集进行了分类；分析了算法的复杂度，并将新方法与相关工作进行了比较。该算法程序容易编制，而且效率高。     

CSPs with counters: a likelihood-based heuristic

Abstract. Counter constraints are a naturalrepresentation of constraints on the finite capacity of resources in resource-allocation type problems. They are a generic family of non-binary constraints that limit the number of variables that may be assigned particular values. Counter constraints can be represented by binary constraints, at a cost. We analyse the cost, show how a counter can be represented as a linear number of binary constraints, and demonstrate empirically that even with the optimal reduction,an explicit representation of counters is preferable to their representation as a set of binary constraints. For counter constraints, value ordering is essential. An heuristic for value ordering on constraint satisfaction problems (CSP), based on the estimated likelihoodof a solution, is presented. The proposed value ordering heuristic is useful for counter constraints, as well as for binary CSPs, where it can be used to approximate the number of solutions consistent with a particular value assignment to a variable. The proposed value ordering heuristic integrates counter constraints with binary constraint networks in a novel manner. Counter constraints are problematic for most heuristics, which are local in scope, yet we demonstrated empirically that the proposed value ordering heuristic is significantly superior to heuristics used in previous work.     

Efficient Sequential Consistency Using Conditional Fences

Among the various memory consistency models, the sequential consistency (SC) model is the most intuitive and enables programmers to reason about their parallel programs the best. Nevertheless, processor designers often choose to support relaxed memory consistency models because the weaker ordering constraints imposed by such models allow for more instructions to be reordered and enable higher performance. Programs running on machines supporting weaker consistency models can be transformed into ones in which SC is enforced. The compiler does this by computing a minimal set of memory access pairs whose ordering automatically guarantees SC. To ensure that these memory access pairs are not reordered, memory fences are inserted. Unfortunately, insertion of such memory fences can significantly slowdown the program. We observe that the ordering of the minimal set of memory accesses that the compiler strives to enforce, is typically already enforced in the normal course of program execution. A study we conducted on programs with compiler inserted memory fences shows that only 8% of the executed instances of the memory fences are really necessary to ensure SC. Motivated by this study we propose the conditional fence mechanism, known as C-Fence that utilizes compiler information to decide dynamically if there is a need to stall at each fence, only stalling when necessary. Our experiments with SPLASH-2 benchmarks show that, with C-Fences and a centralized active table, programs can be transformed to enforce SC incurring only 12% slowdown, as opposed to 43% slowdown using normal fence instructions. Our approach requires very little hardware support (<350 bytes of on-chip-storage) and it avoids the use of speculation and its associated costs. Furthermore, to ameliorate the contention in the centralized active table arising from the increasing number of processors, we also design a distributed active table, which further improves the performance of C-Fence for a larger number of processors.     

Development of a Temporal Extension to Query Travel Behavior Time Paths Using an Object-Oriented GIS

An essential requirement to better understand activity-based travel behavior (ABTB) at the disaggregate level is the development of a spatio-temporal model able to support queries related to activities of individuals or groups of individuals. This paper describes the development and implementation of a temporal extension to a geographic information system (GIS) object-oriented model for the modeling of the time path and the retrieval of its event chaining. In this approach, time path is formulated as a totally time ordered set composed by activity events and trip events, themselves organized into time ordered sets. As sets, the time path and its components can be searched using their respective indexes. A series of methods were built that implement temporal predicates as an interface to temporally query the database. A set of positional operator methods were also designed that transform temporal topological queries into retrieval functions based on set ordering indices. Taken together, the temporal predicates and the positional operator methods define a temporal query extension that meets the retrieval needs of an ABTB database.     

An approach to ontology for institutional facts in the semantic web

Refinement in software engineering allows a specification to be developed in stages, with design decisions taken at earlier stages constraining the design at later stages. Refinement in complex data models is difficult due to lack of a way of defining constraints, which can be progressively maintained over increasingly detailed refinements. Category theory provides a way of stating wide scale constraints. These constraints lead to a set of design guidelines, which maintain the wide scale constraints under increasing detail. Previous methods of refinement are essentially local, and the proposed method does not interfere very much with these local methods. The result is particularly applicable to semantic web applications, where ontologies provide systems of more or less abstract constraints on systems, which must be implemented and therefore refined by participating systems. With the approach of this paper, the concept of committing to an ontology carries much more force.     

Improving clustering with pairwise constraints: a discriminative approach

To obtain a user-desired and accurate clustering result in practical applications, one way is to utilize additional pairwise constraints that indicate the relationship between two samples, that is, whether these samples belong to the same cluster or not. In this paper, we put forward a discriminative learning approach which can incorporate pairwise constraints into the recently proposed two-class maximum margin clustering framework. In particular, a set of pairwise loss functions is proposed, which features robust detection and penalization for violating the pairwise constraints. Consequently, the proposed method is able to directly find the partitioning hyperplane, which can separate the data into two groups and satisfy the given pairwise constraints as much as possible. In this way, it makes fewer assumptions on the distance metric or similarity matrix for the data, which may be complicated in practice, than existing popular constrained clustering algorithms. Finally, an iterative updating algorithm is proposed for the resulting optimization problem. The experiments on a number of real-world data sets demonstrate that the proposed pairwise constrained two-class clustering algorithm outperforms several representative pairwise constrained clustering counterparts in the literature.     

空间职责分离约束的实施

支持空间特性的RBAC模型描述了多种空间约束,这些空间约束不但表达了位置感知系统中细粒度空间语义,而且给模型增加了空间安全描述能力.能否准确实施空间约束直接影响应用系统功能和开销.本文研究空间职责分离(SSoD)约束的两种实施策略:(1)直接实施(2)间接实施.证明了直接实施是一个NP完全问题,而通过互斥空间角色(MESR)约束间接实施SSoD是有效的.多个MESR约束可以实施同一个SSoD,在比较后发现,当使用最小MESR约束作为实施机制时,能有效避免冗余约束准确实施该SSoD.为获得最小MESR约束本文给出了GEN-MESR算法.     

Homomorphisms of symbolic dynamical systems

The densities of finite blocks of symbols can be computed for points in any substitution minimal set arising from a substitution of constant length and also for points in any Sturmian minimal set. It follows from the computations that all Sturmian minimal sets and all substitution minimal sets are strictly ergodic and have topological entropy zero. It also follows that no Sturmian minimal set is the homomorphic image of a substitution minimal set. It can also be shown that no non-trivial substitution minimal set is powerfully (totally) minimal, and it follows that no non-trivial substitution minimal set is the homomorphic image of a Sturmian minimal set.Most of the results in this paper were first obtained in the author's doctoral dissertation which was presented to the Faculty of the Graduate School of Yale University in 1968.     

Nonnegative discriminative encoded nearest points for image set classification

Image set classification has drawn much attention due to its rich set information. Recently, the most popular set-to-set distance-based representation methods have achieved interesting results by measuring the between-set distance. However, there are two intuitive assumptions, which are largely ignored: (1) The homogeneous samples should have positive contributions to approximate the nearest point in the probe set, while the heterogeneous samples should have no contributions and (2) the learned nearest points in each gallery set should have the lowest correlations. Therefore, this paper presents a novel method called nonnegative discriminative encoded nearest points for image set classification. Specifically, we use two explicit nonnegative constraints to ensure the coding coefficients sparse and discriminative simultaneously. Moreover, we additionally introduce a new class-wise discriminative term to further boost the discriminant ability of different sets. In this way, they can be boosted mutually so that the obtained coding coefficients are beneficial to the purpose of set classification. The results from extensive experiments and comparisons with some state-of-the-art methods on four challenging datasets demonstrate the superiority of our method.

     

能量约束下的Bézier曲线构造

Bézier曲线是计算机辅助几何设计中应用广泛的曲线造型工具,构造具有能量约束的曲线也是曲线造型研究的重要内容之一.构造给定首末控制顶点与初始切方向的Bézier曲线,当其满足jerk能量极小时,其余控制顶点可以由已知条件与参数α确定;其中α与初始切向量长度有关.当曲线满足弯曲能量约束时,参数α唯一确定,从而对有序点集,可以显式地构造满足jerk能量极小与弯曲能量约束的G^1拼接组合Bézier曲线.最后,通过具体实例构造通过给定有序点集且满足能量约束的组合Bézier曲线,并与其他方法所得结果进行对比,验证了方法的有效性与可行性.     

Optimal selection of reference set for the nearest neighbor classification by Tabu search

In this paper,a new approach is presented to find the reference set for the nearest neighbor classifer.The optimal reference set,which has minimum sample size and satisfies a certain error rate threshold,is obtained through a Tabu search algorithm.When the error rate threshold is set to zero,the algorithm obtains a near minimal consistent subset of a given training set.While the threshold is set to a small appropriate value,the obtained reference set may compensate the bias of the nearest neighbor estimate.An aspiration criterion for Tabu search is introduced,which aims to prevent the search process form the inefficient wandering between the feasible and infeasible regions in the search space and speed up the convergence.Experimental results based on a number of typical data sets are presented and analyzed to illustrate the benefits of the proposed method.Compared to conventional methods,such as CNN and Dasarathy‘s algorithm,the size of the reduced reference sets is much smaller,and the nearest neighbor classification performance is better,especially when the error rate thresholds are set to appropriate nonzerovalues,The experimental results also illustrate that the MCS(inimal consistent set)of Dasarathy‘s algorithm is not minimal,and its candidate consistent set is not always ensured to reduce monotonically.A counter example is also given to confirm this claim.     

The complexity of soft constraint satisfaction

Over the past few years there has been considerable progress in methods to systematically analyse the complexity of constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the complexity of a set of constraints to a corresponding set of algebraic operations, known as polymorphisms.In this paper we extend the analysis of complexity to the more general framework of combinatorial optimisation problems expressed using various forms of soft constraints. We launch a systematic investigation of the complexity of these problems by extending the notion of a polymorphism to a more general algebraic operation, which we call a multimorphism. We show that many tractable sets of soft constraints, both established and novel, can be characterised by the presence of particular multimorphisms. We also show that a simple set of NP-hard constraints has very restricted multimorphisms. Finally, we use the notion of multimorphism to give a complete classification of complexity for the Boolean case which extends several earlier classification results for particular special cases.     

Dominating,weakly stable,and uncovered sets: Properties and generalizations

We consider the problem of collective choice in a tournament, i.e., when the majority relation, which plays the role of the collective preference system on this set of alternatives, can be represented by a complete asymmetric oriented graph. We compare three solutions of the collective choice problem: minimal dominating, uncovered, and minimal weakly stable sets. We construct generalizations of the minimal dominating set and find out, with their help, how the system of dominating sets looks like in the general case. We formulate a criterion that determines whether an alternative belongs to a minimal weakly stable set. We find out how minimal weakly stable sets relate to uncovered sets. Based on the notion of stability of an alternative and the set of alternatives we construct generalizations for the notions of uncovered and weakly stable sets—the classes of k-stable alternatives and k-stable sets. We prove inclusion relations between these classes.     

Decomposition's Dantzig–Wolfe applied to fuzzy multicommodity flow problems

We present, in this paper, a method for solving linear programming problems with fuzzy costs based on the classical method of decomposition's Dantzig–Wolfe. Methods using decomposition techniques address problems that have a special structure in the set of constraints. An example of such a problem that has this structure is the fuzzy multicommodity flow problem. This problem can be modeled by a graph whose nodes represent points of supply, demand and passage of commodities, which travel on the arcs of the network. The objective is to determine the flow of each commodity on the arcs, in order to meet demand at minimal cost while respecting the capacity constraints of the arcs and the flow conservation constraints of the nodes. Using the theory of fuzzy sets, the proposed method aims to find the optimal solution, working with the problem in the fuzzy form during the resolution procedure.     

Effective computation of immersion obstructions for unions of graph classes

In the final paper of the Graph Minors series Robertson and Seymour proved that graphs are well-quasi-ordered under the immersion ordering. A direct implication of this theorem is that each class of graphs that is closed under taking immersions can be fully characterized by forbidding a finite set of graphs (immersion obstruction set). However, as the proof of the well-quasi-ordering theorem is non-constructive, there is no generic procedure for computing such a set. Moreover, it remains an open issue to identify for which immersion-closed graph classes the computation of those sets can become effective. By adapting the tools that were introduced by Adler, Grohe and Kreutzer, for the effective computation of minor obstruction sets, we expand the horizon of computability to immersion obstruction sets. In particular, our results propagate the computability of immersion obstruction sets of immersion-closed graph classes to immersion obstruction sets of finite unions of immersion-closed graph classes.