Linear-Time Construction of Two-Dimensional Suffix Trees

The two-dimensional suffix tree of a matrix A is a compacted tree that represents all square submatrices of A. We present the first complete version of a deterministic linear-time algorithm to construct the two-dimensional suffix tree by applying a divide-and-conquer approach.     

Comfort evaluation and bed adjustment according to sleeping positions

This study explodes the relationships between the height adjustment of bed sectors and subjective comfort depending on three types of sleeping positions. An adjustable bed system that regulates the heights of 8 adjustment sectors of the bed was developed. To evaluate the comfort of 9 body areas, subjective ratings were requested from 64 subjects ranging in age from 25 to 50. The subjects included 29 males and 35 females. For an objective evaluation, the patterns of pressure distribution were investigated according to the three sleeping positions. During two separate states (before bed adjustment and after bed adjustment), measurements of the adjusted bed height and pressure distribution, and subjective ratings according to three sleeping positions were performed. Based on the results of the adjusted heights of the 8 sectors in the bed, the subjects preferred the W‐shaped sleeping posture in both the supine and side positions. However, the U‐shaped sleeping posture was preferred in the prone position. With respect to these sleeping positions, the heights of sectors significantly correlated with the subjective ratings presented by the subjects, as well as the ratios of pressure. © 2009 Wiley Periodicals, Inc.     

Security system architecture for data integrity based on a virtual smart meter overlay in a smart grid system

As an efficient and intelligent system for managing and monitoring electricity usage, the “smart grid” has many useful applications. It supports energy producers and energy consumers efficiently by supporting the estimation and provision of the proper amount of electricity at the proper time. The most serious threat to a smart grid system may be when information is altered or forged by attackers; the system could malfunction and could collapse. In some cases, the attackers could waste system resources on purpose and this could lead to disastrous results. In this paper, we propose security system architecture to provide the secure and reliable smart grid service. It includes a data authentication process to verify the aggregated data and virtual network management to detect a compromised area or node. It detects a false data injection attack and further prevents a denial of service attack efficiently with less overhead for the individual devices comprising the smart grid system.     

Microfluidic-based biosensors toward point-of-care detection of nucleic acids and proteins

This article reviews state-of-the-art microfluidic biosensors of nucleic acids and proteins for point-of-care (POC) diagnostics. Microfluidics is capable of analyzing small sample volumes (10⁻⁹–10⁻¹⁸ l) and minimizing costly reagent consumption as well as automating sample preparation and reducing processing time. The merger of microfluidics and advanced biosensor technologies offers new promises for POC diagnostics, including high-throughput analysis, portability and disposability. However, this merger also imposes technological challenges on biosensors, such as high sensitivity and selectivity requirements with sample volumes orders of magnitude smaller than those of conventional practices, false response errors due to non-specific adsorption, and integrability with other necessary modules. There have been many prior review articles on microfluidic-based biosensors, and this review focuses on the recent progress in last 5 years. Herein, we review general technologies of DNA and protein biosensors. Then, recent advances on the coupling of the biosensors to microfluidics are highlighted. Finally, we discuss the key challenges and potential solutions for transforming microfluidic biosensors into POC diagnostic applications.     

A resource allocation policy for delay minimization in fetching capacitated feeds

As social media services such as Twitter and Facebook are gaining popularity, the amount of information published from those services is explosively growing. Most of them use feeds to facilitate distribution of a huge volume of content they publish. In this context, many users subscribe to feeds to acquire up-to-date information through feed aggregation services, and recent real-time search engines also increasingly utilize feeds to promptly find recent web content when it is produced. Accordingly, it is necessary for such services to effectively fetch feeds for minimizing fetching delay, while at the same time maximizing the number of fetched entries. Fetching delay is a time lag between entry publication and retrieval, which is primarily incurred by finiteness of fetching resources. In this paper, we consider a polling-based approach among the methods applicable to fetching feeds, which bases on a specific schedule for visiting feeds. While the existing polling-based approaches have focused on the allocation of fetching resources to feeds in order to either reduce the fetching delay or increase the number of fetched entries, we propose a resource allocation policy that can optimize both objectives. Extensive experiments have been carried out to evaluate the proposed model, in comparison with the existing alternative methods.     

