Frontiers of Computer Science

Online First
The manuscripts published below will continue to be available from this page until they are assigned to an issue.
Please wait a minute...
For Selected: View Abstracts Toggle Thumbnails
A parallel data generator for efficiently generating “realistic” social streams
Chengcheng YU, Fan XIA, Weining QIAN, Aoying ZHOU
Front. Comput. Sci.
Abstract   PDF (2814KB)

A social stream refers to the data stream that records a series of social entities and the dynamic interactions between two entities. It can be employed to model the changes of entity states in numerous applications. The social streams, the combination of graph and streaming data, pose great challenge to efficient analytical query processing, and are key to better understanding users’ behavior. Considering of privacy and other related issues, a social stream generator is of great significance. A framework of synthetic social stream generator (SSG) is proposed in this paper. The generated social streams using SSG can be tuned to capture several kinds of fundamental social stream properties, including patterns about users’ behavior and graph patterns. Extensive empirical studies with several real-life social stream data sets show that SSG can produce data that better fit to real data. It is also confirmed that SSG can generate social stream data continuously with stable throughput and memory consumption. Furthermore, we propose a parallel implementation of SSG with the help of asynchronized parallel processing model and delayed update strategy. Our experiments verify that the throughput of the parallel implementation can increase linearly by increasing nodes.

Reference | Supplementary Material | Related Articles | Metrics
A survey on fast simulation of elastic objects
Jin HUANG, Jiong CHEN, Weiwei XU, Hujun BAO
Front. Comput. Sci.
Abstract   PDF (872KB)

Elastic simulation plays an important role in computer graphics and has been widely applied to film and game industries. It also has a tight relationship to virtual reality and computational fabrication applications. The balance between accuracy and performance are the most important challenge in the design of an elastic simulation algorithm. This survey will begin with the basic knowledge of elastic simulation, and then investigate two major acceleration techniques for it. From the viewpoint of deformation energy, we introduce typical linearization and reduction ideas for accelerating. We also introduce some recent progress in projective and position-based dynamics, which mainly rely on special numerical methods. Besides, optimal control for elastic objects and typical collision resolving techniques are discussed. Finally, we discuss several possible future works on integrating elastic simulation into virtual reality and 3D printing applications.

Reference | Supplementary Material | Related Articles | Metrics
Joint view synthesis and disparity refinement for stereo matching
Gaochang WU, Yipeng LI, Yuanhao HUANG, Yebin LIU
Front. Comput. Sci.
Abstract   PDF (1405KB)

Typical stereo algorithms treat disparity estimation and view synthesis as two sequential procedures. In this paper, we consider stereo matching and view synthesis as two complementary components, and present a novel iterative refinement model for joint view synthesis and disparity refinement. To achieve the mutual promotion between view synthesis and disparity refinement, we apply two key strategies, disparity maps fusion and disparity-assisted plane sweep-based rendering (DAPSR). On the one hand, the disparity maps fusion strategy is applied to generate disparity map from synthesized view and input views. This strategy is able to detect and counteract disparity errors caused by potential artifacts from synthesized view. On the other hand, the DAPSR is used for view synthesis and updating, and is able to weaken the interpolation errors caused by outliers in the disparity maps. Experiments onMiddlebury benchmarks demonstrate that by introducing the synthesized view, disparity errors due to large occluded region and large baseline are eliminated effectively and the synthesis quality is greatly improved.

Reference | Supplementary Material | Related Articles | Metrics
Dynamic data auditing scheme for big data storage
Xingyue CHEN, Tao SHANG, Feng ZHANG, Jianwei LIU, Zhenyu GUAN
Front. Comput. Sci.
Abstract   PDF (485KB)

When users store data in big data platforms, the integrity of outsourced data is a major concern for data owners due to the lack of direct control over the data. However, the existing remote data auditing schemes for big data platforms are only applicable to static data. In order to verify the integrity of dynamic data in a Hadoop big data platform, we presents a dynamic auditing scheme meeting the special requirement of Hadoop. Concretely, a new data structure, namely Data Block Index Table, is designed to support dynamic data operations on HDFS (Hadoop distributed file system), including appending, inserting, deleting, and modifying. Then combined with the MapReduce framework, a dynamic auditing algorithm is designed to audit the data on HDFS concurrently. Analysis shows that the proposed scheme is secure enough to resist forge attack, replace attack and replay attack on big data platform. It is also efficient in both computation and communication.

