Content area
High-dimensional search problems are fundamental to many domains, including data analysis, cryptography and computer security. As data complexity and volume increase, traditional search methods become inefficient, necessitating novel approaches to optimize performance. This dissertation presents three primary search strategies across two distinct high-dimensional spaces: Euclidean space and Hamming space.
For Euclidean spaces, we introduce Coordinate Oblivious Similarity Search (COSS) and Multi-Space Tree with Incremental Construction (MiSTIC), two indexing techniques designed to mitigate the curse of dimensionality. COSS employs metric-based indexing to accelerate range queries, while MiSTIC integrates coordinate- and metric-based strategies to improve performance across various dataset characteristics. Experimental results demonstrate that these approaches outperform existing state-of-the-art methods in efficiency and scalability.
In the domain of cryptographic key retrieval, we explore Noisy Probabilistic Response-Based Cryptography (npRBC), a method for authenticating devices in high-noise environments using Physical Unclonable Functions (PUFs). We further develop npRBC-GPU, a GPU-accelerated variant that significantly enhances search throughput compared to its CPU counterpart. Additionally, we investigate optimization techniques for rapid seed generation in cryptographic searches, addressing computational bottlenecks in permutation-based key matching.
By leveraging parallel processing on both CPUs and GPUs, this dissertation provides novel methodologies for efficiently navigating high-dimensional search spaces. These contributions have broad implications for fields such as high-performance computing, cybersecurity, and data science, offering scalable approaches to computationally intensive search problems.