IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

With ever-increasing power densities, managing on-chip temperatures by optimizing mapping and scheduling of tasks is becoming increasingly necessary. We study the minimization of end-to-end delay for thermally constrained scheduling of an application that is specified as a task graph and is executing on parallel processors without speed scaling. We show that task graph scheduling on thermally constrained systems is monotonic, i.e., delaying the execution of a task longer than necessary cannot lead to the early completion of any other task. Using this monotonicity principle, we design the provably optimal schedule for a given mapping, called the JUST schedule. The JUST schedule can be easily implemented using temperature sensors. We then present different thermal-aware modifications to standard mapping heuristics and evaluate them on a large set of problem instances. The experimental results illustrate that with simple thermal-aware modifications, mappings with much smaller end-to-end delay can be identified. © 2011 IEEE.

Department of Computer Science and Engineering

World University root node

Proceedings - Euromicro Conference on Real-Time Systems

End-to-end delay minimization in thermally constrained distributed systems

With ever-increasing power densities, temperature management using software and hardware techniques has become a necessity in the design of modern electronic systems. Such techniques have to be validated and optimized with respect to the thermal guarantee they provide, i.e., a safe upper-bound on the peak temperature of the system under all operating conditions. The computation of such a guarantee depends on the power and timing characteristics of the system. In this paper, we present formalisms to capture such characteristics at the system-level and provide an analytical technique to compute a provably safe upper-bound on the peak temperature. The proposed characterization and analysis is general in that it considers an impulse-response-based thermal model, task-dependent power consumption, tasks with dynamic arrival patterns and variable resource demand, and a scheduling policy expressed as a hierarchical composition of several commonly used policies.

Proceedings of the seventh IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis

System-level power and timing variability characterization to compute thermal guarantees

An ETL process is used to extract data from various sources, transform it and load it into a Data Warehouse. In this paper, we analyse an ETL flow and observe that only some of the dependencies in an ETL flow are essential while others are basically represents the flow of data. For the linear flows, we exploit the underlying dependency graph and develop a greedy heuristic technique to determine a reordering that significantly improves the quality of the flow. Rather than adopting a state-space search approach, we use the cost functions and selectivities to determine the best option at each position in a right-to-left manner. To deal with complex flows, we identify activities that can be transferred between linear segments in it and position those activities appropriately. We then use the re-orderings of the linear segments to obtain a cost-optimal semantically equivalent flow for a given complex flow. Experimental evaluation has shown that by using the proposed techniques, ETL flows can be better optimized and with much less effort compared to existing methods. © 2011 Springer-Verlag Berlin Heidelberg.

GENERAL

Lecture Notes in Business Information Processing

An efficient heuristic for logical optimization of ETL workflows

Servers have been proposed to implement resource reservations on shared resources. Such reservations isolate the temporal behavior of tasks sharing the shared resources, thereby providing performance guarantees to tasks independent of other tasks. In existing work, resource reservation has been synonymous to utilization (also called bandwidth) on the resource, i.e., we can reserve only a constant fraction of the resource utilization via a server. Such reservation schemes are not suited to serve interrupt-like tasks: tasks that occur seldom but require quick service or tasks with jitter. With this motivation, we present a generalized server algorithm, called Demand Bound Server (DBS), whose offered service is characterized by the demand bound function (dbf) of the task it serves. We show that schedulability of DBS tightly follows that of EDF, and if schedulable a DBS provides a performance guarantee as requested by the dbf of the task. We present an implementation of DBS when the dbf is a shifted-periodic curve and characterize its overhead. We also present efficient composition operations on DBS that widen the class of implemented servers to tightly serve tasks arising in most practical settings. Copyright © 2011 ACM.

Embedded Systems Week 2011, ESWEEK 2011 - Proceedings of the 9th ACM International Conference on Embedded Software, EMSOFT'11

Demand bound server: Generalized resource reservation for hard real-time systems

In this paper, we present a system called QueSTS, which generates a query specific extractive summary of a selected set of documents. We have proposed an integrated graph approach to represent the contextual relationships among sentences of all the input documents. These relationships are exploited and several sub-graphs of the integrated graph are constructed. These sub-graphs consist of sentences that are highly relevant to the query and that are highly related to each other. These sub-graphs are ranked by a scoring model. The highest ranked sub-graph which is rich in query relevant information is selected as a query specific summary. A sentence ordering strategy has also been proposed by us to improve the coherence of the summary. Sentences in the selected summary are sequenced as per the above strategy. Experimental results show that the summaries generated by the QueSTS system are significantly better than other systems in terms of user satisfaction. © 2010 World Scientific Publishing Company.

