# US 2017/0255682 A1 · Database access using a space-filling curve > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2017/0255682 A1 - Document ID: US20170255682A1 - Status: Published application - Kind: A1 - Application number: 15/063,338 - Filed: 2016-03-07 - Published: 2017-09-07 - Earliest claimed: 2016-03-07 - Assignees: eBay Inc. - Applicants: eBay Inc. - Inventors: Jennica Pounds; Jiaxin Shan; Xiangdong Peng - Web page: https://patentgrep.com/patent/US20170255682A1 ## CPC - G06F 16/24552: {Database cache management} - G06F 16/2228: {Indexing structures} - G06F 16/2246: {Trees, e.g. B+trees} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Disclosed is an approach for improved access of databases using a space-filling curve, such as a z-order curve, and a sparse tree. The space-filling curve traverses every point in n-dimensional space of a multidimensional data structure. The sparse tree can be implemented as a cache to store which rows of the multidimensional data structure have actual data. The sparse tree may have one or more nodes merged into a single node, The sparse tree may have one or more node limits at each node that limit node spawning. Node counters track how many rows containing data not mapped correspond to each node. As the multidimensional data structure is searched, the search path is adjusted by reseeking back to rows that are located in the sparse tree. Further, the search path is adjusted by reseeking back to rows that are located within a query box. ## Claims ### Claim 1 A method comprising: identifying, by a hardware processor, a first row in a database using a curve data structure, the first row located within one or more of ranges at a first point along the curve data structure; determining, using a tree data structure, whether the first row is in a cache that corresponds to the database; and in response to determining that the first row is not in the cache, identifying a second row in the database using the curve data structure, the second row being located within the one or more ranges at a second point along the curve data structure. ### Claim 2 (depends on 1) The method of claim 1, further comprising, in response to determining that the first row is in the cache, returning one or more values from the first row as a result to a query. ### Claim 3 (depends on 1) The method of claim 1, wherein the cache comprises rows located in the database. ### Claim 4 (depends on 1) The method of claim 1, wherein ranges of the one or more ranges correspond to columns of the database. ### Claim 5 (depends on 1) The method of claim 1, wherein the curve data structure is a z-order space-filling curve. ### Claim 6 (depends on 1) The method of claim 1, wherein the tree data structure is a binary tree data structure having merged nodes. ### Claim 7 (depends on 1) The method of claim 1, wherein the tree data structure implements a node spawning threshold. ### Claim 8 (depends on 1) The method of claim 1, wherein at least one range in the one or more ranges is limited by an upper boundary or a lower boundary. ### Claim 9 (depends on 1) The method of claim 1, wherein the one or more ranges corresponds to one or more rows, and the tree data structure is used to determine whether each row in the one or more rows is in the cache. ### Claim 10 A system comprising: one or more processors of a machine; and a memory storing instructions that, when executed by the one or more processors, cause the machine to at least: identify a first row in the database using a curve data structure, the first row located within one or more ranges at a first point along the curve data structure; use a tree data structure to determine whether the first row is in a. cache that corresponds to the database; and in response to a determination that the first row is not in the cache, identify a second row in the database using the curve data structure, the second row being located within the one or more ranges at a second point along the curve data structure. ### Claim 11 (depends on 10) The system of claim 10, wherein the machine is further to, in response to a determination that the first row is in the cache, return one or more values from the first row as a result to a query. ### Claim 12 (depends on 10) The system of claim 10, wherein the cache comprises rows located in the database. ### Claim 13 (depends on 10) The system of claim 10, wherein ranges of the one or more ranges correspond to columns of the database. ### Claim 14 (depends on 10) The system of claim 10, wherein the curve data structure is a z-order space-filling curve. ### Claim 15 (depends on 10) The system of claim 10, wherein the tree data structure is a binary tree data structure having merged nodes. ### Claim 16 (depends on 10) The system of claim 10, wherein the tree data structure implements a node spawning threshold. ### Claim 17 (depends on 10) The system of claim 10, wherein at least one range in the one or more ranges is limited by an upper boundary or a lower boundary. ### Claim 18 (depends on 10) The system of claim 10, wherein the one or more ranges corresponds to one or more rows, and the tree data structure is used to determine whether each row in the plurality of rows is in the cache. ### Claim 19 A non-transitory machine-readable storage medium embodying instructions that, when executed by a machine, cause the machine to perform operations comprising: identifying a first row in a database using a curve data structure, the first row located within one or more ranges at a first point along the curve data structure: using a tree data structure to determine whether the first row is in a cache that corresponds to the database; and in response to a determination that the first row is not in the cache, identifying a second row in the database using the curve data structure, the second row being located within the one or more ranges at a second point along the curve data structure. ### Claim 20 (depends on 19) The non-transitory machine-readable storage medium of claim 19, wherein: the tree data structure is a binary tree data structure having merged nodes, and the tree data structure implements a node spawning threshold.