Please wait a minute...

Frontiers of Computer Science

Current Issue

, Volume 12 Issue 5 Previous Issue   
For Selected: View Abstracts Toggle Thumbnails
REVIEW ARTICLE
Large-scale video compression: recent advances and challenges
Tao TIAN, Hanli WANG
Front. Comput. Sci.. 2018, 12 (5): 825-839.  https://doi.org/10.1007/s11704-018-7304-9
Abstract   PDF (785KB)

The evolution of social network and multimedia technologies encourage more and more people to generate and upload visual information, which leads to the generation of large-scale video data. Therefore, preeminent compression technologies are highly desired to facilitate the storage and transmission of these tremendous video data for a wide variety of applications. In this paper, a systematic review of the recent advances for large-scale video compression (LSVC) is presented. Specifically, fast video coding algorithms and effective models to improve video compression efficiency are introduced in detail, since coding complexity and compression efficiency are two important factors to evaluate video coding approaches. Finally, the challenges and future research trends for LSVC are discussed.

References | Supplementary Material | Related Articles | Metrics
RESEARCH ARTICLE
Learning deep representations for semantic image parsing: a comprehensive overview
Lili HUANG, Jiefeng PENG, Ruimao ZHANG, Guanbin LI, Liang LIN
Front. Comput. Sci.. 2018, 12 (5): 840-857.  https://doi.org/10.1007/s11704-018-7195-8
Abstract   PDF (1089KB)

Semantic image parsing, which refers to the process of decomposing images into semantic regions and constructing the structure representation of the input, has recently aroused widespread interest in the field of computer vision. The recent application of deep representation learning has driven this field into a new stage of development. In this paper, we summarize three aspects of the progress of research on semantic image parsing, i.e., category-level semantic segmentation, instance-level semantic segmentation, and beyond segmentation. Specifically, we first review the general frameworks for each task and introduce the relevant variants. The advantages and limitations of each method are also discussed. Moreover, we present a comprehensive comparison of different benchmark datasets and evaluation metrics. Finally, we explore the future trends and challenges of semantic image parsing.

References | Supplementary Material | Related Articles | Metrics
REVIEW ARTICLE
Remote heart rate measurement using low-cost RGB face video: a technical literature review
Philipp V. ROUAST, Marc T. P. ADAM, Raymond CHIONG, David CORNFORTH, Ewa LUX
Front. Comput. Sci.. 2018, 12 (5): 858-872.  https://doi.org/10.1007/s11704-016-6243-6
Abstract   PDF (2256KB)

Remote photoplethysmography (rPPG) allows remote measurement of the heart rate using low-cost RGB imaging equipment. In this study, we review the development of the field of rPPG since its emergence in 2008. We also classify existing rPPG approaches and derive a framework that provides an overview of modular steps. Based on this framework, practitioners can use our classification to design algorithms for an rPPG approach that suits their specific needs. Researchers can use the reviewed and classified algorithms as a starting point to improve particular features of an rPPG algorithm.

References | Supplementary Material | Related Articles | Metrics
RESEARCH ARTICLE
VBMq: pursuit baremetal performance by embracing block I/O parallelism in virtualization
Diming ZHANG, Fei XUE, Hao HUANG, Shaodi YOU
Front. Comput. Sci.. 2018, 12 (5): 873-886.  https://doi.org/10.1007/s11704-017-6466-1
Abstract   PDF (881KB)

Barely acceptable block I/O performance prevents virtualization from being widely used in the High-Performance Computing field. Although the virtio paravirtual framework brings great I/O performance improvement, there is a sharp performance degradation when accessing high-performance NAND-flash-based devices in the virtual machine due to their data parallel design. The primary cause of this fact is the deficiency of block I/O parallelism in hypervisor, such as KVM and Xen. In this paper, we propose a novel design of block I/O layer for virtualization, named VBMq. VBMq is based on virtio paravirtual I/O model, aiming to solve the block I/O parallelism issue in virtualization. It uses multiple dedicated I/O threads to handle I/O requests in parallel. In the meanwhile, we use polling mechanism to alleviate overheads caused by the frequent context switches of the VM’s notification to and from its hypervisor. Each dedicated I/O thread is assigned to a non-overlapping core to improve performance by avoiding unnecessary scheduling. In addition, we configure CPU affinity to optimize I/O completion for each request. The CPU affinity setting is very helpful to reduce CPU cache miss rate and increase CPU efficiency. The prototype system is based on Linux 4.1 kernel and QEMU 2.3.1. Our measurements show that the proposed method scales graciously in the multi-core environment, and provides performance which is 39.6x better than the baseline at most, and approaches bare-metal performance.

