gbase: an efficient analysis platform for large graphs

Graphs appear in numerous applications including cyber security, the Internet, social networks, protein networks, recommendation systems, citation networks, and many more. Graphs with millions or even billions of nodes and edges are common-place. How to store such large graphs efficiently? What are the core operations/queries on those graph? How to answer the graph queries quickly? We propose Gbase, an efficient analysis platform for large graphs. The key novelties lie in (1) our storage and compression scheme for a parallel, distributed settings and (2) the carefully chosen graph operations and their efficient implementations. We designed and implemented an instance of Gbase using Mapreduce/Hadoop. Gbase provides a parallel indexing mechanism for graph operations that both saves storage space, as well as accelerates query responses. We run numerous experiments on real and synthetic graphs, spanning billions of nodes and edges, and we show that our proposed Gbase is indeed fast, scalable, and nimble, with significant savings in space and time.     

New results on robust output regulation of nonlinear systems with a nonlinear exosystem

The global robust output regulation problem for nonlinear plants subject to nonlinear exosystems has been a challenging problem and has not been well addressed. The main difficulty lies in finding a suitable internal model. The existing internal model for handling the nonlinear exosystem is not zero input globally asymptotically stable, and can only guarantee a local solution for the output regulation problem. In this paper, we first propose a new class of internal models, which is guaranteed to exist under the generalized immersion condition. An advantage of this internal model is that it is zero input globally asymptotically stable. This fact will greatly facilitate the global stabilization of the augmented system associated with the given plant and the internal model. Then we will further utilize this class of internal models to solve the global robust output regulation problem for output feedback systems with a nonlinear exosystem. Copyright © 2011 John Wiley & Sons, Ltd.     

A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines

We study on-line scheduling on parallel batch machines. Jobs arrive over time. A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch and all jobs in a batch start and are completed at the same time. The processing time of a batch is given by the processing time of the longest job in the batch. The objective is to minimize the makespan. We deal with the unbounded model, where B is sufficiently large. We first show that no deterministic on-line algorithm can have a competitive ratio of less than 1+(?{m²+4}-m)/21+(\sqrt{m^{2}+4}-m)/2 , where m is the number of parallel batch machines. We then present an on-line algorithm which is the one best possible for any specific values of m.     

Point-based manifold harmonics

This paper proposes an algorithm to build a set of orthogonal Point-Based Manifold Harmonic Bases (PB-MHB) for spectral analysis over point-sampled manifold surfaces. To ensure that PB-MHB are orthogonal to each other, it is necessary to have symmetrizable discrete Laplace-Beltrami Operator (LBO) over the surfaces. Existing converging discrete LBO for point clouds, as proposed by Belkin et al. [CHECK END OF SENTENCE], is not guaranteed to be symmetrizable. We build a new point-wisely discrete LBO over the point-sampled surface that is guaranteed to be symmetrizable, and prove its convergence. By solving the eigen problem related to the new operator, we define a set of orthogonal bases over the point cloud. Experiments show that the new operator is converging better than other symmetrizable discrete Laplacian operators (such as graph Laplacian) defined on point-sampled surfaces, and can provide orthogonal bases for further spectral geometric analysis and processing tasks.     

Human motion retrieval from hand-drawn sketch

The rapid growth of motion capture data increases the importance of motion retrieval. The majority of the existing motion retrieval approaches are based on a labor-intensive step in which the user browses and selects a desired query motion clip from the large motion clip database. In this work, a novel sketching interface for defining the query is presented. This simple approach allows users to define the required motion by sketching several motion strokes over a drawn character, which requires less effort and extends the users’ expressiveness. To support the real-time interface, a specialized encoding of the motions and the hand-drawn query is required. Here, we introduce a novel hierarchical encoding scheme based on a set of orthonormal spherical harmonic (SH) basis functions, which provides a compact representation, and avoids the CPU/processing intensive stage of temporal alignment used by previous solutions. Experimental results show that the proposed approach can well retrieve the motions, and is capable of retrieve logically and numerically similar motions, which is superior to previous approaches. The user study shows that the proposed system can be a useful tool to input motion query if the users are familiar with it. Finally, an application of generating a 3D animation from a hand-drawn comics strip is demonstrated.     

