Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

   Online First

Administered by

, Volume 11 Issue 4

For Selected: View Abstracts Toggle Thumbnails
NSFC EXCELLENT YOUNG SCHOLAR FORUM
A survey on Lyapunov-based methods for stability of linear time-delay systems
Jian SUN, Jie CHEN
Front. Comput. Sci.. 2017, 11 (4): 555-567.  
https://doi.org/10.1007/s11704-016-6120-3

Abstract   PDF (314KB)

Recently, stability analysis of time-delay systems has received much attention. Rich results have been obtained on this topic using various approaches and techniques. Most of those results are based on Lyapunov stability theories. The purpose of this article is to give a broad overview of stability of linear time-delay systems with emphasis on the more recent progress. Methods and techniques for the choice of an appropriate Lyapunov functional and the estimation of the derivative of the Lyapunov functional are reported in this article, and special attention is paid to reduce the conservatism of stability conditions using as few as possible decision variables. Several future research directions on this topic are also discussed.

References | Related Articles | Metrics
A comparative study of network robustness measures
Jing LIU, Mingxing ZHOU, Shuai WANG, Penghui LIU
Front. Comput. Sci.. 2017, 11 (4): 568-584.  
https://doi.org/10.1007/s11704-016-6108-z

Abstract   PDF (2369KB)

The robustness is an important functionality of networks because it manifests the ability of networks to resist failures or attacks. Many robustness measures have been proposed from different aspects, which provide us various ways to evaluate the network robustness. However, whether these measures can properly evaluate the network robustness and which aspects of network robustness these measures can evaluate are still open questions. Therefore, in this paper, a thorough introduction over attacks and robustness measures is first given, and then nine widely used robustness measures are comparatively studied. To validate whether a robustness measure can evaluate the network robustness properly, the sensitivity of robustness measures is first studied on both initial and optimized networks. Then, the performance of robustness measures in guiding the optimization process is studied, where both the optimization process and the obtained optimized networks are studied. The experimental results show that, first, the robustness measures are more sensitive to the changes in initial networks than to those in optimized networks; second, an optimized network may not be useful in practical situations because some useful functionalities, such as the shortest path length and communication efficiency, are sacrificed too much to improve the robustness; third, the robustness of networks in terms of closely correlated robustness measures can often be improved together. These results indicate that it is not wise to just apply the optimized networks obtained by optimizing over one certain robustness measure into practical situations. Practical requirements should be considered, and optimizing over two or more suitable robustnessmeasures simultaneously is also a promising way.

References | Supplementary Material | Related Articles | Metrics
REVIEW ARTICLE
A survey on formal specification and verification of separation kernels
Yongwang ZHAO, Zhibin YANG, Dianfu MA
Front. Comput. Sci.. 2017, 11 (4): 585-607.  
https://doi.org/10.1007/s11704-016-4226-2

Abstract   PDF (1329KB)

Separation kernels are fundamental software of safety and security-critical systems, which provide their hosted applications with spatial and temporal separation as well as controlled information flows among partitions. The application of separation kernels in critical domain demands the correctness of the kernel by formal verification. To the best of our knowledge, there is no survey paper on this topic. This paper presents an overview of formal specification and verification of separation kernels. We first present the background including the concept of separation kernel and the comparisons among different kernels. Then, we survey the state of the art on this topic since 2000. Finally, we summarize research work by detailed comparison and discussion.

References | Supplementary Material | Related Articles | Metrics
RESEARCH ARTICLE
A parallel computing framework for big data
Guoliang CHEN, Rui MAO, Kezhong LU
Front. Comput. Sci.. 2017, 11 (4): 608-621.  
https://doi.org/10.1007/s11704-016-5003-y

Abstract   PDF (627KB)

Big data has received great attention in research and application. However, most of the current efforts focus on system and application to handle the challenges of “volume” and “velocity”, and not much has been done on the theoretical foundation and to handle the challenge of “variety”. Based on metric-space indexing and computationalcomplexity theory, we propose a parallel computing framework for big data. This framework consists of three components, i.e., universal representation of big data by abstracting various data types into metric space, partitioning of big data based on pair-wise distances in metric space, and parallel computing of big data with the NC-class computing theory.

References | Supplementary Material | Related Articles | Metrics
A novel mapping algorithm for three-dimensional network on chip based on quantum-behaved particle swarm optimization
Cui HUANG, Dakun ZHANG, Guozhi SONG
Front. Comput. Sci.. 2017, 11 (4): 622-631.  
https://doi.org/10.1007/s11704-016-5196-0

Abstract   PDF (542KB)

Mapping of three-dimensional network on chip is a key problem in the research of three-dimensional network on chip. The quality of the mapping algorithm used directly affects the communication efficiency between IP cores and plays an important role in the optimization of power consumption and throughput of the whole chip. In this paper, basic concepts and related work of three-dimensional network on chip are introduced. Quantum-behaved particle swarm optimization algorithm is applied to the mapping problem of three-dimensional network on chip for the first time. Simulation results show that the mapping algorithm based on quantum-behaved particle swarm algorithm has faster convergence speed with much better optimization performance compared with the mapping algorithm based on particle swarm algorithm. It also can effectively reduce the power consumption of mapping of three-dimensional network on chip.