References | Supplementary Material | Related Articles | Metrics
A communication-reduced and computation-balanced framework for fast graph computation
Yongli CHENG, Fang WANG, Hong JIANG, Yu HUA, Dan FENG, Lingling ZHANG, Jun ZHOU
Front. Comput. Sci.. 2018, 12 (5): 887-907.  https://doi.org/10.1007/s11704-018-6400-1
Abstract   PDF (1064KB)

The bulk synchronous parallel (BSP) model is very user friendly for coding and debugging parallel graph algorithms. However, existing BSP-based distributed graphprocessing frameworks, such as Pregel, GPS and Giraph, routinely suffer from high communication costs. These high communication costs mainly stem from the fine-grained message-passing communication model. In order to address this problem, we propose a new computation model with low communication costs, called LCC-BSP. We use this model to design and implement a high-performance distributed graphprocessing framework called LCC-Graph. This framework eliminates high communication costs in existing distributed graph-processing frameworks. Moreover, LCC-Graph also balances the computation workloads among all compute nodes by optimizing graph partitioning, significantly reducing the computation time for each superstep. Evaluation of LCC-Graph on a 32-node cluster, driven by real-world graph datasets, shows that it significantly outperforms existing distributed graph-processing frameworks in terms of runtime, particularly when the system is supported by a highbandwidth network. For example, LCC-Graph achieves an order of magnitude performance improvement over GPS and GraphLab.

References | Supplementary Material | Related Articles | Metrics
Software design pattern mining using classification-based techniques
Ashish Kumar DWIVEDI, Anand TIRKEY, Santanu Kumar RATH
Front. Comput. Sci.. 2018, 12 (5): 908-922.  https://doi.org/10.1007/s11704-017-6424-y
Abstract   PDF (668KB)

Design patterns are often used in the development of object-oriented software. It offers reusable abstract information that is helpful in solving recurring design problems. Detecting design patterns is beneficial to the comprehension and maintenance of object-oriented software systems. Several pattern detection techniques based on static analysis often encounter problems when detecting design patterns for identical structures of patterns. In this study, we attempt to detect software design patterns by using software metrics and classification-based techniques. Our study is conducted in two phases: creation of metrics-oriented dataset and detection of software design patterns. The datasets are prepared by using software metrics for the learning of classifiers. Then, pattern detection is performed by using classification-based techniques. To evaluate the proposed method, experiments are conducted using three open source software programs, JHotDraw, QuickUML, and JUnit, and the results are analyzed.

References | Supplementary Material | Related Articles | Metrics
Correlation-based software search by leveraging software term database
Zhixing LI, Gang YIN, Tao WANG, Yang ZHANG, Yue YU, Huaimin WANG
Front. Comput. Sci.. 2018, 12 (5): 923-938.  https://doi.org/10.1007/s11704-017-6573-z
Abstract   PDF (638KB)

Internet-scale open source software (OSS) production in various communities generates abundant reusable resources for software developers. However, finding the desired and mature software with keyword queries from a considerable number of candidates, especially for the fresher, is a significant challenge because current search services often fail to understand the semantics of user queries. In this paper, we construct a software term database (STDB) by analyzing tagging data in Stack Overflow and propose a correlationbased software search (CBSS) approach that performs correlation retrieval based on the term relevance obtained from STDB. In addition, we design a novel ranking method to optimize the initial retrieval result. We explore four research questions in four experiments, respectively, to evaluate the effectiveness of the STDB and investigate the performance of the CBSS. The experiment results show that the proposed CBSS can effectively respond to keyword-based software searches and significantly outperforms other existing search services at finding mature software.