Finding the longest common nonsuperstring in linear time

String inclusion and non-inclusion problems have been vigorously studied in such diverse fields as molecular biology, data compression, and computer security. Among the well-known string inclusion or non-inclusion notions, we are interested in the longest common nonsuperstring. Given a set of strings, the longest common nonsuperstring problem is finding the longest string that is not a superstring of any string in the given set. It is known that the longest common nonsuperstring problem is solvable in polynomial time.In this paper, we propose an efficient algorithm for the longest common nonsuperstring problem. The running time of our algorithm is linear with respect to the sum of the lengths of the strings in the given set, using generalized suffix trees.     

Robust person re-identification via graph convolution networks

Person re-identification (re-id) aims to identity the same person over multiple cameras; it has been successfully applied to various computer vision applications as a fundamental method. Owing to the development of deep learning, person re-id methods, which typically use triplet networks based on triplet loss, have demonstrated great success. However, the appearances of people are similar and hence difficult to distinguish in many cases. Therefore, we present a novel graph convolution network and enhances traditional triplet loss functions. Our method defines reference, positive, and negative features for triplet loss as three vertices of a graph, respectively, and adjusts their mutual distance through learning. The method adopts graph convolutions efficiently, thereby affording low computational costs. Experimental results demonstrate that our method is superior to the baseline on the Market-1501 dataset. The proposed GCN-based triplet loss considerably contributes to improve re-identification methods quantitatively and qualitatively.

     

On-Line Construction of Two-Dimensional Suffix Trees in O(n<Superscript>2</Superscript> log n) Time

The two-dimensional suffix tree of an n × n square matrix A is a compacted trie that represents all square submatrices of A[11]. For the off-line case, i.e., A is given in advance to the algorithm, it is known how to build it in optimal time, for any type of alphabet size [11],[18]. Motivated by applications in Image Compression[22[, Giancarlo and Guaiana [14] considered the on-line version of the two-dimensional suffix tree and presented an O(n² log² n)-time algorithm, which we refer to as GG. That algorithm is a nontrivial generalization of Ukkonen's on-line algorithm for standard suffix trees [23]. The main contribution in this paper is an O(log n) factor improvement in the time complexity of the GG algorithm, making it optimal for unbounded alphabets [9]. Moreover, the ideas presented here also lead to a major simplification of the GG algorithm. Technically, we are able to preserve most of the structure of the original GG algorithm, by reducing a computational bottleneck to a primitive operation, i.e., comparison of Lcharacters, which is here implemented in constant time rather than O(log n) time as in GG. However, preserving that structure comes at a price. Indeed, in order to make everything work, we need a careful reorganization of another fundamental algorithm: Weiner's algorithm for the construction of standard suffix trees [24]. Specifically, here we provide a version of that algorithm which takes linear time and works on-line and concurrently over a set of strings.     

A Projection Method for the Conservative Discretizations of Parabolic Partial Differential Equations

We present a projection method for the conservative discretizations of parabolic partial differential equations. When we solve a system of discrete equations arising from the finite difference discretization of the PDE, we can use iterative algorithms such as conjugate gradient, generalized minimum residual, and multigrid methods. An iterative method is a numerical approach that generates a sequence of improved approximate solutions for a system of equations. We repeat the iterative algorithm until a numerical solution is within a specified tolerance. Therefore, even though the discretization is conservative, the actual numerical solution obtained from an iterative method is not conservative. We propose a simple projection method which projects the non-conservative numerical solution into a conservative one by using the original scheme. Numerical experiments demonstrate the proposed scheme does not degrade the accuracy of the original numerical scheme and it preserves the conservative quantity within rounding errors.     

A modified advancing layers mesh generation for thin three-dimensional objects with variable thickness

A method of generating modified advancing layers mesh is proposed. In this paper the mesh generation process of semi-unstructured prismatic/tetrahedral mesh is presented for relatively thin three-dimensional geometries with variable thickness, as in the case of injection molding analysis. Prismatic meshes are generated by offsetting initial surface triangular meshes. During the mesh generation process, mesh quality is efficiently improved with the use of a new node relocation method. Finally, tetrahedral meshes are automatically generated in the rest of the domain. The mesh generating capability of the proposed algorithm is demonstrated with the several practical test cases.