Clustering is spotting pattern in a group of objects and resultantly grouping\nthe similar objects together. Objects have attributes which are not always\nnumerical, sometimes attributes have domain or categories to which they could\nbelong to. Such data is called categorical data. To group categorical data many\nclustering algorithms are used, among which k- modes algorithm has so far given\nthe most significant results. Nevertheless, there is still a lot which could be\nimproved. Algorithms like k-means, fuzzy-c-means or hierarchical have given far\nbetter accuracies with numerical data. In this paper, we have proposed a novel\ndistance metric, similarity-based distance (SBD) to find the distance between\nobjects of categorical data. Experiments have shown that our proposed distance\n(SBD), when used with the SBC (space structure based clustering) type algorithm\nsignificantly outperforms the existing algorithms like k-modes or other SBC\ntype algorithms when used on categorical datasets.\n