Use of published organizational data for a variety of purposes has the chance of violation of leakage of individual secret information. Though this is taken care by the organizations by removal or encryption of explicit identifiers, valuable information may still be leaked by quasi identifiers in the released data. The concept of k-anonymity was introduced and several algorithms in this direction have been proposed by different researchers [1, 2, 3, 4, 5, 6, 7, 8, 11] to handle this problem. But the notion of k-anonymity is susceptible to two types of attacks which necessitated the requirement of a better privacy preserving notion leading to the proposal of l- diversity [6]. In [14] a third phase is added to the two phase clustering-based k-anonymisation algorithm OKA [4] to achieve l-diversity. Recently, the clustering stage of the algorithm has been improved in [14] and the diversity stage algorithm is improved in [16] to come up with a fast l-diversity algorithm which deals with a single sensitive attribute in a relational table. Our main contribution in this paper is to develop an l-diversity algorithm to handle multi-sensitive attributes in databases. Also, we shall improve the adjustment stage algorithm so that it becomes more efficient. We also analyse and provide enough reasons to show that though the second and third stages of the algorithm are not necessary in most of the cases, we cannot avoid using these two stages in some cases. © 2011 IEEE.