Optimizing multiple dimensional queries simultaneously in multidimensional databases

Some significant progress related to multidimensional data analysis has been achieved in the past few years, including the design of fast algorithms for computing datacubes, selecting some precomputed group-bys to materialize, and designing efficient storage structures for multidimensional data. However, little work has been carried out on multidimensional query optimization issues. Particularly the response time (or evaluation cost) for answering several related dimensional queries simultaneously is crucial to the OLAP applications. Recently, Zhao et al. first exploited this problem by presenting three heuristic algorithms. In this paper we first consider in detail two cases of the problem in which all the queries are either hash-based star joins or index-based star joins only. In the case of the hash-based star join, we devise a polynomial approximation algorithm which delivers a plan whose evaluation cost is $ O(n^{\epsilon }$) times the optimal, where n is the number of queries and is a fixed constant with . We also present an exponential algorithm which delivers a plan with the optimal evaluation cost. In the case of the index-based star join, we present a heuristic algorithm which delivers a plan whose evaluation cost is n times the optimal, and an exponential algorithm which delivers a plan with the optimal evaluation cost. We then consider a general case in which both hash-based star-join and index-based star-join queries are included. For this case, we give a possible improvement on the work of Zhao et al., based on an analysis of their solutions. We also develop another heuristic and an exact algorithm for the problem. We finally conduct a performance study by implementing our algorithms. The experimental results demonstrate that the solutions delivered for the restricted cases are always within two times of the optimal, which confirms our theoretical upper bounds. Actually these experiments produce much better results than our theoretical estimates. To the best of our knowledge, this is the only development of polynomial algorithms for the first two cases which are able to deliver plans with deterministic performance guarantees in terms of the qualities of the plans generated. The previous approaches including that of [ZDNS98] may generate a feasible plan for the problem in these two cases, but they do not provide any performance guarantee, i.e., the plans generated by their algorithms can be arbitrarily far from the optimal one. Received: July 21, 1998 / Accepted: August 26, 1999     

基于有限障碍的全牛顿步内点算法

针对线性规划问题,文中引入了一种与传统障碍函数不同的新的障碍函数,其在可行域边界上的取值是有限的.沿此有限障碍函数所确定的新的搜索方向,给出了短步长全牛顿步内点算法,结果证明该算法具有目前求解线性规划问题最好的复杂性界.     

A Tabu search algorithm for the network pricing problem

In this paper, we propose an efficient Tabu Search procedure for solving the NP-hard network pricing problem. By exploiting the problem's features, the algorithm allows the near-optimal solution of problem instances that are out of reach of exact combinatorial methods.     

Bacteria foraging optimization for protein sequence analysis on the grid

Scientific applications such as protein sequence analysis require a coordination of resources. This is due to hundreds and hundreds of protein sequences being deposited into data banks by the research community which results in an extensive database search when one wants to find a similar protein sequence. This search becomes easier and the time taken is reduced when it is conducted in a grid environment implemented using the Globus tool kit. This paper proposes the use of Bacteria Foraging Optimization (BFO) for finding similar protein sequences in the existing databases. Usage of BFO further reduces the time taken by a resource to execute the user’s requests. Also, the resources utilized in the proposed method are better balanced compared to the existing scheduling algorithms. Also, it is found that the number of tasks executed is more compared to the existing algorithms even though there is a fall in the execution of tasks as the number of resources increases which might be due to network failure etc. The proposed BFO has been compared with the existing First Come First Serve (FCFS) and Minimum Execution Time (MET) scheduling algorithms and it has been found that the proposed BFO performs well compared to the existing algorithms in terms of makespan, resource utilization and minimization in the case of non-execution of client requests.     

我国南方某铀矿井通风系统优化改造研究

在全面分析总结我国南方某铀矿井通风系统存在的问题基础上,以按需分风的通风网络优化技术,对原有通风系统进行优化,提出了矿井通风系统总体改造方案.通过方案实施,氡及氡子体浓度达到了国家辐射防护标准要求,各采掘面平均氡子体浓度下降了22.9%.     

基于李雅普诺夫函数法的扩张状态观测器参数优化

针对ESO参数不易整定的问题,研究了扩张状态观测器(ESO)参数优化的李雅普诺夫函数法.首先建立关于误差的线性定常状态方程和误差指标函数J,在误差指标函数J中综合考虑了跟踪误差的权重和系统的稳定性以及实际运行时的饱和值限制等因素.仿真结果表明,此方法具有概念清晰,实用简便,计算量小的优点.所提ESO参数整定方法是有效的.     

Two-stage updating pheromone for invariant ant colony optimization algorithm

Ant colony optimization (ACO) is a metaheuristic approach for combinatorial optimization problems. With the introduction of hypercube framework, invariance property of ACO algorithms draws more attention. In this paper, we propose a novel two-stage updating pheromone for invariant ant colony optimization (TSIACO) algorithm. Compared with standard ACO algorithms, TSIACO algorithm uses solution order other than solution itself as independent variable for quality function. In addition, the pheromone trail is updated with two stages: in one stage, the first r iterative optimal solutions are employed to enhance search capability, and in another stage, only optimal solution is used to accelerate the speed of convergence. And besides, the pheromone value is limited to an interval. We prove that TSIACO not only has the property of linear transformational invariance but also has translational invariance. We also prove that the pheromone trail can limit to the interval (0, 1]. Computational results on the traveling salesman problem show the effectiveness of TSIACO algorithm.     

An improved SVD-based watermarking technique for copyright protection

The drawbacks of SVD-based image watermarking are false positive, robust and transparency. The former can be overcome by embedding the principal components of the watermark into the host image, the latter is dependent on how much the quantity (i.e., scaling factor) of the principal components is embedded. For the existing methods, the scaling factor is a fixed value; actually, it is image-dependent. Different watermarks need the different scaling factors, although they are embedded in the same host image. In this paper, two methods are proposed to improve the reliability and robustness. To improve the reliability, for the first method, the principal components of the watermark are embedded into the host image in discrete cosine transform (DCT); and for the second method, those are embedded into the host image in discrete wavelets transform (DWT). To improve the robustness, the particle swarm optimization (PSO) is used for finding the suitable scaling factors. The experimental results demonstrate that the performance of the proposed methods outperforms than those of the existing methods.     

An MIP model to optimize a Colombian cash supply chain

Financial institutions operate a supply chain where only one product is moved across the network. Although the cash is kept in several nodes to service the demand of final customers, availability causes opportunity cost related with its investment options. When planning the inventory of cash that should be maintained across the network, transportation decisions are also expected to be made. Cash transportation has a high cost, associated with the high risk of theft. Increasing the inventory can reduce the need for transportation, but the opportunity cost can be very high. Moreover, the inventory is also related with the service level perceived for final customers; therefore because of low inventory some people are not able to make some transactions. The aim of this work is to find optimal decisions related with cash inventory and transportation across the network, trying to balance the cost of the service and the quality perceived for final users.