Feb 2013, Volume 7 Issue 1
    

  • Select all
  • RESEARCH ARTICLE
    Botao WANG, Jingwei QU, Xiaosong WANG, Guoren WANG, Masaru KITSUREGAWA

    Performing mobile k nearest neighbor (MkNN) queries whilst also being mobile is a challenging problem. All the mobile objects issuing queries and/or being queried aremobile. The performance of this kind of query relies heavily on the maintenance of the current locations of the objects. The index used for mobile objects must support efficient update operations and efficient query handling. This study aims to improve the performance of the MkNN queries while reducing update costs. Our approach is based on an observation that the frequency of one region changing between being occupied or not by mobile objects is much lower than the frequency of the position changes reported by the mobile objects. We first propose an virtual grid quadtree with Voronoi diagram(VGQ-Vor), which is a two-layer index structure that indexes regions occupied by mobile objects in a quadtree and builds a Voronoi diagram of the regions. Then we propose a moving k nearest neighbor (kNN) query algorithm on the VGQ-Vor and prove the correctness of the algorithm. The experimental results show that the VGQ-Vor outperforms the existing techniques (Bx-tree, Bdual-tree) by one to three orders of magnitude in most cases.

  • RESEARCH ARTICLE
    Yuming WU, Xiaodong LUO, Zhen YANG

    Grammar learning has been a bottleneck problem for a long time. In this paper, we propose a method of semantic separator learning, a special case of grammar learning. The method is based on the hypothesis that some classes of words, called semantic separators, split a sentence into several constituents. The semantic separators are represented by words together with their part-of-speech tags and other information so that rich semantic information can be involved. In the method, we first identify the semantic separators with the help of noun phrase boundaries, called subseparators. Next, the argument classes of the separators are learned from corpus by generalizing argument instances in a hypernym space. Finally, in order to evaluate the learned semantic separators, we use them in unsupervised Chinese text parsing. The experiments on a manually labeled test set show that the proposed method outperforms previous methods of unsupervised text parsing.

  • RESEARCH ARTICLE
    Lai KANG, Lingda WU, Yee-Hong YANG

    A novel unsupervised approach to automatically constructing multilevel image clusters from unordered images is proposed in this paper. The whole input image collection is represented as an imaging sample space (ISS) consisting of globally indexed image features extracted by a new efficientmulti-viewimage featurematchingmethod. By making an analogy between image capturing and observation of ISS, each image is represented as a binary sequence, in which each bit indicates the visibility of a corresponding feature. Based on information theory-inspired image popularity and dissimilarity measures, we show that the image content and distance can be quantitatively described, guided by which an input image collection is organized into multilevel clusters automatically. The effectiveness and the efficiency of the proposed approach are demonstrated using three real image collections and promising results were obtained from both qualitative and quantitative evaluation.

  • RESEARCH ARTICLE
    Jie LUO

    This paper investigates the problem of computing all maximal contractions of a given formula set Γ with respect to a consistent set Δ of atomic formulas and negations of atomic formulas. We first give a constructive definition of minimal inconsistent subsets and propose an algorithmic framework for computing all minimal inconsistent subsets of any given formula set. Then we present an algorithm to compute all maximal contractions fromminimal inconsistent subsets. Based on the algorithmic framework and the algorithm, we propose a general framework for computing all maximal contractions. The computability of the minimal inconsistent subset and maximal contraction problems are discussed. Finally, we demonstrate the ability of this framework by applying it to the first-order language without variables and design an algorithmfor the computation of all maximal contractions.

  • RESEARCH ARTICLE
    Jing LIU, Ziwei LIU, Jifeng HE, Frédéric MALLET, Zuohua DING

    The specification of modeling and analysis of real-time and embedded systems (MARTE) is an extension of the unified modeling language (UML) in the domain of real-time and embedded systems. Even though MARTE time model offers a support to describe both discrete and dense clocks, the biggest effort has been put so far on the specification and analysis of discrete MARTE models. To address hybrid real-time and embedded systems, we propose to extend statecharts using both MARTE and the theory of hybrid automata. We call this extension hybrid MARTE statecharts. It provides an improvement over the hybrid automata in that: the logical time variables and the chronometric time variables are unified. The formal syntax and semantics of hybrid MARTE statecharts are given based on labeled transition systems and live transition systems. As a case study, we model the behavior of a train control system with hybrid MARTE statecharts to demonstrate the benefit.

  • RESEARCH ARTICLE
    Wei KE, Zhiming LIU, Shuling WANG, Liang ZHAO

    We present a graph-basedmodel of a generic type system for an OO language. The type system supports the features of recursive types, generics and interfaces, which are commonly found in modern OO languages such as Java. In the classical graph theory, we define type graphs, instantiation graphs and conjunction graphs that naturally illustrate the relations among types, generics and interfaces within complex OO programs. The model employs a combination of nominal and anonymous nodes to represent respectively types that are identified by names and structures, and defines graph-based relations and operations on types including equivalence, subtyping, conjunction and instantiation. Algorithms based on the graph structures are designed for the implementation of the type system. We believe that this type system is important for the development of a graph-based logical foundation of a formal method for verification of and reasoning about OO programs.

  • RESEARCH ARTICLE
    Yongjian ZHAO, Hong HE, Jianxun Mi

    Blind source extraction (BSE) is particularly attractive to solve blind signal mixture problems where only a few source signals are desired. Many existing BSE methods do not take into account the existence of noise and can only work well in noise-free environments. In practice, the desired signal is often contaminated by additional noise. Therefore, we try to tackle the problem of noisy component extraction. The reference signal carries enough prior information to distinguish the desired signal from signal mixtures. According to the useful properties of Gaussian moments, we incorporate the reference signal into a negentropy objective function so as to guide the extraction process and develop an improved BSE method. Extensive computer simulations demonstrate its validity in the process of revealing the underlying desired signal.

  • RESEARCH ARTICLE
    Xuejuan ZHANG, Xiaochun CAO, Jingjie LI

    Geometric distortions are simple and effective attacks rendering many watermarking methods useless. They make detection and extraction of the embedded watermark difficult or even impossible by destroying the synchronization between the watermark reader and the embedded watermark. In this paper, we propose a blind content-based image watermarking scheme against geometric distortions. Firstly, the MSER detector is adopted to extract a set of maximally stable extremal regions which are affine covariant and robust to geometric distortions and common signal processing. Secondly, every original MSER is fitted into an elliptical region that was proved to be affine invariant. In order to achieve rotation invariance, an image normalization process is performed to transform the elliptical regions into circular ones. Finally, watermarks are repeatedly embedded into every circular disk by modifying the wavelet transform coefficients. Experimental results on standard benchmark demonstrate that the proposed scheme is robust to geometric distortions as well as common signal processing.