H.264帧内预测模式选择快速算法的研究

提出一种适用于H.264帧内预测的快速算法,利用相邻像素间的梯度筛选预测模式来避免不必要的预测模式计算。实验结果表明:用全I帧编码,该算法在图像质量和输出码率基本不变的情况下,编码时间大约节省了60%。     

一种面向主题的关键词查询扩展方法

提出一种基于局部统计和语义扩展相结合,面向主题的关键词查询扩展方法。该方法通过对给定主题的初始关键词搜索反馈网页进行分析,采用TF*PSF语义加权方法计算主题候选词的权重来进一步筛选主题关键词。在此基础上,设计了面向Web的主题关键词迭代查询扩展算法,采用主题关键词的组合查询策略,迭代扩展出主题的关键词集合。实验证明该方法是有效的。     

基于SNMP的校园网ARP攻击检测方法研究

防范地址解析协议ARP(Address Resolution Protocol)欺骗攻击的难点是:攻击源可以隐藏在网段内任何一个主机中,即使发现了攻击的存在,也难以迅速定位攻击源。结合校园网络的特点,提出了一种新的ARP攻击检测方案:检测服务器通过SNMP协议定期读取核心交换机的ARP、VLAN等信息和接入交换机的MAC-PORT信息,利用综合检测算法,及时发现攻击现象,迅速定位攻击源,并根据网络实际情况采用不同的技术措施进行处理。实践证明,该方法能够有效保障校园网络安全。     

Improvement of Machine Translation Evaluation by Simple Linguistically Motivated Features

Adopting the regression SVM framework, this paper proposes a linguistically motivated feature engineering strategy to develop an MT evaluation metric with a better correlation with human assessments. In contrast to current practices of “greedy” combination of all available features, six features are suggested according to the human intuition for translation quality. Then the contribution of linguistic features is examined and analyzed via a hill-climbing strategy. Experiments indicate that, compared to either the SVM-ranking model or the previous attempts on exhaustive linguistic features, the regression SVM model with six linguistic information based features generalizes across different datasets better, and augmenting these linguistic features with proper non-linguistic metrics can achieve additional improvements.     

A 1-Local Asymptotic 13/9-Competitive Algorithm for Multicoloring Hexagonal Graphs

