Application of principal component analysis to multi-disk concurrent accessing

This paper is concerned with the allocation of multi-attribute records on several disks so as to achieve high degree of concurrency of disk access when responding to partial match queries.An algorithm to distribute a set of multi-attribute records onto different disks is presented. Since our allocation method will use the principal component analysis, this concept is first introduced. We then use it to generate a set of real numbers which are the projections on the first principal component direction and can be viewed as hashing addresses.Then we propose an algorithm based upon these hashing addresses to allocate multi-attribute records onto different disks. Some experimental results show that our method can indeed be used to solve the multi-disk data allocation problem for concurrent accessing.     

Optimality criteria of the disk modulo allocation method for Cartesian product files

Cartesian product (CP) files have been shown to be very effective for partial match retrieval. Further the Disk Modulo (DM) allocation method has been shown to be a simple and effective method for allocating CP files onto multiple independently accessible disks to further facilitate partial match retrieval. In this paper, a useful criterion for the DM method to be the best allocation method for a given CP file is presented. The presented criterion is much more general than that suggested previously which makes the DM allocation method much more applicable for real applications.     

Disk allocation methods for binary Cartesian product files

Since a file is usually stored on a disk, the response time to a query is dominated by the disk access time. In order to reduce the disk access time, a file can be stored on several independently accessible disks. In this paper, we discuss the problem of allocating buckets in a file among disks such that the maximum disk accessing concurrency can be achieved. We are particularly concerned with the disk allocation problem for binary Cartesian product files. A new allocation method is first proposed for the cases when the number (m) of available disks is a power of 2. Then it is extended to fit the cases wherem is not a power of 2. The proposed algorithm has a near strict optimal performance for a partial match query in which the number of unspecified attributes is greater than a small number (5 or 6).This work was supported in part by NSF Grant DCR-8405498.     

SOME EXTENDED KNAPSACK PROBLEMS INVOLVING JOB PARTITION BETWEEN TWO PARTIES

Some novel applications and pragmatic variations of knapsack problem(KP)are presented and constructed,which are formulated and developed from a model initiated in this paper on profit allocation from partition of jobs in terms of two-person discrete cooperation game.     

On the Brownian-directed polymer in a Gaussian random environment

In this paper, we introduce a model of Brownian polymer in a continuous random environment. The asymptotic behavior of the partition function associated to this polymer measure is studied, and we are able to separate a weak and strong disorder regime under some reasonable assumptions on the spatial covariance of the environment. Some further developments, concerning some concentration inequalities for the partition function, are given for the weak disorder regime.     

Invariant submanifolds for systems of vector fields of constant rank

Given a system of vector fields on a smooth manifold that spans a plane field of constant rank, we present a systematic method and an algorithm to find submanifolds that are invariant under the flows of the vector fields. We present examples of partition into invariant submanifolds, which further gives partition into orbits. We use the method of generalized Frobenius theorem by means of exterior differential systems.     

一类网络成本分配函数的规范性质

该文以数学方法论证了一类网络成本分配函数的性质,证明了成本分配函数具有规范形式的充要条件是它满足无记名性,可加性和等价性。并进一步论证了若成本分配函数还具有对成员数的单调递减性,它必是下游均等分配函数。     

Inferring null join dependencies in relational databases

The inference problem for data dependencies in relational databases is the problem of deciding whether a set of data dependencies logically implies another data dependency. For join dependencies (JDs), the inference problem has been extensively studied by utilising the well-known chase procedure. We generalise JDs to null join dependencies (NJDs) that hold in relations which may contain null values. In our model for incomplete information we allow only a single unmarked null value denoted bynull. This allows us to solve the inference problem for NJDs by extending the chase procedure to the or-chase procedure. In order to define the or-chase procedure we generalise relations with nulls to or-relations which contain a limited form of disjunctive information. The main result of the paper shows that the inference problem for NJDs, including embedded NJDs (which are a special case of NJDs), is decidable; this is realised via the or-chase procedure.     

基于属性约简的分类及其应用

约简是粗糙集用于数据分析的重要方法和手段,也是粗糙集理论的核心内容之一.论域U上的等价关系可以确定U的划分,U上的不可区分关系是等价关系.利用不可区分关系定义信息系统的划分协调集及划分约简集,而且证明了划分约简集的判定定理,并将其应用于实际分类问题.     

改进卡方检验

In goodness-of-fit tests, Pearson＇s chi-squared test is one of most widely used tools of formal statistical analysis. However, Pearson＇s chi-squared test depends on the partition of the sample space. Different constructions of the partition of the sample space may lead to different conclusions. Based on an equiprobable partition of sample space, a modified chi~quared test is proposed. A method for constructing the modified chi-squared test is proposed. As an application, the proposed test is used to test whether vectorial data come from an uniformity distribution defined on the hypersphere. Some simulation studies show that the modified chisquared test against different alternative is robust.     

The Fefferman–Szegő metric and applications

In this paper, we develop properties of the Szeg? kernel and Fefferman–Szeg? metric that were first introduced by D. Barrett and L. Lee. In particular, we produce a representative coordinate system related to the metric. We also explore the Poisson–Szeg? kernel. Additional analytic and geometric properties of the Szeg? kernel and Fefferman–Szeg? metric are developed.     

