Method of generating hierarchical data structure

• US 10,078,624 B2
• Filed: 04/08/2015
• Issued: 09/18/2018
• Est. Priority Date: 12/25/2014
• Status: Active Grant

• Current Assignee: YE Hub Armenia LLC
• Original Assignee: Yandex Europe AG (Yandex N.V.)
• Inventors: Nalchadzhi, Leonid Leonidovich
• Primary Examiner(s): Wu, Yicun
• Application Number:
  US15/504,786
• Publication Number:
  US 20170364487A1
• Time in Patent Office: 1,259 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines
• CPC Class Codes: G06F 40/14 Tree-structured documents parsing G06F40/205; validation G06F40/226
• CPC Class Codes: G06F 40/154 Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets

Abstract

There is disclosed a computer-implemented method for generating a hierarchical data structure. The computer-implemented method can be executable at a server. The computer implemented method comprises: identifying a plurality of data elements to be searched, the plurality of data elements having a set of descriptors, each descriptor within the set of descriptors being associated with a data type being different from data types of other descriptors within the set of descriptors; defining the hierarchical data structure, having a first level and a second level.

Claims

1. A computer-implemented method for generating a multi-level hierarchical data tree structure and searching data therein, the hierarchical data structure having at least a first level, a second level, and a leaf level, the computer-implemented method executable at a server, the computer-implemented method comprising:

receiving, by a partitioner at the server, a plurality of data elements, the plurality of data elements having a set of descriptors, each descriptor within the set of descriptors being associated with a data type being different from data types of other descriptors within the set of descriptors;

generating, by an index tree manager at the server, the multi-level hierarchical data tree structure for storing elements of the plurality of data elements of the same type, the plurality of data elements having a common root, the first level accommodating a parent node, the second level accommodating a first child node and a second child node both dependent from the parent node, and the leaf level accommodating a first leaf node and second leaf node each dependent of the respective first child node and the second child node;

the parent node for storing a first descriptor from the set of descriptors, the first descriptor associated with one or more data elements of the plurality of data elements, the descriptor being of a first data type;

each of the first child node and the second child node for storing a respective second descriptor of the respective one of the one or more data elements;

the respective second descriptor being of the same second data type, the same second data type being different from the first data type; and

each of the first leaf node and second leaf node for storing a respective statistical snapshot, each of the first and second leaf node comprising a plurality of third descriptors of different third data types being different from the first and second data type, the third data type being at least one of;

(i) a data element count associated with its respective branch, and

(ii) a lowest minimum and highest maximum value associated with the one or more data element stored therein;

recording, at an index tree storage by the index tree manager at the server, the multi-level hierarchical tree structure into a sequential linear data structure, the sequential linear data structure being implemented as a sequential record of cells having descriptors and an auxiliary data structure for navigation, the auxiliary data structure including;

a number of child nodes of the parent node,

a number of leaf nodes of each of the child nodes, and

at least one offset between two cells of the sequential record of cells and at least one link between two non-contiguous cells of the sequential record of cells for direct navigation therebetween;

receiving, by a searcher at the server from an electronic device, a search query having a search parameter, the search parameter being associated with a search data type;

navigating, by the index tree manager at the server, using the at least one offset through the cells of the sequential linear data structure using the auxiliary data structure and comparing, by the server, the search parameter with the descriptors of the sequential record of cells to identify a statistical snapshot cell storing a statistical snapshot, the statistical snapshot cell associated with a leaf node associated with a branch of the hierarchical data structure, the branch comprising at least one node associated with a descriptor being of the same data type as the search data type, the descriptor matching with the search parameter;

accessing, by the index tree manager at the server, the statistical snapshot cell having at least one data element being associated with the descriptor;

retrieving, by the index tree manager at the server, the at least one data element from the statistical snapshot cell; and

causing, by the server, the electronic device to display the at least one data element retrieved from the statistical snapshot cell.

2. The method of claim 1, the parent node being a first parent node, and wherein the defining the hierarchical data structure further comprises defining a second parent node for storing a descriptor from the set of descriptors;

the descriptor being different from the descriptor of a first parent node;

both descriptors being of the same first data type.

3. The method of claim 2, the defining the hierarchical data structure further comprises defining a third child node and a fourth child node, both dependent from the second parent node;

each of the third child node and the fourth child node for storing a respective other descriptor of the other ones of the one or more data elements;

the respective other descriptor being of the same second data type.

4. The method of claim 1, the defining the hierarchical data structure is executed in response to receiving an indication of a data element of the plurality of data elements of the same type, the data element to be indexed in the hierarchical data structure, the data element associated with the set of descriptors, the set of descriptors having a first descriptor and a second descriptor.

5. The method of claim 4, wherein in response to receiving an indication of the data element being associated with the first descriptor being of the first data type the defining comprises identifying the parent node at the first level of the hierarchical data structure.

6. The method of claim 5, wherein in response to receiving an indication of the data element being associated with the second descriptor being of the second data type, the defining comprises identifying the first child node at the second level of the hierarchical data structure.

7. The method of claim 5, wherein the data element is the first data element and wherein in response to receiving an indication of a second data element being associated with a second descriptor being of the second data type, the second descriptor being the different from the second descriptor of the first data element the defining comprises identifying the second child node at the second level of the hierarchical data structure.