In the frequency allocation problem, we are given a mobile telephone network, whose geographical coverage area is divided into cells, wherein phone calls are serviced by assigning frequencies to them so that no two calls emanating from the same or neighboring cells are assigned the same frequency. The problem is to use the frequencies efficiently, i.e., minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper, we give a 1-local asymptotic 4/3-competitive distributed algorithm for multicoloring a triangle-free hexagonal graph, which is a special case of hexagonal graph. Based on this result, we then propose a 1-local asymptotic13/9-competitive algorithm for multicoloring the (general-case) hexagonal graph, thereby improving the previous 1-local 3/2-competitive algorithm. A preliminary version of this paper appeared in the Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON 2007), LNCS 4598, pp. 526–536. Y. Zhang research was supported by European Regional Development Fund (ERDF). F.Y.L. Chin research was supported by Hong Kong RGC Grant HKU-7113/07E. H. Zhu research was supported by National Natural Science Fund (grant #60496321).     

Graph OLAP: a multi-dimensional framework for graph data analysis

Databases and data warehouse systems have been evolving from handling normalized spreadsheets stored in relational databases, to managing and analyzing diverse application-oriented data with complex interconnecting structures. Responding to this emerging trend, graphs have been growing rapidly and showing their critical importance in many applications, such as the analysis of XML, social networks, Web, biological data, multimedia data and spatiotemporal data. Can we extend useful functions of databases and data warehouse systems to handle graph structured data? In particular, OLAP (On-Line Analytical Processing) has been a popular tool for fast and user-friendly multi-dimensional analysis of data warehouses. Can we OLAP graphs? Unfortunately, to our best knowledge, there are no OLAP tools available that can interactively view and analyze graph data from different perspectives and with multiple granularities. In this paper, we argue that it is critically important to OLAP graph structured data and propose a novel Graph OLAP framework. According to this framework, given a graph dataset with its nodes and edges associated with respective attributes, a multi-dimensional model can be built to enable efficient on-line analytical processing so that any portions of the graphs can be generalized/specialized dynamically, offering multiple, versatile views of the data. The contributions of this work are three-fold. First, starting from basic definitions, i.e., what are dimensions and measures in the Graph OLAP scenario, we develop a conceptual framework for data cubes on graphs. We also look into different semantics of OLAP operations, and classify the framework into two major subcases: informational OLAP and topological OLAP. Second, we show how a graph cube can be materialized by calculating a special kind of measure called aggregated graph and how to implement it efficiently. This includes both full materialization and partial materialization where constraints are enforced to obtain an iceberg cube. As we can see, due to the increased structural complexity of data, aggregated graphs that depend on the underlying “network” properties of the graph dataset are much harder to compute than their traditional OLAP counterparts. Third, to provide more flexible, interesting and informative OLAP of graphs, we further propose a discovery-driven multi-dimensional analysis model to ensure that OLAP is performed in an intelligent manner, guided by expert rules and knowledge discovery processes. We outline such a framework and discuss some challenging research issues for discovery-driven Graph OLAP.     

Deadline division-based heuristic for cost optimization in workflow scheduling

Cost optimization for workflow applications described by Directed Acyclic Graph (DAG) with deadline constraints is a fundamental and intractable problem on Grids. In this paper, an effective and efficient heuristic called DET (Deadline Early Tree) is proposed. An early feasible schedule for a workflow application is defined as an Early Tree. According to the Early Tree, all tasks are grouped and the Critical Path is given. For critical activities, the optimal cost solution under the deadline constraint can be obtained by a dynamic programming strategy, and the whole deadline is segmented into time windows according to the slack time float. For non-critical activities, an iterative procedure is proposed to maximize time windows while maintaining the precedence constraints among activities. In terms of the time window allocations, a local optimization method is developed to minimize execution costs. The two local cost optimization methods can lead to a global near-optimal solution. Experimental results show that DET outperforms two other recent leveling algorithms. Moreover, the deadline division strategy adopted by DET can be applied to all feasible deadlines.     

Visual Tracking by Continuous Density Propagation in Sequential Bayesian Filtering Framework

Particle filtering is frequently used for visual tracking problems since it provides a general framework for estimating and propagating probability density functions for nonlinear and non-Gaussian dynamic systems. However, this algorithm is based on a Monte Carlo approach and the cost of sampling and measurement is a problematic issue, especially for high-dimensional problems. We describe an alternative to the classical particle filter in which the underlying density function has an analytic representation for better approximation and effective propagation. The techniques of density interpolation and density approximation are introduced to represent the likelihood and the posterior densities with Gaussian mixtures, where all relevant parameters are automatically determined. The proposed analytic approach is shown to perform more efficiently in sampling in high-dimensional space. We apply the algorithm to real-time tracking problems and demonstrate its performance on real video sequences as well as synthetic examples.     

Parameterized computational complexity of control problems in voting systems

Voting systems are common tools in a variety of areas. This paper studies parameterized computational complexity of control of Plurality, Condorcet and Approval voting systems, respectively. The types of controls considered include adding or deleting candidates or voters, under constructive or destructive setting. We obtain the following results: (1) constructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter “number of added candidates”, (2) destructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter “number of added candidates”, (3) constructive control by adding voters in Condorcet voting is W[1]-hard with respect to the parameter “number of added voters”, (4) constructive control by deleting voters in Condorcet voting is W[1]-hard with respect to the parameter “number of deleted voters”, (5) constructive control by adding voters in Approval voting is W[1]-hard with respect to the parameter “number of added voters”, and (6) constructive control by deleting voters in Approval voting is W[2]-hard with respect to the parameter “number of deleted voters”.