Exact match search in sequence data using suffix trees Mihail Halachev, Nematollaah Shiri, and Anand Thamildurai   View Paper (PDF)   Return to KM-2 (Knowledge Management): Index Structures Abstract . To study the performance of STA and STA-DF, we develop a memory efficient ST-based Exact Match (STEM) search algorithm. We implemented STEM and both representations of ST and conducted extensive experiments. Our results indicate that the STA and STA-DF representations are very similar in construction time, storage utilization, and search time using STEM. In terms of the access patterns by STEM, our results show that compared to STA, the STA-DF representation exhibits better spatial and sequential locality of reference. This suggests that STA-DF would require less number of disk I/Os, and hence is more amenable to efficient and scalable disk-based computation. ©2006 Association for Computing Machinery