Clustering Constrained Data without Locality Property