References | Supplementary Material | Related Articles | Metrics
Achieving data-driven actionability by combining learning and planning
Qiang LV, Yixin CHEN, Zhaorong LI, Zhicheng CUI, Ling CHEN, Xing ZHANG, Haihua SHEN
Front. Comput. Sci.. 2018, 12 (5): 939-949.  https://doi.org/10.1007/s11704-017-6315-2
Abstract   PDF (437KB)

A main focus of machine learning research has been improving the generalization accuracy and efficiency of prediction models. However, what emerges as missing in many applications is actionability, i.e., the ability to turn prediction results into actions. Existing effort in deriving such actionable knowledge is few and limited to simple action models while in many real applications those models are often more complex and harder to extract an optimal solution. In this paper, we propose a novel approach that achieves actionability by combining learning with planning, two core areas of AI. In particular, we propose a framework to extract actionable knowledge from random forest, one of the most widely used and best off-the-shelf classifiers. We formulate the actionability problem to a sub-optimal action planning (SOAP) problem, which is to find a plan to alter certain features of a given input so that the random forest would yield a desirable output, while minimizing the total costs of actions. Technically, the SOAP problem is formulated in the SAS+ planning formalism, and solved using a Max-SAT based approach. Our experimental results demonstrate the effectiveness and efficiency of the proposed approach on a personal credit dataset and other benchmarks. Our work represents a new application of automated planning on an emerging and challenging machine learning paradigm.

References | Supplementary Material | Related Articles | Metrics
Polygene-based evolutionary algorithms with frequent pattern mining
Shuaiqiang WANG, Yilong YIN
Front. Comput. Sci.. 2018, 12 (5): 950-965.  https://doi.org/10.1007/s11704-016-6104-3
Abstract   PDF (994KB)

In this paper, we introduce polygene-based evolution, a novel framework for evolutionary algorithms (EAs) that features distinctive operations in the evolutionary process. In traditional EAs, the primitive evolution unit is a gene, wherein genes are independent components during evolution. In polygene-based evolutionary algorithms (PGEAs), the evolution unit is a polygene, i.e., a set of co-regulated genes. Discovering and maintaining quality polygenes can play an effective role in evolving quality individuals. Polygenes generalize genes, and PGEAs generalize EAs. Implementing the PGEA framework involves three phases: (I) polygene discovery, (II) polygene planting, and (III) polygene-compatible evolution. For Phase I, we adopt an associative classificationbased approach to discover quality polygenes. For Phase II, we perform probabilistic planting to maintain the diversity of individuals. For Phase III, we incorporate polygenecompatible crossover and mutation in producing the next generation of individuals. Extensive experiments on function optimization benchmarks in comparison with the conventional and state-of-the-art EAs demonstrate the potential of the approach in terms of accuracy and efficiency improvement.

References | Supplementary Material | Related Articles | Metrics
Using partial evaluation in holistic subgraph search
Peng PENG, Lei ZOU, Zhenqin DU, Dongyan ZHAO
Front. Comput. Sci.. 2018, 12 (5): 966-983.  https://doi.org/10.1007/s11704-016-5522-6
Abstract   PDF (798KB)

Because of its wide application, the subgraph matching problem has been studied extensively during the past decade. However, most existing solutions assume that a data graph is a vertex/edge-labeled graph (i.e., each vertex/ edge has a simple label). These solutions build structural indices by considering the vertex labels. However, some real graphs contain rich-content vertices such as user profiles in social networks and HTML pages on the World Wide Web. In this study, we consider the problem of subgraph matching using a more general scenario. We build a structural index that does not depend on any vertex content. Based on the index, we design a holistic subgraph matching algorithm that considers the query graph as a whole and finds one match at a time. In order to further improve efficiency, we propose a “partial evaluation and assembly” framework to find subgraph matches over large graphs. Last but not least, our index has light maintenance overhead. Therefore, our method can work well on dynamic graphs. Extensive experiments on real graphs show that our method outperforms the state-of-the-art algorithms.

References | Supplementary Material | Related Articles | Metrics
Efficient histogram-based range query estimation for dirty data
Yan ZHANG, Hongzhi WANG, Long YANG, Jianzhong LI
Front. Comput. Sci.. 2018, 12 (5): 984-999.  https://doi.org/10.1007/s11704-016-5551-1
Abstract   PDF (564KB)

