A k nearest neighbor query q retrieves k objects that lie closest to the query point q among a given set of objects P. With the availability of inexpensive location aware mobile devices, the continuous monitoring of such queries has gained lot of attention and many methods have been proposed for continuously monitoring the kNNs in highly dynamic environment. Multiple continuous queries require real-time results and both the objects and queries issue frequent location updates. Most popular spatial index, R-tree, is not suitable for continuous monitoring of these queries due to its inefficiency in handling frequent updates. Recently, the interest of database community has been shifting towards using grid-based index for continuous queries due to its simplicity and efficient update handling. For kNN queries, the order in which cells of the grid are accessed is very important. In this research, we present two efficient and effective grid access methods, CircularTrip and ArcTrip, that ensure that the number of cells visited for any continuous kNN query is minimum. Our extensive experimental study demonstrates that CircularTrip-based continuous kNN algorithm outperforms existing approaches in terms of both efficiency and space requirement. Moreover, we show that CircularTrip and ArcTrip can be used for many other variants of nearest neighbor queries like constrained nearest neighbor queries, farthest neighbor queries and (k + m)-NN queries. All the algorithms presented for these queries preserve the properties that they visit minimum number of cells for each query and the space requirement is low. Our proposed techniques are flexible and efficient and can be used to answer any query that is hybrid of above mentioned queries. For example, our algorithms can easily be used to efficiently monitor a (k + m) farthest neighbor query in a constrained region with the flexibility that the spatial conditions that constrain the region can be changed by the user at any time.

