Tree Expressions for Information Systems

The discernibility matrix is one of the most important approaches to computing positive region, reduct, core and value reduct in rough sets. The subject of this paper is to develop a parallel approach of it, called ＂tree expression＂. Its computational complexity for positive region and reduct is O（m^2 × n） instead of O（m × n^2） in discernibility-matrix-based approach, and is not over O（n^2） for other concepts in rough sets, where rn and n are the numbers of attributes and objects respectively in a given dataset （also called an ＂information system＂ in rough sets）. This approach suits information systems with n ≥ m and containing over one million objects.

Second Attribute Algorithm Based on Tree Expression

One view of finding a personalized solution of reduct in an information system is grounded on the viewpoint that attribute order can serve as a kind of semantic representation of user requirements. Thus the problem of finding personalized solutions can be transformed into computing the reduct on an attribute order. The second attribute theorem describes the relationship between the set of attribute orders and the set of reducts, and can be used to transform the problem of searching solutions to meet user requirements into the problem of modifying reduct based on a given attribute order. An algorithm is implied based on the second attribute theorem, with computation on the discernibility matrix. Its time complexity is O（n^2 × m） （n is the number of the objects and m the number of the attributes of an information system）. This paper presents another effective second attribute algorithm for facilitating the use of the second attribute theorem, with computation on the tree expression of an information system. The time complexity of the new algorithm is linear in n. This algorithm is proved to be equivalent to the algorithm on the discernibility matrix.

Optimized XML Storage in NXD Based on Tree-Structure Disassemble

Independent XML storage based on XSD （XML Schema Document） is adopted in NXD（Native XML Data base）, XMI. storage structure based on tree-structure disassemble and the algorithm used in dynamically updating XML document are provided in this paper. The main idea is that in term of data model of XML document, XML document is parsed to Document Structure-Tree with Hierarchical Model and Leaf-Data with Relation Model for storage. Simultaneously Proxy node is imported in order to solve the problem that XML data store in cross-blocks. And with XSD model information, sparse index is constructed to save storage space. It is proved that this storage structure could improve efficiency of XML document operation.

Improving SPARQL query performance with algebraic expression tree based caching and entity caching

To obtain comparable high query performance with relational databases,diverse database technologies have to be adapted to confront the complexity posed by both Resource Description Framework(RDF) data and SPARQL query.Database caching is one of such technologies that improves the performance of database with reasonable space expense based on the spatial/temporal/semantic locality principle.However,existing caching schemes exploited in RDF stores are found to be dysfunctional for complex query semantics.Although semantic caching approaches work effectively in this case,little work has been done in this area.In this paper,we try to improve SPARQL query performance with semantic caching approaches,i.e.,SPARQL algebraic expression tree(AET) based caching and entity caching.Successive queries with multiple identical sub-queries and star-shaped joins can be efficiently evaluated with these two approaches.The approaches are implemented on a two-level-storage structure.The main memory stores the most frequently accessed cache items,and items swapped out are stored on the disk for future possible reuse.Evaluation results on three mainstream RDF benchmarks illustrate the effectiveness and efficiency of our approaches.Comparisons with previous research are also provided.

Matching suitable feature construction for SAR images based on evolutionary synthesis strategy

In the paper,a set of algorithms to construct synthetic aperture radar（SAR）matching suitable features are frstly proposed based on the evolutionary synthesis strategy.During the process,on the one hand,the indexes of primary matching suitable features（PMSFs）are designed based on the characteristics of image texture,SAR imaging and SAR matching algorithm,which is a process involving expertise;on the other hand,by designing a synthesized operation expression tree based on PMSFs,a much more flexible expression form of synthesized features is built,which greatly expands the construction space.Then,the genetic algorithm-based optimized searching process is employed to search the synthesized matching suitable feature（SMSF）with the highest effciency,largely improving the optimized searching effciency.In addition,the experimental results of the airborne synthetic aperture radar ortho-images of C-band and P-band show that the SMSFs gained via the algorithms can reflect the matching suitability of SAR images accurately and the matching probabilities of selected matching suitable areas of ortho-images could reach 99±0.5%.