# US 12,111,818 B2 · Comparing ordered sets generated by different data-processing engines > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,111,818 B2 - Document ID: US12111818B2 - Status: Granted - Kind: B2 - Application number: 18/080,484 - Filed: 2022-12-13 - Published: 2024-06-13 - Granted: 2024-10-08 - Earliest claimed: 2022-12-13 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Peter Joseph Rise - Web page: https://patentgrep.com/patent/US12111818B2 ## CPC - G06F 16/2365: {Ensuring data consistency and integrity} - G01C 21/3415: {Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents} - G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes} - G01C 21/3811: {Point data, e.g. Point of Interest [POI]} - G01C 21/3815: {Road data} - G01C 21/3859: {Differential updating map data} - G06F 16/24578: {using ranking} - G06F 16/29: Geographical information databases - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) ## Abstract A technique updates a first data-processing engine based on reference information produced by a second data-processing engine. The technique involves obtaining ordered sets of result items from both engines, where the result items produced by the second engine serve the role of the reference information. The technique then produces accuracy information by assessing the accuracy of the first-set result items relative to the second-set result items. The accuracy information is a set-wide assessment that reflects how well the first-set result items match the second-set result items, taking into account the similarity between pairs of result items and the ordering of result items in the ordered sets. The technique then modifies a configuration of the first data-processing engine based on the accuracy information to improve its quality. In some implementations, the first and second data-processing engines are first and second map engines that generate routes through a physical space. ## Claims ### Claim 1 A computer-implemented method for updating data-processing functionality, comprising: obtaining a first ordered set of first-set result items produced by a first data-processing engine in response to an input query; obtaining a second ordered set of second-set result items produced by a second data-processing engine in response to the same input query, the second data-processing engine serving as a reference engine that provides ground-truth result items; generating accuracy information by assessing accuracy of the first-set result items relative to the second-set result items, the generating being based on an assessment of item similarity between individual pairings formed from the first ordered set and the second ordered set, and based on a comparison of an order of the first-set result items and an order of the second-set result items; and producing output information that identifies deficiencies in the first data-processing engine based on the accuracy information, which enables modification of a configuration of the first data-processing engine to increase quality of result items produced by the first data-processing engine in a production stage of operation, the generating including: producing matching information that uses a prescribed test of similarity to identify first-set result items that match respective second-set result items; and determining relevance information based on the matching information, the relevance information including individual relevance measures that express relevance of respective first-set result items in the first ordered set, wherein a particular first-set result item matches a particular second-set result item, and wherein the determining relevance information assigns a relevance measure to the particular first-set result item based on a position of the particular second-set result item in the second ordered set. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the first-set result items and the second-set result items describe suggestions that are generated based on query information specified in the input query. ### Claim 3 (depends on 2) The computer-implemented method of claim 2, wherein the query information describes a starting location and an ending location, and wherein the suggestions are candidate routes between the starting location and the ending location. ### Claim 4 (depends on 2) The computer-implemented method of claim 2, wherein the query information specifies one or more words, and the suggestions are transformations of the one or more words, or wherein the query information specifies a topic, and the suggestions are recommendations pertaining to the topic. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein, in the production stage of operation, the first data-processing engine and/or the second data-processing engine operate by processing user queries submitted over a wide-area network. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein the generating also includes: producing discounted cumulative gain information based on an aggregation of the relevance measures produced by the determining; and producing the accuracy information based on the discounted cumulative gain information. ### Claim 7 (depends on 6) The computer-implemented method of claim 6, wherein the relevance measures in the relevance information have a particular order, and wherein the discounted cumulative gain information discounts contributions from the relevance measures based on positions of the relevance measures in the particular order. ### Claim 8 (depends on 1) The computer-implemented method of claim 1, wherein the producing matching information operates by processing each second-set result item in a same order as the order of the second-set result items in the second ordered set, and wherein the producing matching information includes, for each candidate second-set result item, matching the candidate second-set result item with a first-occurring unmatched first-set result item that is assessed as matching the candidate second-set result item, based on the prescribed test of similarity. ### Claim 9 (depends on 1) The computer-implemented method of claim 1, wherein another particular first-set result item does not match any second-set result item in the second ordered set, and wherein the determining relevance information assigns a relevance measure to said another particular first-set result item that conveys that said another particular first-set result item is not relevant. ### Claim 10 (depends on 1) The computer-implemented method of claim 1, wherein the relevance information includes: actual relevance information that expresses relevance of the first-set result items in an actual order of the first-set result items as given, as assessed against the second ordered set; and ideal relevance information that expresses relevance of the first-set result items based on an expectation that more relevant first-set result items should be ranked more favorably than less relevant first-set result items. ### Claim 11 (depends on 10) The computer-implemented method of claim 10, wherein the discounted cumulative gain information includes: actual discounted cumulative gain information that is produced based on the actual relevance information; and ideal discounted cumulative gain information that is produced based on the ideal relevance information. ### Claim 12 (depends on 11) The computer-implemented method of claim 11, wherein the producing accuracy information involves normalizing the actual discounted cumulative gain information by the ideal discounted cumulative gain information. ### Claim 13 (depends on 1) The computer-implemented method of claim 1, further including automatically changing the configuration of the first data-processing engine based on the output information. ### Claim 14 (depends on 1) The computer-implemented method of claim 1, wherein the first data-processing engine is a first map engine, and the first ordered set of first-set result items is a first ordered set of first-set route items produced by the first map engine, wherein the second data-processing engine is a second map engine, and the second ordered set of second-set result items is a second ordered set of second-set route items produced by the second map engine. ### Claim 15 (depends on 14) The computer-implemented method of claim 14, wherein the generating includes producing matching information that uses a prescribed test of similarity to identify first-set route items that match respective second-set route items, wherein the prescribed test of similarity determines an extent of geometric similarity between a particular second-set route item and a particular first-set route item based on: route lengths of the particular first-set route item and the particular second-set route item; and a metric that assesses a separation between the particular first-set route item and the particular second-set route item, over a course of trajectories defined by the particular first-set route item and the particular second-set route item. ### Claim 16 (depends on 14) The computer-implemented method of claim 14, further including changing a configuration of the first map engine based on the output information by correcting a map database used by the first map engine. ### Claim 17 (depends on 14) The computer-implemented method of claim 14, further including changing a configuration of the first map engine based on the output information by training operation of the first map engine. ### Claim 18 A computing system for updating data-processing functionality, comprising: a memory for storing machine-readable instructions; and a processing system that executes the machine-readable instructions to perform operations of: obtaining a first ordered set of first-set result items produced by a first data-processing engine in response to an input query; obtaining a second ordered set of second-set result items produced by a second data-processing engine in response to the same input query, the second data-processing engine serving as a reference engine that provides ground-truth result items; generating accuracy information by assessing accuracy of the first-set result items relative to the second-set result items, the generating being based on an assessment of item similarity between individual pairings formed from the first ordered set and the second ordered set, and based on a comparison of an order of the first-set result items and an order of the second-set result items; and producing output information that identifies deficiencies in the first data-processing engine based on the accuracy information, which enables modification of a configuration of the first data-processing engine to increase quality of result items produced by the first data-processing engine in a production stage of operation, wherein the generating includes: producing matching information that uses a prescribed test of similarity to identify first-set result items that match respective second-set result items; determining relevance information based on the matching information, the relevance information including individual relevance measures that express relevance of respective first-set result items in the first ordered set; producing discounted cumulative gain information based on an aggregation of the relevance measures produced by the determining; and producing the accuracy information based on the discounted cumulative gain information. ### Claim 19 A computer-readable storage medium for storing computer-readable instructions, the computer-readable memory excluding propagated signals in transit, wherein a processing system executing the computer-readable instructions performs operations comprising: obtaining a first ordered set of first-set result items produced by a first data-processing engine in response to an input query; obtaining a second ordered set of second-set result items produced by a second data-processing engine in response to the same input query, the second data-processing engine serving as a reference engine that provides ground-truth result items; generating accuracy information by assessing accuracy of the first-set result items relative to the second-set result items, the generating being based on an assessment of item similarity between individual pairings formed from the first ordered set and the second ordered set, and based on a comparison of an order of the first-set result items and an order of the second-set result items; and producing output information that identifies deficiencies in the first data-processing engine based on the accuracy information, which enables modification of a configuration of the first data-processing engine to increase quality of result items produced by the first data-processing engine in a production stage of operation, wherein the generating includes: producing matching information that uses a prescribed test of similarity to identify first-set result items that match respective second-set result items; determining relevance information based on the matching information, the relevance information including individual relevance measures that express relevance of respective first-set result items in the first ordered set; producing discounted cumulative gain information based on an aggregation of the relevance measures produced by the determining; and producing the accuracy information based on the discounted cumulative gain information.