Face retrieval in news video has been identified as a challenging task due to the huge variations in the visual appearance of the human face. Although several approaches have been proposed to deal with this problem, their extremely high computational cost limits their scalability to large-scale video datasets that may contain millions of faces of hundreds of characters. In this paper, we introduce approaches for face retrieval that are scalable to such datasets while maintaining competitive performances with state-of-the-art approaches. To utilize the variability of face appearances in video, we use a set of face images called face-track to represent the appearance of a character in a video shot. Our first proposal is an approach for extracting face-tracks. We use a point tracker to explore the connections between detected faces belonging to the same character and then group them into one face-track. We present techniques to make the approach robust against common problems caused by flash lights, partial occlusions, and scattered appearances of characters in news videos. In the second proposal, we introduce an efficient approach to match face-tracks for retrieval. Instead of using all the faces in the face-tracks to compute their similarity, our approach obtains a representative face for each face-track. The representative face is computed from faces that are sampled from the original face-track. As a result, we significantly reduce the computational cost of face-track matching while taking into account the variability of faces in face-tracks to achieve high matching accuracy. Experiments are conducted on two face-track datasets extracted from real-world news videos, of such scales that have never been considered in the literature. One dataset contains 1,497 face-tracks of 41 characters extracted from 370 hours of TRECVID videos. The other dataset provides 5,567 face-tracks of 111 characters observed from a television news program (NHK News 7) over 11 years. We make both datasets publically accessible by the research community. The experimental results show that our proposed approaches achieved a remarkable balance between accuracy and efficiency.

Apriori-based mining algorithms enumerate frequent patterns efficiently, but the resulting large number of patterns makes it difficult to directly apply subsequent learning tasks. Recently, efficient iterative methods are proposed for mining discriminative patterns for classification and regression. These methods iteratively execute discriminative pattern mining algorithm and update example weights to emphasize on examples which received large errors in the previous iteration. In this paper, we study a family of loss functions that induces sparsity on example weights. Most of the resulting example weights become zeros, so we can eliminate those examples from discriminative pattern mining, leading to a significant decrease in search space and time. In computational experiments we compare and evaluate various loss functions in terms of the amount of sparsity induced and resulting speed-up obtained.

Scaling up the system size has been the common approach to achieving high performance in parallel computing. However, designing and implementing a large-scale parallel system can be very costly in terms of money and time. When building a target system, it is desirable to initially build a smaller version by using the processing nodes with the same architecture as those in the target system. This allows us to achieve efficient and scalable prediction by using the smaller system to predict the performance of the target system. Such scalability prediction is critical because it enables system designers to evaluate different design alternatives so that a certain performance goal can be successfully achieved. As the de facto standard for writing parallel applications, MPI is widely used in large-scale parallel computing. By categorizing the discrete event simulation methods for MPI programs and analyzing the characteristics of scalability prediction, we propose a novel simulation method, called virtual-actual combined execution-driven (VACED) simulation, to achieve scalable prediction for MPI programs. The basic idea behind is to predict the execution time of an MPI program on a target machine by running it on a smaller system so that we can predict its communication time by virtual simulation and obtain its sequential computation time by actual execution. We introduce a model for the VACED simulation as well as the design and implementation of VACED-SIM, a lightweight simulator based on fine-grained activity and event definitions. We have validated our approach on a sub-system of Tianhe-1A. Our experimental results show that VACED-SIM exhibits higher accuracy and efficiency than MPI-SIM. In particular, for a target system with 1024 cores, the relative errors of VACED-SIM are less than 10% and the slowdowns are close to 1.

The capacity of general mobile ad hoc networks (MANETs) remains largely unknown up to now, which significantly hinders the development and commercialization of such networks. Available throughput capacity studies of MANETs mainly focus on either the order sense capacity scaling laws, the exact throughput capacity under a specific algorithm, or the exact throughput capacity without a careful consideration of critical wireless interference and transmission range issues. In this paper, we explore the exact throughput capacity for a class of MANETs, where we adopt group-based scheduling to schedule simultaneous link transmissions for interference avoidance and allow the transmission range of each node to be adjusted. We first determine a general throughput capacity upper bound for the concerned MANETs, which holds for any feasible packet delivery algorithm in such networks. We then prove that the upper bound we determined is just the exact throughput capacity for this class of MANETs by showing that for any traffic input rate within the throughput capacity upper bound, there exists a corresponding two-hop relay algorithm to stabilize such networks. A closed-form upper bound for packet delay is further derived under any traffic input rate within the throughput capacity. Finally, based on the network capacity result, we examine the impacts of transmission range and node density upon network capacity.

