The past few years have brought a major surge in the volumes of collected data. More and more enterprises and research institutions find tremendous value in data analysis and exploration. Big Data analytics is used for improving customer experience, perform complex weather data integration and model prediction, as well as personalized medicine and many other services. Advances in technology, along with high interest in big data, can only increase the demand on data collection and mining in the years to come. As a result, and in order to keep up with the data volumes, data processing has become increasingly distributed. However, most of the distributed processing for large data is done by batch processing and interactive exploration is hardly an option. To efficiently support queries over large amounts of data, appropriate indexing mechanisms must be in place. This dissertation proposes an indexing and query processing framework that can run on top of a distributed computing engine, to support fast, interactive data explorations in data warehouses. Our data processing layer is built around bit-vector based indices. This type of indexing features fast bit-wise operations and scales up well for high dimensional data. Additionally, compression can be applied to reduce the index size, and thus utilize less memory and network communication. Our work can be divided into two areas: index compression and query processing. Two compression schemes are proposed for sparse and dense bit-vectors. The design of these encoding methods is hardware-driven, and the query processing is optimized for the available computing hardware. Query algorithms are proposed for selection, aggregation, and other specialized queries. The query processing is supported on single machines, as well as computer clusters.

Dès qu’on manipule des ordres partiels (des hiérarchies), il est naturel de se demander comment les représenter dans un système informatique. Parmi les solutions proposées dans la littérature, on retrouve le codage par vecteur de bits. Dans cette thèse, nous nous intéressons au problème de calcul d’un codage des ordres par vecteur de bits de taille minimale, aussi connu par le problème de calcul de la 2-dimension des ordres, qui est NP-complet. Nous proposons des solutions du problème de nature heuristique, pour le cas général et pour des classes d’ordres particulières.Cette thèse présente également des résultats sur des conjectures autour de la 2-dimension des arbres. Notamment celle de Habib et al. à propos de la 2-approximabilité de la 2-dimension des arbres. Nous proposons quelques pistes de preuve de cette conjecture puis une reformulation, permettant d’apporter un nouveau regard sur le problème en question et d’espérer trouver des codages des ordres par vecteur de bits efficaces et de taille inférieure à leur 2-dimension. Nous apportons une réponse négative à deux autres conjectures. / The main question asked when manipulating partial orders (hierarchies), is how to represent them in computer. Among solutions proposed in literature, there is the bit-vector encoding. In this thesis, we consider the problem of computing a bit-vector encoding of orders with minimal size, which is also known as the problem of computing the2-dimension of orders that is NP-complete. We propose heuristics solutions of the problem for the general case and for some particular order classes. In addition, this thesis presents some results about conjectures on the 2-dimension of trees. Especially, the conjecture of Habib et al. about the 2-approximability of the 2-dimension of trees. We propose some ideas of a proof of this conjecture then give a reformulation of it that brings new perspectives on the problem that are finding efficient bits-vector encodings of orders of size less than their 2-dimension. We disprove two other conjectures.

Indiana University-Purdue University Indianapolis (IUPUI) / Current mainstream computing systems have become increasingly complex. Most of which have Central Processing Units (CPUs) that invoke multiple threads for their computing tasks. The growing issue with these systems is resource contention and with resource contention comes the risk of encountering a deadlock status in the system. Various software and hardware approaches exist that implement deadlock detection/avoidance techniques; however, they lack either the speed or problem size capability needed for real-time systems. The research conducted for this thesis aims to resolve issues present in past approaches by converging the two platforms (software and hardware) by means of the Graphics Processing Unit (GPU). Presented in this thesis are two GPU-based deadlock detection algorithms and one GPU-based deadlock avoidance algorithm. These GPU-based algorithms are: (i) GPU-OSDDA: A GPU-based Single Unit Resource Deadlock Detection Algorithm, (ii) GPU-LMDDA: A GPU-based Multi-Unit Resource Deadlock Detection Algorithm, and (iii) GPU-PBA: A GPU-based Deadlock Avoidance Algorithm. Both GPU-OSDDA and GPU-LMDDA utilize the Resource Allocation Graph (RAG) to represent resource allocation status in the system. However, the RAG is represented using integer-length bit-vectors. The advantages brought forth by this approach are plenty: (i) less memory required for algorithm matrices, (ii) 32 computations performed per instruction (in most cases), and (iii) allows our algorithms to handle large numbers of processes and resources. The deadlock detection algorithms also require minimal interaction with the CPU by implementing matrix storage and algorithm computations on the GPU, thus providing an interactive service type of behavior. As a result of this approach, both algorithms were able to achieve speedups over two orders of magnitude higher than their serial CPU implementations (3.17-317.42x for GPU-OSDDA and 37.17-812.50x for GPU-LMDDA). Lastly, GPU-PBA is the first parallel deadlock avoidance algorithm implemented on the GPU. While it does not achieve two orders of magnitude speedup over its CPU implementation, it does provide a platform for future deadlock avoidance research for the GPU.