References | Supplementary Material | Related Articles | Metrics
Local structured representation for generic object detection
Junge ZHANG, Kaiqi HUANG, Tieniu TAN, Zhaoxiang ZHANG
Front. Comput. Sci.. 2017, 11 (4): 632-648.  
https://doi.org/10.1007/s11704-016-5530-6

Abstract   PDF (659KB)

Structure information plays an important role in both object recognition and detection. This paper studies what visual structure is and addresses the problem of structure modeling and representation from two aspects: visual feature and topology model. Firstly, at feature level, we propose Local Structured Descriptor to capture the object’s local structure effectively, and develop the descriptors from shape and texture information, respectively. Secondly, at topology level, we present a local structured model with a boosted feature selection and fusion scheme. All experiments are conducted on the challenging PASCAL Visual Object Classes (VOC) datasets from VOC2007 to VOC2010. Experimental results show that our method achieves very competitive performance.

References | Supplementary Material | Related Articles | Metrics
E-GrabCut: an economic method of iterative video object extraction
Le DONG, Ning FENG, Mengdie MAO, Ling HE, Jingjing WANG
Front. Comput. Sci.. 2017, 11 (4): 649-660.  
https://doi.org/10.1007/s11704-016-5558-7

Abstract   PDF (974KB)

Efficient, interactive foreground/background segmentation in video is of great practical importance in video editing. This paper proposes an interactive and unsupervised video object segmentation algorithm named E-GrabCut concentrating on achieving both of the segmentation quality and time efficiency as highly demanded in the related filed. There are three features in the proposed algorithms. Firstly, we have developed a powerful, non-iterative version of the optimization process for each frame. Secondly, more user interaction in the first frame is used to improve the Gaussian Mixture Model (GMM). Thirdly, a robust algorithm for the following frame segmentation has been developed by reusing the previous GMM. Extensive experiments demonstrate that our method outperforms the state-of-the-art video segmentation algorithm in terms of integration of time efficiency and segmentation quality.

References | Supplementary Material | Related Articles | Metrics
An online electricity cost budgeting algorithm for maximizing green energy usage across data centers
Hui DOU, Yong QI
Front. Comput. Sci.. 2017, 11 (4): 661-674.  
https://doi.org/10.1007/s11704-016-5420-y

Abstract   PDF (539KB)

With the sky-rocketing development of Internet services, the power usage in data centers has been significantly increasing. This ever increasing energy consumption leads to negative environmental impact such as global warming. To reduce their carbon footprints, large Internet service operators begin to utilize green energy. Since green energy is currently more expensive than the traditional brown one, it is important for the operators to maximize the green energy usage subject to their desired long-term (e.g., a month) cost budget constraint. In this paper, we propose an online algorithm GreenBudget based on the Lyapunov optimization framework. We prove that our algorithm is able to achieve a delicate tradeoff between the green energy usage and the enforcement of the cost budget constraint, and a control parameter V is the knob to arbitrarily tune such a tradeoff. We evaluate GreenBudget utilizing real-life traces of user requests, cooling efficiency, electricity price and green energy availability. Experimental results demonstrate that under the same cost budget constraint, GreenBudget can increase the green energy usage by 11.55% compared with the state-of-the-art work, without incurring any performance violation of user requests.

References | Supplementary Material | Related Articles | Metrics
Interest-suppression-based NDN live video broadcasting over wireless LAN
Menghan LI, Dan PEI, Xiaoping ZHANG, Beichuan ZHANG, Ke XU
Front. Comput. Sci.. 2017, 11 (4): 675-687.  
https://doi.org/10.1007/s11704-016-5563-x

Abstract   PDF (538KB)

Named data networking (NDN) is a new Internet architecture that replaces today’s focus on where – addresses and hosts with what – the content that users and applications care about. One of NDN’s prominent advantages is scalable and efficient content distribution due to its native support of caching and multicast in the network. However, at the last hop to wireless users, often the WiFi link, current NDN implementation still treats the communication as multiple unicast sessions, which will cause duplicate packets and waste of bandwidth when multiple users request for the same popular content. WiFi’s built-in broadcast mechanism can alleviate this problem, but it suffers from packet loss since there is no MAC-layer acknowledgement as in unicast. In this paper, we develop a new NDN-based cross-layer approach called NLB for efficient and scalable live video streaming over wireless LAN. The core ideas are: using WiFi’s broadcast channel to deliver content from the access point to the users, a leaderbased mechanism to suppress duplicate requests from users, and receiver-driven rate control and loss recovery. The design is implemented and evaluated in a physical testbed comprised of one software AP and 20 Raspberry Pi-based WiFi clients. While NDN with multiple unicast sessions or plain broadcast can support no more than ten concurrent viewers of a 1Mbps streaming video, NDN plus NLB supports all 20 viewers, and can likely support much more when present.

