P Sreenivasa Kumar

XML is widely used for representing and exchanging hierar chical data and queries naturally specify hierarchical patterns to select relevant parts of an XML document. These patterns have a sequence of selection predicates connected by operators representing parent-child or ancestor-descendant relationships. In this context, the operation of structural join involves discovering pairs of nodes that are in ancestor descendant relationship from the cross product of two sets of nodes. In this paper, we propose a novel way of solving queries with multiple struc tural joins by maintaining an extra piece of information for each element called nDesc, which specifies the number of descendants having same tag name as that of the element. An extensive experimental evaluation of our algorithms with datasets of varying nDesc value shows that our algorithms perform better than the currently existing join algorithms. © Springer-Verlag 2004.

In the context of Linked Open Data, substantial progress has been made in mining of property subsumption and equivalence axioms. However, little progress has been made in determining if a predicate is symmetric or if its inverse exists within the data. Our study of popular linked datasets such as DBpedia, YAGO and their associated ontologies has shown that they contain very few inverse and symmetric property axioms. The state-of-the-art approach ignores the open-world nature of linked data and involves a time-consuming step of preparing the input for the rule-miner. To overcome these shortcomings, we propose a schema-agnostic unsupervised method to discover inverse and symmetric axioms from linked datasets. For mining inverse property axioms, we find that other than support and confidence scores, a new factor called predicate-preference factor (ppf) is useful and setting an appropriate threshold on ppf helps in mining quality axioms. We also introduce a novel mechanism, which also takes into account the semantic-similarity of predicates to rank-order candidate axioms. Using experimental evaluation, we show that our method discovers potential axioms with good accuracy.

This paper attempts to study the impact of wavelength converters in WDM wavelength routed all-optical networks. A new heuristic approach for placement of wavelength converters to reduce blocking probabilities is explored. Multihop virtual topology is designed to minimize the number and overall cost of the converters. Blocking probabilities for Static Lightpath Establishment (SLE) and Dynamic Lightpath Establishment (DLE) are analyzed. In the case of SLE, arranging lightpaths in ascending order of their path length reduces blocking probability. Wavelength converters placed at nodes with high nodal degree further reduces the blocking probabilities. Simulation studies performed on 28-node USA long haul network, 20-node arbitrary mesh network, and 19-node EON (European Optical Network) validate the observations made earlier. © 1999 Elsevier Science B.V.

This paper considers Wavelength Division Multiplexing (WDM) networks, which employ wavelength routing switches that enable the establishment of lightpaths through the network between node-pairs. Conventional Routing and Wavelength Assignment (RWA) algorithms for Static Lightpath Establishment (SLE) are based on traditional circuit-switched networks where routing and wavelength assignment steps are decoupled. In this paper, we propose new Integer Linear Program (ILP) formulations for maximizing network throughput for two different types of traffic patterns namely, uniform and non-uniform. In the proposed formulations, routing and wavelength assignment steps are tightly coupled, unlike earlier proposed formulations. However, for large size networks solving the ILP formulations can easily overwhelm the capabilities of today's state-of-art computing facilities. Hence, we propose two heuristic algorithms based on wavelength-graph for maximizing network throughput. Simulation studies indicate that the heuristic approach gives performance close to the optimal solution obtained using ILP based solution. © 2002 Elsevier Science B.V. All rights reserved.

The existing query-log based on-line index maintenance approaches rely on frequency distribution of terms in the static query-log. Though these approaches are proved to be efficient, but in real world, the frequency distribution of the terms changes over a period of time. This negatively affects the efficiency of the static query-log based approaches. To overcome this problem, we propose an index tuning strategy for reorganizing the indexes according to the latest frequency distribution of the terms captured from query-logs.Experimental results show that the proposed tuning strategy improves the performance of static query-log based approaches. © 2011 ACM.

Program debugging is often an ad hoc activity, with a combination of manual and semi-automated processing. A challenge posed by debugging is the lack of standardized procedures for instrumenting, representing, and analyzing the execution trace. Further, debugging is often low level, getting into the nitty-gritty details of variables and their semantics—rather than at a high-level. The presence of libraries only exacerbates these issues. We propose BOLD, an Ontology-based Log Debugger, to unify various activities involved in the debugging of sequential C programs. The syntactical information of programs can be represented as Resource Description Framework (RDF) triples. BOLD automatically instruments programs by querying these triples. It represents the execution trace of the program also as RDF triples called trace triples. BOLD’s novel high-level reasoning abstracts these triples as spans. A span gives a way of examining the values of a particular variable over certain portions of the program execution. The properties of the spans are defined formally as a Web Ontology Language ontology. A developer can debug a given buggy program by querying the trace triples and reasoning with the spans. To empirically assess BOLD, we debugged the programs in standard Software-artifact Infrastructure Repository. Experiments related to debugging through automated reasoning show improvement in conciseness of the developers’ specifications and run time performance of BOLD compared to gdb-Python.

Wavelength routed optical networks have emerged as a technology that can effectively utilize the enormous bandwidth of the optical fiber. Wavelength converters play an important role in enhancing the fiber utilization and reducing the overall call blocking probability of the network. Placement of wavelength converters is an NP-complete problem in an arbitrary mesh network. In this paper, new Integer Linear Program (ILP) formulations have been proposed for the static and dynamic routing and wavelength assignment problem to reduce the number of conversions. We use Genetic Algorithms (GAs) for placing limited range wavelength converters in arbitrary mesh wavelength routed optical networks. The objective is to achieve near optimal placement of full and limited range wavelength converters resulting in reduced blocking probabilities and low distortion of the optical signal. Certain heuristics are used to obtain starting solutions for the GAs to enable it to converge faster. The results obtained using GAs are compared with the heuristic method of placement. We study the range of loads for which converters are useful. We observe that limited range converters placed near optimally at a few nodes can provide almost the same blocking probability as full range wavelength converters placed at all the nodes and that increasing the number of converters yields only a marginal improvement in blocking probability. We also observe that uniform placement of converters can be adopted in ring networks at low offered loads. We study the effect of uniform placement at higher loads and suggest that when used with reservation in the routing algorithm, converters ensure fairness to all nodes. Simulations have been carried out on a 12-node ring network and 14-node NSFNET.

Chordal graphs form an important and widely studied subclass of perfect graphs. The set of minimal vertex separators constitute an unique class of separators of a chordal graph and capture the structure of the graph. In this paper, we explore the connection between perfect elimination orderings of a chordal graph and its minimal vertex separators. Specifically, we prove a characterization of these separators in terms of the monotone adjacency sets of the vertices of the graph, numbered by the maximum cardinality search (MCS) scheme. This leads to a simple linear-time algorithm to identify the minimal vertex separators of a chordal graph using the MCS scheme. We also introduce the notion of multiplicity of a minimal vertex separator which indicates the number of different pairs of vertices separated by it. We prove a useful property of the lexicographic breadth first scheme (LBFS) that enables us to determine the multiplicities of minimal vertex separators of a chordal graph. © 1998 Elsevier Science B.V. All rights reserved.

In this paper we present a conceptual framework and the implementation details of a semantic web tool named SAQI (Semantic Aware Query Interface) that enables querying across structurally disparate XML documents that use the vocabulary from a shared ontology. Through this tool we provide an interface for querying the web pages of a group of participants with common interest who have agreed to use the common base ontology for publishing their data. Our interface guides a naive user in his querying process. It helps him to formulate his queries and retrieve semantically correct information from the web pages of this user group. © Springer-Verlag 2004.