Interactive curvilinear reformatting in native space

Curvilinear reformatting of 3D magnetic resonance imaging data has been recognized by the medical community as a helpful noninvasive tool for displaying the cerebral anatomy. It consists of automatically creating, with respect to a reference surface, a series of equidistant curvilinear slices at progressively deeper cuts. In comparison with planar slices, it allows more precise localization of lesions and identification of subtle structural abnormalities. However, current curvilinear reformatting tools either rely on the time-consuming manual delineation of guiding curves on 2D slices, or require costly automatic brain segmentation procedures. In addition, they extract the skin and skull, impeding a precise topographic correlation between the location of the brain lesion and skin surface. This impairs planning of craniotomy for neurosurgery, and of the appropriate implantation of electrodes for intracranial electroencephalography in presurgical evaluation. In this work, we present a novel approach based on direct manipulation of the visualized volume data. By using a 3D painting metaphor, the reference surface can be defined incrementally, according to the principle that the user interacts with what she/he sees. As a response, an animation of the reformatting process is displayed. The focus of this paper is a new volume tagging algorithm behind user interactions. It works at an interactive frame rate on current graphics hardware.     

The implementation of technical practices and human factors of the toyota production system in different industries

The Toyota Production System (TPS) can result in huge benefits for companies and has been widely implemented around the world. Nevertheless, most adopters emphasize only the technical practices of the TPS, but neglect the critical role of human factors in the implementation of the TPS. Therefore, this study aims at developing an integrated TPS model that fully integrates the technical elements and human elements of the TPS with Total Quality Management (TQM) practices. An empirical study was conducted to confirm the causal relationships among these constructs. In the empirical study, questionnaires were mailed and e‐mailed to 620 companies that had implemented the TPS, and 151 of the completed questionnaires were valid. These 151 respondents were divided into eight categories. The results revealed that the implementation level of each construct was significantly different in each industry. The automobile and motorcycle industries have put a great deal of effort into the application of Humanity, Human Resource Management (HRM), and TQM practices and obtained good results. Other industries, however, ignored the implementation of HRM practices. The results also revealed that the early adopters enjoyed significant benefits from the implementation of the TPS, which led high‐tech companies to start adopting TPS practices and become lean enterprises. © 2011 Wiley Periodicals, Inc.     

Retraction of “Developing an integrated display of health data for aging in place”

The following article from Human Factors and Ergonomics in Manufacturing & Service Industries, “Developing an Integrated Display of Health Data for Aging in Place,” by Yang Gong and Arpita Chandra, published online on October 20, 2011 in Wiley Online Library ( www.onlinelibrary.wiley.com ), has been retracted by agreement between the authors, the journal Editors‐in‐Chief, Waldemar Karwowski and Gavriel Salvendy, and Publisher Wiley Periodicals, Inc. The retraction has been agreed as these articles were mistakenly published after being rejected.     

Detection of sudden pedestrian crossings for driving assistance systems

In this paper, we study the problem of detecting sudden pedestrian crossings to assist drivers in avoiding accidents. This application has two major requirements: to detect crossing pedestrians as early as possible just as they enter the view of the car-mounted camera and to maintain a false alarm rate as low as possible for practical purposes. Although many current sliding-window-based approaches using various features and classification algorithms have been proposed for image-/video-based pedestrian detection, their performance in terms of accuracy and processing speed falls far short of practical application requirements. To address this problem, we propose a three-level coarse-to-fine video-based framework that detects partially visible pedestrians just as they enter the camera view, with low false alarm rate and high speed. The framework is tested on a new collection of high-resolution videos captured from a moving vehicle and yields a performance better than that of state-of-the-art pedestrian detection while running at a frame rate of 55 fps.