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.

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

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.