ISSN 1000-1239 CN 11-1777/TP

Table of Content

15 January 2010, Volume 47 Issue 1
Rigid Mesh Deformation with Detail Preserving
Zhao Yong, Xiao Chunxia, Shi Feng, and Peng Qunsheng
2010, 47(1):  1-7. 
Asbtract ( 652 )   HTML ( 5)   PDF (1294KB) ( 864 )  
Related Articles | Metrics
Mesh deformation with detail preserving is very important in many application fields, such as online game, computer animation, digital entertainment, movie production, computer aided design, military simulation and virtual worlds. However, it is a challenging problem in computer graphics to efficiently edit complex triangular meshes for existing deformation techniques. In this paper, a novel mesh deformation algorithm with detail preserving is presented. It deforms the input mesh as rigidly as possible, hence greatly reducing surface detail distortion even under large deformations. This approach first conducts clustering-based simplification on the original mesh according to the richness of local details. The simplified mesh is then deformed, and adjacent vertices undergoing similar transformation are merged into one vertex. By local frame encoding, this deformation is then transferred to the original mesh to generate an initial deformation result. Since vertices belonging to the same cluster undergo the same rigid transformation, discontinuity will occur between vertices belonging to different clusters. To prevent these artifacts, the position of each vertex is further adjusted by iteratively minimizing a quadric energy function to arrive at the final deformation result. Various experiment results show that the presented algorithm is simple, easy to use, robust and very effective in preserving surface details.
Real-Time Garment Animation Based on Mixed Model
Mao Tianlu, Xia Shihong, Zhu Xiaolong, and Wang Zhaoqi
2010, 47(1):  8-15. 
Asbtract ( 556 )   HTML ( 0)   PDF (1772KB) ( 651 )  
Related Articles | Metrics
Real-time garment animation could generate vivid cloth animation on 3D virtual avatars under the limitation of computational time cost. It potentially has broad applications in fields of games, entertainment, garment industry, etc. The problems concentrate on how to establish a computational model which could generate visually plausible garment animation under the restriction of real-time computing. Currently, cloth animation models could be divided into two categories based on the properties of fabric. They are physical-based models and geometric-based models. The former has the advantage of vision realism and the latter has the advantage of high efficiency. Mixed models, which combine physical-based models and geometric-based ones together, are effective ways for real-time cloth animation. In this paper, a new mixed model for garment animation based on the sample data is presented. In sample data, collision between cloth and body are investigated by a probability analysis method for predicting correlation between cloth motion and body motion. So that cloth could be compartmentalized reasonably under such correlation and mixed two different types of cloth animation models. The new mixed model could support real-time cloth animation and has a mechanism for dynamic control of efficiency. It has the following advantages: Firstly, it could automatically mix two different models; Secondly, it could support real-time cloth animation; Thirdly, the efficiency could be controlled dynamically; Finally, the compartmentalization of cloth are more subtly and reasonable. Experiments show that compared with the method based on static distance, cloth animation results of our method are more close to physical-based animation results under the same efficiency.
Face Occlusion Detection and Reconstruction
Wang Zhiming and Tao Jianhua
2010, 47(1):  16-22. 
Asbtract ( 1002 )   HTML ( 5)   PDF (1661KB) ( 579 )  
Related Articles | Metrics
Face occlusions (such as glasses, respirator, scarf, etc.) can degrade the performance of face recognition and face animation evidently. How to remove occlusions on face image quickly and automatically becomes a important problem in face image processing. A face occlusion detection and reconstruction algorithm based on fuzzy principal component analysis (FPCA) is proposed in this paper. The main framework is based on analysis and synthesis techniques. In analysis step, optimal coefficients are estimate from occluded face by project to face space (eigenfaces) in the sense of least-square minimization (LSM). In synthesis step, reconstructed face is obtained by linear combinations of prototypes. Then, difference image is computed from original and reconstructed face, and it is filtered by weights calculated from distance and gray level gap from current pixel to its surrounding neighbors, and normalized to [0 1]. This difference was used as the probability of being occluded. New face is synthesized by weighted sum of reconstructed face and original face based on this occluding probability. In succeeding iterations, fuzzy PCA in stead of classical PCA is used for analysis and reconstruction, and accumulated error is used for occlusion detection. Experimental results show that the proposed algorithm could detect face occlusion precisely and reconstruct smooth natural face, outperforming classical iterative PCA method.
An Image Matching Algorithm Based on Singular Value Decomposition
Zhao Feng, Huang Qingming, and Gao Wen
2010, 47(1):  23-32. 
Asbtract ( 994 )   HTML ( 7)   PDF (2084KB) ( 740 )  
Related Articles | Metrics
Image matching plays an important role in many fields, such as computer vision, remote sensing and medical image analysis. Traditional-correlation-based matching methods require heavy computation time and they are sensitive to image rotation. In this paper, a new image matching algorithm based on singular value decomposition is proposed to efficiently match image pairs with arbitrary rotation angle. Corner points with dominant orientation are firstly extracted as feature points in the two images. The initial set of feature point matches is then obtained by singular value decomposition of a correspondence strength matrix. A new expression of the correspondence strength matrix is introduced to handle more complicated imaging conditions. Each element of this matrix is computed from the similarity measure between two feature points based on normalized cross-correlation. The similarity measure is invariant to image rotation by taking into account the dominant orientation of the two feature points. Finally the epipolar geometry constraint is imposed on the initial matches in order to reject the false matches. Experimental results on complicated real images show the effectiveness and robustness of the algorithm. Moreover, it is easy to combine the proposed algorithm with other matching techniques. Experimental results with SVD-SIFT prove the expansibility and practicability of the algorithm.
Patch Similarity Based Anisotropic Diffusion for Image Denoising
Chen Qiang, Zheng Yuhui, Sun Quansen, and Xia Deshen
2010, 47(1):  33-42. 
Asbtract ( 771 )   HTML ( 0)   PDF (3284KB) ( 616 )  
Related Articles | Metrics
A patch-similarity-based anisotropic diffusion is presented for image denoising. The traditionally anisotropic diffusion based on the intensity similarity of each single pixel (or gradient information) cannot effectively preserve weak edges and details, such as texture. The non-local means algorithm based on patch similarity can preserve texture details well, since the non-local means utilizes the intensity similarity of neighbor pixels. In the proposed method, the patch similarity is adopted to construct the diffusion function of the anisotropic diffusion for gray and color image denoising, namely the diffusion coefficient of the anisotropic diffusion depends on the patch similarity, not image gradient. Therefore, the diffusion of this method is more effective and accurate than the traditional method, because image patches can represent structure information, such as edge and texture etc, while single pixel cannot represent structure information. Experimental results of gray and color images demonstrate that the proposed method can preserve details better than the traditional anisotropic diffusion, and has not noticeable staircase effect that appears in the traditional anisotropic diffusion. In addition, the time complexity is lower than that of the non-local means algorithm. Brain and cardiac magnetic resonance (MR) images and brain Chinese visible human image denoising experiments also indicate that the proposed method has a promising application.
Research on Statistical Information Reconstruction of Images Based on Multiple-Point Geostatistics Integrating Soft Data with Hard Data
Zhang Ting, Lu Detang, Li Daolun, and Du Yi
2010, 47(1):  43-52. 
Asbtract ( 544 )   HTML ( 3)   PDF (2330KB) ( 634 )  
Related Articles | Metrics
In many fields, there are two types of data: hard data and soft data. Soft data typically provide an extensive coverage of the field under study although with low resolution. It is necessary to condition the reconstructed models to all these different types of data so as to improve the accuracy. The statistical information reconstruction of images will be difficult and inaccurate when only hard data are available or there are no conditional data. Accuracy of reconstructed images can be improved through the use of soft data during the process of reconstruction. Integrating soft data with hard data, a method based on MPS (multiple-point geostatistics) is proposed to reconstruct statistical information of images. By reproducing high-order statistics, MPS allows capturing structures from a training image, and then anchoring them to the specific model data. A training image is a numerical prior model which contains the structures and relationship existing in realistic models. During the process of regenerating characteristic patterns in a training image, the accuracy of reconstructed images is improved, using both soft data and hard data as conditional data. The experimental results show that, compared with the unconditional reconstruction images and the reconstructed images using only hard data, the structure characteristics in reconstructed images using this method are similar to those obtained from real volume data.
A Terrain Model Simplification Method Based on Adaptive Areas Division
Zhang Huijie, Lü Yinghua, and Liu Shuhua
2010, 47(1):  53-61. 
Asbtract ( 502 )   HTML ( 0)   PDF (2557KB) ( 502 )  
Related Articles | Metrics
In view of the problem of the approximation models with poor self-adaptability by uniform error threshold, a method is proposed in this paper. In this method, the terrain is divided into some different areas with various terrain features, and then the error function and the error threshold are adaptively determined according to these areas. Aimed at the character of big data in terrain model, a detailed hierarchy is constructed and its fast index method is described. In order to control the density of feature points in the primary step, the feature points are selected based on the convex terrain and its diffused points. It solves the problem of the feature selection for the gentle slope terrain. The method of searching for multi-resolution adjacent nodes is put forward to accelerate the area division process with coarse grain, and the matching function between the adjacent nodes is also described. Besides, a relief degree function for terrain surface is proposed to evaluate the terrain areas, so as to determine the division strategy of the approximation model. As a result, the terrain model is of higher adaptability and precision. The experiments on some real data show that the method is superior to the uniform error threshold method.
Example Based 3D Animation Creating Interactively
Lu Difei, Ren Wenhua, Li Guojun, and Si Jin
2010, 47(1):  62-71. 
Asbtract ( 486 )   HTML ( 3)   PDF (2735KB) ( 420 )  
Related Articles | Metrics
Proposed in this paper is an example based synthesis approach to create 3D animation of a target character interactively on the basis of sketch based 3D animation transfer. Users can add new creative idea to their works while reserving the styles of source animations. This approach consists of the following steps: 1)inputting pairs of sketches to source and target meshes, and building correspondences between the sources and target; 2)inputting control points on the target mesh; and 3)adjusting the control points interactively, calculating the weights of each key frame of source animations and creating an optimized deformed target mesh according to the control points. The authors provide new research contributions to all these topics, and integrate them into the newly developed prototype animating system, which is an easy-to-use interactive animating tool and not limited to trained experts. This approach is general and does not require the sources and target to share the same number of vertices or triangles, or to have matching connectivity. The above approach is intuitive and able to produce highly authentic 3D animations. The approach is demonstrated by constructing different examples according to a series of key frames of different sources and different number of control points to illustrate the feasibility.
An Efficient Algorithm for Mining Compressed Sequential Patterns
Tong Yongxin, Zhang Yuanyuan, Yuan Mei, Ma Shilong , Yu Dan, and Zhao Li
2010, 47(1):  72-80. 
Asbtract ( 677 )   HTML ( 1)   PDF (1574KB) ( 584 )  
Related Articles | Metrics
Mining frequent sequential patterns from sequence databases has been a central research topic in data mining and various efficient algorithms for mining sequential patterns have been proposed and studied. Recently, many researchers have not focused on the efficiency of sequential patterns mining algorithms, but have paid attention to how to make users understand the result set of sequential patterns easily, due to the huge number of frequent sequential patterns generated by the mining process. In this paper, the problem of compressing frequent sequential patterns is studied. Inspired by the ideas of compressing frequent itemsets, an algorithm, CFSP (compressing frequent sequential patterns), is developed to mine a few representative sequential patterns to express all the information of all frequent sequential patterns and eliminate a large number of redundant sequential patterns. The CFSP adopts a two-steps approach: in the first step, all closed sequential patterns as the candidate set of representative sequential patterns are obtained, and at the same time most of the representative sequential patterns are obtained; in the second step, finding the remaining representative sequential patterns takes only a little time. An empirical study with both real and synthetic data sets proves that the CFSP has good performance.
A Semi-Supervised Learning Algorithm from Imbalanced Data Based on KL Divergence
Xu Zhen, Sha Chaofeng, Wang Xiaoling, and Zhou Aoying,
2010, 47(1):  81-87. 
Asbtract ( 977 )   HTML ( 2)   PDF (1561KB) ( 686 )  
Related Articles | Metrics
In many real applications, it’s often difficult or quite expensive to get labeled negative examples for learning, such as Web search, medical diagnosis, earthquake identification and so on. This situation makes the traditional classification techniques work ineffectively, because the precondition that every class has to own its labeled instances is not met. Therefore, the semi-supervised learning method from positive and unlabeled data becomes a hot topic in the literature. In the past years, researchers have proposed many methods, but they can’t cope well with the imbalanced classification problem, especially when the number of hidden negative examples in the unlabeled set is relatively small or the distribution of training examples in the training set becomes quite different. In this paper, a novel KL divergence-based semi-supervised classification algorithm, named LiKL (i.e. semi-supervised learning algorithm from imbalanced data based on KL divergence), is proposed to tackle this special problem. The proposed approach firstly finds likely positive examples existing in the unlabeled set, and successively finds likely negative ones, followed by an enhanced logistic regression classifier to classify the unlabeled set. The experiments show that the proposed approach not only improves precision and recall, but also is very robust, compared with former work in the literature.
A Query Relaxation Strategy Applied in a Deep Web Data Integration System
Shen Derong, Ma Ye, Nie Tiezheng, Kou Yue, and Yu Ge
2010, 47(1):  88-95. 
Asbtract ( 500 )   HTML ( 0)   PDF (1223KB) ( 483 )  
Related Articles | Metrics
In the process of query in Deep Web data integration system, it is hard to avoid the so-called failed query that brings unsatisfactory result. So it is more cooperative to modify the raw query to return non-empty result set than to notify the user that there is no result corresponding to the query at all. Inspired by the observations and analysis on deep Web, a query relaxation solution applied in a deep Web data integration system is proposed in this paper, in which, all the Deep Web sources are grouped based on their query interface attributes and constructed as a global database relationship graph (DRG), the global database relationship graph (DRG) is transformed to database relationship graph fitting a specified query, and then the query is relaxed and executed based on the DRG. However, because of query relaxation the amount of the results from the data sources may be very large, and part of them may be not similar to the user’s query. Therefore after receiving the results from the data sources, a part of the results is first selected by using the skyline method, and then is sorted based on the similarity between the results and the user’s query, Finally the results satisfying the user’s requirement are returned to the user. Experiments demonstrate the availability of the query relaxation strategy.
Pass-Count-Based Path Query on Big Graph Datasets
Xu Shifeng, Gao Jun, Yang Dongqing, and Wang Tengjiao
2010, 47(1):  96-103. 
Asbtract ( 500 )   HTML ( 4)   PDF (880KB) ( 541 )  
Related Articles | Metrics
Distance and path queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs and yet require fast query answering. A new data structure is created for representing all distances in a graph. The data structure is distributed in the sense that it may be viewed as assigning labels to the vertices, such that a query involving vertices u and v may be answered using only the labels of u and v. In this paper, a new concept “pass count” is proposed to measure the importance of a vertex in the graph. Based on the pass-count, a special heuristic rule is used to build distance labels for each vertex of the graph, so distance queries and path queries can be processed on those labels exclusively. This method is efficient by avoiding graph traversal, and hence reduces time complexity. A “pass count algorithm” is also presented based on the pass-count of each vertex in the graph, which aims to minimize labels’ size, improve the query processing, and accelerate the construction of the labels. Extensive experiments are conducted to prove the effectiveness and efficiency of the algorithm.
Uncertain Path Prediction of Moving Objects on Road Networks
Guo Limin, Ding Zhiming, Hu Zelin, and Chen Chao,
2010, 47(1):  104-112. 
Asbtract ( 881 )   HTML ( 1)   PDF (927KB) ( 856 )  
Related Articles | Metrics
With the advancement of mobile computing technology and the widespread use of GPS-enabled mobile devices, the location-based services have received more and more attentions, and the path prediction of moving objects is one of the most important issues. The existing prediction methods of moving objects focus mainly on the precise historic trajectory in Euclidean space. However, in the real world, there are a lot of applications which require predicting network-constrained trajectory based on the uncertain historic trajectory. As yet, there has been no research on uncertain path prediction of moving objects on road networks. In order to solve this problem, a method of generating the uncertain trajectory is proposed firstly, the definition of path probability and an uncertain path prefix tree are used to generate the uncertain trajectory, and a corresponding data format of the uncertain trajectory is given. Then an uncertain trajectory pattern mining algorithm is proposed, and a data structure named id-list is used in the algorithm. Finally trajectory patterns which are mined from the uncertain trajectory pattern mining algorithm are indexed by a novel access method for efficient query processing. The experiment shows good performance of the system, and the results demonstrate that the proposed techniques are accurate, efficient and of low storage capacity.
Feature Point Based Image Watermarking Scheme in Contourlet Domain Against Geometrical Attacks
Lou Oujun
2010, 47(1):  113-120. 
Asbtract ( 592 )   HTML ( 0)   PDF (1785KB) ( 510 )  
Related Articles | Metrics
Image watermarking resistant to geometrical attacks is the hotspot and challenging task in the state-of-the-art research on watermarking. Even an invisible affine transformation can invalidate most existing watermarking algorithms. This the authors analyse and discuss the characteristic of contourlet transform and Harris-Affine detector, and on this basis, propose a novel contourlet-domain watermarking algorithm against geometric attacks based on the affine-invariant feature points and characteristics of regions. First, the proposed scheme uses contourlet transform to extract multidirectional and multiscale texture information, and then obtains the feature points invariant to the affine transformation from the low and middle directional subbands by Harris-Affine detector. Second, the feature regions are adaptively computed by the feature scale of the local structure and normalized by U transform. The watermarking is emdedded adaptively in those characteristic regions which are normalized. Finally, by vector quantization, several copies of the watermark are embedded into the no overlapped local feature regions in different directional subbands. During detection, the resynchronization is achieved through feature points. And the embedded sequence can be extracted by “majority principles” without resorting to the original host image. Experimental results show that the proposed algorithm has good transparency and is very robust to common image processing and geometric attacks.
Privacy Preserving Towards Continuous Query in Location-Based Services
Pan Xiao, Hao Xing, and Meng Xiaofeng
2010, 47(1):  121-129. 
Asbtract ( 641 )   HTML ( 0)   PDF (1330KB) ( 587 )  
Related Articles | Metrics
With advances in wireless communication and mobile positioning technologies, location-based mobile services have been gaining increasingly popularity in recent years. Privacy preservation, including location privacy and query privacy, has recently received considerable attention for location-based mobile services. A lot of location cloaking approaches have been proposed for protecting the location privacy of mobile users. However, they mostly focus on anonymizing snapshot queries based on proximity of locations at query issued time. Therefore, most of them are ill-suited for continuous queries. In view of the privacy disclosure (including location and query privacy) and poor quality of service under continuous query anonymization, a δp-privacy model and a δq-distortion model are proposed to balance the tradeoff between privacy preserving and quality of service. Meanwhile a temporal distortion model is proposed to measure the location information loss during a time interval, and it is mapped to a temporal similar distance between two queries. Finally, a greedy cloaking algorithm (GCA) is proposed, which is applicable to both anonymizing snapshot queries and continuous queries. Average cloaking success rate, cloaking time, processing time and anonymization cost for successful requests are evaluated with increasing privacy level (k). Experimental results validate the efficiency and effectiveness of the proposed algorithm.
Convergence Property of a Generic Particle Filter Algorithm
Qu Yanwen, Zhang Erhua, and Yang Jingyu
2010, 47(1):  130-139. 
Asbtract ( 684 )   HTML ( 4)   PDF (1032KB) ( 477 )  
Related Articles | Metrics
Particle filters are widely utilized in the optimal filtering problems. These methods approximate the posteriori distribution of the state (or the posteriori joint distribution of the extened state) by a population of weighted particles which evolve randomly according to the dynamic system model and the measurements. Despite many theoretical advance which have been reported in the last decade, the study of the convergence property of particle filters is still an open question. In this paper, the almost sure convergence of the generic particle filter (GPF) is discussed in a circuitous way. First, a modified-generic particle filter (M-GPF) is constructed. Different from the GPF, the M-GPF will determine whether it is necessary to rerun both the resampling step and the importance sampling (IS) step according to a conditional criterion after performing the IS step at each time. Then the almost sure convergence of the M-GPF will be concerned. Later, when the recursive time is finite and the interesting function is 4th power integrable with respect to the posteriori joint distribution of the extended state, the sufficient condition for the GPF estimation converges almost surely to the optimal estimation is discussed. Finally, a novel simulation experiment will be presented to illustrate the almost sure convergence of the GPF.
A Novel Subjective Logic for Trust Management
Wang Jin, and Sun Huaijiang
2010, 47(1):  140-146. 
Asbtract ( 524 )   HTML ( 2)   PDF (716KB) ( 491 )  
Related Articles | Metrics
A novel subjective logic based on the Dezert-Smarandache theory is proposed. The original subjective logic based on the Dempster-Shafer theory of evidence is an extension of the standard logic and probability calculus. The subjective logic is a framework of uncertain reasoning, and it is widely studied because of its successful application to trust management. But the elementary elements of the frame of discernment are assumed to be exclusive, which is a strong constraint. The new subjective logic based on the framework of the Dezert-Smarandache theory, which is able to handle both uncertain and paradoxical information, is an extension of the subjective logic by overcoming this strong constraint. In addition, the logical operators of the new subjective logic are inferred and proved to be the extension of the logical operators of the subjective logic. Two evidential operators including discounting operator and consensus operator are defined for trust recommendation and accumulation. The discounting operator of the new subjective logic is more flexible. The shortcomings of the consensus operator of the original subjective logic are presented. A consensus operator of the new subjective logic is proposed which can overcome these shortcomings. Finally, the experiment shows that the computational complexity of the novel subjective logic is acceptable.
Dynamic Web Service Selection Based on Discrete Particle Swarm Optimization
Fan Xiaoqin, , Jiang Changjun, Fang Xianwen, and Ding Zhijun,
2010, 47(1):  147-156. 
Asbtract ( 570 )   HTML ( 0)   PDF (2083KB) ( 505 )  
Related Articles | Metrics
With the development of Web service theories and technologies, Web service has been spreading rapidly. In order to meet the requirements of different users, multiple services need to be composed. Therefore, how to dynamically and efficiently select appropriate Web services from existing services to build newly value-added and complex services has been a popular research focus. In this paper, a discrete particle swarm optimization (DPSO) algorithm is designed to facilitate the dynamic Web service selection, and combined with the specific meaning of service selection, three kinds of velocity operator and one position evolution equation are proposed. Aimed at the common limitation that evolutionary algorithms are prone to fall into the local optimal solution, no-hope/re-hope criterion is introduced to guarantee the diversity of particle swarm and improve the global search ability. Theoretical analysis and experimental results show that the proposed algorithm not only owns a good globally convergent performance but also has a faster convergent rate. Specially, the service selection method is independent of the candidate services number, which means that the efficiency of service selection will not decrease with the increase of available services. Furthermore, compared with other two velocity operators, the Max operator has best comprehensive properties in the process of service selection.
A Probabilistic Approach to Analyze and Adjust Time Constraints in Workflow Management System
Han Rui, Liu Yingbo, Wen Lijie, and Wang Jianmin
2010, 47(1):  157-163. 
Asbtract ( 550 )   HTML ( 1)   PDF (1282KB) ( 460 )  
Related Articles | Metrics
Dealing with time and time constraints is crucial in designing and managing business processes, so time management should be an important part of workflow management systems. One key issue in time management is to analyze the feasibility of time constraints. Besides, when time constraints are violated, they should be adjusted to regain a satisfaction state. Traditional work on time constraint analysis considers discrete activity (execution) durations and presents qualitative analysis result such as time constraints are satisfied or violated. However, the dynamic nature of workflows causes high uncertainties in workflow process, thus activities of workflow process probabilistically satisfy their time constraints, e.g., 95% of activities satisfy their time constraints. Therefore, traditional deterministic analysis is too rigorous. For such an issue, probabilistic time constraint workflow nets (PTCWF-nets) are introduced to describe uncertainties in time-constrained workflow process. Based on PTCWF-nets, a probabilistic approach is proposed at worklow build-time. This approach analyzes every activity’s probability of satisfying time constraints in a stochastic way. This quantitative analysis result allows process designer to flexibly check the feasibility of time constraints. The result also provides a precise estimation to guide time constraint adjustment. Moreover, the proposed approach is implemented in a real-world workflow management system, and its effectiveness is evaluated by means of a concrete example.
Answer Set Programming Representation for E-R Model
Li Xin, Li Fan, Bian Xingbin, and Liu Qihe
2010, 47(1):  164-173. 
Asbtract ( 700 )   HTML ( 0)   PDF (1048KB) ( 504 )  
Related Articles | Metrics
As a well-known semantic data model, E-R model is widely applied in the database design phase. But, E-R model itself has some defects, and these defects restrict the further applications of the model. Currently there are two main approaches about the improvements for E-R model. One is based on the graphical representation and the other is based on the description logic representation. Whereas, the former still has not automatic reasoning capability, and the latter has some shortcomings such as the weak representation capability and the insufficient compatibility with relational database. To overcome these shortcomings, a novel method is proposed which utilizes the answer set programming to represent E-R Model. Firstly, E-R schemata corresponding to the databases are distinguished as the basic and the extended types, and then their syntax and semantic definitions are accomplished. Secondly, the answer set programming is utilized to accomplish the representations of the two types of the schemata above. Finally, the correctness of these representations is proved. The proposed method not only supplies a new logic representation approach for E-R model, but also has some obvious advantages over the two common used improvement approaches. More importantly, the results of this paper make it possible to apply E-R model to realize the semantic interoperability among heterogeneous databases.
GPE: A Graph-Based Determination Model for Meaningful NFS Query Result
Li Xiaoguang and Song Baoyan
2010, 47(1):  174-181. 
Asbtract ( 519 )   HTML ( 0)   PDF (1081KB) ( 449 )  
Related Articles | Metrics
Non-fully structured query (NFS) is an important query approach for the XML documents lacking in full structure information. NFS query faces the situations: the user doesn’t know fully the structural knowledge of an XML document, or a document doesn’t provide any structural information, or documents are heterogeneous. However, the user can describe his querying requirement by an NFS query containing a part of XML structural information, or some keywords only. The issue of meaningful results determination is critical to the quality of NFS query. Based on the PE model for XML data of tree model in the authors, previous work, a graph-based meaningful determination model of NFS query results for XML data of graph model, called GPE, is proposed. the GPE model mainly includes the result’s granularity, the definition of pattern and entity, the definition of equivalent pattern, and determination rules. For the ambiguous label and complicate structural semantic, an equivalent pattern in the GPE is evaluated by combining a domain-dictionary-based and context-constricted label similarity with a pattern structure similarity. Such equivalent pattern evaluation can improve greatly the precision of meaningful results determination. With the extensive experiments on both the real dataset and XML benchmark, the GPE outperforms the PE model on both the recall and the precision.
Server Transparent Query Authentication of Outsourced Database
Zhang Min, Hong Cheng, and Chen Chi
2010, 47(1):  182-190. 
Asbtract ( 488 )   HTML ( 1)   PDF (1484KB) ( 550 )  
Related Articles | Metrics
With the rapid growth of database outsourcing, the security concerns in the outsourced database (ODB) paradigm are receiving more and more attentions. Query authentication is one of the important security requirements which enable the database clients to verify the authenticity and the completeness of the query results. Currently several query verification schemes are proposed based on the specially designed authentication data structures (ADS), in which the DBMS computes verification object (VO) for each query, and returns the result together with its VO. Since this “server-centric” model requires the functional extensions of DBMS and the modification of communication protocols, it will inevitably affect the application in practice. In this paper the authors propose a server transparent query authentication method called chain embedded signature (CES), which embeds the VO inside the ODB, therefore it supports the query authentication with commercial DBMS and standard SQL commands. This transparency also frees the server from heavy verification tasks, and prevents it from becoming the bottleneck of performance. Furthermore, since the VOs are stored inside ODB, the consistency of them is promised by the database transaction mechanism. The cost analysis and experimental results show that the time and space overhead are reasonable to be deployed in real systems.
Index Structures for Supporting Block Edit Distance
Wang Bin, Guo Qing, Li Zhongbo, and Yang Xiaochun,
2010, 47(1):  191-199. 
Asbtract ( 604 )   HTML ( 1)   PDF (1767KB) ( 505 )  
Related Articles | Metrics
In approximate string matching, the traditional edit distance cannot evaluate the similarity between strings very well, especially for the name, address datasets, etc. The block edit distance, however, can do the job easily. It is important to efficiently support block edit distance for approximate string query processing. Since computing the block edit distance between two strings is an NP-Complete problem, it is desired to provide solutions to increase filterability and decrease false positives. In this paper, a novel index structure, called SHV-Trie, is proposed. A lower bound of the block edit distances is presented according to the features of the block edit distance with move operations, i.e. the frequencies of each character in a string. A corresponding query filter approach is proposed based on the lower bound on character frequencies. Meanwhile, considering the large space cost problem, an optimized ordered character index structure and a compressed index structure are proposed. The corresponding query filtering approaches are further given based on the optimized and compressed index structures. The experimental results and analysis on real data sets show that the proposed index structures can provide good filtering ability and high query performance by decreasing false positives.