@article {12464,
	title = {Video Pr{\'e}cis: Highlighting Diverse Aspects of Videos},
	journal = {IEEE Transactions on Multimedia},
	volume = {12},
	year = {2010},
	month = {2010/12//},
	pages = {853 - 868},
	abstract = {Summarizing long unconstrained videos is gaining importance in surveillance, web-based video browsing, and video-archival applications. Summarizing a video requires one to identify key aspects that contain the essence of the video. In this paper, we propose an approach that optimizes two criteria that a video summary should embody. The first criterion, {\textquotedblleft}coverage,{\textquotedblright} requires that the summary be able to represent the original video well. The second criterion, {\textquotedblleft}diversity,{\textquotedblright} requires that the elements of the summary be as distinct from each other as possible. Given a user-specified summary length, we propose a cost function to measure the quality of a summary. The problem of generating a précis is then reduced to a combinatorial optimization problem of minimizing the proposed cost function. We propose an efficient method to solve the optimization problem. We demonstrate through experiments (on KTH data, unconstrained skating video, a surveillance video, and a YouTube home video) that optimizing the proposed criterion results in meaningful video summaries over a wide range of scenarios. Summaries thus generated are then evaluated using both quantitative measures and user studies.},
	keywords = {$K$-means, CAMERAS, combinatorial mathematics, combinatorial optimization, Cost function, data compression, Exemplar selection, Image segmentation, Internet, Iron, Length measurement, multimedia systems, Ncut, optimisation, Optimization methods, original video, Permission, shot segmentation, Surveillance, user specified summary length, video précis, Video sharing, video signal processing, Video summarization},
	isbn = {1520-9210},
	doi = {10.1109/TMM.2010.2058795},
	author = {Shroff, N. and Turaga,P. and Chellapa, Rama}
}
@conference {13385,
	title = {Minimizing Communication Cost in Distributed Multi-query Processing},
	booktitle = {IEEE 25th International Conference on Data Engineering, 2009. ICDE {\textquoteright}09},
	year = {2009},
	month = {2009/04/29/March},
	pages = {772 - 783},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Increasing prevalence of large-scale distributed monitoring and computing environments such as sensor networks, scientific federations, Grids etc., has led to a renewed interest in the area of distributed query processing and optimization. In this paper we address a general, distributed multi-query processing problem motivated by the need to minimize the communication cost in these environments. Specifically we address the problem of optimally sharing data movement across the communication edges in a distributed communication network given a set of overlapping queries and query plans for them (specifying the operations to be executed). Most of the problem variations of our general problem can be shown to be NP-Hard by a reduction from the Steiner tree problem. However, we show that the problem can be solved optimally if the communication network is a tree, and present a novel algorithm for finding an optimal data movement plan. For general communication networks, we present efficient approximation algorithms for several variations of the problem. Finally, we present an experimental study over synthetic datasets showing both the need for exploiting the sharing of data movement and the effectiveness of our algorithms at finding such plans.},
	keywords = {Approximation algorithms, Communication networks, Computer science, Cost function, Data engineering, distributed communication network, distributed databases, distributed multi-query processing, grid computing, Large-scale systems, NP-hard, optimisation, Polynomials, Publish-subscribe, publish-subscribe systems, Query optimization, Query processing, sensor networks, Steiner tree problem, Tree graphs, trees (mathematics)},
	isbn = {978-1-4244-3422-0},
	doi = {10.1109/ICDE.2009.85},
	author = {Li,Jian and Deshpande, Amol and Khuller, Samir}
}
@conference {13369,
	title = {Flow Algorithms for Parallel Query Optimization},
	booktitle = {IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008},
	year = {2008},
	month = {2008/04/07/12},
	pages = {754 - 763},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We address the problem of minimizing the response time of a multi-way join query using pipelined (inter-operator) parallelism, in a parallel or a distributed environment. We observe that in order to fully exploit the parallelism in the system, we must consider a new class of ";interleaving"; plans, where multiple query plans are used simultaneously to minimize the response time of a query (or to maximize the tuple-throughput of the system). We cast the query planning problem in this environment as a ";flow maximization problem";, and present polynomial-time algorithms that (statically) find the optimal set of plans to use for a given query, for a large class of multi-way join queries. Our proposed algorithms also naturally extend to query optimization over web services. Finally we present an extensive experimental evaluation that demonstrates both the need to consider such plans in parallel query processing and the effectiveness of our algorithms.},
	keywords = {Casting, computational complexity, Cost function, Databases, Delay, distributed environment, Educational institutions, flow maximization algorithm, Interleaved codes, interoperator parallelism, minimisation, multiway join query response time minimization problem, parallel database, Parallel databases, parallel query optimization, Partitioning algorithms, pipeline processing, pipelined parallelism, polynomial-time algorithm, query planning problem, Query processing, Web service, Web services},
	isbn = {978-1-4244-1836-7},
	doi = {10.1109/ICDE.2008.4497484},
	author = {Deshpande, Amol and Hellerstein,L.}
}
@conference {13363,
	title = {Decoupled query optimization for federated database systems},
	booktitle = {18th International Conference on Data Engineering, 2002. Proceedings},
	year = {2002},
	month = {2002///},
	pages = {716 - 727},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We study the problem of query optimization in federated relational database systems. The nature of federated databases explicitly decouples many aspects of the optimization process, often making it imperative for the optimizer to consult underlying data sources while doing cost-based optimization. This not only increases the cost of optimization, but also changes the trade-offs involved in the optimization process significantly. The dominant cost in the decoupled optimization process is the "cost of costing" that traditionally has been considered insignificant. The optimizer can only afford a few rounds of messages to the underlying data sources and hence the optimization techniques in this environment must be geared toward gathering all the required cost information with minimal communication. In this paper, we explore the design space for a query optimizer in this environment and demonstrate the need for decoupling various aspects of the optimization process. We present minimum-communication decoupled variants of various query optimization techniques, and discuss tradeoffs in their performance in this scenario. We have implemented these techniques in the Cohera federated database system and our experimental results, somewhat surprisingly, indicate that a simple two-phase optimization scheme performs fairly well as long as the physical database design is known to the optimizer, though more aggressive algorithms are required otherwise},
	keywords = {Algorithm design and analysis, Cohera federated database, Computer science, Corporate acquisitions, Cost function, Database systems, decoupled optimization, Design optimization, distributed databases, federated databases, federated relational database systems, Internet, Query optimization, query optimizer, Query processing, Relational databases, Space exploration},
	isbn = {0-7695-1531-2},
	doi = {10.1109/ICDE.2002.994788},
	author = {Deshpande, Amol and Hellerstein,J. M}
}
@conference {17640,
	title = {Optimal design of signaling networks for Internet telephony},
	booktitle = {IEEE INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings},
	volume = {2},
	year = {2000},
	month = {2000///},
	pages = {707-716 vol.2 - 707-716 vol.2},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We present an approach for efficient design of a signaling network for a network of software switches supporting Internet telephony. While one may take an integer programming approach to solve this problem, it quickly becomes intractable even for modest-sized networks. Instead, our topology design uses random graphs that we show to be nearly optimal in cost, highly connected, and computationally efficient even for large networks. We then formulate a quadratic assignment problem (QAP) to map the abstract topology into the physical network to achieve optimal load balancing for given demand forecasts, which we solve using randomized heuristics. Numerical results on several example networks illustrate the performance and computational efficiency of our method. A graphical design tool has been developed based on our algorithms},
	keywords = {bandwidth allocation, Computational efficiency, Computer networks, Cost function, Demand forecasting, demand forecasts, graph theory, graphical design tool, Internet telephony, Linear programming, Load forecasting, Load management, Network topology, optimal design, optimal load balancing, optimisation, performance, quadratic assignment problem, random graphs, randomised algorithms, randomized heuristics, Signal design, signaling networks, Switches, telecommunication signalling, topology design},
	isbn = {0-7803-5880-5},
	doi = {10.1109/INFCOM.2000.832245},
	author = {Srinivasan, Aravind and Ramakrishnan,K. G and Kumaran,K. and Aravamudan,M. and Naqvi,S.}
}
