# US 2021/0334256 A1 · Agent-based data pre-processing and data indexing for efficient data retrieval > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0334256 A1 - Document ID: US20210334256A1 - Status: Published application - Kind: A1 - Application number: 16/859,733 - Filed: 2020-04-27 - Published: 2021-10-28 - Earliest claimed: 2020-04-27 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Rahul Potharaju; Terry Y. Kim; Wentao Wu - Web page: https://patentgrep.com/patent/US20210334256A1 ## CPC - G06F 16/2228: {Indexing structures} - G06F 16/245: Query processing - G06F 16/248: Presentation of query results - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods, systems, apparatuses, and computer program products are directed to the generation of a global index structure. Agents executing on different data sources locally pre-process (e.g., format, filter, compress, encode, serialize etc.) data generated thereby and index such data. The agents also manage the resources thereof to perform the pre-processing and indexing operations. Each index generated by an agent is formatted as a plurality of index nodes. The index nodes and pre-processed data are provided to backend server(s) that maintain the global index structure and store the data in a globally distributed file system, which aid in unexpected disaster recovery. The backend server(s) generate the global index structure based on the index nodes. As new index nodes are received by the backend servers, the backend servers merge the newly-received index nodes with the global index structure. Global index structure traversal techniques for retrieving search keys are also described herein. ## Claims ### Claim 1 A method implemented by one or more computing devices, comprising: receiving, from a first data source, first data and a plurality of first index nodes that are generated by the first data source, each index node of the plurality of first index nodes comprising a plurality of first search keys corresponding to the first data; receiving, from a second data source, second data and a plurality of second index nodes that are generated by the second data source, each index node of the plurality of second index nodes comprising a plurality of second search keys corresponding to the second data; and combining the plurality of first index nodes and the plurality of second index nodes with an index structure maintained by the one or more computing devices. ### Claim 2 (depends on 1) The method of claim 1, wherein the plurality of first index nodes and the plurality of second index nodes are received in a compressed format. ### Claim 3 (depends on 2) The method of claim 2, further comprising: decompressing the received plurality of first index nodes and the received plurality of second index nodes before said combining. ### Claim 4 (depends on 1) The method of claim 1, wherein the first data source encodes the first data and the second data source encodes the second data in accordance with an encoding format. ### Claim 5 (depends on 1) The method of claim 1, wherein the first data source serializes the first data and the second data source serializes the second data in accordance with one of a row-major format or a column-major format. ### Claim 6 (depends on 1) The method of claim 1, wherein the first data source filters the first data and the second data source filters the second data to remove particular data therefrom. ### Claim 7 (depends on 1) The method of claim 1, wherein the first data source formats the first data and the second data source formats the second data in accordance with at least one of a delimiter-separated value format, a JavaScript Object Notation format, or a binary format. ### Claim 8 (depends on 1) The method of claim 1, wherein the first data source is configured to constrain one or more first resources thereof that are utilized to perform at least one of: compression of the first data; encoding of the first data; formatting of the first data; filtering of the first data; serialization of the first data; or generation of the plurality of first index nodes, and wherein the second data source is configured to constrain one or more second resources thereof that are utilized to perform at least one of: compression of the second data; encoding of the second data; formatting of the second data; filtering of the second data; serialization of the second data; or generation of the plurality of second index nodes. ### Claim 9 (depends on 1) The method of claim 1, wherein said combining comprises: determining that an index node of the index structure and an index node of at least one of the plurality of first index nodes or the plurality of second index nodes have a size below a predetermined threshold; and merging the index node of the index structure and the index node of at least one of the plurality of first index nodes or the plurality of second index nodes. ### Claim 10 (depends on 1) The method of claim 1, wherein said combining comprises: determining that a first index node of the index structure and an index node of at least one of the plurality of first index nodes or the plurality of second index nodes comprise a number of duplicate search keys that exceed a predetermined threshold; and generating a second index node for the index structure that comprises the duplicate search keys, the second index node referencing the first index node of the index structure and the index node of at least one of the plurality of first index nodes or the plurality of second index nodes. ### Claim 11 (depends on 1) The method of claim 1, wherein the plurality of first index nodes comprise first location information specifying a location at which each of the plurality of first search keys is stored in a file system maintained by the one or more computing devices, and wherein the plurality of second index nodes comprise second location information specifying a location at which each of the plurality of second search keys is stored in the file system. ### Claim 12 (depends on 1) The method of claim 1, further comprising: receiving a search query comprising a search key; traversing the index structure for the search key; determining at least one data record from at least one of the first data or the second data that comprises the search key; and returning the at least one data record responsive to the search query. ### Claim 13 A system, comprising: at least one processor circuit; and at least one memory that stores program code configured to be executed by the at least one processor circuit, the program code comprising: an index generator configured to: receive, from a first data source, first data and a plurality of first index nodes that are generated by the first data source, each index node of the plurality of first index nodes comprising a plurality of first search keys corresponding to the first data; receive, from a second data source, second data and a plurality of second index nodes that are generated by the second data source, each index node of the plurality of second index nodes comprising a plurality of second search keys corresponding to the second data; and combine the plurality of first index nodes and the plurality of second index nodes with an index structure maintained by the system. ### Claim 14 (depends on 13) The system of claim 13, wherein the plurality of first index nodes and the plurality of second index nodes are received in a compressed format. ### Claim 15 (depends on 14) The system of claim 14, wherein the index generator is further configured to: decompress the received plurality of first index nodes and the received plurality of second index nodes before said combining. ### Claim 16 (depends on 13) The system of claim 13, wherein the index generator is configured to combine the plurality of first index nodes and the plurality of second index nodes with an index structure maintained by the system by: determining that an index node of the index structure and an index node of at least one of the plurality of first index nodes or the plurality of second index nodes have a size below a predetermined threshold; and merging the index node of the index structure and the index node of at least one of the plurality of first index nodes or the plurality of second index nodes. ### Claim 17 (depends on 13) The system of claim 13, wherein the index generator is configured to combine the plurality of first index nodes and the plurality of second index nodes with an index structure maintained by the system by: determining that a first index node of the index structure and an index node of at least one of the plurality of first index nodes or the plurality of second index nodes comprise a number of duplicate search keys that exceed a predetermined threshold; and generating a second index node for the index structure that comprises the duplicate search keys, the second index node referencing the first index node of the index structure and the index node of at least one of the plurality of first index nodes or the plurality of second index nodes. ### Claim 18 (depends on 13) The system of claim 13, wherein the plurality of first index nodes comprise first location information specifying a location at which each of the plurality of first search keys is stored in a file system maintained by the system, and wherein the plurality of second index nodes comprise second location information specifying a location at which each of the plurality of second search keys is stored in the file system. ### Claim 19 A computer-readable storage medium having program instructions recorded thereon that, when executed by at least one processor of a computing device, perform a method, the method comprising: receiving, from a first data source, first data and a plurality of first index nodes that are generated by the first data source, each index node of the plurality of first index nodes comprising a plurality of first search keys corresponding to the first data; receiving, from a second data source, second data and a plurality of second index nodes that are generated by the second data source, each index node of the plurality of second index nodes comprising a plurality of second search keys corresponding to the second data; and combining the plurality of first index nodes and the plurality of second index nodes with an index structure maintained by the computing device. ### Claim 20 (depends on 19) The computer-readable storage medium of claim 19, wherein the plurality of first index nodes and the plurality of second index nodes are received in a compressed format.