Modern Astrophysics is one of the most data intensive research fields in the world and is driving many of the required innovations in the 'big data' space. Foremost in astronomy in terms of data generation is ...
详细信息
ISBN:
(纸本)9781450349130
Modern Astrophysics is one of the most data intensive research fields in the world and is driving many of the required innovations in the 'big data' space. Foremost in astronomy in terms of data generation is radio astronomy, and in the last decade an increase in global interest and investment in the field had led to a large number of new or upgraded facilities which are each currently generating petabytes of data per annum. The peak of this so-called 'radio renaissance' will be the Square Kilometre Array (SKA) - a global observatory designed to uncover the mysteries of the Universe. The SKA will create the highest resolution, fastest frame rate movie of the evolving Universe ever and in doing so will generate 160 terrabytes of data a day, or close to 5 zettabytes of data per annum. Furthermore, due to the extreme faintness of extraterrestrial radio signals, the telescope elements for the SKA must be located in radio quite parts of the world with very low population density. Thus the project aims to build the most data intensive scientific experiment ever, in some of the most remote places on Earth. Generating and serving scientific data products of this scale to a global community of researchers from remote locations is just the first of the 'big data' challenges the project faces. Coordination of a global network of tiered data resources will be required along with software tools to exploit the vast sea of results generated. In fact, to fully realize the enormous scientific potential of this project, we will need not only better data distribution and coordination mechanisms, but also improved algorithms, artificial intelligence and ontologies to extract knowledge in an automated way at a scale not yet attempted in science. In this keynote I will present an overview of the SKA project, outline the 'big data' challenges the project faces and discuss some of the approaches we are taking to tame the astronomical data deluge we face.
The bipartite Star123-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star123-free graphs a linear time algorithm of J...
详细信息
The bipartite Star123-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star123-free graphs a linear time algorithm of J. L. Fouquet, V. Giakoumakis and J. M. Vanherpe for finding a maximum matching in bipartite Star123, P7-free graphs presented in [2]. Our algorithm is a solution of Lozin’s conjecture.
Image matching under rotation is a computational problem to determine for two given images A and B a rotation of A that most accurately resembles B. The research in combinatorial pattern matching led to a series of im...
详细信息
Image matching under rotation is a computational problem to determine for two given images A and B a rotation of A that most accurately resembles B. The research in combinatorial pattern matching led to a series of improved algorithms which commonly solve this problem by a sophisticated search in the set of all rotations of A. This paper provides the lower bound Omega(n3) on the worst case cardinality of this set for images of size n x n and presents the first optimal algorithm of such kind, i.e., one that solves image matching under rotations in time Omega(n(3)). Moreover, for image matching under compositions of rotation and scaling a new lower bound Omega(n(6)/log n) on the worst case cardinality of the set of rotated and scaled transformations of an n x n image is provided. This bound almost matches the upper bound Omega(n(6)). (C) 2010 Elsevier B.V. All rights reserved.
Molecular biology has posed a number of fascinating and sometimes daunting computational problems, which came naturally expressed in its native language of character strings. Through the years, some such problems have...
详细信息
Molecular biology has posed a number of fascinating and sometimes daunting computational problems, which came naturally expressed in its native language of character strings. Through the years, some such problems have found elegant and even useful solutions in response to the needs that originally motivated them. What is perhaps even more remarkable, several of the ideas inspired by computational molecular biology have found application in remote and diverse domains, so that it may be argued that molecular biology did more for computing than the latter did for it. As a modest tribute, this paper reviews a small sample of these cases drawing from the personal exposure of the author.
The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit desi...
详细信息
The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit design, synchronous systems, computer systems, and very-large-scale integration (VLSI) circuits. The FVS problem is known to be NP-hard for simple graphs, but polynomi-al-time algorithms have been found for special classes of graphs. The intersection graph of a collection of arcs on a circle is called a circular-arc graph. A normal Helly circular-arc graph is a proper subclass of the set of circular-arc graphs. In this paper, we present an algorithm that takes time to solve the FVS problem in a normal Helly circular-arc graph with n vertices and m edges.
In this paper, we define a family of patterns with don't cares occurring in a text. We call them primitive patterns. The set of primitive patterns forms a basis for all the maximal patterns occurring in the text. ...
详细信息
In this paper, we define a family of patterns with don't cares occurring in a text. We call them primitive patterns. The set of primitive patterns forms a basis for all the maximal patterns occurring in the text. The number of primitive patterns is smaller than other known basis. We present an incremental algorithm that computes the primitive patterns occurring at least q times in a text of length n, given the N primitive patterns occurring at least q - 1 times, in time O(|Sigma| Nn(2) log n), where Sigma is the alphabet. In the particular case where q = 2, the complexity in time is only O(|Sigma| n(2) log n). We also give an algorithm that decides if a given pattern is primitive in a given text. These algorithms are generalized, taking many sequences in input. Finally, we give a solution for reducing the number of patterns of interest by using scoring techniques, as we show that the number of primitive patterns is exponential. (C) 2004 Elsevier B. V. All rights reserved.
In this paper, we study an semi-online version of bin stretching problem on m parallel identical machines. Where the jobs arrive sorted by non-increasing processing times. We propose an semi-online algorithm and prove...
详细信息
In this paper, we study an semi-online version of bin stretching problem on m parallel identical machines. Where the jobs arrive sorted by non-increasing processing times. We propose an semi-online algorithm and prove that the competitive ratio of the algorithm is at most 1 + m-1-4m-2 < 5/4. We also show that the lower bound of the problem is at least 10/9.
We carry out an experimental analysis of a number of shortest-path (routing) algorithms investigated in the context of the TRANSIMS (TRansportation analysis and SIMulation System) project. The main focus of the paper ...
详细信息
暂无评论