Thesis (Ph. D.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Computer Science, 2009. / Includes bibliographical references.

Στην παρούσα διατριβή αντιμετωπίζεται το πρόβλημα της παροχής επιστημονικού λογισμικού σαν υπηρεσία διαδικτύου, με έμφαση στις εφαρμογές χρονοπρογραμματισμού ανθρώπινων πόρων. Οι εφαρμογές αυτές χαρακτηρίζονται από ειδικές ανάγκες ως προς το περιβάλλον υλικού και λογισμικού, ανήκοντας στο γενικότερο χώρο των NP-hard προβλημάτων βελτιστοποίησης. Δημιουργήθηκαν και παρουσιάζονται δύο πλατφόρμες παροχής υπηρεσιών, SchedSP και SchedSP-WS, με στόχο να παρέχουν υπηρεσίες λειτουργικού συστήματος στους δημιουργούς εφαρμογών ιστού, ενώ παρέχονται ειδικές υπηρεσίες για την υποστήριξη εφαρμογών χρονοπρογραμματισμού. Η απαιτούμενη υπολογιστική χωρητικότητα εξασφαλίστικε αρχικά από το σύστημα PLEIADES, που επίσης παρουσιάζεται ως πάροχος υπολογιστικής υποδομής σαν υπηρεσιά, το οποίο αργότερα αντικαταστάθηκε από την υποδομή του ευρωπαϊκού έργου υποδομής EGEE. Επίσης, παρουσιάζεται ένα μοντέλο κατανεμημένης εφαρμογής χρονοπρογραμματισμού, το οποίο αποτελεί τη βάση του πλαισίου SchedScripter. Το πλαίσιο SchedScripter που επίσης παρουσιάζεται, επιτρέπει τη δημιουργία κατανεμημένων εφαρμογών χρονοπρογραμματισμού, βασισμένων στο υπολογιστικό πλέγμα. / This PhD dissertation deals with the provision of scientific software as Internet service, with emphasis on human resources scheduling applications. These applications have special needs from the computational environment, in terms of software and hardware, as they are NP-hard optimization problems. Two application service provider platforms have been created and presented, SchedSP and SchedSP-WS, aiming to offer operating system like services to web application developers, while they offer special support for scheduling applications. The required computational capacity initially was provided by PLEADES, which is also presented as a computational infrastructure service provider, to be substituded later by the EU infrastructures project EGEE. A distributed scheduling application model is presented, which is the foundation of the SchedScripter framework. The SchedScripter framework, which is also presented, enables the creation of distributed scheduling applications, running on a computational grid.

This thesis presents the author's contribution <p>to the design and implementation of COOLFluiD,<p>an object oriented software platform for <p>the high performance simulation of multi-physics phenomena on unstructured grids. In this context, the final goal has been to provide a reliable tool for handling high speed aerothermodynamic <p>applications. To this end, we introduce a number of design techniques that have been developed in order to provide the framework with flexibility<p>and reusability, allowing developers to easily integrate new functionalities such as arbitrary mesh-based data structures, numerical algorithms (space discretizations, time stepping schemes, linear system solvers, ),and physical models. <p>Furthermore, we describe the parallel algorithms <p>that we have implemented in order to efficiently <p>read/write generic computational meshes involving <p>millions of degrees of freedom and partition them <p>in a scalable way: benchmarks on HPC clusters with <p>up to 512 processors show their effective suitability for large scale computing. <p>Several systems of partial differential equations, <p>characterizing flows in conditions of thermal and <p>chemical equilibrium (with fixed and variable elemental fractions)and, particularly, nonequilibrium (multi-temperature models) <p>have been integrated in the framework. <p>In order to simulate such flows, we have developed <p>two state-of-the-art flow solvers: <p>1- a parallel implicit 2D/3D steady and unsteady cell-centered Finite Volume (FV) solver for arbitrary systems of PDE's on hybrid unstructured meshes; <p>2- a parallel implicit 2D/3D steady vertex-centered Residual Distribution (RD) solver for arbitrary systems of PDE's on meshes with simplex elements (triangles and tetrahedra). <p>The FV~code has been extended to handle all <p>the available physical models, in regimes ranging from incompressible to hypersonic. <p>As far as the RD code is concerned, the strictly conservative variant of the RD method, denominated CRD, has been applied for the first time in literature to solve high speed viscous flows in thermochemical nonequilibrium, yielding some preliminary outstanding results on a challenging double cone flow simulation. <p>All the developments have been validated on real-life testcases of current interest in the aerospace community. A quantitative comparison with experimental measurements and/or literature has been performed whenever possible. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

<p>La tolérance et la gestion des fautes dans les grilles de données/calcul est d’une importance capitale. En effet, comme dans tout autre système distribué, les composants d’une grille sont susceptibles de tomber en panne à tout moment. Mais le risque de panne croît avec la taille du système, et est donc plus exacerbé dans un système de grille. En plus, tout en essayant de mettre à profit les ressources offertes par la grille, les applications tournant sur celle-ci sont de plus en plus complexes (ex. impliquent des interactions complexes, prennent des jours d’exécution), ce qui les rend plus vulnérables aux fautes. Le plus difficile dans la gestion des fautes dans une grille, c’est qu’il est difficile de savoir si une faute qui survient sur une entité de la grille est induite malicieusement ou accidentellement.<p><p>Dans notre travail de thèse, nous utilisons le terme faute, au sens large, pour faire référence à tout étant inattendu qui survient sur tout composant de la grille. Certains de ces états provoquent des comportements aussi inattendus et perceptibles au niveau de la grille tandis que d’autres passent inaperçues. De plus, certaines de ces fautes sont le résultat d’une action malveillante alors que d’autres surviennent accidentellement ou instantanément. Dans ce travail de thèse, nous avons traité le cas de ces fautes induites malicieusement, et qui généralement passent inaperçues. Nous avons considéré en particulier le problème de la confidentialité et de l’intégrité des données stockées à long-terme sur la grille.<p><p>L’étude de la confidentialité des données a été faite en deux temps dont la première partie concerne la confidentialité des données actives. Dans cette partie, nous avons considéré une application liée à la recherche des similitudes d’une séquence d’ADN dans une base de données contenant des séquences d’ADN et stockée sur la grille. Pour cela, nous avons proposé une méthode qui permet d’effectuer la comparaison sur un composant distant, mais tout en gardant confidentielle la séquence qui fait l’objet de la comparaison. <p>Concernant les données passives, nous avons proposé une méthode de partage des données confidentielles et chiffrés sur la grille.<p> <p>En rapport avec l’intégrité des données, nous avons considéré le cas des données anonymes dans le cadre de l’intégrité des données passives. Pour les données actives, nous avons considéré le problème de la corruption des jobs exécutés sur la grille. Pour chacune des cas, nous avons proposé des mécanismes permettant de vérifier l’authenticité des données utilisées ou produites par ces applications.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

No description available.

A computational grid is a hardware and software infrastructure that provides dependable, consistent, pervasive, and inexpensive access to high-end computational capabilities. In the presence of grid users who are autonomous, rational, and intelligent, there is an overall degradation of the total efficiency of the computational grid in comparison to what can be achieved when the participating users are centrally coordinated . This loss in efficiency might arise due to an unwillingness on the part of some of the grid resource providers to either not perform completely or not perform to the fullest capability, the computational jobs of other users in the grid. In this thesis, our attention is focused on designing grid resource procurement mechanisms which a grid user can use for procuring resources in a computational grid based on bids submitted by autonomous, rational, and intelligent resource providers. Specifically, we follow a game theoretic and mechanism design approach to design three elegant, different incentive compatible procurement mechanisms for this purpose: G-DSIC (Grid-Dominant Strategy Incentive Compatible) mechanism which guarantees that truthful bidding is a best response for each resource provider, irrespective of what the other resource providers bid G-BIC (Grid-Bayesian Nash Incentive Compatible) mechanism which only guarantees that truthful bidding is a best response for each resource provider whenever all other resource providers also bid truthfully G-OPT (Grid-Optimal) mechanism which minimizes the cost to the grid user, satisfying at the same time, (1) Bayesian Incentive Compatibility (which guarantees that truthful bidding is a best response for each resource provider whenever all other resource providers also bid truthfully) and (2) Individual Rationality (which guarantees that the resource providers have non-negative payoffs if they participate in the bidding process). We evaluate the relative merits and demerits of the above three mechanisms using game theoretical analysis and numerical experiments. The mechanisms developed in this thesis are in the context of parameter sweep type of jobs, which consist of multiple homogeneous and independent tasks. We believe the use of the mechanisms proposed transcends beyond parameter sweep type of jobs and in general, the proposed mechanisms could be extended to provide a robust way of procuring resources in a computational grid where the resource providers exhibit rational and strategic behavior.

Indiana University-Purdue University Indianapolis (IUPUI) / This thesis proposes an automated grid-based alignment system utilizing lasers and an array of light-detecting photodiodes. The intent is to create an inexpensive and scalable alignment system for pick-and-place robotic systems. The system utilizes the transformation matrix, geometry, and trigonometry to determine the movements to align the robot with a grid-based array of photodiodes. The alignment system consists of a sending unit utilizing lasers, a receiving module consisting of photodiodes, a data acquisition unit, a computer-based control system, and the robot being aligned. The control system computes the robot movements needed to position the lasers based on the laser positions detected by the photodiodes. A transformation matrix converts movements from the coordinate system of the grid formed by the photodiodes to the coordinate system of the robot. The photodiode grid can detect a single laser spot and move it to any part of the grid, or it can detect up to four laser spots and use their relative positions to determine rotational misalignment of the robot. Testing the alignment consists of detecting the position of a single laser at individual points in a distinct pattern on the grid array of photodiodes, and running the entire alignment process multiple times starting with different misalignment cases. The first test provides a measure of the position detection accuracy of the system, while the second test demonstrates the alignment accuracy and repeatability of the system. The system detects the position of a single laser or multiple lasers by using a method similar to a center-of-gravity calculation. The intensity of each photodiode is multiplied by the X-position of that photodiode. The summed result from each photodiode intensity and position product is divided by the summed value of all of the photodiode intensities to get the X-position of the laser. The same thing is done with the Y-values to get the Y-position of the laser. Results show that with this method the system can read a single laser position value with a resolution of 0.1mm, and with a maximum X-error of 2.9mm and Y-error of 2.0mm. It takes approximately 1.5 seconds to process the reading. The alignment procedure calculates the initial misalignment between the robot and the grid of photodiodes by moving the robot to two distinct points along the robot’s X-axis so that only one laser is over the grid. Using these two detected points, a movement trajectory is generated to move that laser to the X = 0, Y = 0 position on the grid. In the process, this moves the other three lasers over the grid, allowing the system to detect the positions of four lasers and uses the positions to determine the rotational and translational offset needed to align the lasers to the grid of photodiodes. This step is run in a feedback loop to update the adjustment until it is within a permissible error value. The desired result for the complete alignment is a robot manipulator positioning within ±0.5mm along the X and Y-axes. The system shows a maximum error of 0.2mm in the X-direction and 0.5mm in the Y-direction with a run-time of approximately 4 to 5 minutes per alignment. If the permissible error value of the final alignment is tripled the alignment time goes down to 1 to 1.5 minutes and the maximum error goes up to 1.4mm in both the X and Y-directions. The run time of the alignment decreases because the system runs fewer alignment iterations.