International Journal on Artificial Intelligence Tools

A system for query specific coherent text multi-document summarization

The web of linked data represents a globally distributed dataspace which can be queried using the SPARQL query language. However, with the growth in size and complexity of the web of linked data, it becomes impractical for the user to know enough about its structure and semantics for the user queries to produce enough answers. This problem is addressed in the paper by making use of ontologies available on the web of linked data to produce approximate results. The existing approach, which generates multiple relaxed queries and executes them sequentially one by one, is improved by integrating the approximation steps with the query execution itself. Thus, by performing query relaxation on-the-y at runtime, the shared data between relaxed queries are not fetched repeatedly, resulting in significant performance benefits. Further opportunities for optimization during query execution are identified and are used to prune relaxation steps which do not produce results. The implementation of our approach demonstrates its efficacy.

CEUR Workshop Proceedings

Efficient approximate SPARQL querying of web of linked data

The web of linked data represents a globally distributed dataspace. It can be queried with SPARQL whose execution takes place by asynchronously traversing the RDF links to discover data sources at run-time. However, the optimization of SPARQL queries over the web of data remains a challenge and in this paper we present an approach addressing this problem. The proposed approach works in two-phases to optimize the SPARQL queries. The first phase analyzes the query before its execution and discovers classes of data that do not contribute towards answering it which can then be prevented from being fetched. However, this analysis may miss a number of patterns that can only be discovered at run-time. The second phase analyzes the query execution to discover more patterns which are used to further reduce the amount of data fetched from the web to answer the query. The main idea of this phase is to model the query execution as a context graph that is used by a heuristic to discover the patterns which are passed sideways to prune nodes in the context graph, resulting in an improvement in query performance. The implementation of our approach demonstrates its benefits.

Optimizing SPARQL queries over the web of linked data

Keyword search is an easy way to allow inexperienced users to query an information system. It does not need knowledge of specific query language or underlying schema. Recently answering keyword queries on graph structured data has emerged as an important research topic. Many efforts focus on queries on RDF(Resource Description Framework) graphs as RDF has emerged as a viable data model for representing/integrating semistructured, distributed and interconnected datathis paper, we present a novel algorithm for constructing answer graphs using pruned exploration strategy. We form component structures comprising closely related class and relationship nodes for the keywords and join the identified component structures using appropriate hook nodes. The Class/SubClass relationships available in RDF schema are also utilized for the answer graph construction. The paper illustrates the working of the algorithm using AIFB institute data.

KDIR 2010 - Proceedings of the International Conference on Knowledge Discovery and Information Retrieval

Answer graph construction for keyword search on graph structured(RDF) data

With increasing power densities, runtime thermal management is becoming a necessity in today's systems, especially so for highly integrated Multi-Processor Systems-on-Chip (MPSoCs). In this paper, we propose a neural network (NN) based approach to implement an on-chip thermal simulator to aid such runtime management for MPSoCs. The proposed method combines the advantage of approximating the thermal properties of the chip as a linear system with the ease of fully parallel analog implementation of NNs. We perform a case study with the Niagara UltraSPARC T1 MPSoC for real-life applications, benchmarking our results with an accurate higher order Runge-Kutta (RK4) solver, that is employed in tools such as HotSpot. Within a few gate delays, the proposed NN design can simulate temperatures of the MPSoC 500 ms into the future - corresponding to thousands of iterations of the RK4 solver, with a maximum error of 1-2 K. ©2010 IEEE.

ISCAS 2010 - 2010 IEEE International Symposium on Circuits and Systems: Nano-Bio Circuit Fabrics and Systems

Neural network based on-chip thermal simulator

Processing of backward XPath axes against XML streams is challenging for two reasons: (i) Data is not cached for future access. (ii) Query contains steps specifying navigation to the data that already passed by. While there are some attempts to process parent and ancestor axes, there are very few proposals to process ordered backward axes namely, preceding and preceding-sibling. For ordered backward axis processing, the algorithm, in addition to overcoming the limitations on data availability, has to take care of ordering constraints imposed by these axes. In this paper, we show how backward ordered axes can be effectively represented using forward constraints. We then discuss an algorithm for XML stream processing of XPath expressions containing ordered backward axes. The algorithm uses a layered cache structure to systematically accumulate query results. Our experiments show that the new algorithm gains remarkable speed up over the existing algorithm without compromising on bufferspace requirement. © 2009 Springer.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Ordered backward XPath axis processing against XML streams

