Cloud computing has become the mainstream computing paradigm nowadays. More and more data owners (DO) choose to outsource their data to a cloud service provider (CSP), who is responsible for data management and query processing on behalf of DO, so as to cut down operational costs for the DO.  However, in real-world applications, CSP may be untrusted, hence it is necessary to authenticate the query result returned from the CSP.  In this paper, we consider the problem of approximate string query result authentication in the context of database outsourcing. Based on Merkle Hash Tree (MHT) and Trie, we propose an authenticated tree structure named MTrie for authenticating approximate string query results. We design efficient algorithms for query processing and query result authentication. To verify effectiveness of our method, we have conducted extensive experiments on real datasets and the results show that our proposed method can effectively authenticate approximate string query results.

The continuous development of the mobile computing environment has led to the emergence of fintech to enable convenient financial transactions in this environment. Previously proposed financial identity services mostly adopted centralized servers that are prone to single-point-of-failure problems and performance bottlenecks. Blockchain-based self-sovereign identity (SSI), which emerged to address this problem, is a technology that solves centralized problems and allows decentralized identification. However, the verifiable credential (VC), a unit of SSI data transactions, guarantees unlimited right to erasure for self-sovereignty. This does not suit the specificity of the financial transaction network, which requires the restriction of the right to erasure for credit evaluation. This paper proposes a model for VC generation and revocation verification for credit scoring data. The proposed model includes double zero knowledge - succinct non-interactive argument of knowledge (zk-SNARK) proof in the VC generation process between the holder and the issuer. In addition, cross-revocation verification takes place between the holder and the verifier. As a result, the proposed model builds a trust platform among the holder, issuer, and verifier while maintaining the decentralized SSI attributes and focusing on the VC life cycle. The model also improves the way in which credit evaluation data are processed as VCs by granting opt-in and the special right to erasure.

We propose a video authentication scheme to verify whether a given video file is recorded by a camera device or touched by a video editing tool. The proposed scheme prepares software characteristics of camera devices and video editing tools in advance, and compares them with the metadata of the given video file. Through practical implementation, we show that the proposed scheme has benefits of fast analysis time, high accuracy and full automation.

Massive open online course (MOOC) is an online course aimed at unlimited participation and open access via the web. Although there are many MOOC providers, they typically focus on the online course providing and typically do not link with traditional education and business sector requirements. This paper presents a MOOC service framework that focuses on adopting MOOC to provide additional services to support students in traditional education and to provide credit bank consisting of student academic credentials for business sector demand. Particularly, it extends typical MOOC to support academic/ credential record and transcript issuance. The MOOC service framework consists of five layers: authentication, resources, learning, assessment and credential layers. We discuss the adoption of the framework in Thai MOOC, the national MOOC system for Thai universities. Several main issues related to the framework adoption are discussed, including the service strategy and model as well as infrastructure design for large-scale MOOC service.

The closeness of a match is an important measure with a number of practical applications, including computational biology, signal processing and text retrieval. The approximate string matching (ASM) problem asks to find a substring of string Y of length n that is most similar to string X of length m. It is well-know that the ASM can be solved by dynamic programming technique by computing a table of size m×n. The main contribution of this work is to present a memory-access-efficient implementation for computing the ASM on a GPU. The proposed GPU implementation relies on warp shuffle instructions which are used to accelerate the communication between threads without resorting to shared memory access. Despite the fact that O(mn) memory access operations are necessary to access all elements of a table with size n×m, the proposed implementation performs only $O(rac{mn}{w})$ memory access operations, where w is the warp size. Experimental results carried out on a GeForce GTX 980 GPU show that the proposed implementation, called w-SCAN, provides speed-up of over two fold in computing the ASM as compared to another prominent alternative.

There have been many previous studies to facilitate the use of smartphones as remote controllers of PCs. Image-based user interfaces have been suggested to provide fully functioning remote applications. However, most previous image-based interfaces consume high battery power and network bandwidth. Also most users have specific preferences on various applications on remote PCs, but previous smartphone interface systems would not allow users to define their own smartphone interfaces to set their preferences. This paper presents a new smartphone user interface system, SmartUI, for remote PC control. SmartUI is designed as a text-oriented web-based interface, so that it can be used on any smartphone with a built-in web browser while saving battery power and network bandwidth. Moreover, SmartUI enables a user to create buttons on a smartphone; for a quick launch and for shortcut keys, associated with a specific remote PC application. As a result, SmartUI allows a user to create his or her own smartphone interface for remote PC control, while saving battery power and network bandwidth. SmartUI has been tested with various smartphones and the results are also presented in this paper.

