A prevalent co-location pattern (PCP) depicts a set of features that it’s instances are frequently located closely and form a neighbor relationship with each other. The selection of proper methods for constructing neighbor relationships is significantly important in PCP mining. Many finding neighbor methods have proposed, however they still have limitations, e.g., some of them perform worse at noise datasets and/or heterogeneous density datasets, while some have too many parameters to fine-tune, and so on. This paper introduces a more proper algorithm for generating neighborhoods for discovering PCPs. First, the unique set of neighbors for each instance is formed after four filtering stages considering both density and connectivity. Then, an improvement of a state-of-the-art algorithm, clique-based method, is utilized to mine PCPs. The experiment results show that our algorithm not only yields much less candidates but also is 50–100 times faster than the original method. Moreover, the designed algorithm exhibits greater robustness due to its parameter-free nature.