Loading...
ISSN 1000-1239 CN 11-1777/TP

Table of Content

01 November 2015, Volume 52 Issue 11
A Hierarchical Model for Joint Object Detection and Pose Estimation
Chen Yaodong, Li Renfa
2015, 52(11):  2431-2440.  doi:10.7544/issn1000-1239.2015.20140492
Asbtract ( 938 )   HTML ( 1)   PDF (4297KB) ( 905 )  
Related Articles | Metrics
Object detection and pose estimation belong to different tasks in computer vision. Viewed from research methods and practical application, there is great complementarity between these two tasks. This paper presents a mixture of hierarchical tree models that consists of three types of nodes, representing the whole object, discriminative parts and components (i.e. semantic parts) respectively. A key point of the model is that the discriminative parts in the middle level characterize not only object features but also mutual information among components. The proposed model can detect articulated objects and estimate their poses in parallel so as to address the error propagation problem that exists in previous joint models. For training the model, we use a latent structured SVM method where the discriminative nodes are viewed as latent variables. A novel learning method is introduced to initialize and optimize the parameters of the discriminative parts automatically. In experiments we design two evaluation scenarios (i.e. multi-task recognition and single-task recognition) to compare the proposed model and obtain the performance with the state-of-the-art joint methods on PASCAL VOC datasets. The results show that the hierarchical model not only outperforms other joint models in both recognition rate, but also has higher time-effectiveness.
Dynamic Incremental Analysis of Sub-Topic Evolution
Li Fenghuan, Zheng Dequan, Zhao Tiejun
2015, 52(11):  2441-2450.  doi:10.7544/issn1000-1239.2015.20140583
Asbtract ( 809 )   HTML ( 1)   PDF (2192KB) ( 686 )  
Related Articles | Metrics
There has been increasing interest in the follow-up progress of events because of sustainability and mutual influence of events. Meanwhile, more and more emergent events make it necessary to follow events in an intuitive and efficient way. However, the majority of traditional event analysis is sentence-oriented or topic-oriented which is event extraction or topic detection and tracking. A hierarchical structure of the topic event is constructed according to the research objects and the scope. A dynamic incremental model is presented for analyzing sub-topic dynamics in the topic event, which borrows the ideas of single-pass clustering, multi-category and dynamic incremental model. It is document-oriented and built on temporal property of the topic event, including dynamic threshold selection, similarity smoothing and dynamic incremental strategy. Meanwhile, overall evaluation criteria combinied with χ\+2-test is served for performance analysis. The algorithm is effective and facilitates users to follow the topic event explicitly. Experimental results reported for four well-known topic events in China show that the performance of sub-topic evolution analysis is improved significantly.
A Kind of Nonferrous Metal Industry Entity Recognition Model Based on Deep Neural Network Architecture
Mao Cunli, Yu Zhengtao, Shen Tao, Gao Shengxiang, Guo Jianyi, Xian Yantuan
2015, 52(11):  2451-2459.  doi:10.7544/issn1000-1239.2015.20140808
Asbtract ( 990 )   HTML ( 11)   PDF (1547KB) ( 1134 )  
Related Articles | Metrics
Aimed at entity recognition in the field of nonferrous metal, and oriented the complex and strongly nested structure characteristics of domain entity such as product names, organizations, and placenames, it is proposed a kind of nonferrous metal industry entity recognition model based on deep neural network (DNN) architecture. In order to effectively use the characteristics of tight combination between the characters of domain entity and to bypass the Chinese words segmentation in the professional field, the model uses neural networks to automatically learn the word embeddings vector representation of Chinese characteristics as its inputs. The denoising autoencoder (DAE) of text window makes some pre-training on each DNN hidden layer. The pre-training extracts optimal feature vector combination which will be used in nonferrous metal domain entity recognition. Moreover, we detailedly describe the pre-training process that the denoising autoencoder of text window based on neuron language model makes and the construction process of deep network on nonferrous metal entity recognition. Finally, to validate the method’s effectiveness, we make some experiments of entity recognition on several entity types, such as product names, mineral names and place names in nonferrous metal domain. The experimental results show that the proposed model has good effect on the entity recognition of the professional domain.
A Joint Model for Ellipsis Identification and Recovery
Yin Qingyu, Zhang Weinan, Zhang Yu, Liu Ting
2015, 52(11):  2460-2467.  doi:10.7544/issn1000-1239.2015.20140807
Asbtract ( 909 )   HTML ( 0)   PDF (1024KB) ( 787 )  
Related Articles | Metrics
An ellipsis is a gap in a sentence due to the pragmatics conventional use of grammar. Ellipsis is a ubiquitous phenomenon in daily conversation, especially in Chinese. A question-answering (QA) system can hardly automatically understand sentences with ellipsis. As a result, the QA system may produce wrong answer and thus cannot naturally interact with humans. Therefore, it is important to recover these ellipses in order to gain a better QA system. To automatically recover these ellipsis elements, we take the recovery system into two parts: zero anaphora identification and zero anaphora resolution. When connecting these two parts together, previous work always models the two steps separately, which suffers the error accumulation problem. In order to deal with this problem, we propose a joint model method that performs the zero anaphora identification and zero anaphora resolution simultaneously in a unified framework. Besides, we focus on Chinese dialogue text, which is collected from the interview of broadcast. The experimental results show that the proposed joint model method outperforms the state-of-the-art methods significantly.
State Vector Selective Generation of Parallel Folding Counters
Yi Maoxiang, Yu Chenglin, Fang Xiangsheng, Huang Zhengfeng, Ouyang Yiming, Liang Huaguo
2015, 52(11):  2468-2475.  doi:10.7544/issn1000-1239.2015.20140591
Asbtract ( 566 )   HTML ( 1)   PDF (1945KB) ( 565 )  
Related Articles | Metrics
Test pattern generation has a significant impact on the efficiency of built-in self-test (BIST) of integrated circuits. The existing parallel folding counters can only implement sequential state vector folding calculation, resulting in generating a large number of redundant test patterns and hindering its application in BIST test generation. In this paper, a parallel folding counter (PFC) that supports state vector selective generation is proposed, in which an original flip control vector (FCV) is introduced to establish the internal logic relation between the folding distances and FCVs. A given folding distance (FD) is decoded by the bit replacement control logic to control bit replacement for the original FCV with the lowest bit of the folding distance, producing a FCV that is then used to perform XOR operation with the folding seed vector, generating the selected state vector, where the bit replacement control logic can be designed recursively with folding distance increasing. Theoretical analysis and experimental results show that compared with the existing schemes, the proposed folding counter can be used to generate anyone of all the n+1 state vectors corresponding to a given n-bits of seed vector, which reduces BIST deterministic test set generation time significantly, while keeping comparable hardware overhead with the existing parallel folding counters.
Implicit Discourse Relation Inference Based on the External Relation
Hong Yu, Zhu Shanshan, Ding Siyuan, Yao Jianmin, Zhu Qiaoming, Zhou Guodong
2015, 52(11):  2476-2487.  doi:10.7544/issn1000-1239.2015.20140803
Asbtract ( 651 )   HTML ( 0)   PDF (2481KB) ( 499 )  
Related Articles | Metrics
The main task of the discourse relation recognition is to automatically identify the relationships between two text spans. Currently, the performance of the explicit discourse relation can reach 93.09% because of its direct clues, however the performance of the implicit discourse recognition is still far from satisfactory since it has no direct clues. For the resolution of this issue, this paper proposes a novel implicit discourse relation inference approach based on the external relation. The method follows the existing inference pattern that uses the explicit relation to infer the implicit relation. Firstly, it searches the explicit reference arguments that have the similar content with the test arguments in the large scale of external data, then it uses the standard sorting algorithm to rank the explicit reference arguments. Finally, it predicts the implicit discourse relation based on the ranking results. Especially, the method focuses on mining the text fragments which can synergistically trigger the discourse relation between two arguments (called external elements), and predicts the implicit discourse relation of the arguments with reference to the relation between two external elements. Experiments on the Penn discourse treebank (PDTB) show an accuracy of 54.12%, which is a significant improvement of 11.82% over the current state-of-the-art system.
A Study of Query Expansion Based on Social Tagging
Dong Hualei, Wang Jian, Lin Hongfei, Wang Hao
2015, 52(11):  2488-2495.  doi:10.7544/issn1000-1239.2015.20140805
Asbtract ( 762 )   HTML ( 1)   PDF (1285KB) ( 623 )  
Related Articles | Metrics
With the development of Web 2.0, many websites allow users to create and manage their social tags. A lot of searches show that social annotations can be used to improve search quality, but the real tagging system is often sparse, uncategorized, lack of structure and of low quality, therefore traditional SimRank algorithm is so difficult to work. Introducing Jaccard index to SimRank algorithm, we put forward the improvement of social tagging Jaccard SimRank (JSR) similarity calculation method which automatically analyzes the similarity of user-input social annotations and expands them to increase the density. JSR algorithm can make full use of the information of social tagging to achieve effective retrieval and to describe similarity between any two tags intuitively. The experimental datasets come from bibsonomy website, and we have applied Jaccard index, SimRank and JSR algorithms against the test datasets. Experimental results show that the JSR algorithm is more effective in improving search quality than the traditional algorithms.
Orthogonal Crossover Cuckoo Search Algorithm with External Archive
Wang Lijin, Zhong Yiwen, Yin Yilong
2015, 52(11):  2496-2507.  doi:10.7544/issn1000-1239.2015.20148042
Asbtract ( 738 )   HTML ( 0)   PDF (1896KB) ( 727 )  
Related Articles | Metrics
Cuckoo search algorithm is a new population-based optimization technique inspired by the obligate brood parasitic behavior of some cuckoo species. It searches new solutions by iteratively using Lévy flights random walk and Biased random walk, which employs a mutation and crossover operators respectively. In Biased random walk, the crossover operator with random search schema will be a certain blindness or inefficiency, resulting in weakening the search ability of cuckoo search algorithm. Thus, this paper proposes an orthogonal crossover cuckoo search algorithm with external archive (OXCS). By being embedded in Biased random walk, the orthogonal crossover operator, which is an efficient search schema, is employed to enhance the crossover operator schema so as to polish the search ability of cuckoo search algorithm. The proposed algorithm also utilizes an external archive, which maintains the historical information of population within a certain period, to provide one parent-individual for the orthogonal crossover operator in order to improve the diversity. The comprehensive experiments are carried out on 24 benchmark functions in comparison with other algorithms. The results demonstrate the proposed strategies can improve the search ability of cuckoo search algorithm, and enhance the convergence speed and the solution quality of the algorithm for the continuous function optimization problems effectively.
Extracting Social Network from Transaction Logs
Chen Chuang, Xu Bo, Xiao Yanghua, Shi Quan, Wang Wei
2015, 52(11):  2508-2516.  doi:10.7544/issn1000-1239.2015.20148134
Asbtract ( 755 )   HTML ( 0)   PDF (2409KB) ( 587 )  
Related Articles | Metrics
Social network analysis (SNA) is a popular research topic in the field of data mining, and the quality and the scale of networks are extremely important for the research. But most previous studies are conducted on large online social networks or small real social networks. Online social networks are only the approximation of real social networks, and in general they have different properties. Some research conducts on real social networks which are constructed from the survey of quite small population. Social network study expects large real social network data. Transaction logs generated by modern software systems make it possible to construct social networks from large real social data. This paper conducts a case study of extracting student social network (SSN) from school card system transaction logs to explore how to extract social network from transaction logs. Firstly, we build a relation extracting model based on co-occurrence. Then, we define probability coefficient for edge based on the weight of edge and Jaccard coefficient, filtering noisy edges from the network. We conduct our method on real transaction logs data, and the experiments show that our method can generate social networks with high precision. The topology of the network shows that this social network has small-world network features and a scale-free degree distribution.
EMTM: A Method for Experts Mining in Micro-Blog with Topic-Level
Zhang Lamei, Huang Weijing, Chen Wei, Wang Tengjiao, Lei Kai
2015, 52(11):  2517-2526.  doi:10.7544/issn1000-1239.2015.20148133
Asbtract ( 854 )   HTML ( 0)   PDF (1413KB) ( 779 )  
Related Articles | Metrics
So far, micro-blog has been one of the most popular platforms for people to access and share information. After long-term development, there are many experts with authoritative professional background knowledge. Mining experts in topic-level will contribute to the user recommendation and public opinion analysis in micro-blog. In micro-blog, experts in a topic are the users who have high influence on the topic, since they have authoritative professional knowledge and skills about the topic. High influence is a necessary condition for experts. Influence analysis belongs to subjective problems and need to be quantified objectively. In micro-blog, the probability of being retweeted is one of the most important indexes to measure the influence of users. So we can find out the high influencers by analyzing the retweet data. But, there are two kinds of retweet behaviors for the users in micro-blog: “topic-sensitive retweet” and “following retweet”. Therefore, the users who have high influence because of being retweeted with high probability are not always experts. In this paper, we propose a probability generation model EMTM (experts mining topic model) which can find out the experts in topic-level by distinguishing two kinds of the retweet behaviors. We use Gibbs sampling for model inference. Our experiments on real Sina Weibo data show that our model EMTM is effective in mining experts in topic-level.
Study on We Media Account Detection in Microblog
Liu Jinbao, Sheng Dakui, Zhang Ming
2015, 52(11):  2527-2534.  doi:10.7544/issn1000-1239.2015.20140804
Asbtract ( 844 )   HTML ( 0)   PDF (967KB) ( 875 )  
Related Articles | Metrics
As an outcome of Web 2.0 era and a rising social media, microblog service has been playing a more and more important role in people’s daily life. It serves as not only a bridge of communication and information sharing, but also a crucial way to acquire information.As a mixture of social network and information media, microblog has a diverse ecological environment.We media accounts as a component of microblog, have been taking rapid development.In this paper, we creatively introduce the we media account detection problem and illustrate its meaning, then we propose a comprehensive feature set from account profile, posting behavior and posting content.Based on these features, we perform a supervised learning method to detect we media account. Experimental results show that: 1) we media accounts distinct from general accounts in the environment of Sina Weibo, and the difference is mainly on the behavior of publishing microblogs and the topic of microblogs. 2) The proposed three feature sets are effective for we media account detection, and they complement with each other as well, achieving an impressively high accuracy of 96.71%.
Methods for Team Formation Problem with Grouping Task in Social Networks
Sun Huanliang, Jin Mingyu, Liu Junling, Yu Ge
2015, 52(11):  2535-2544.  doi:10.7544/issn1000-1239.2015.20148136
Asbtract ( 674 )   HTML ( 0)   PDF (2000KB) ( 634 )  
Related Articles | Metrics
Team formation problem in social network is gaining prominence in the research field of social network analysis and data mining. Previous study about team formation aimed at finding a team with the lowest communication cost. Some practical applications, such as large-scale software development and large-scale scientific research teams, usually need to divide a task. Based on this requirement, this paper presents a problem named grouping supported team formation in social network, which finds a team of experts to satisfy a complex grouping task and minimize the communication cost. The input of this problem is not a set of keywords of the traditional team formation problem, but a grouping task graph. Meanwhile, we also prove that this problem is NP-hard. Based on team communication models in organizational behavior, we define communication cost criterions for measuring grouping task teams, and propose multiple corresponding greedy searching strategies. The experimental results on real datasets demonstrate that different search strategies are suitable for different communication cost criterions and prove the effectiveness of the proposed algorithm.
Accelerated Multi-Task Online Learning Algorithm for Big Data Stream
Li Zhijie, Li Yuanxiang, Wang Feng, Kuang Li
2015, 52(11):  2545-2554.  doi:10.7544/issn1000-1239.2015.20148280
Asbtract ( 920 )   HTML ( 2)   PDF (1650KB) ( 959 )  
Related Articles | Metrics
Conventional machine learning and data mining techniques with batch computing mode suffer from many limitations when being applied to big data stream analytics tasks. Multi-task online learning framework with stream computing mode is a promising tool for big data stream analysis. However, current multi-task online learning algorithm has low convergence rate, such as O(1/〖KF(〗T〖KF)〗) up to the T-th iteration, and its low convergence rate has become a bottleneck of online algorithm performance. In this paper, we propose a novel multi-task accelerated online learning algorithm, called ADA-MTL(accelerated dual averaging method for multi-task learning), which simultaneously obtains low computational time complexity and optimal convergence rate O(1/T\+2). The proof of a closed-form solution theorem which efficiently updates the weight matrix W\-t at each iteration is provided, and detailed theoretical analysis for the algorithm convergence rate is conducted. The experimental results on real-world datasets demonstrate the merits of the proposed multi-task accelerated online learning algorithm for large-scale dynamic data stream problems. Since this multi-task accelerated online learning algorithm can obviously improve the real-time performance and the scalability for big data stream analysis, it is a realistic method for big data stream analytics tasks.
Parallel TNN Spectral Clustering Algorithm in CPU-GPU Heterogeneous Computing Environment
Zhang Shuai, Li Tao, Jiao Xiaofan, Wang Yifeng, Yang Yulu
2015, 52(11):  2555-2567.  doi:10.7544/issn1000-1239.2015.20148151
Asbtract ( 1060 )   HTML ( 0)   PDF (2494KB) ( 718 )  
Related Articles | Metrics
Spectral clustering is one of the most popular clustering algorithms in the data mining field. However, this algorithm suffers from the storage and computational bottlenecks heavily when dealing with large-scale datasets. Current work focuses on improving the spectral clustering on both algorithm and implementation levels. But how to design an efficient spectral clustering algorithm, which can handle million scale datasets on a single node with multicore CPU and manycore accelerators, is still an unsolved problem. A parallel spectral clustering using T-nearest-neighbors (TNN) and its implementation for CPU-GPU heterogeneous computing environment, named parallel spectral clustering for hybrids (PSCH), is proposed in this paper. It breaks the GPU device memory limitation by partitioning the TNN similarity matrix into blocks, so the dataset scale only subjects to the size of the host memory. In PSCH, the 4-stage pipeline mechanism with dual rotating buffers is designed to compute the TNN similarity matrix using CUDA, which keeps all the CPU, GPU, and PCIe bus busy to achieve high performance gains while breaking the device memory limitation. The implicitly restarted Lanczos method (IRIM) on GPU is employed for the eigen-decomposition of the sparse TNN similarity matrix, alleviating the computational bottleneck of the eigensolver. The results show that PSCH is highly-efficient at exploring the GPU memory bandwidth and hybrid CPU-GPU computation power. PSCH is able to cluster million scale datasets on a single node equipped with one GTX 480 GPU and achieve 2.0~4.5 times performance gains compared with the MPI parallel spectral clustering implementation PSC using 16 processes for 4 datasets.
Network Declustering BWRAID: Faster Scalability, Recovery and IO Performance
Sun Zhenyuan, Xu Lu, Liu Zhenjun, Dong Huanqing, Liu Chang
2015, 52(11):  2568-2576.  doi:10.7544/issn1000-1239.2015.20148038
Asbtract ( 850 )   HTML ( 1)   PDF (2579KB) ( 465 )  
Related Articles | Metrics
Storage area network (SAN) is important for network storage. We construct BWRAID, a distributed RAID in a SAN, from commodity hardware. The original version BWRAID has a symmetric architecture. However, it has three problems: Firstly, it reads data to re-calculate parity when it expands, and the re-calculation consumes much IO and time. Secondly, it recovers data to one storage node (SN), and recovery can be more efficient if parallel on multi nodes. Thirdly, its data layout is bad for IO, that makes its internal RAID4 have many costly read-modify-write updates even on sequential writes. To solve these problems, we propose a network declustering BWRAID. It has an asymmetric architecture like a declustering RAID, but it is declustered by equal size virtual disks instead of blocks. It is expanded by moving virtual disks without calculation. It runs multi recovery in parallel as the number of nodes involved in each recovery is less than the total number of nodes in the system. To optimize IO, we change its data layout to express user IO space by internal RAID4 stripes. We also provide algorithms to search suitable virtual disks for system allocation, expansion, or recovery. Experiments show that network declustering BWRAID is better than the original one. It expands the system without calculating parity five to eight times faster, and its parallel recovery is multi times faster, and it increases the IO performance with the new data layout.
Decoupling Contention with VRB Mechanism for Multi-Threaded Applications
Gao Ke, Fan Dongrui, Liu Zhiyong
2015, 52(11):  2577-2588.  doi:10.7544/issn1000-1239.2015.20148178
Asbtract ( 676 )   HTML ( 0)   PDF (2706KB) ( 515 )  
Related Articles | Metrics
Currently, the processors improve system performance by increasing the number of cores and simultaneously running threads. However, increasing the number of processor cores and threads which share the memory system will decrease the memory row-buffer hit rate (RBHR), causing more memory power consumption and longer memory access latencies. We design and develop a fine-grained victim row-buffer (VRB) memory system to solve this problem. VRB mechanism provides an additional row-buffer (VRB) which temporarily stores the expelled data due to the row-buffer (RB) conflict for a possible access in the near future. This mechanism mitigates the multi-threaded interference phenomenon and increases the reuse ratio of row-buffer data in DRAM and avoids unnecessary accesses of the array of cells, thus some row activations, precharge operations and data transmission activities can be reduced. VRB can improve system performance and power consumption while incurring minor hardware complexity. Through full-system cycle-accurate simulations of many threads applications, we demonstrate that VRB mechanism achieves an up to 17.6% (8.7% on average) system-level throughput improvement, an up to 142.9% (51.4% on average) RBHR improvement, and saves an up to 17.6% (9.2% on average) power consumption compared with an 8-core Intel Xeon server.
Power-Constrained SoC Test Scheduling Optimization Using Asynchronous Clock Periods
Ling Li,Jiang Jianhui
2015, 52(11):  2589-2598.  doi:10.7544/issn1000-1239.2015.20148145
Asbtract ( 644 )   HTML ( 0)   PDF (1794KB) ( 474 )  
Related Articles | Metrics
Test cost of very large scale integration (VLSI) circuits is highly related to the test application time (TAT). Test scheduling is an effective technique to reduce the TAT of testing a SoC, which has been studied for decades. However, increasing power issues and consequences have made power-aware test necessary and important. Power-constrained test scheduling is one of the promising methods. Recently asynchronous clock test which can vary the clock period of each test cycle has been developed and shown great potential in TAT reduction for single circuit. However, applying such features to SoC test scheduling is not straight forward. Using conventional test scheduling model may lead to inferior results and longer scheduling time. After analyzing the characteristics of asynchronous clock test and power-constrained test scheduling problems, we propose a method to exploit asynchronous clock to SoC test scheduling based on clique. The resource constraint among each tests is represented by test-compatibility-graph (TCG); the scheduling problem is formed using mixed-integer linear programming (MILP) model; and the problem is solved by state-of-the-art mathematical programming solver. The results of both theoretical analysis and simulation experiment on the ITC02 benchmarks show that combining test scheduling technique with asynchronous clock can reduce TAT effectively and the proposed method can optimize the scheduling problem even further.
A Memory Partition Policy for Mitigating Contention
Jia Gangyong, Li Xi, Wan Jian, Wang Chao, Dai Dong
2015, 52(11):  2599-2607.  doi:10.7544/issn1000-1239.2015.20140706
Asbtract ( 697 )   HTML ( 0)   PDF (2818KB) ( 536 )  
Related Articles | Metrics
In modern multi-core system, memory is shared among more and more concurrently running threads. Therefore, memory contention and interference are more and more serious, which induces performance degradation differently, unfairness resource sharing and priority inversion even starvation. In this paper, we firstly analyze the problems induced by contention and interference in detail, and propose a pseudoshare framework which brings shared memory to be exclusive likely in multi-core system. The pseudoshare framework contains three main components: 1) Partition threads, cores and memory into thread, core and memory groups respectively, and one thread group runs on one core group occupying unique one memory group, and one core group is only scheduled for its corresponding thread group accessing its unique memory group. Through this way, memory access among core groups is isolated; 2) Analyze the behavior characteristics of threads, especially the threads performance influence after memory is shared for each thread; 3) According to the performance influence of parallel running threads, allocate memory bandwidth for each thread. We implement pseudoshare in both 4-core and 8-core platforms. Experimental results show pseudoshare optimizes both the problems of performance degradation differently and unfairness resource sharing in both 4-core and 8-core, 9.8% and 22.5% on average for interference and fairness respectively. Moreover, pseudoshare solves starvation and reduces 5.3% power on average.
Multiple DAGs Dynamic Scheduling for Mixed-Criticality Systems with Communication Contention
Liu Liangjiao, Xie Guoqi, Li Renfa, Yang Liu, Xie Yong
2015, 52(11):  2608-2621.  doi:10.7544/issn1000-1239.2015.20140776
Asbtract ( 678 )   HTML ( 0)   PDF (2763KB) ( 667 )  
Related Articles | Metrics
The scheduling of mixed-criticality systems with communication contention based on multiple DAGs model is the requirement of automobile electronic systems with heterogeneity and distribution. Firstly, the more accurate “upward rank value” and “earliest finish time” with communication contention on time are implemented to adapt to the heterogeneity of both computing and networking, and the synchronization of task and message in this paper. Then, an algorithm called fairness on multiple DAGs dynamic task and message scheduling (F_MDDTMS) is proposed to reduce scheduling length. An algorithm called criticality on multiple DAGs dynamic task and message scheduling (C_MDDTMS) is proposed to ensure the real-time of higher criticality applications. An algorithm called mixed criticality on multiple DAGs dynamic task and message scheduling (MC_MDDTMS) is also proposed based on the joint of F_MDDTMS algorithm and C_MDDTMS algorithm to ensure hard real-time of higher criticality applications and the activity of lower criticality applications of mixed-criticality systems. Example analysis and experimental results show that the proposed algorithms are excellent on scheduling length, unfairness, worst-case response time (WCRT) and real-time.
A New Lower Bound for the Distance of Sorting Permutations by Short Block Moves
Wang Tong, Jiang Haitao, Zhu Daming
2015, 52(11):  2622-2627.  doi:10.7544/issn1000-1239.2015.20148259
Asbtract ( 686 )   HTML ( 0)   PDF (872KB) ( 513 )  
Related Articles | Metrics
Over the past twenty years, computational biology has been trying tracing the rule of evolution by genome rearrangement events, therefore the rearrangement problem of genomic permutations has been researched widely and deeply. The operations of genome rearrangement include reversals, translocations, transpositions and so on. Bulteau et al proved that the problem of sorting permutations by transpositions was NP-complete. A transposition is also called a block-move. The short block-move is the most common case of block-moves. A short block-move is a block-move whose segments are moved from its original position at most two positions,so its another name is 3-bounded transposition. For the problem of the distance of sorting permutations by short block moves, we present an implicit lower bound. In this paper, we use a special permutation called “double increasing permutation” and gain a new lower bound through analyzing the double increasing permutation. On this basis, we analyse all the maximal double increasing sub-permutations of the original permutations, and then simply sum the lower bounds to obtain a new lower bound for the distance of sorting permutations by short block moves, which improves Health and Vergaras result greatly, so that we will lay a foundation of the design of a better approximate algorithm.
Location Privacy-Preserving Method for LBS Continuous KNN Query in Road Networks
Zhou Changli, Ma Chunguang, Yang Songtao
2015, 52(11):  2628-2644.  doi:10.7544/issn1000-1239.2015.20140532
Asbtract ( 979 )   HTML ( 0)   PDF (3857KB) ( 763 )  
Related Articles | Metrics
Location privacy preservation and query service quality are a pair of contradiction in location based service (LBS). In the road network, there are a lot of limiting factors to be considered for continuous query. How to protect location privacy efficiently and acquire accurate continuous query results of places of interest (POIs) are great challenges in the road network. In this paper, based on the idea of using fake location, a query algorithm is proposed firstly, which picks the intersections of the road network gradually to form an anchor sequence to query POIs, and the query algorithm can not only achieve location privacy preservation but also deduce accurate K nearest neighbor (KNN) query results. And then, based on the idea of sending fake queries and constructing query anonymity group, a trajectory privacy preservation algorithm is proposed, which is used to resist continuous query correlation attack and movement model inference attack. At last, a discussion about the trade-off between privacy preservation and query service quality is given in the road networking LBS. The performance analysis and experiments show that our methods provide strong location privacy preservation and get accurate query results in the road network, and our algorithms have favorable timeliness and well-balanced data communication overhead.
An Enhanced Biometrics-Key-Based Remote User Authentication Scheme with Smart Card
Xu Qingui, Huang Peican, Yang Taolan
2015, 52(11):  2645-2655.  doi:10.7544/issn1000-1239.2015.20140755
Asbtract ( 784 )   HTML ( 0)   PDF (1269KB) ( 575 )  
Related Articles | Metrics
Biometrics-based remote user authentication scheme with smart card enforces triple protection including smartcard hardware, user password authentication and biometrics recognition, which brings new breakthrough to authentication. Khan-Kumari scheme, which is characterized with high security performance, is reviewed. Four defects that may do harm to authentication are found in this scheme: flawed encapsulation of user identity secrets, improper access way of them, lack of message freshness check, and insufficient interaction between authentication parties. An enhanced biometrics-key-based remote user authentication scheme with smart card is put forward in this paper. Our scheme enforces four enhancing procedures: mutal verifiable dual factors are used to protect user identity secrets, and playback messages are recognized based on message freshness check, and protected parameters are transmitted after encrypted with dynamic Hash key integrating time flag, and authentication process is made be completed gracefully with acknowledgement message. With these measures, user identity protection is enhanced remarkably. Hence, resistance against smart card cracking, message replay, identity impersonation and service refusal is aggrandized. Security analysis shows that the enhanced scheme effectually fixes vulnerabilities found in Khan-Kumari scheme with small computation and communication cost, achieving remarkably enhanced security performance in defending against varying attacking means. Under the circumstances that even dual protection measures are compromised, the probability of impersonation and authentication failure caused by attacks can be made be less than 10\+{-38}.