The Hierarchical Memory Machine (HMM) is a theoretical parallel computing model that captures the essence of computing on CUDA-enabled GPUs. The approximate string matching (ASM) for two strings X and Y of length m and n is a task to find a substring of Y most similar to X. The main contribution of this paper is to show an optimal parallel algorithm for the approximate string matching on the HMM and implement it on GeForce GTX 580 GPU. Our algorithm runs in $O({nover w}+{mnover dw}+{nLover p}+{mnlover p})$ time units on the HMM with p threads, d streaming processors, memory band width w, global memory access latency L, and shared memory access latency l. We also show that the lower bound of the computing time is $Omega({nover w}+{mnover dw}+{nLover p}+{mnlover p})$ time units. Thus, our algorithm for the approximate string matching is time optimal. Further, we implemented our algorithm on GeForce GTX 580 GPU and evaluated the performance. The experimental results show that the ASM of two strings of 1024 and 4M (=222) characters can be done in 419.6ms, while the sequential algorithm can compute it in 27720ms. Thus, our implementation on the GPU attains a speedup factor of 66.1 over the single CPU implementation.

This paper shows a way to derive positive definite kernels from edit distances. It is well-known that, if a distance d is negative definite, e-λd is positive definite for any λ > 0. This property provides us the opportunity to apply useful techniques of kernel multivariate analysis to the features of data captured by means of the distance. However, the known instances of edit distance are not always negative definite. Even worse, it is usually not easy to examine whether a given instance of edit distance is negative definite. This paper introduces alignment kernels to present an alternative means to derive kernels from edit distance. The most important advantage of the alignment kernel consists in its easy-to-check sufficient condition for the positive definiteness. In fact, when we surveyed edit distances for strings, trees and graphs, all but one are instantly verified to meet the condition and therefore proven to be positive definite.

In P2P applications, networks are formed by devices belonging to independent users. Therefore, routing hotspots or routing congestions are typically created by an unanticipated new event that triggers an unanticipated surge of users to request streaming service from some particular nodes; and a challenging problem is how to provide incentive mechanisms to allocation bandwidth more fairly in order to avoid congestion and other short backs for P2P QoS. In this paper, we study P2P bandwidth game — the bandwidth allocation in P2P networks. Unlike previous works which focus either on routing or on forwarding, this paper investigates the game theoretic mechanism to incentivize node's real bandwidth demands and propose novel method that avoid congestion proactively, that is, prior to a congestion event. More specifically, we define an incentive-compatible pricing vector explicitly and give theoretical proofs to demonstrate that our mechanism can provide incentives for nodes to tell the true bandwidth demand. In order to apply this mechanism to the P2P distribution applications, we evaluate our mechanism by NS-2 simulations. The simulation results show that the incentive pricing mechanism can distribute the bandwidth fairly and effectively and can also avoid the routing hotspot and congestion effectively.

This letter presents a method of adding a virtual halo effect to an object of interest in video sequences. A modified graph-cut segmentation algorithm extracts object layers. The halo is modeled by the accumulation of gradually changing Gaussians. With a synthesized blooming effect, the experimental results show that the proposed method conveys realistic halo effect.

A scalable pattern discovery by compression is proposed. A string is representable by a context-free grammar deriving the string deterministically. In this framework of grammar-based compression, the aim of the algorithm is to output as small a grammar as possible. Beyond that, the optimization problem is approximately solvable. In such approximation algorithms, the compressor based on edit-sensitive parsing (ESP) is especially suitable for detecting maximal common substrings as well as long frequent substrings. Based on ESP, we design a linear time algorithm to find all frequent patterns in a string approximately and prove several lower bounds to guarantee the length of extracted patterns. We also examine the performance of our algorithm by experiments in biological sequences and other compressible real world texts. Compared to other practical algorithms, our algorithm is faster and more scalable with large and repetitive strings.

This paper proposes Direct Spectrum Division Transmission with spectrum editing technique. The transmitter divides the single carrier modulated signal into multiple “sub-spectra” in the frequency domain and arranges each sub-spectrum so as to more fully utilize the unused frequency resources. In the receiver, the divided sub-spectra are combined in the frequency domain and demodulated. By editing the divided spectrum in the frequency domain, the total bandwidth occupied by the multiple “sub-spectra” is less than that of the modulated signal. The proposed technique allows the unused frequency resources scattered across the bands to be better utilized. Simulations show that the proposed technique makes the bit error rate negligible.

Recently, the need for multimedia devices, such as mobile phones, digital TV, PMP, digital camcorders, digital cameras has increased. These devices provide various services for multimedia file manipulation, allowing multimedia contents playback, multimedia file editing, etc. Additionally, digital TV provides a recorded multimedia file copy to a portable USB disk. However, Linux Ext3 file system, as employed by these devices, has a lot of drawbacks, as it required a considerable amount of time and disk I/Os to store large-size edited multimedia files, and it is hard to access for typical PC users. Therefore, in this paper a design and implementation of an amortized Ext3 with FWAE (Fast Writing-After-Editing) for WinXP-based multimedia applications is described. The FWAE is a fast and efficient multimedia file editing/storing technique for the Ext3 that exploits inode block pointer re-setting and shared data blocks by simply modifying metadata information. Individual experiments in this research show that the amortized Ext3 with FWAE for WinXP not only dramatically improves written performance of the Ext3 by 16 times on average with various types of edited multimedia files but also notably reduces the amount of consumed disk space through data block sharing. Also, it provides ease and comfort to use for typical PC users unfamiliar with Linux OS.