In this paper, an area-efficient decoder architecture is proposed for the quasi-cyclic low-density parity check (QC-LDPC) codes specified in the IEEE 802.16e WiMAX standard. The decoder supports all the code rates and codeword lengths defined in the standard. In order to achieve low area and maximize hardware utilization, the decoder utilizes 4 decoding function units, which is the greatest common divisor of the expansion factors. In addition, the decoder adopts a novel scheduling scheme named stride scheduling, which stores the extrinsic messages in non-sequential order to replace the conventional complex flexible permutation network with simple small-sized cyclic shifters and also minimize the number of memory accesses. To further minimize the complexity, the number of extrinsic memory instances for 24 block columns is reduced to 5 banks by identifying independent sets. All the memory instances used in the decoder are single-port memories which cost less area and price compared to dual-port ones. Finally, the decoding function units have partially parallel structure to make the decoding throughput sufficiently over the requirement of the WiMAX standard. The proposed decoder is synthesized with 49 K equivalent gates and 54,144 bits of memory, and the implementation occupies 0.40 mm2 in a 65 nm CMOS technology.

Although shared caches allow the dynamic allocation of limited cache capacity among cores, traditional LRU replacement policies often cannot prevent negative interference among cores. To address the contention problem in shared caches, cache partitioning and application scheduling techniques have been extensively studied. Partitioning explicitly determines cache capacity for each core to maximize the overall throughput. On the other hand, application scheduling by operating systems groups the least interfering applications for each shared cache, when multiple shared caches exist in systems. Although application scheduling can mitigate the contention problem without any extra hardware support, its effect can be limited for some severe contentions. This paper proposes a low cost solution, based on application scheduling with a simple cache insertion control. Instead of using a full hardware-based cache partitioning mechanism, the proposed technique mostly relies on application scheduling. It selectively uses LRU insertion to the shared caches, which can be added with negligible hardware changes from the current commercial processor designs. For the completeness of cache interference evaluation, this paper examines all possible mixes from a set of applications, instead of using a just few selected mixes. The evaluation shows that the proposed technique can mitigate the cache contention problem effectively, close to the ideal scheduling and partitioning.

Information-centric networking has been touted as an alternative to the current Internet architecture. Our work addresses a crucial part of such a proposal, namely the design of a network node within an information-centric networking architecture. Special attention is given in providing a platform for development and experimentation in an emerging network research area; an area that questions many starting points of the current Internet. In this paper, we describe the service model exposed to applications and provide background on the operation of the platform. For illustration, we present current efforts in deployment and experimentation with demo applications presented, too.

We propose a computing method for linear convolution and linear correlation between sequences using discrete cosine transform (DCT). Zero-padding is considered as well as linear convolution using discrete Fourier transform (DFT). Analyzing the circular convolution between symmetrically extended sequences, we derive the condition for zero-padding before and after the sequences. The proposed method can calculate linear convolution for any filter and also calculate linear correlation without reversing one of the input sequences. The computational complexity of the proposed method is lower than that of linear convolution using DFT.

Discrete structures are foundational material for computer science and mathematics, which are related to set theory, symbolic logic, inductive proof, graph theory, combinatorics, probability theory, etc. Many problems solved by computers can be decomposed into discrete structures using simple primitive algebraic operations. It is very important to represent discrete structures compactly and to execute efficiently tasks such as equivalency/validity checking, analysis of models, and optimization. Recently, BDDs (Binary Decision Diagrams) and ZDDs (Zero-suppressed BDDs) have attracted a great deal of attention, because they efficiently represent and manipulate large-scale combinational logic data, which are the basic discrete structures in various fields of application. Although a quarter of a century has passed since Bryant's first idea, there are still a lot of interesting and exciting research topics related to BDD and ZDD. BDD/ZDD is based on in-memory data processing techniques, and it enjoys the advantage of using random access memory. Recent commodity PCs are equipped with gigabytes of main memory, and we can now solve large-scale problems which used to be impossible due to memory shortage. Thus, especially since 2000, the scope of BDD/ZDD methods has increased. This survey paper describes the history of, and recent research activity pertaining to, techniques related to BDD and ZDD.

Resource discovery is an essential function for distributed mobile applications integrated in vehicular communication systems. Key requirements of the mobile resource discovery are wide-area geographic-based discovery and scalable resource discovery not only inside a vehicular ad-hoc network but also through the Internet. While a number of resource discovery solutions have been proposed, most of them have focused on specific scale of network. Furthermore, managing a large number of mobile resources in the Internet raises a scalability issue due to the mobility of vehicles. In this paper, we design a solution to wide area geographical mobile resource discovery in heterogeneous networks composed of numerous mobile networks possibly connected to the Internet. The proposed system relies on a hierarchical publish-subscribe architecture and geographic routing so that users can locate resources according to geographical coordinates without scalability issue. Furthermore we propose a location management mechanism for mobile resources, which enables to reduce periodic updates of geographical location. Numerical analysis and simulation results show that our system can discover mobile resources without overloading both mobile network and the Internet.

