Information Extraction (IE) is an emerging technology to transform unstructured textual information into a structured knowledge base. With the potential to analyze the structured information, IE significantly improves analysts ability to see underlying trends and to discover the unexpected, in various domains. IE research in counter-terrorism has been mushrooming after the 9/11 attack. A huge data warehouse on surveillance, that is freely available for training and testing, has become the major support to this research. Link Analysis is a topic in IE focusing on possible link detection between concepts across multiple documents. This paper presents some of the recently developed link analysis tools and approaches to detecting potentially interesting links in surveillance data. The related challenges and issues arising within the research are explored and discussed. © 2010 IEEE.