8. The method of claim 5, wherein the parent node is the first parent node, and wherein in response to receiving an indication of the second data element associated with a descriptor being different from the first descriptor;

both descriptors being of the same first data type, the defining further comprises identifying a second parent node at the first level of the hierarchical data structure.

9. The method of claim 4, wherein in response to receiving an indication of the data element being associated with the first descriptor being of the first data type, the second descriptor being of the second data type and the third descriptor being of the third data type, the defining further comprises identifying a first leaf node being associated with the first child node;

the first leaf node for storing the third descriptor.

10. The method of claim 9, wherein the data element is the first data element, and wherein in response to receiving an indication of a second data element being associated with the same first descriptor and the same second descriptor as the first data element, but a different third descriptor of the same third data type, the defining further comprises associating the second data element with the first leaf node.

11. The method of claim 10, further comprising updating the first leaf node with a statistical snapshot of the third descriptor of the first data element and the different third descriptor of the second data element.

12. The method of claim 10, wherein in response to receiving an indication of a third data element being associated with the same first descriptor and the same second descriptor as both the first and second data elements, but a different third descriptor of the same third data type, the defining further comprises associating the third data element with the first leaf node.

13. The method of claim 12, further comprising updating the statistical snapshot with information associated with the third data element.

14. The method of claim 13, wherein the updating comprises:

(i) updating a count within the number of data elements, (ii) determining if the indication of the minimum value and the maximum value needs to be updated based on the value of a third descriptor of the third data element.

15. The method of claim 14, wherein the determining if the indication of the minimum value and the maximum value needs to be updated comprises checking if the value of the third descriptor falls within a range defined between the minimum value and the maximum value, and, in response to the value of the third descriptor being outside of the range defined between the minimum value and the maximum value, modifying the range to include the value of the third descriptor.

16. The method of claim 15, wherein responsive to the value of the third descriptor falling outside one of the minimum value and the maximum value, changing the respective one of the minimum value and the maximum value to the value of the third descriptor of the third data element.

17. The method of claim 9, wherein the data element is the first data element, and wherein in response to receiving an indication of a fourth data element being associated with the same first descriptor and a second descriptor being of the same second data type but being different from the second descriptor of the first data element, and a third descriptor being of the same third data type, the defining further comprises identifying a second leaf node being associated with the second child node;

the second leaf node for storing the third descriptor associated with the fourth data element.

18. A server configured to generate a multi-level hierarchical data tree structure and searching data therein, the hierarchical data structure having at least a first level, a second level, and a leaf level, the server comprising non-transient storage medium for storing computer-executable instructions, which instructions when executed are configured to render the server operable to:

receive, at a partitioner via a communications network, a plurality of data elements, the plurality of data elements having a set of descriptors, each descriptor within the set of descriptors being associated with a data type being different from data types of other descriptors within the set of descriptors;

generate, at an index tree manager, the multi-level hierarchical data tree structure for storing elements of the plurality of data elements of the same type, the plurality of data elements having a common root, the first level accommodating a parent node, the second level accommodating a first child node and a second child node both dependent from the parent node, and the leaf level accommodating a first leaf node and second leaf node each dependent of the respective first child node and the second child node;

the parent node for storing a first descriptor from the set of descriptors, the first descriptor associated with one or more data elements of the plurality of data elements, the descriptor being of a first data type;

each of the first child node and the second child node for storing a respective second descriptor of the respective one of the one or more data elements;

the respective second descriptor being of the same second data type, the same second data type being different from the first data type;

each of the first leaf node and second leaf node for storing a respective statistical snapshot, each of the first and second leaf node comprising a plurality of third descriptors of different third data types being different from the first and second data type, the third data type being at least one of;

(i) a data element count associated with its respective branch, and (ii) a lowest minimum and highest maximum value associated with the one or more data element stored therein;

record, at an index tree storage, the multi-level hierarchical tree structure into a sequential linear data structure, the sequential linear data structure being implemented as a sequential record of cells having descriptors and an auxiliary data structure for navigation, the auxiliary data structure including;

a number of child nodes of the parent node,

a number of leaf nodes of each of the child nodes, and

at least one offset between two cells of the sequential record of cells and at least one link between two non-contiguous cells of the sequential record of cells for direct navigation therebetween;

receive, at a searcher from an electronic device via the communications network, a search query having a search parameter, the search parameter being associated with a search data type;

navigate, by the index tree manager, using the at least one offset through the cells of the sequential linear data structure using the auxiliary data structure and compare the search parameter with the descriptors of the sequential record of cells to identify a statistical snapshot cell storing a statistical snapshot, the statistical snapshot cell associated with a leaf node associated with a branch of the hierarchical data structure, the branch comprising at least one node associated with a descriptor being of the same data type as the search data type, the descriptor matching with the search parameter;

access, by the index tree manager, the statistical snapshot cell having at least one data element being associated with the descriptor;

retrieve, by the index tree manager, the at least one data element from the statistical snapshot cell; and

cause, over the communications network, the electronic device to display the at least one data element retrieved from the statistical snapshot cell.