Presentations are one of the most common and effective ways of communicating the overview of a work to the audience. Given a technical paper, automatic generation of presentation slides reduces the effort of the presenter and helps in creating a structured summary of the paper. In this paper, we propose the framework of a novel system that does this task. Any paper that has an abstract and whose sections can be categorized under introduction, related work, model, experiments and conclusions can be given as input. As documents in LATEX are rich in structural and semantic information we used them as input to our system. These documents are initially converted to XML format. This XML file is parsed and information in it is extracted. A query specific extractive summarizer has been used to generate slides. All graphical elements from the paper are made well use of by placing them at appropriate locations in the slides. These slides are presented in the document order. Copyright © 2009, Assocation for the Advancement of ArtdicaI Intelligence (www.aaai.org). All rights reserved.

Proceedings of the 22nd International Florida Artificial Intelligence Research Society Conference, FLAIRS-22

SlidesGen: Automatic generation of presentation slides for a technical paper using summarization

In this paper, we address the problem of generating a queryspecific extractive summary in a an efficient manner for a given set of documents. In many of the current solutions, the entire collection of documents is modeled as a single graph which is used for summary generation. Unlike these approaches, in this paper, we model each individual document as a graph and generate a query-specific summary for it. These individual summaries are then intelligently combined to produce the final summary. This approach greatly reduces the computational complexity. © Springer-Verlag Berlin Heidelberg 2009.

ESUM: An efficient system for query-specific multi-document summarization

Online systems that help users select the most preferential item from a large electronic catalog are known as product search and recommender systems. Evaluation of various proposed technologies is essential for further development in this area. This paper describes the design and implementation of two user studies in which a particular product search tool, known as example critiquing, was evaluated against a chosen baseline model. The results confirm that example critiquing significantly reduces users’ task time and error rate while increasing decision accuracy. Additionally, the results of the second user study show that a particular implementation of example critiquing also made users more confident about their choices. The main contribution is that through these two user studies, an evaluation framework of three criteria was successfully identified, which can be used for evaluating general product search and recommender systems in E-commerce environments. These two experiments and the actual procedures also shed light on some of the most important issues which need to be considered for evaluating such tools, such as the preparation of materials for evaluation, user task design, the context of evaluation, the criteria, the measures and the methodology of result analyses.

Fulltext

Electronic Commerce Research

Evaluating product search and recommender systems for E-commerce environments

Effective extraction of query relevant information present within documents on the web is a nontrivial task. In this paper we present our system called QueSTS, which does the above task by filtering and aggregating important query relevant sentences distributed across a set of documents. Our approach captures the contextual relationships among sentences of all input documents and represents them as an "integrated graph". These relationships are exploited and several subgraphs of integrated graph which consist of sentences that are highly relevant to the query and that are highly related to each other are constructed. These subgraphs are ranked by our scoring model. The highest ranked subgraph which is rich in query relevant information and also has sentences that are highly coherent is returned as a query specific summary. Copyright © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Proceedings of the 21th International Florida Artificial Intelligence Research Society Conference, FLAIRS-21

QueSTS: A query specific text summarization system

As XML has become the de-facto standard for data exchange in several applications, XML message brokers assume a lot of importance. Message brokers we address in this paper store a large number of user profiles, in the form of XML twig queries, that represent the data requirement of users/applications. In contrast to publisher-subscriber systems, message brokers select the part of the data that is of interest to the user and send it to her, instead of the whole matched document. In this paper, we propose a new sequencing based XML message broker architecture that handles tens of thousands of user profiles and delivers to each user the XML elements (or nodes) that satisfy the user's twig query. We introduce a novel node sequencing method called branch sequencing that converts an XML twig query into a branch sequence. Intuitively, nodes are sequenced branch by branch. We show that by storing user profiles in the form of branch sequences, and appropriately indexing them, we can efficiently generate the qualifying nodes for each profile, as the input XML document streams by. The input document nodes are streamed into the system in the document order. The branch sequencing technique we propose enables holistic, matching of twig queries to the document. Another important feature of the system is that it carries out ordered profile matching. We have implemented the system and compared its performance with a state-of-art XML filtering system and have shown that the filtering time reduces significantly and the system scales up very well. © 2007 IEEE.

Proceedings - International Conference on Data Engineering

Branch sequencing based XML message broker architecture

