Plenary Lecture

Fast Information Retrieval for Textual and Geometrical Applications

Professor Vaclav Skala
Center of Computer Graphics and Visualization
Department of Computer Science and Engineering
Faculty of Applied Sciences
University of West Bohemia
Department of Computer Science
Faculty of Electrical Engineering and Computer Science
VSB-Technical University of Ostrava
Czech Republic
E-mail: skala@kiv.zcu.cz

Abstract: Today, datasets are becoming extremely large. One of the main problems is a retrieval of an item from the dataset for the given key. Of course, the index-sequential and other data techniques can be used. Nevertheless the computational complexity is high as the search in the index table is at least of O(lgN) complexity. One well known technique is hashing where a query for an item is made with O(1) expected complexity if the hash function is so called perfect hash function (PFH). The problem is that PFH is generally very expensive to construct especially for large data sets. In today’s applications it is necessary to process textual data and geometrical data as well. It should be noted that the longest word has 189 819 characters (the largest protein - titin), the longest word used in printed text has been 1 909 characters. The geometrical data has to usually handle 105-109 points in E3. It seems to that the requirements for textual and geometrical hash functions will be quite different.
We will present a unifying approach to hashing in general including methodology how the hash function is to be constructed. This approach leads to very short clusters and therefore to significant speed up as well. The approach has been extensively tested for textual and geometrical large data sets.

Brief Biography of the Speaker: Prof. Vaclav Skala is a Full professor of Computer Science at the University of West Bohemia, Plzen and VSB-Technical University Ostrava, Czech Republic. He received his ING.(equivalent of MSc.) degree in 1975 from the Institute of Technology in Plzen and CSc. (equivalent of Ph.D.) degree from the Czech Technical University in Prague in 1981. In 1996 he became a full professor in Computer Science. In 1997 the Center of Computer Graphics and Visualization (CCGV) was formally established and since then he is the Head of the CCGV in Plzen (http://Graphics.zcu.cz).
Prof.Vaclav Skala is an associate editor of The Visual Computer (Springer), Computers and Graphics (Elsevier), member of the Editorial Board fo Machine Graphics and Vision (Polish Academy of Sciences) and the Editor in Chief of the Journal of WSCG. He is a member of international program committees of prestigious conferences and workshops. He is a member of ACM SIGGRAPH, IEEE and Eurographics Association.
Prof.Vaclav Skala has published over 200 research papers at conferences and research journals. His current research interests are computer graphics and visualization, mathematics, especially geometrical algebra, algorithms and data structures.
Details can be found at http://www.VaclavSkala.eu.