{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T22:32:44Z","timestamp":1784068364993,"version":"3.55.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,7,1]],"date-time":"2010-07-01T00:00:00Z","timestamp":1277942400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["CNS-0746943IIS-0306838"],"award-info":[{"award-number":["CNS-0746943IIS-0306838"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0746943IIS-0306838"],"award-info":[{"award-number":["CNS-0746943IIS-0306838"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2010,7]]},"abstract":"<jats:p>\n                    Devising a complete and correct set of roles has been recognized as one of the most important and challenging tasks in implementing role-based access control. A key problem related to this is the notion of goodness\/interestingness\u2014when is a role good\/interesting? In this article, we define the\n                    <jats:italic toggle=\"yes\">Role Mining Problem<\/jats:italic>\n                    (RMP) as the problem of discovering an optimal set of roles from existing user permissions. The main contribution of this article is to formally define RMP and analyze its theoretical bounds. In addition to the above basic RMP, we introduce two different variations of the RMP, called the\n                    <jats:italic toggle=\"yes\">\u03b4-Approx RMP<\/jats:italic>\n                    and the\n                    <jats:italic toggle=\"yes\">minimal-noise RMP<\/jats:italic>\n                    that have pragmatic implications. We reduce the known \u201cSet Basis Problem\u201d to RMP to show that RMP is an NP-complete problem. An important contribution of this article is also to show the relation of the RMP to several problems already identified in the data mining and data analysis literature. By showing that the RMP is in essence reducible to these known problems, we can directly borrow the existing implementation solutions and guide further research in this direction. We also develop a heuristic solution based on the previously proposed FastMiner algorithm, which is very accurate and efficient.\n                  <\/jats:p>","DOI":"10.1145\/1805974.1805983","type":"journal-article","created":{"date-parts":[[2011,3,15]],"date-time":"2011-03-15T12:38:06Z","timestamp":1300192686000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":54,"title":["The role mining problem"],"prefix":"10.1145","volume":"13","author":[{"given":"Jaideep","family":"Vaidya","sequence":"first","affiliation":[{"name":"Rutgers University, Newark, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vijayalakshmi","family":"Atluri","sequence":"additional","affiliation":[{"name":"Rutgers University, Newark, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qi","family":"Guo","sequence":"additional","affiliation":[{"name":"Rutgers University, Newark, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,7,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/319171.319178"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/270152.270159"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1765751.1765769"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377836.1377838"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/872016.872162"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/266741.266767"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/501978.501980"},{"key":"e_1_2_1_8_1","unstructured":"Gallagher M. P. O'Connor A. C. and Kropp B. 2002. The economic impact of role-based access control. Planning report 02-1 National Institute of Standards and Technology."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman New York.","DOI":"10.5555\/578533"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Geerts F. Goethals B. and Mielikainen T. 2004. Tiling databases. In Discovery Science. Springer-Verlag Berlin 278--289.","DOI":"10.1007\/978-3-540-30214-8_22"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335372"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0964"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/507711.507718"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/775412.775435"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497438"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574357"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Workshop on Frequent Itemset Mining Implementations. CEUR, The Netherlands.","author":"Mielik\u00e4inen T.","year":"2003","unstructured":"Mielik\u00e4inen, T. 2003. Intersecting data to closed sets with constraints. In Proceedings of the Workshop on Frequent Itemset Mining Implementations. CEUR, The Netherlands."},{"key":"e_1_2_1_18_1","unstructured":"Miettinen P. 2006. The discrete basis problem master's thesis. M.S. thesis University of Helsinki."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3120676.3120711"},{"key":"e_1_2_1_20_1","volume-title":"Learning Theory and Kernel Machines: Proceedings of the 16th Annual Conference on Learning Theory and 7th Kernel Workshop (COLT\/Kernel'03)","author":"Mishra N.","unstructured":"Mishra, N., Ron, D., and Swaminathan, R. 2003. On finding large conjunctive clusters. In Learning Theory and Kernel Machines: Proceedings of the 16th Annual Conference on Learning Theory and 7th Kernel Workshop (COLT\/Kernel'03). Springer, Berlin, 448--462."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377836.1377840"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/507711.507717"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956832"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00333-0"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/344287.344308"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.485845"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/373256.373257"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1063979.1064008"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/775412.775434"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/784589.784658"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180424"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1805974.1805983","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1805974.1805983","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1805974.1805983","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:23:34Z","timestamp":1763457814000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1805974.1805983"}},"subtitle":["A formal perspective"],"short-title":[],"issued":{"date-parts":[[2010,7]]},"references-count":31,"aliases":["10.1145\/1805974.1895983"],"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["10.1145\/1805974.1805983"],"URL":"https:\/\/doi.org\/10.1145\/1805974.1805983","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"value":"1094-9224","type":"print"},{"value":"1557-7406","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7]]},"assertion":[{"value":"2008-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}