With the advent of XML as the new standard for information representation and exchange, indexing and querying of XML data is of major concern. In this paper, we propose a method for representing an XML document as a sequence based on a variation of Prüfer sequences. We incorporate new components in the node encodings such as level, number of a certain kind of descendants and develop methods for holistic processing of tree pattern queries. The query processing involves converting the query also into a sequence and performing subsequence matching on the document sequence. We establish certain interesting properties of the proposed method of sequencing that give rise to a new efficient pattern matching algorithm. The sequence data is stored in a two level B+-trees to support query processing. We also propose an optimization for parent-child axis to speed up the query processing. Our approach does not require any post-processing and guarantees results that are free of false positives and duplicates. Experimental results show that our system performs significantly better than previous systems in a large number of cases. Copyright 2005 ACM.

International Conference on Information and Knowledge Management, Proceedings

Efficient indexing and querying of XML data using modified Prüfer sequences

A crucial element in consumer electronic commerce is a catalog tool that not only finds the product for the user, but also convinces him that he has made the best choice. To do that, it is important to show him ample choices while keeping his interaction effort below an acceptable limit. Among the various interaction models used in operational e-commerce sites, ranked lists are by far the most popular tool for product navigation and selection. However, as the number of product features and the complexity of user's criteria increase, a ranked list's efficiency becomes less satisfactory. As an alternative, research groups from the intelligent user interface community have developed various example-based search tools, including SmartClient from our laboratory. These tools not only perform personalized search, but also support tradeoff analysis. However, despite the academic interest, example-based search paradigms have not been widely adopted in practice. We have examined the performance of such tools on a variety of tasks involving selection and tradeoff. The studies clearly show that example-based search is comparable to ranked lists on simple tasks, but significantly reduces the error rate and search time when complex tradeoffs are involved. This shows that such tools are likely to be useful particularly for extending the scope of consumer e-commerce to more complex products.

Proceedings of the ACM Conference on Electronic Commerce

Evaluating example-based search tools

The notion of a clique tree plays a central role in obtaining an intersection graph representation of a chordal graph. In this paper, we introduce a new structure called the reduced clique hypergraph of a chordal graph. Unlike a clique tree, the reduced clique hypergraph is a unique structure associated with a chordal graph. We show that all clique trees of a chordal graph can be obtained from the reduced clique hypergraph; thus the reduced clique hypergraph can be thought of as a generalization of the notion of a clique tree. We then link the reduced clique hypergraph notion to minimal vertex separators of chordal graph by proving a structure theorem which shows that the edges of the reduced clique hypergraph are in one-one correspondence with the minimal vertex separators. We also show that a closed-form formula for the number of clique trees of a chordal graph can be derived using these results. Using an algorithmic characterization of minimal vertex separators, we obtain efficient algorithms to compute the reduced clique hypergraph and to count the number of clique trees of a chordal graph. Finally, guided by the reduced clique hypergraph structure we propose a few new subclasses of chordal graphs and relate them to each other and the existing subclasses. © 2002 Elsevier Science B.V.

Discrete Applied Mathematics

Clique tree generalization and new subclasses of chordal graphs

Wavelength Division Multiplexing (WDM) technology evolved to utilize effectively the enormous bandwidth of optical fiber. In circuit-switched WDM networks data transfer between a given pair of source and destination nodes takes place by using a lightpath. A lightpath is an optical channel having a single wavelength established between the given pair of nodes by configuring the Wavelength Routing Switches (WRS) at the intermediate nodes along the path. In a reconfigurable optical wavelength routing switch, the time required to reconfigure the switch is often long when compared to the speed of data passing through the switch. It is necessary to consider the delay introduced by slow switches as it has significant impact on the performance of the network. In this paper, we present a new technique to mitigate the lightpath setup time overheads in Dynamic Lightpath Establishment (DLE) algorithms for the wavelength continuous circuit switched all-optical networks. Simulation studies indicate that the proposed technique significantly reduces the number of reconfigurations required to setup new lightpaths. © 2001 Elsevier Science B.V.

Computer Communications

Lightpath setup time optimization in wavelength routed all-optical networks

We present a conceptually simple algorithm to generate an ordering of the vertices of an undirected graph. The ordering generated turns out to be a strong elimination ordering if and only if the given graph is a strongly chordal graph. This algorithm makes use of maximum cardinality search and lexicographic breadth first search algorithms which are used to generate perfect elimination orderings of a chordal graph. Our algorithm takes O(k2n) time where k is the size of the largest minimal vertex separator and n denotes the number vertices in the graph. The algorithm provides a new insight into the structure of strongly chordal graphs and also gives rise to a new algorithm of the same time complexity for recognition of strongly chordal graphs. © Springer-Verlag Berlin Heidelberg 1998.