An important application of sequential mining technique is frequent traversal sequence (FTS) mining. However, the web data grows quickly, some data may be outdated, and previous FTS may be changed when the database is updated. We have to re-mine FTS from the updated database, but re-finding FTS will consume too much execution time. In this paper, a novel structure, IE-LATTICE (improved extended lattice) is designed to store the previous FTS. An efficient algorithm based on bidirectional constraint, IMFTS (incremental mining frequent traversal sequence) is proposed, which utilizes the previous mining results and constraint strategy to discover the new FTS just from the added and deleted part of the database. Experimental results show that IMFTS algorithm efficiently reduces the execution time for mining FTS.