A multiple-valued data transfer scheme using X-net is proposed to realize a compact bit-serial reconfigurable VLSI (BS-RVLSI). In the multiple-valued data transfer scheme using X-net, two binary data can be transferred from two adjacent cells to one common adjacent cell simultaneously at each “X” intersection. One cell composed of a logic block and a switch block is connected to four adjacent cross points by four one-bit switches so that the complexity of the switch block is reduced to 50% in comparison with the cell of a BS-RVLSI using an eight nearest-neighbor mesh network (8-NNM). In the logic block, threshold logic circuits are used to perform threshold operations, and then their binary dual-rail voltage outputs enter a binary logic module which can be programmed to realize an arbitrary two-variable binary function or a bit-serial adder. As a result, the configuration memory count and transistor count of the proposed multiple-valued cell are reduced to 34% and 58%, respectively, in comparison with those of an equivalent CMOS cell. Moreover, its power consumption for an arbitrary 2-variable binary function becomes 67% at 800 MHz under the condition of the same delay time.

This paper proposes a device discovery method for consolidated IP and ZigBee home networks. The method broadcasts an IP multicasted device discovery request of UPnP, m-search, in the ZigBee network as a Constrained Application Protocol (CoAP) message. Upon receiving the m-search broadcast, ZigBee devices respond after a constant time delay with their device description Universal Resource Name (URN). We refer to this device discovery mechanism as transparent msearch. Transparent m-search enables reliable and swift device discovery in home networks which may include constrained networks such as ZigBee. It is revealed by an experiment with 41 ZigBee devices that the delayed response from ZigBee devices is essential to avoid collisions between m-search broadcast and responses from devices and, as a result, to secure the reliability of device discovery. Since the transparent m-search requires the receiving ZigBee devices to respond with their device description URNs, the execution time of device discovery is significantly improved. In our experiment with 41 ZigBee devices, a conventional m-search took 38.1 second to complete device discovery while that of transparent m-search took only 6.3 second.

As wireless LAN systems become more widespread, the number of access points (APs) is increasing. A large number of APs cause overlapping cells where nearby cells utilize the same frequency channel. In the overlapping cells, inter-cell interference (ICI) degrades the throughput. This paper proposes an interference-aware multi-cell beamforming (IMB) technique to reduce the throughput degradation in the overlapping cells. The IMB technique improves transmission performance better than conventional multi-cell beamforming based on a decentralized control scheme. The conventional technique mitigates ICI by nullifying all the interference signal space (ISS) by beamforming, but the signal spaces to the user terminal (UT) is also limited because the degree of freedom (DoF) at the AP is limited. On the other hand, the IMB technique increases the signal space to the UT because the DoF at the AP is increased by selecting the ISS by allowing a small amount of ICI. In addition, we introduce a method of selecting the ISS in a decentralized control scheme. In our work, we analyze the interference channel state information (CSI) and evaluate the transmission performance of the IMB technique by using a measured CSI in an actual indoor environment. As a result, we find that the IMB technique becomes more effective as the number of UT antennas in nearby cells increases.

This paper analyzes the conventional unequal erasure protection (UXP) scheme for scalable video transmission, and proposes a dynamic hybrid UXP/ARQ transmission framework to improve the performance of the conventional UXP method for bandwidth-constrained scalable video transmission. This framework applies automatic retransmission request (ARQ) to the conventional UXP scheme for scalable video transmission, and dynamically adjusts the transmission time budget of each group of picture (GOP) according to the feedback about the transmission results of the current and previous GOPs from the receiver. Moreover, the parameter of target video quality is introduced and optimized to adapt to the channel condition in pursuit of more efficient dynamic time allocation. In addition, considering the play-out deadline constraint, the time schedule for the proposed scalable video transmission system is presented. Simulation results show that compared with the conventional UXP scheme and its enhanced method, the average peak signal to noise ratio (PSNR) of the reconstructed video can be improved significantly over a wide range of packet loss rates. Besides, the visual quality fluctuation among the GOPs can be reduced for the video which has much movement change.