References | Supplementary Material | Related Articles | Metrics
Discovering context-aware conditional functional dependencies
Yuefeng DU, Derong SHEN, Tiezheng NIE, Yue KOU, Ge YU
Front. Comput. Sci.. 2017, 11 (4): 688-701.  
https://doi.org/10.1007/s11704-016-5265-4

Abstract   PDF (603KB)

Conditional functional dependencies(CFDs) are important techniques for data consistency. However, CFDs are limited to 1) provide the reasonable values for consistency repairing and 2) detect potential errors. This paper presents context-aware conditional functional dependencies(CCFDs) which contribute to provide reasonable values and detect potential errors. Especially, we focus on automatically discovering minimal CCFDs. In this paper, we present context relativity to measure the relationship of CFDs. The overlap of the related CFDs can provide reasonable values which result in more accuracy consistency repairing, and some related CFDs are combined into CCFDs.Moreover,we prove that discovering minimal CCFDs is NP-complete and we design the precise method and the heuristic method. We also present the dominating value to facilitate the process in both the precise method and the heuristic method. Additionally, the context relativity of the CFDs affects the cleaning results. We will give an approximate threshold of context relativity according to data distribution for suggestion. The repairing results are approvedmore accuracy, even evidenced by our empirical evaluation.

References | Supplementary Material | Related Articles | Metrics
Time-aware conversion prediction
Wendi JI, Xiaoling WANG, Feida ZHU
Front. Comput. Sci.. 2017, 11 (4): 702-716.  
https://doi.org/10.1007/s11704-016-5546-y

Abstract   PDF (696KB)

The importance of product recommendation has been well recognized as a central task in business intelligence for e-commerce websites. Interestingly, what has been less aware of is the fact that different products take different time periods for conversion. The “conversion” here refers to actually a more general set of pre-defined actions, including for example purchases or registrations in recommendation and advertising systems. The mismatch between the product’s actual conversion period and the application’s target conversion period has been the subtle culprit compromising many existing recommendation algorithms.

The challenging question: what products should be recommended for a given time period to maximize conversion—is what has motivated us in this paper to propose a rank-based time-aware conversion prediction model (rTCP), which considers both recommendation relevance and conversion time. We adopt lifetime models in survival analysis to model the conversion time and personalize the temporal prediction by incorporating context information such as user preference. A novel mixture lifetime model is proposed to further accommodate the complexity of conversion intervals. Experimental results on two real-world data sets illustrate the high goodness of fit of our proposed model rTCP and demonstrate its effectiveness in time-aware conversion rate prediction for advertising and product recommendation.

References | Supplementary Material | Related Articles | Metrics
An improved brain MR image binarization method as a preprocessing for abnormality detection and features extraction
Sudipta ROY, Debnath BHATTACHARYYA, Samir Kumar BANDYOPADHYAY, Tai-Hoon KIM
Front. Comput. Sci.. 2017, 11 (4): 717-727.  
https://doi.org/10.1007/s11704-016-5129-y

Abstract   PDF (649KB)

This paper propose a computerized method of magnetic resonance imaging (MRI) of brain binarization for the uses of preprocessing of features extraction and brain abnormality identification. One of the main problems of MRI binarization is that many pixels of brain part cannot be correctly binarized due to extensive black background or large variation in contrast between background and foreground of MRI. We have proposed a binarization that uses mean, variance, standard deviation and entropy to determine a threshold value followed by a non-gamut enhancement which can overcome the binarization problem of brain component. The proposed binarization technique is extensively tested with a variety of MRI and generates good binarization with improved accuracy and reduced error. A comparison is carried out among the obtained outcome with this innovative method with respect to other well-known methods.

References | Supplementary Material | Related Articles | Metrics
An efficient and fast polarity optimization approach for mixed polarity Reed-Muller logic circuits
Zhenxue HE, Limin XIAO, Fei GU, Tongsheng XIA, Shubin SU, Zhisheng HUO, Rong ZHANG, Longbing ZHANG, Li RUAN, Xiang WANG
Front. Comput. Sci.. 2017, 11 (4): 728-742.  
https://doi.org/10.1007/s11704-016-5259-2

Abstract   PDF (709KB)

Although the genetic algorithm has been widely used in the polarity optimization of mixed polarity Reed- Muller (MPRM) logic circuits, few studies have taken into account the polarity conversion sequence. In order to improve the efficiency of polarity optimization of MPRM logic circuits, we propose an efficient and fast polarity optimization approach (FPOA) considering the polarity conversion sequence. The main idea behind the FPOA is that, firstly, the best polarity conversion sequence of the polarity set waiting for evaluation is obtained by using the proposed hybrid genetic algorithm (HGA); secondly, each of polarity in the polarity set is converted according to the best polarity conversion sequence obtained by HGA. Our proposed FPOA is implemented in C and a comparative analysis has been presented for MCNC benchmark circuits. The experimental results show that for the circuits with more variables, the FPOA is highly effective in improving the efficiency of polarity optimization of MPRM logic circuits compared with the traditional polarity optimization approach which neglects the polarity conversion sequence and the improved polarity optimization approach with heuristic technique.

References | Supplementary Material | Related Articles | Metrics
13 articles