We propose a new stereo image retargeting method based on the framework of shift-map image editing. Retargeting is the process of changing the image size according to the target display while preserving as much of the richness of the image as possible, and is often applied to monocular images and videos. Retargeting stereo images poses a new challenge because pixel correspondences between the stereo pair should be preserved to keep the scene's structure. The main contribution of this paper is integrating a stereo correspondence constraint into the retargeting process. Among several retargeting methods, we adopt shift-map image editing because this framework can be extended naturally to stereo images, as we show in this paper. We confirmed the effectiveness of our method through experiments.

This paper presents a novel algorithm for Nearest Neighbor (NN) classifier. NN classification is a well-known method of pattern classification having the following properties: * it performs maximum-margin classification and achieves less than twice the ideal Bayesian error, * it does not require knowledge of pattern distributions, kernel functions or base classifiers, and * it can naturally be applied to multiclass classification problems. Among the drawbacks are A) inefficient memory use and B) ineffective pattern classification speed. This paper deals with the problems A and B. In most cases, NN search algorithms, such as k-d tree, are employed as a pattern search engine of the NN classifier. However, NN classification does not always require the NN search. Based on this idea, we propose a novel algorithm named k-d decision tree (KDDT). Since KDDT uses Voronoi-condensed prototypes, it consumes less memory than naive NN classifiers. We have confirmed that KDDT is much faster than NN search-based classifier through a comparative experiment (from 9 to 369 times faster than NN search based classifier). Furthermore, in order to extend applicability of the KDDT algorithm to high-dimensional NN classification, we modified it by incorporating Gabriel editing or RNG editing instead of Voronoi condensing. Through experiments using simulated and real data, we have confirmed the modified KDDT algorithms are superior to the original one.

Tree structured data often appear in bioinformatics. For example, glycans, RNA secondary structures and phylogenetic trees usually have tree structures. Comparison of trees is one of fundamental tasks in analysis of these data. Various distance measures have been proposed and utilized for comparison of trees, among which extensive studies have been done on tree edit distance. In this paper, we review key results and our recent results on the tree edit distance problem and related problems. In particular, we review polynomial time exact algorithms and more efficient approximation algorithms for the edit distance problem for ordered trees, and approximation algorithms for the largest common sub-tree problem for unordered trees. We also review applications of tree edit distance and its variants to bioinformatics with focusing on comparison of glycan structures.

Credit-based router-to-router flow control is one main link-level flow control mechanism proposed for Networks on Chip (NoCs). Based on network calculus, we analyze its performance and optimal buffer size. To model the feedback control behavior due to credits, we introduce a virtual network service element called flow controller. Then we derive its service curve, and further the system service curve. In addition, we give and prove a theorem that determines the optimal buffer size guaranteeing the maximum system service curve. Moreover, assuming the latency-rate server model for routers, we give closed-form formulas to calculate the flit delay bound and optimal buffer size. Our experiments with real on-chip traffic traces validate that our analysis is correct; delay bounds are tight and the optimal buffer size is exact.

Moving object completion is a process of completing moving object's missing information based on local structures. Over the past few years, a number of computable algorithms of video completion have been developed, however most of these algorithms are based on the pixel domain. Little theoretical and computational work in video completion is based on the compressed domain. In this paper, a moving object completion method on the compressed domain is proposed. It is composed of three steps: motion field transferring, thin plate spline interpolation and combination. Missing space-time blocks will be completed by placing new motion vectors on them so that the resulting video sequence will have as much global visual coherence with the video portions outside the hole. The experimental results are presented to demonstrate the efficiency and accuracy of the proposed algorithm.

In software design and development, program diagrams are often used for good visualization. Many kinds of program diagrams have been proposed and used. To process such diagrams automatically and efficiently, the program diagram structure needs to be formalized. We aim to construct a diagram processing system with an efficient parser for our program diagram Hichart. In this paper, we give a precedence graph grammar for Hichart that can parse in linear time. We also describe a parsing method and processing system incorporating the Hichart graphical editor that is based on the precedence graph grammar.

Based on the clonal selection principle proposed by Burnet, in the immune response process there is no crossover of genetic material between members of the repertoire, i.e., there is no knowledge communication during different elite pools in the previous clonal selection models. As a result, the search performance of these models is ineffective. To solve this problem, inspired by the concept of the idiotypic network theory, an expanded lateral interactive clonal selection algorithm (LICS) is put forward. In LICS, an antibody is matured not only through the somatic hypermutation and the receptor editing from the B cell, but also through the stimuli from other antibodies. The stimuli is realized by memorizing some common gene segment on the idiotypes, based on which a lateral interactive receptor editing operator is also introduced. Then, LICS is applied to several benchmark instances of the traveling salesman problem. Simulation results show the efficiency and robustness of LICS when compared to other traditional algorithms.