Full-Text (Substring) Indexes in External Memory

Marina Barsky is a Post-Doctoral Fellow in the Department of Computer Science at the University of Illinois at Urbana[1]Champaign, US. She received her PhD in Computer Science from the University of Victoria, British Columbia, Canada in 2010. Her PhD research was dedicated to better construction of full-text indexes using disk. Currently she expands her expertise in database management to the field of data mining. Alex Thomo is an Associate Professor in the Department of Computer Science at the University of Victoria, British Columbia, Canada. He received his PhD in Computer Science from Concordia University of Montreal in 2003. Before joining UVic, he was a software engineer for Ericsson Inc, and Assistant Professor at Suffolk University in Boston. His main research is on theoretical and practical aspects of semistructured and graph databases, with a current focus on social and biological networks, automata-based techniques, and index structures for textual data. Ulrike Stege is an Associate Professor in the Department of Computer Science at the University of Victoria, British Columbia, Canada. She received her PhD in Computer Science from the ETH Zürich – a Science and Technology University in Zürich, Switzerland, in year 2000. Her main research interests are interdisciplinary, including the areas of Parameterized Complexity, Computational Biology, Cognitive Science and Human Problem Solving, and Computer Science Education.

• Structures for Indexing Substrings.- External Construction of Suffix Trees.- Scaling Up: When the Input Exceeds the Main Memory.- Queries for Disk-based Indexes.- Conclusions and Open Problems.