An approach is provided for discovering social ties among users based on cloaked trajectories. In a method, cloaked regions of a first trajectory of a first user and cloaked regions of a second trajectory of a second user are transformed to corresponding semantic regions, respectively, wherein a semantic region is expressed with a semantic meaning of a corresponding cloaked region. The transformed semantic regions are mapped into nodes of a hierarchical semantic tree, wherein each node of the hierarchical semantic tree corresponds to a semantic region. According to relationships between nodes mapped to semantic regions of the first trajectory and node mapped to the semantic regions of the second trajectory, social ties among the first user and the second user can be inferred.