Dec 2007, Volume 1 Issue 4
    

  • Select all
  • Weakly distributive domains (II)
    JIANG Ying, ZHANG Guo - Qiang
    2007, 1(4): 373-384. https://doi.org/10.1007/s11704-007-0036-x
    Download PDF
    In our previous work (Inform. and Comput., 2005, 202: 87–103), we have shown that for any ω-algebraic meet-cpo D, if all higher-order stable function spaces built from D are ω-algebraic, then D is finitary. This accomplishes the first of a possible, two-step process in solving the problem raised (LNCS, 1991, 530: 16–33; Domains and lambda-calculi, Cambridge Univ. Press, 1998) whether the category of stable bifinite domains of Amadio-Droste-Göbel (LNCS, 1991, 530: 16–33; Theor. Comput. Sci., 1993, 111: 89–101) is the largest cartesian closed full sub-category within the category of ω-algebraic meet-cpos with stable functions. This paper presents the results of the second step, which is to show that for any ω - algebraic meet-cpo D satisfying axioms M and I to be contained in a cartesian closed full sub-category using ω - algebraic meet-cpos with stable functions, it must not violate MI". We introduce a new class of domains called weakly distributive domains and show that for these domains to be in a cartesian closed category using ω-algebraic meet-cpos, property MI" must not be violated. Further, we demonstrate that principally distributive domains (those for which each principle ideal is distributive) form a proper subclass of weakly distributive domains, and Birkhoff s M3 and N5 (Introduction to Lattices and order, Cambridge Univ. Press, 2002) are weakly distributive (but non-distributive). Then, we establish characterization results for weakly distributive domains. We also introduce the notion of meet-generators in constructing stable functions and show that if an ω-algebraic meet-cpo D contains an infinite number of meet-generators, then [D!?D] fails I. However, the original problem of Amadio and Curien remains open.
  • Advances in cryptography and information security—introduction of 2002-2006 progress of SKLOIS
    FENG Dengguo, WU Chuankun
    2007, 1(4): 385-396. https://doi.org/10.1007/s11704-007-0037-9
    Download PDF
    This paper introduces the research progress of the State Key Laboratory of Information Security (SKLOIS) in China during 2002–2006. This introduction covers four selected areas with each covering some selected research findings. The four selected areas are: the fundamentals of cryptography; the design, analysis and testing of block cipher algorithms; the design and analysis of security protocols based on computational intractability; authentication, authorization and their applications.
  • Online isolation of defects in cellular nanocomputers
    Teijiro Isokawa, Shin′ya Kowada, Naotake Kamiura, Nobuyuki Matsui, Ferdinand Peper
    2007, 1(4): 397-406. https://doi.org/10.1007/s11704-007-0038-8
    Download PDF
    Unreliability will be a major issue for computers built from components at nanometer scales. Thus, it’s to be expected that such computers will need a high degree of defect-tolerance to overcome components’ defects which have arisen during the process of manufacturing. This paper presents a novel approach to defect-tolerance that is especially geared towards nanocomputers based on asynchronous cellular automata. According to this approach, defective cells are detected and isolated by small configurations that move around randomly in cellular space. These configurations, called random flies, will attach to configurations that are static, which is typical for configurations that contain defective cells. On the other hand, dynamic configurations, like those that conduct computations, will not be isolated from the rest of the cellular space by the random flies, and will be able to continue their operations unaffectedly.
  • Ranking with uncertain labels and its applications
    YAN Shuicheng, Thomas S. Huang, WANG Huan, LIU Jianzhuang, TANG Xiao′ou
    2007, 1(4): 407-412. https://doi.org/10.1007/s11704-007-0039-7
    Download PDF
    The techniques for image analysis and classification generally consider the image sample labels fixed and without uncertainties. The rank regression problem studied in this paper is based on the training samples with uncertain labels, which often is the case for the manual estimated image labels. A core ranking model is designed first as the bilinear fusing of multiple candidate kernels. Then, the parameters for feature selection and kernel selection are learned simultaneously by maximum a posteriori for given samples and uncertain labels. The provable convergency Expectation Maximization (EM) method is used for inferring these parameters in an iterative manner. The effectiveness of the proposed algorithm is finally validated by the extensive experiments on age ranking task and human tracking task. The popular FG-NET and the large scale Yamaha aging database are used for the age estimation experiments, and our algorithm outperforms those state-of-the-art algorithms ever reported by other interrelated literatures significantly. The experiment result of human tracking task also validates its advantage over conventional linear regression algorithm.
  • Recent advances on NLP research in Harbin Institute of Technology
    ZHAO Tiejun, GUAN Yi, LIU Ting, WANG Qiang
    2007, 1(4): 413-428. https://doi.org/10.1007/s11704-007-0040-1
    Download PDF
    In the 1960s, the researchers of Harbin Institute of Technology (HIT) attempted to do relevant research on natural language processing. With more than 40-year’s effort, HIT has already established three research laboratories for Chinese information processing, i.e. the Machine Intelligence and Translation Laboratory (MI&T Lab), the Intelligent Technology and Natural Language Processing Laboratory (ITNLP) and the Information Retrieval Laboratory (IR-Lab). At present, it has a well-balanced research team of over 200 persons, and the research interests have extended to language processing, machine translation, text retrieval and other fields. Harbin Institute of Technology has accumulated a batch of key techniques and data resources, won many prizes in the technical evaluations at home and abroad. Harbin Institute of Technology has become one of the most important natural language processing bases for teaching and scientific research in China now. This paper gives an introduction to the achievements on NLP in HIT.
  • Inference and learning in hybrid probabilistic network
    WANG Limin, LI Xiongfei, WANG Xuecheng
    2007, 1(4): 429-435. https://doi.org/10.1007/s11704-007-0041-0
    Download PDF
    This paper proposed a novel hybrid probabilistic network, which is a good tradeoff between the model complexity and learnability in practice. It relaxes the conditional independence assumptions of Naive Bayes while still permitting efficient inference and learning. Experimental studies on a set of natural domains prove its clear advantages with respect to the generalization ability.
  • Discourage free riding in Peer-to-Peer file sharing systems with file migration and workload balancing approach
    YU Yijiao, JIN Hai
    2007, 1(4): 436-449. https://doi.org/10.1007/s11704-007-0042-z
    Download PDF
    Free riding is a great challenge to the development and maintenance of Peer-to-Peer (P2P) networks. A file migration and workload balancing based approach (FMWBBA) to discourage free riding is proposed in this paper. The heart of our mechanism is to migrate some shared files from the overloaded peers to the neighboring free riders automatically and transparently, which enforces free riders to offer services when altruistic peers are heavily overloaded. File migration is a key issue in our approach, and some related strategies are discussed. A simulation is designed to verify this approach, and the results show that it can not only alleviate free riding, but also improve the Quality of Service (QoS) and robustness of P2P networks efficiently.
  • Towards structural Web Services matching based on Kernel methods
    NAN Kai, YU Jianjun, SU Hao, GUO Shengmin, ZHANG Hui, XU Ke
    2007, 1(4): 450-458. https://doi.org/10.1007/s11704-007-0043-y
    Download PDF
    This paper describes a kernel methods based Web Services matching mechanism for Web Services discovery and integration. The matching mechanism tries to exploit the latent semantics by the structure of Web Services. In this paper, Web Services are schemed by WSDL (Web Services Description Language) as tree-structured XML documents, and their matching degree is calculated by our novel algorithm designed for loosely tree matching against the traditional methods. In order to achieve the task, we bring forward the concept of path subsequence to model WSDL documents in the vector space. Then, an advanced n-spectrum kernel function is defined, so that the similarity of two WSDL documents can be drawn by implementing the kernel function in the space. Using textual similarity and n-spectrum kernel values as features of low-level and mid-level, we build up a model to estimate the functional similarity between Web Services, whose parameters are learned by a ranking-SVM. Finally, a set of experiments were designed to verify the model, and the results showed that several metrics for the retrieval of Web Services have been improved by our approach.
  • An improved algorithm for finding community structure in networks with an application to IPv6 backbone network
    GUO Yingxin, XU Ke
    2007, 1(4): 459-467. https://doi.org/10.1007/s11704-007-0045-9
    Download PDF
    The discovery of community structure in a large number of complex networks has attracted lots of interest in recent years. One category of algorithms for detecting community structure, the divisive algorithms, has been proposed and improved impressively. In this paper, we propose an improved divisive algorithm, the basic idea of which is to take more than one parameters into consideration to describe the networks from different points of view. Although its basic idea appears to be a little simple, it is shown experimentally that it outperforms some other algorithms when it is applied to the networks with a relatively obscure community structure. We also demonstrate its effectiveness by applying it to IPv6 backbone network. The communities detected by our algorithm indicate that although underdeveloped compared with IPv4 network, IPv6 network has already exhibited a preliminary community structure. Moreover, our algorithm can be further extended and adapted in the future. In fact, it suggests a simple yet possibly efficient way to improve algorithms.
  • Adaptive scheduling for shared window joins over data streams
    JIN Cheqing, ZHOU Aoying, Jeffrey Xu Yu, Joshua Zhexue Huang, CAO Feng
    2007, 1(4): 468-477. https://doi.org/10.1007/s11704-007-0046-8
    Download PDF
    Recently a few Continuous Query systems have been developed to cope with applications involving continuous data streams. At the same time, numerous algorithms are proposed for better performance. A recent work on this subject was to define scheduling strategies on shared window joins over data streams from multiple query expressions. In these strategies, a tuple with the highest priority is selected to process from multiple candidates. However, the performance of these static strategies is deeply influenced when data are bursting, because the priority is determined only by static information, such as the query windows, arriving order, etc. In this paper, we propose a novel adaptive strategy where the priority of a tuple is integrated with realtime information. A thorough experimental evaluation has demonstrated that this new strategy can outperform the existing strategies.
  • A high-speed and low-cost storage architecture based on virtual interface
    ZENG Lingfang, FENG Dan, SHI Zhan, CHEN Jianxi, WEI Qingsong, LI Zhixiang
    2007, 1(4): 478-492. https://doi.org/10.1007/s11704-007-0047-7
    Download PDF
    Over the years, the network storage bandwidth has increased rapidly while the node-to-node latency has not decreased much. This is because the latency is dominated by the protocol software execution time in the kernel, instead of by the raw transmission time over the link. Virtual Interface (VI) protocol has been proposed to overcome the software overhead of the TCP/IP. In this paper, we introduce another new technology vSCSI (VI-attached SCSI) to compete with iSCSI in LAN (Local Area Networks) environment, and compare performance of vSCSI and iSCSI experimentally. Meanwhile, we present a Virtual Interface Storage Architecture (VISA) as a new network storage architecture which uses vSCSI as the network communication protocol. Then, we can take advantage of VI s superior performance over TCP/IP in LAN environment. Also, actually we have implemented and measured our data transport and Remote Procedure Call (RPC) layer over VI. The aim of our design and implementation is to put forward new techniques to reduce overheads.
  • Study on consistent query answering in inconsistent databases
    XIE Dong, YANG Luming
    2007, 1(4): 493-501. https://doi.org/10.1007/s11704-007-0048-6
    Download PDF
    Consistent query answering is an approach to retrieving consistent answers over databases that might be inconsistent with respect to some given integrity constraints. The approach is based on a concept of repair. This paper surveys several recent researches on obtaining consistent information from inconsistent databases, such as the underlying semantic model, a number of approaches to computing consistent query answers and the computational complexity of this problem. Furthermore, the work outlines potential research directions in this area.