Name
Abstract | ||
|---|---|---|
A decomposition of a binary matrix into two matrices gives a set of basis vectors and their appropriate combination to form the original matrix. Such decomposition solutions are useful in a number of application domains including text mining, role engineering as well as knowledge discovery. While a binary matrix can be decomposed in several ways, however, certain decompositions better characterize the semantics associated with the original matrix in a succinct but comprehensive way. Indeed, one can find different decompositions optimizing different criteria matching various semantics. In this paper, we first present a number of variants to the optimal Boolean matrix decomposition problem that have pragmatic implications. We then present a unified framework for modeling the optimal binary matrix decomposition and its variants using binary integer programming. Such modeling allows us to directly adopt the huge body of heuristic solutions and tools developed for binary integer programming. Although the proposed solutions are applicable to any domain of interest, for providing more meaningful discussions and results, in this paper, we present the binary matrix decomposition problem in a role engineering context, whose goal is to discover an optimal and correct set of roles from existing permissions, referred to as the role mining problem (RMP). This problem has gained significant interest in recent years as role based access control has become a popular means of enforcing security in databases. We consider several variants of the above basic RMP, including the min-noise RMP, delta-approximate RMP and edge-RMP. Solutions to each of them aid security administrators in specific scenarios. We then model these variants as Boolean matrix decomposition and present efficient heuristics to solve them. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/ICDE.2008.4497438 | ICDE |
Keywords | Field | DocType |
decomposition solution,optimal boolean matrix decomposition,binary matrix,boolean algebra,optimal binary matrix decomposition,integer programming,role mining problem,certain decomposition,different decomposition,basic rmp,role engineering,original matrix,binary matrix decomposition problem,knowledge discovery,data mining,boolean matrix decomposition,text mining,binary integer programming,knowledge engineering,data security,access control,data engineering,matrix decomposition,role based access control,linear programming,databases,security | Data mining,Heuristic,Logical matrix,Matrix (mathematics),Computer science,Matrix decomposition,Theoretical computer science,Integer programming,Heuristics,Boolean algebra,Linear programming,Database | Conference |
ISSN | ISBN | Citations |
1084-4627 | 978-1-4244-1837-4 | 91 |
PageRank | References | Authors |
3.24 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haibing Lu | 1 | 357 | 24.88 |
| Jaideep Vaidya | 2 | 2778 | 171.18 |
| Vijayalakshmi Atluri | 3 | 3256 | 424.98 |