# US 2018/0322159 A1 · Graph-based data models for partitioned data > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2018/0322159 A1 - Document ID: US20180322159A1 - Status: Published application - Kind: A1 - Application number: 16/039,651 - Filed: 2018-07-19 - Published: 2018-11-08 - Earliest claimed: 2013-09-12 - Assignees: Dropbox, Inc. - Applicants: Dropbox, Inc. - Inventors: Zviad Metreveli; Akhil Wable - Web page: https://patentgrep.com/patent/US20180322159A1 ## CPC - G06F 16/2343: {Locking methods, e.g. distributed locking or locking implementation details} - G06F 16/22: Indexing; Data structures therefor; Storage structures - G06F 16/24552: {Database cache management} - G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning} - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F 16/986: {Document structures and storage, e.g. HTML extensions} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method and system for managing access to data. A plurality of data items is stored across a plurality of partitions according to a graph-based data model. The data model associates each data item with an identifier of a source entity pertaining to the data item, an identifier of a destination entity pertaining to the data item, and an identifier of a type of directed relationship pertaining to the data item from the source entity to the destination entity. When a lookup request is received identifying a source entity and a type of directed relationship from the source entity, a particular partition is identified based on the source entity identifier. A response to the lookup request is then returned that includes data item(s) from the identified partition that are associated in the partition with both the identified source entity identifier and the identified directed relationship type. ## Claims ### Claim 1 A method of managing access to data, comprising: at one or more computer systems comprising processors, memory, and storage: storing a plurality of data items across a plurality of partitions; wherein the storing comprises storing a graph-based data model that associates each data item of the plurality of data items with an identifier of a source entity pertaining to the data item, an identifier of a destination entity pertaining to the data item, and an identifier of a type of directed relationship pertaining to the data item from the source entity to the destination entity; receiving a lookup request specifying an identifier of a particular source entity and an identifier of a particular type of directed relationship from the particular source entity; based on the identifier of the particular source entity specified in the lookup request, identifying a particular partition of the plurality of partitions; and returning a response to the lookup request, the response comprising data items, each of the data items both: (a) stored in the partition; and (b) associated in the partition, according to the graph-based data model, with both: (b1) the identifier of the particular source entity and (b2) the identifier of the particular type of directed relationship. ### Claim 2 (depends on 1) The method of claim 1, wherein the particular source entity is a user having a user account with an online content management system; and wherein each data item, of the data items returned in the response, identifies a different collection of content items, under management of the online content management system, to which the user having the user account has permission to access. ### Claim 3 (depends on 1) The method of claim 1, wherein the particular source entity is a collection of content items under management of an online content management system; and wherein each data item, of the data items returned in the response, identifies a different user having a user account, with the online content management system, that has permission to access the collection of content items. ### Claim 4 (depends on 1) The method of claim 1, wherein each data item, of the data items returned in the response, represents permissions that a particular user having a user account with an online content management system has with respect to a different collection of content items under management of the online content management system, the particular user identified by the identifier of the particular source entity, the different collection of content items identified by the each data item. ### Claim 5 (depends on 1) The method of claim 1, wherein each data item, of the data items returned in the response, represents permissions that a different user having a user account with an online content management system has with respect to a particular collection of content items under management of the online content management system, the particular collection of content items identified by the identifier of the particular source entity, the different user having a user account identified by the each data item. ### Claim 6 (depends on 1) The method of claim 1, wherein: the lookup request is a first lookup request; the response is a first response; the method further comprises: receiving a second lookup request specifying the identifier of the particular source entity, an identifier of a particular destination entity, and the identifier of the particular type of directed relationship; responsive to receiving the second lookup request, identifying, based on the identifier of the particular source entity specified in the second lookup request, the particular partition of the plurality of partitions; and returning a second response to the second lookup request, the second response comprising a particular data item that is both: (a) stored in the particular partition; and (b) associated in the particular partition, according to the graph-based data model, with all of: (b1) the identifier of the particular source entity, (b2) the identifier of the destination entity, and (b3) the identifier of the type of directed relationship. ### Claim 7 (depends on 1) The method of claim 1, wherein the particular source entity corresponds to a node in the graph-based data model and the particular type of directed relationship corresponds to a directed edge from the node in the graph-based data model. ### Claim 8 (depends on 1) The method of claim 1, wherein at least one data item of the data items returned in the response is obtained from a cache of data items. ### Claim 9 (depends on 1) The method of claim 1, further comprising: storing a plurality of slave partitions corresponding to the plurality of partitions. ### Claim 10 An online content management system comprising: one or more processors; one or more computer-readable media storing one or more computers programs, the one or more computer programs configured for: storing a plurality of data items across a plurality of partitions; receiving a first lookup request specifying an identifier of a particular source entity, an identifier of a particular destination entity, and an identifier of a particular type of directed relationship from the particular source entity to the particular destination entity; based on the identifier of the particular source entity specified in the first lookup request, identifying a particular partition of the plurality of partitions; returning a first response to the first lookup request, the first response comprising a particular data item that is both: (a) stored in the particular partition; and (b) associated, according to a graph-based data model, with all of: (b1) the identifier of the particular source entity, (b2) the identifier of the particular destination entity, and (b3) the identifier of the particular type of directed relationship; receiving a second lookup request specifying the identifier of the particular source entity and the identifier of the particular type of directed relationship; based on the identifier of the particular source entity specified in the second lookup request, identifying the partition of the plurality of partitions; and returning a second response to the second lookup request, the second response comprising data items, each of the data items both: (a) stored in the particular partition; and (b) associated, according to the graph-based data model, with at least both: (b1) the identifier of the particular source entity and (b2) the identifier of the particular type of directed relationship. ### Claim 11 A system for managing access to data, the system comprising: one or more processors; one of more computer-readable media storing one or more sets of instructions configured for: storing a plurality of data items across a plurality of partitions; wherein the storing comprises storing a graph-based data model that associates each data item of the plurality of data items with an identifier of a source entity pertaining to the data item, an identifier of a destination entity pertaining to the data item, and an identifier of a type of directed relationship pertaining to the data item from the source entity to the destination entity; receiving a lookup request specifying an identifier of a particular source entity and an identifier of a particular type of directed relationship from the particular source entity; based on the identifier of the particular source entity specified in the lookup request, identifying a particular partition of the plurality of partitions; and returning a response to the lookup request, the response comprising data items, each of the data items both: (a) stored in the particular partition; and (b) associated in the particular partition, according to the graph-based data model, with both: (b1) the identifier of the particular source entity and (b2) the identifier of the particular type of directed relationship. ### Claim 12 (depends on 11) The system of claim 11, wherein the particular source entity is a user having a user account with an online content management system; and wherein each data item, of the data items returned in the response, identifies a different collection of content items, under management of the online content management system, to which the user having the user account has permission to access. ### Claim 13 (depends on 11) The system of claim 11, wherein the particular source entity is a collection of content items under management of an online content management system; and wherein each data item, of the data items returned in the response, identifies a different user having a user account, with the online content management system, that has permission to access the collection of content items. ### Claim 14 (depends on 11) The system of claim 11, wherein each data item, of the data items returned in the response, represents permissions that a particular user having a user account with an online content management system has with respect to a different collection of content items under management of the online content management system, the particular user identified by the identifier of the particular source entity, the different collection of content items identified by the each data item. ### Claim 15 (depends on 11) The system of claim 11, wherein each data item, of the data items returned in the response, represents permissions that a different user having a user account with an online content management system has with respect to a particular collection of content items under management of the online content management system, the particular collection of content items identified by the identifier of the particular source entity, the different user having a user account identified by the each data item. ### Claim 16 (depends on 11) The system of claim 11, wherein: the lookup request is a first lookup request; the response is a first response; the one or more sets of instructions are further configured for: receiving a second lookup request specifying the identifier of the particular source entity, an identifier of a particular destination entity, and the identifier of the particular type of directed relationship; responsive to receiving the second lookup request, identifying, based on the identifier of the particular source entity specified in the second lookup request, the particular partition of the plurality of partitions; and returning a second response to the second lookup request, the second response comprising a particular data item that is both: (a) stored in the particular partition; and (b) associated in the particular partition, according to the graph-based data model, with all of: (b1) the identifier of the particular source entity, (b2) the identifier of the destination entity, and (b3) the identifier of the type of directed relationship. ### Claim 17 (depends on 11) The system of claim 11, wherein the particular source entity corresponds to a node in the graph-based data model and the particular type of directed relationship corresponds to a directed edge from the node in the graph-based data model. ### Claim 18 (depends on 11) The system of claim 11, wherein at least one data item of the data items returned in the response is obtained from a cache of data items. ### Claim 19 (depends on 11) The system of claim 11, wherein the one or more sets of instructions are further configured for: storing a plurality of slave partitions corresponding to the plurality of partitions. ### Claim 20 One or more non-transitory computer-readable media storing one or more sets of instructions for execution by one or more processors, the one or more sets of instructions configured for: storing a plurality of data items across a plurality of partitions; wherein the storing comprises storing a graph-based data model that associates each data item of the plurality of data items with an identifier of a source entity pertaining to the data item, an identifier of a destination entity pertaining to the data item, and an identifier of a type of directed relationship pertaining to the data item from the source entity to the destination entity; receiving a lookup request specifying an identifier of a particular source entity and an identifier of a particular type of directed relationship from the particular source entity; based on the identifier of the particular source entity specified in the lookup request, identifying a particular partition of the plurality of partitions; and returning a response to the lookup request, the response comprising data items, each of the data items both: (a) stored in the particular partition; and (b) associated in the particular partition, according to the graph-based data model, with both: (b1) the identifier of the particular source entity and (b2) the identifier of the particular type of directed relationship.