9362943
Finding shortest paths in large network systems
This paper describes a disk-based algorithm for finding shortest paths in a large network system. It employs a strategy of processing the network piece by piece and is based on new algorithms for graph partitioning and for finding shortest paths that overcome the problem of existing approaches. To show that it is scalable to large network systems and is adaptable to different computing environments, seven states in Tiger/Line files are extracted as test cases and are experimented on machines with different configurations. The running time for finding the shortest path depends primarily on the power of the underlying systems. Moreover, to run the algorithm optimally, the memory requirement is not large, even for a very large network system such as the road system in several states in Tiger/Line file. To evaluate its performance, New Mexico state road system is used as the test case, and is compared with Dijkstra's algorithm. The average running time of the proposed algorithm is, in the worst case, about two and a half times slower than that of Dijkstra's algorithm; provided that in Dijkstra's algorithm, the whole graph can be fit into main memory and is already loaded in advance. If the I/O time for loading the whole graph is counted, the proposed algorithm is faster in essentially all cases.
17853419
A succinct physical storage scheme for efficient evaluation of path queries in XML
Path expressions are ubiquitous in XML processing languages. Existing approaches evaluate a path expression by selecting nodes that satisfies the tag-name and value constraints and then joining them according to the structural constraints. We propose a novel approach, next-of-kin (NoK) pattern matching, to speed up the node-selection step, and to reduce the join size significantly in the second step. To efficiently perform NoK pattern matching, we also propose a succinct XML physical storage scheme that is adaptive to updates and streaming XML as well. Our performance results demonstrate that the proposed storage scheme and path evaluation algorithm is highly efficient and outperforms the other tested systems in most cases.
35884730
Compact access control labeling for efficient secure XML query evaluation
Fine-grained access controls for XML define access privileges at the granularity of individual XML nodes. In this paper, we present a fine-grained access control mechanism for XML data. This mechanism exploits the structural locality of access rights as well as correlations among the access rights of different users to produce a compact physical encoding of the access control data. This encoding can be constructed using a single pass over a labeled XML database. It is block-oriented and suitable for use in secondary storage. We show how this access control mechanism can be integrated with a next-of-kin (NoK) XML query processor to provide efficient, secure query evaluation. The key idea is that the structural information of the nodes and their encoded access controls are stored together, allowing the access privileges to be checked efficiently. Our evaluation shows that the access control mechanism introduces little overhead into the query evaluation process.
11505780
InterJoin: Exploiting Indexes and Materialized Views in XPath Evaluation
XML has become the standard for data exchange for a wide variety of applications, particularly in the scientific community. In order to efficiently process queries on XML representations of scientific data, we require specialized techniques for evaluating XPath expressions. Exploiting materialized views in query processing significantly enhances query processing performance. We propose a novel view definition that allows for intermediate (structural) join results to be stored and reused in XML query evaluation. Unlike current XML view proposals, our views do not require navigation in the original document or path-based pattern matching. Hence, they are evaluated significantly faster and are easily costed as part of a query plan. In general, current structural joins cannot exploit views efficiently when the view definition is not a prefix (or a suffix) of the XPath query. To increase the applicability of our proposed view definition, we propose a novel physical structural join operator called InterJoin. The InterJoin operator allows for joining interleaving XPath expressions, e.g., joining //A//C with //B to evaluate //A//B//C. InterJoin allows for more join alternatives in XML query plans. We propose several physical implementations for InterJoin, including a technique to exploit spatial indexes on the inputs. We give analytic cost models for the implementations so they can be costed in an existing XML query optimizer. Experiments on real and synthetic XML data show significant speed-ups of up to 200% using InterJoin, and speed-ups of up to 400% using our materialized views
10807744
XML Query Processing and Optimization
In this paper, I summarize my research on optimizing XML queries This work has two components: the first component is the definition of a logical algebra and logical optimization techniques This algebra can be translated into different physical algebras such as native or extended-relational algebras The second component is the design of physical storage structures and physical optimization techniques.
5525123
FIX: feature-based indexing technique for XML documents
Indexing large XML databases is crucial for efficient evaluation of XML twig queries. In this paper, we propose a feature-based indexing technique, called FIX, based on spectral graph theory. The basic idea is that for each twig pattern in a collection of XML documents, we calculate a vector of features based on its structural properties. These features are used as keys for the patterns and stored in a B+tree. Given an XPath query, its feature vector is first calculated and looked up in the index. Then a further refinement phase is performed to fetch the final results. We experimentally study the indexing technique over both synthetic and real data sets. Our experiments show that FIX provides great pruning power and could gain an order of magnitude performance improvement for many XPath queries over existing evaluation techniques.
10586032
A tag recommendation system for folksonomy
Social bookmarking tools become more and more popular nowadays and tagging is used to organize information and allow users to recall or search the resources. Users need to type the tags whenever they post a resource, so that a good tag recommendation system can ease the process of finding some useful and relevant keywords for users. Researchers have made lots of relevant work for tag recommendation systems, but those traditional collaborative systems may not perform well in the case of a new user and a new resource.
 To address this problem, we propose a tag recommendation system for two different cases. The first case is that the active user or active resource is a new one which has not appeared in the past while the second case is that the active user and resource has already been posted. In this paper, we present two different methods for these two cases: a content-based method and a graph-based method. We implement our tag recommendation system in a realworld academic Folksonomy system. In order to gain better results,we apply improvements and combinations of previous work in each of these two methods.and combinations of previous work in each of these two methods. We participated into the Discovery Challenge 2009 with the proposed methods. The results of our teams are within the top teams.
8241163
MS-BID: a Java package for label-free LC-MS-based comparative proteomic analysis
UNLABELLED
MS-BID (MS Biomarker Discovery Platform) is an integrative computational pipeline for biomarker discovery using LC-MS-based comparative proteomic analysis. This platform consists of several computational tools for: (i) detecting peptides in the collected patterns; (ii) matching detected peptides across a number of LC-MS datasets and (iii) selecting discriminatory peptides between classes of samples.


AVAILABILITY
MS-BID source codes, binaries and documentations are freely available under LGPL from http://tools.proteomecenter.org/msBID.php.
1934229
Automated regression testing using DBT and Sleuth
SUMMARY Regression testing is an important activity in software maintenance. Current regression testing strategies can be categorized into two groups: retest all and selective regression testing. Each of these two groups encompasses a variety of strategies. In industrial practice, regression testing procedures vary widely. Sometimes, several regression testing techniques are used in combination. Technique selection is also innuenced by the expected quality of the system to be tested. Such variations in regression testing strategies and techniques mandate exibility for a regression testing tool. This paper presents regression testing support for Sleuth, a test generation tool based on Domain-Based Testing. We explain the rules for building regression tests for a variety of possible regression testing strategies from retest all strategies to selective regression testing strategies.
2697231
Lossless compression of color mosaic images
We present a low complexity algorithm for lossless compression of color mosaic images generated by a Bayer CCD color filter array. This algorithm is based on an interesting use of the integer wavelet transform followed by a fast adaptive context-based Golomb-Rice coding. The lossless compression performance of the proposed algorithm is apparently the best reported in the literature so far for color mosaic images.
34672242
An effective model for composition of secure systems
Abstract In this paper we present a composable security property based on the principle of an existing one that was developed for the non-interference requirement and used to deal with composition of components linked as a chain. This new property is more general in the sense that it can handle composition of components connected as a tree, and allow each component and their system to meet different security requirements. The applicability of the new property is then assessed based on a case study of security analysis of a file system. Useful observations derived from this case study are finally discussed which can help to develop cost-effective approaches to design and evaluation of secure systems.