Plenary lecture 10: multi-key search algorithms - a new paradigm in algorithm design
A. Tarek Abouelfadl Mohamed · 2009
This talk is a consolidated representation of my recent research findings. Search algorithms are fundamental to the computing sciences with intensive database applications. So far, a significant amount of efforts has been set forth to improving the computer-based search strategies. Multi-element search techniques are relatively new in computer science. I have introduced this concept at the 8th World Multi-Conference on Systemics, Cybernetics and Informatics back in 2004. The multiple key search algorithms may effectively be combined with the traditional concepts prevailing in the data structure literature to optimize the computer-based resource requirements for certain applications. Further research in this area has appeared to be appealing in integrating these concepts with the traditional designs prevailing in the algorithmic. Among the most useful search algorithms, interpolation search uses the concept of projection for equally separated elements inside a given list. An extended multiple key interpolation search algorithm is developed and implemented, which has time and computational memory requirements much less than the other algorithms in this class with multiple key search criteria and equally separated list of elements. The idea of Block Search is to subdivide a given list of sorted elements into equally sized blocks, and then restrict the search effort into one of these blocks. The concept pertaining to multiple search elements fits nicely with the idea prevailing in Block Search. This hybrid algorithm has the best performance whenever an element to search for exists at each division point of each independent block within the current tier. In that event, the time required by the new algorithm is linear, and proportional to the number of elements to look for. It is also possible to sub-divide each independent block into multiple numbers of sub-blocks and then reapply the multiple element block search strategy to each independent block containing a number of sub-blocks. Though this increases the complexity of algorithm design, but due to the improved efficiency, the algorithm will require substantially less computational resources. The optimum number of tiers for the computational resources requirements is also investigated. The basic binary search technique may be combined with the multi-tier multiple key block search strategy.