In this paper, we develop a framework of trajectory search, called pattern-aware trajectory search (abbreviated as PATS). Given a set of trajectories, potential regions are extracted first and potential regions are viewed as popular regions interested by users. Furthermore, potential regions are organized as a region transition graph, where each vertex is a potential region and edges capture sequential travels of potential regions from a set of trajectories given. By exploring the concept of random walk, the attractiveness of a potential region is derived. In light of attractiveness of potential regions, the attractiveness of a trajectory is formulated and PATS will return top-K trajectories according to their attractiveness. We evaluated our framework by a real GPS dataset. Experimental results show that PATS is able to retrieve trajectories interested by users.