A Space-Efficient Data Structure for Fast Access Control in ECM Systems

An Enterprise Content Management (ECM) system must withstand many queries to its access control subsystem in order to check permissions in support of browsing-oriented operations. This leads us to choose a subject-oriented representation for access control (i.e., maintaining a permissions list for each subject). Additionally, if identifiers (OIDs) are assigned to objects in a breadth-first traversal of the object hierarchy, we will encounter many contiguous OIDs when browsing under one object (e.g., folder). Based on these observations, we present a space-efficient data structure specifically tailored for representing permissions lists in ECM systems. In addition to achieving space efficiency, the operations to check, grant, or revoke a permission are very fast using our data structure. Furthermore, our design supports fast union and intersection of two or more permissions lists (determining the effective permissions inherited from several users' groups or the common permissions among sets of users). Finally, the data structure is scalable to support any increase in the number of objects and subjects. We evaluate our design by comparing it against a compressed (WAH) bitmap-based representation and a hashing-based representation, using both synthetic and real-world data under both random and breadth-first OID numbering schemes.