At Eurocrypt'03, Boneh, Gentry, Lynn and Shacham proposed a pairing based verifiably encrypted signature scheme (the BGLS-VES scheme). In 2004, Hess mounted an efficient rogue-key attack on the BGLS-VES scheme in the plain public-key model. In this letter, we show that the BGLS-VES scheme is not secure in the proof of possession (POP) model.

The paper proposes the PMD method to design an introductory programming practice course plan that is inclusive for all learners and stable throughout a course. To achieve the course plan, the method utilizes personas, each of which represents learners having similar motivation to study programming. The learning of the personas is directed to the course goal with an enforcement resulting from the discipline, which is an integration of effective learning strategies with affective components of the persoans. Under the enforcement, services to facilitate and promote the learning of each persona can be decided, based on motivation components of each persona, motivational effects of the services, and the cycle of self-efficacy. The application of the method on about 500 freshmen in C programming practice course has shown this is a successful approach for designing courses.

In this paper, we introduce the concept of a multi-operator mobile relay node (RN) for cellular networks on buses or trains. The installation of RNs improves spectral efficiency because an antenna with a higher gain than that of user equipment (UE) can be installed in an RN. However, installing different RNs for different operators is not efficient because of the large amount of space needed to install multiple RNs in a bus. Thus, sharing one RN among multiple operators is a more practical approach. When we use a multi-operator mobile RN, the required amount of resource for each operator varies independently as the RN moves. Consequently, we propose a system of shared-spectrum allocation among operators for RN-UEs communication. Shared bandwidth can be allocated to operators according to link quality in order to achieve effective utilization of radio resources. However, to introduce shared-spectrum allocation, fairness among the operators and the total efficiency of the system should be taken into consideration. Using computer simulations, we evaluate shared-spectrum allocation based on the Nash bargaining solution (NBS). The results, in terms of both fairness and efficiency, indicate that total throughput can be improved by approximately 20% compared with the situation where multiple operators install different RNs individually.

Wireless sensor nodes are becoming more and more common in various settings and require a long battery life for better maintainability. Since most sensor nodes are powered by batteries, energy efficiency is a critical problem. In an experiment, we observed that when peak power consumption is high, battery voltage drops quickly, and the sensor stops working even though some useful charge remains in the battery. We propose three off-line algorithms that extend battery life by scheduling sensors' execution time that is able to reduce peak power consumption as much as possible under a deadline constraint. We also developed a simulator to evaluate the effectiveness of these algorithms. The simulation results showed that one of the three algorithms dramatically can extend battery life approximately three time as long as in simultaneous sensor activation.

Scalable Video Coding (SVC) is an extension of H.264/AVC, aiming to provide the ability to adapt to heterogeneous networks or requirements. It offers great flexibility for bitstream adaptation in multi-point applications such as videoconferencing. However, transcoding between SVC and AVC is necessary due to the existence of legacy AVC-based systems. The straightforward re-encoding method requires great computational cost, and delay-sensitive applications like videoconferencing require much faster transcoding scheme. This paper proposes an ultra-low-delay SVC-to-AVC MGS (Medium-Grain quality Scalability) transcoder for videoconferencing applications. Transcoding is performed in pure frequency domain with partial decoding/encoding in order to achieve significant speed-up. Three fast transcoding methods in frequency domain are proposed for macroblocks with different coding modes in non-KEY pictures. KEY pictures are transcoded by reusing the base layer motion data, and error propagation is constrained between KEY pictures. Simulation results show that proposed transcoder achieves averagely 38.5 times speed-up compared with the re-encoding method, while introducing merely 0.71 dB BDPSNR coding quality loss for videoconferencing sequences as compared with the re-encoding algorithm.

Scheduling restriction is attracting much attention in LTE-Advanced as a technique to reduce the power consumption and network overheads in interference coordinated heterogeneous networks (HetNets). Such a network with inter-cell interference coordination (ICIC) provides two radio resources with different channel quality statistics. One of the resources is protected (unprotected) from inter-cell interference (hence, called protected (non-protected) resource) and has higher (lower) average channel quality. Without scheduling restriction, the channel quality feedback would be doubled to reflect the quality difference of the two resources. We present a simple scheduling restriction scheme that addresses the problem without significant performance degradation. Users with relatively larger (smaller) average channel quality difference between the two resources are scheduled in the protected (non-protected) resource only, and a boundary user, determined by a proportional fair resource allocation (PFRA) under simplified static channels, is scheduled on one of the two resources or both depending on PFRA. Having most users scheduled in only one of the resources, the power consumption and network overheads that would otherwise be required for the channel quality feedback on the other resource can be avoided. System level simulation of LTE-Advanced downlink shows that the performance degradation due to our scheduling restriction scheme is less than 2%, with the average feedback reduction of 40%.