Approximation algorithms for scheduling on multi-core processor with shared speedup resources

We consider a joint resource partition and scheduling problem. We are given $m$ identical cores and discrete resources of total size $k$. We need to partition the resources among these cores. A set of jobs must be processed non-preemptively on these cores after the resource partition. The processing time of a job on a core depends on the size of resources allocated to that corresponding core. The resource allocation scheme is static, i.e., we cannot change the amount of resources that was allocated to a core during the whole scheduling. Hassidim et al. (2013) investigated this problem with a general processing time function, i.e., the processing time of a job is an arbitrary function of the level of resources allocated to that core. They provided an algorithm with approximation ratio of 36. In this paper, we improve the approximation ratio to 8 by presenting a new resource partition scheme. Next, we consider a special model where the core’s speed is proportional to its allocated resource, then we present two algorithms with improved approximation ratios.     

Riemann–Hilbert-type problems for Bitsadze equations with strong singularities in low-order coefficients

For the Bitsadze equation with low-order coefficients admitting a power singularity at a fixed point of the domain, we investigate a boundary-value problem with the Riemann–Hilbert data for the solution itself and for its partial derivatives. We prove the Fredholm solvability of that problem and present its index formula.     

Lossless outer joins with incomplete information

In the relational model of data, Rissanen's Theorem provides the basis for the usual normalization process based on decomposition of relations. However, many difficulties occur if information is incomplete in databases and nulls are required to represent missing or unknown data. We concentrate here on the notion of outer join and find some reasonable conditions to guarantee that outer join will also preserve the lossless join property for two relations. Next we provide a generalization of this result to several relations.     

AD HOC网络中的区域划分和资源分配研究

建立了新的Ad Hoc无线网络的区域划分和资源分配模型,讨论了网络覆盖率和抗毁性.通过构造Voronoi图对平面单连通区域的Ad Hoc网络建立区域划分优化模型;定义了网络抗毁性的评价指标连通率,并通过构造Delaunay三角网的最小生成树和蒙特卡罗实验,取得了较好的抗毁仿真结果.最后结合K-均值分簇和罚函数法,得到了近似最优的平面复连通区域的Ad Hoc网络的区域划分和信道安排.     

图的k-单圈划分中的优化问题

图的划分问题曾引起图论界的广泛关注，在文献[4]中讨论了k-单圈划分，本文进一步研究基于k-单圈划分的优化问题，即在一个赋权图中求一个最小权可k-单圈划分的支撑子图，以及对一个不存在k-单圈划分支撑子图的图，如何添最少的边使得它有k-单圈划分的支撑子图。     

Partitioning a non-symmetric measure of association for three-way contingency tables

The Goodman-Kruskal tau index is a popular measure of asymmetry for two-way contingency tables where there is a one-way relationship between the variables. Numerous extensions of this index for multi-way tables have been considered in the statistical literature. These include the Gray-Williams measures, Simonetti's delta index and the Marcotorchino index.This paper looks at the partition of the Marcotorchino index for a three-way contingency table with one, two and three ordered categorical variables. Such a partition makes use of orthogonal polynomials and identifies two-way measures of asymmetry (akin to the Goodman-Kruskal tau index) and three-way measures generalisation. These partitions provide information about the structure of the asymmetric relationship between the categories in terms of location, dispersion and higher order moments.     

Evaluation of stock allocation policies in a divergent inventory system with shipment consolidation

In this paper we consider a one-warehouse N-retailer inventory system characterized by access to real-time point-of-sale data, and a time based dispatching and shipment consolidation policy at the warehouse. More precisely, inventory is reviewed continuously, while a consolidated shipment (for example, a truck) to all retailers is dispatched from the warehouse at regular time intervals. The focus is on investigating the cost benefits of using state-dependent myopic allocation policies instead of a simple FCFS (First-Come-First-Serve) rule to allocate shipped goods to the retailers. The analysis aims to shed some light on when, if ever, FCFS is a reasonable policy to use in this type of system? The FCFS allocations of items to retailers are determined by the sequence in which retailer orders (or equivalently customer demands) arrive to the warehouse. Applying the myopic policy enables the warehouse to postpone the allocation decision to the moment of shipment (from the warehouse) or the moments of delivery (to the different retailers), and to base it on the inventory information available at those times. The myopic allocation method we study is often used in the literature on periodic review systems.     

A power series method for computing singular solutions to nonlinear analytic systems

Summary Given a system of analytic equations having a singular solution, we show how to develop a power series representation for the solution. This series is computable, and when the multiplicity of the solution is small, highly accurate estimates of the solution can be generated for a moderate computational cost. In this paper, a theorem is proven (using results from several complex variables) which establishes the basis for the approach. Then a specific numerical method is developed, and data from numerical experiments are given.     

A cost allocation problem in urban solid wastes collection and disposal

In this paper we consider a cost allocation problem arising in a consortium for urban solid wastes collection and disposal. A classical allocation rule is the proportional division according to the volume of wastes collected; here we propose a different allocation method, rooted in game theory, based on a model developed by Fragnelli et al. [3], using the Shapley Value and the Owen Value as allocation rules. The model was applied to the data of the consortium Ovadese – Valle Scrivia, comparing our results and the actual ones.