Reference | Supplementary Material | Related Articles | Metrics
Analyses for specific defects in android applications: a survey
Tianyong WU, Xi DENG, Jun YAN, Jian ZHANG
Front. Comput. Sci.
Abstract   PDF (424KB)

Android applications (APPS) are in widespread use and have enriched our life. To ensure the quality and security of the apps, many approaches have been proposed in recent years for detecting bugs and defects in the apps, of which program analysis is a major one. This paper mainly makes an investigation of existing works on the analysis of Android apps. We summarize the purposes and proposed techniques of existing approaches, and make a taxonomy of these works, based on which we point out the trends and challenges of research in this field. From our survey, we sum up four main findings: (1) program analysis in Android security field has gained particular attention in the past years, the fields of functionality and performance should also gain proper attention; the infrastructure that supports detection of various defects should be enriched to meet the industry’s need; (2) many kinds of defects result from developers’ misunderstanding or misuse of the characteristics and mechanisms in Android system, thus the works that can systematically collect and formalize Android recommendations are in demand; (3) various program analysis approaches with techniques in other fields are applied in analyzing Android apps; however, they can be improved with more precise techniques to be more applicable; (4) The fragmentation and evolution of Android system blocks the usability of existing tools, which should be taken into consideration when developing new approaches.

Reference | Supplementary Material | Related Articles | Metrics
Privacy-preserving edge-assisted image retrieval and classification in IoT
Xuan LI, Jin LI, Siuming YIU, Chongzhi GAO, Jinbo XIONG
Front. Comput. Sci.
Abstract   PDF (436KB)

Internet of Things (IoT) has drawn much attention in recent years. However, the image data captured by IoT terminal devices are closely related to users’ personal information, which are sensitive and should be protected. Though traditional privacy-preserving outsourced computing solutions such as homomorphic cryptographic primitives can support privacy-preserving computing, they consume a significant amount of computation and storage resources. Thus, it becomes a heavy burden on IoT terminal devices with limited resources. In order to reduce the resource consumption of terminal device, we propose an edge-assisted privacy-preserving outsourced computing framework for image processing, including image retrieval and classification. The edge nodes cooperate with the terminal device to protect data and support privacy-preserving computing on the semitrusted cloud server. Under this framework, edge-assisted privacy-preserving image retrieval and classification schemes are proposed in this paper. The security analysis and performance evaluation show that the proposed schemes greatly reduce the computational, communication and storage burden of IoT terminal device while ensuring image data security.

Reference | Supplementary Material | Related Articles | Metrics
Reducing partition skew on MapReduce: an incremental allocation approach
Zhuo WANG, Qun CHEN, Bo SUO, Wei PAN, ZhanHuai LI
Front. Comput. Sci.
Abstract   PDF (1170KB)

MapReduce, a parallel computational model, has been widely used in processing big data in a distributed cluster. Consisting of alternate map and reduce phases, MapReduce has to shuffle the intermediate data generated by mappers to reducers. The key challenge of ensuring balanced workload on MapReduce is to reduce partition skew among reducers without detailed distribution information on mapped data.

In this paper, we propose an incremental data allocation approach to reduce partition skew among reducers on MapReduce. The proposed approach divides mapped data into many micro-partitions and gradually gathers the statistics on their sizes in the process of mapping. The micropartitions are then incrementally allocated to reducers in multiple rounds. We propose to execute incremental allocation in two steps, micro-partition scheduling and micro-partition allocation. We propose a Markov decision process (MDP) model to optimize the problem of multiple-round micropartition scheduling for allocation commitment. We present an optimal solution with the time complexity of O(K · N2), in which K represents the number of allocation rounds and N represents the number of micro-partitions. Alternatively, we also present a greedy but more efficient algorithm with the time complexity of O(K · N ln N). Then, we propose a minmax programming model to handle the allocation mapping between micro-partitions and reducers, and present an effective heuristic solution due to its NP-completeness. Finally, we have implemented the proposed approach on Hadoop, an open-source MapReduce platform, and empirically evaluated its performance. Our extensive experiments show that compared with the state-of-the-art approaches, the proposed approach achieves considerably better data load balance among reducers as well as overall better parallel performance.

Reference | Supplementary Material | Related Articles | Metrics
First page | Prev page | Next page | Last page Page 1 of 8, 80 articles found