Gnutella-like peer-to-peer file-sharing systems have been widely deployed on the Internet. However, current search techniques used in existing Gnutella-like peer-to-peer systems are often inefficient. We demonstrated the strong “small-world” property of Gnutella systems and proposed an efficient search approach CSTM to utilize the property. In CSTM, each peer maintains a local state table, which contains keyword information of data on all neighbors within T hops to guide query. A new data structure based on Bloom Filter is introduced to represent the state table compactly to reduce storage and bandwidth cost. Query cache is also adopted to utilize query locality and build shortcut connections to lately accessed peers. Simulations show that CSTM can reduce message cost remarkably while maintaining short search path length compared with flooding or random forwarding algorithm.