In recent years, data quality issues have attracted wide attentions. Data quality problems are mainly caused by dirty data. Currently, many methods for dirty data management have been proposed, and one of them is entity-based relational database in which one tuple represents an entity. The traditional query optimizations are not suitable for the new entity-based model. Then new query optimizations need to be developed. In this paper, we propose a new query selectivity estimation strategy based on histogram, and focus on solving the overestimation which traditional methods lead to. We prove our approaches are unbiased. The experimental results on both real and synthetic data sets show that our approaches can give good estimates with low error.

References | Supplementary Material | Related Articles | Metrics
Local features and manifold ranking coupled method for sketch-based 3D model retrieval
Xiaohui TAN, Yachun FAN, Ruiliang GUO
Front. Comput. Sci.. 2018, 12 (5): 1000-1012.  https://doi.org/10.1007/s11704-017-6595-6
Abstract   PDF (539KB)

3D model retrieval can benefit many downstream virtual reality applications. In this paper, we propose a new sketch-based 3D model retrieval framework by coupling local features and manifold ranking. At technical fronts, we exploit spatial pyramids based local structures to facilitate the efficient construction of feature descriptors.Meanwhile, we propose an improved manifold ranking method, wherein all the categories between arbitrary model pairs will be taken into account. Since the smooth and detail-preserving line drawings of 3D model are important for sketch-based 3D model retrieval, the Difference of Gaussians (DoG) method is employed to extract the line drawings over the projected depth images of 3D model, and Bezier Curve is then adopted to further optimize the extracted line drawing. On that basis, we develop a 3D model retrieval engine to verify our method. We have conducted extensive experiments over various public benchmarks, and have made comprehensive comparisons with some state-of-the-art 3D retrieval methods. All the evaluation results based on the widely-used indicators prove the superiority of our method in accuracy, reliability, robustness, and versatility.

References | Supplementary Material | Related Articles | Metrics
Applying rotation-invariant star descriptor to deep-sky image registration
Haiyang ZHOU, Yunzhi YU
Front. Comput. Sci.. 2018, 12 (5): 1013-1025.  https://doi.org/10.1007/s11704-017-6495-9
Abstract   PDF (828KB)

Image registration is a critical process of many deep-sky image processing applications. Image registration methods include image stacking to reduce noise or achieve long exposure effects within a short exposure time, image stitching to extend the field of view, and atmospheric turbulence removal. The most widely used method for deep-sky image registration is the triangle- or polygon-based method, which is both memory and computation intensive. Deepsky image registration mainly focuses on translation and rotation caused by the vibration of imaging devices and the Earth’s rotation, where rotation is the more difficult problem. For this problem, the best method is to find corresponding rotation-invariant features between different images. In this paper, we analyze the defects introduced by applying rotation-invariant feature descriptors to deep-sky image registration and propose a novel descriptor. First, a dominant orientation is estimated from the geometrical relationships between a described star and two neighboring stable stars. An adaptive speeded-up robust features (SURF) descriptor is then constructed. During the construction of SURF, the local patch size adaptively changes based on the described star size. Finally, the proposed descriptor is formed by fusing star properties, geometrical relationships, and the adaptive SURF. Extensive experiments demonstrate that the proposed descriptor successfully addresses the gap resulting from applying the traditional feature-based method to deep-sky image registration and performs well compared to state-of-the-art descriptors.

References | Supplementary Material | Related Articles | Metrics
LETTER
A proof-based method of hybrid systems development using differential invariants
Jie LIU, Jing LIU, Miaomiao ZHANG, Haiying SUN, Xiaohong CHEN, Dehui DU, Mingsong CHEN
Front. Comput. Sci.. 2018, 12 (5): 1026-1028.  https://doi.org/10.1007/s11704-018-7213-y
Abstract   PDF (217KB)
References | Supplementary Material | Related Articles | Metrics
GL-RF: a reconciliation framework for label-free entity resolution
Yaoli XU, Zhanhuai LI, Qun CHEN, Fengfeng FAN
Front. Comput. Sci.. 2018, 12 (5): 1035-1037.  https://doi.org/10.1007/s11704-018-7285-8
Abstract   PDF (219KB)
References | Supplementary Material | Related Articles | Metrics
17 articles

LinksMore