{"value":"“Anytime query” approach adapts to the available resources.\n\nLarge online data repositories like the Amazon Store are distributed across massive banks of servers, and retrieving data from those repositories must be efficient in order to provide a good customer experience. It is usual for a service-level agreement (SLA) to be in place, typically mandating that some fraction of queries (say, 95%) must be responded to within some stipulated upper time limit (say, 150 milliseconds).\n\nOne way to improve efficiency is to cluster related content together on just a handful of servers, limiting the amount of data that information retrieval algorithms must consider.\n\nBut if enough users trying to access the same data, the result may be load imbalances in system utilization, resulting in SLA violations.\n\n![image.png](https://dev-media.amazoncloud.cn/beeb992c4064418f89a14f589a828b96_image.png)\n\nA depiction of the standard approach to data clustering, with cat-related content clustered on just two servers.\n\nIn a [paper we’re publishing](https://www.amazon.science/publications/anytime-ranking-on-document-ordered-indexes) in the journal ACM Transactions on Information Systems (TOIS), my collaborators at the University of Melbourne and I present a new query-processing method that avoids such imbalances by distributing data more uniformly but still limits the amount of data that needs to be considered.\n\nMoreover, our method is an anytime query method, which means that it dynamically adjusts to changing user demand, providing at least some results when bandwidth and processing cycles are scarce but improving the quality of the results in accord with the available resources. This ensures that SLAs are met while minimizing resource usage.\n\nIn experiments involving the standard ClueWeb09B document collection and queries from the TREC Million Query Track, our approach outperformed a series of baselines in terms of query result quality, relative to exhaustive query processing, demonstrating that it is capable of meeting strict latency SLAs over large document collections. \n\n#### **Selective-search-based anytime ranking**\n\nTo preserve resources, selective-search methods target queries to parts of the index that contain topically relevant documents. \n\nMost selective-search methods distribute all topically related documents to a single server node; by contrast, our method distributes a fraction of each topic to every node. This uniform distribution of documents has load-balancing benefits while at the same time simplifying the overall distributed system.\n\n![下载.gif](https://dev-media.amazoncloud.cn/c5541138f6cd4f47ad299690da4d566a_%E4%B8%8B%E8%BD%BD.gif)\n\nA corpus of data is partitioned into shards, which are distributed across server nodes. Within each shard, data has been clustered according to topic. The new algorithm reorders the data within each topic according to finer-grained classifications (color gradients), and then the topics are concatenated for efficient indexing.\n\nWithin each node, we perform a finer-grained clustering of the documents in each topical shard. The cluster categories are determined automatically, but within the topic “headphones”, for instance, our algorithm might cluster documents related to noise-cancelling headphones, wireless headphones, and so on.\n\nWithin each topic, we reorder documents according to this finer-grained clustering, enabling more targeted and therefore more efficient retrieval. We describe the details of the method in our paper “[Faster index reordering with bipartite graph partitioning](https://www.amazon.science/publications/faster-index-reordering-with-bipartite-graph-partitioning)”, which we presented at this year’s meeting of the ACM Special Interest Group on Information Retrieval ([SIGIR](https://www.amazon.science/conferences-and-events/sigir-2021)).\n\n#### **Anytime-ranking query processing**\n\nFiner-grained clustering within nodes lets us establish different relevance thresholds for different topic clusters, enabling anytime query processing. Based on the query, our algorithm determines the order in which the clusters within each topic should be visited. If no data within the cluster crosses the threshold for a given query, the cluster is bypassed entirely. \n\nIn the example below, the goal is to retrieve the pink data points. In the diagram at left, our algorithm determines to first visit the data-rich second cluster, going on to the sparser third cluster only if time permits. The first cluster is skipped entirely, as the current score threshold (blue line) is above the cluster relevance threshold (red line). The right-hand diagram shows a more conventional information retrieval algorithm, which must work its way through all documents in the node in a fixed order.\n\n![image.png](https://dev-media.amazoncloud.cn/8311f16e84d2446f9e92f47bb5614672_image.png)\n\nThe anytime-query method can bypass less relevant topic clusters (such as cluster 1, at left), improving information retrieval efficiency; a conventional retrieval method (right) must work its way through all documents in a fixed order.\n\nIn experiments, we compared our clustering method, when used in conjunction with two standard information retrieval algorithms (VBMW and MaxScore in the figure below), with an existing anytime-query method (JASS). We also compared it to an oracle model, which explores exactly the right topic clusters in exactly the right order, establishing an upper performance bound.\n\nTo evaluate the methods, we used rank-biased overlap (RBO), which indicates what percentage of the top k results (k = 10 and 1,000 in the diagrams below) the algorithm returns in the right order; a score of 1.0 indicates an optimal ordering. As can be seen in the diagram below, our clustering method enables the algorithm to converge on the optimal ordering more efficiently than existing methods.\n\n![image.png](https://dev-media.amazoncloud.cn/0a68f3d8eb504d8da4966c173e1fe1da_image.png)\n\nThese charts compare the performance of two standard information retrieval algorithms (VBMW and MaxScore), when used in conjunction with the researchers’ retrieval method, to those of an oracle method and an existing anytime-query method (JASS).\n\nOverall, our experiments showed that our proposed indexing and query-processing scheme permits adherence to the strict-latency SLAs that are standard in large-scale information retrieval systems while providing fine-grained trade-offs between latency and query result quality.","render":"<p>“Anytime query” approach adapts to the available resources.</p>\n<p>Large online data repositories like the Amazon Store are distributed across massive banks of servers, and retrieving data from those repositories must be efficient in order to provide a good customer experience. It is usual for a service-level agreement (SLA) to be in place, typically mandating that some fraction of queries (say, 95%) must be responded to within some stipulated upper time limit (say, 150 milliseconds).</p>\n<p>One way to improve efficiency is to cluster related content together on just a handful of servers, limiting the amount of data that information retrieval algorithms must consider.</p>\n<p>But if enough users trying to access the same data, the result may be load imbalances in system utilization, resulting in SLA violations.</p>\n<p><img src=\\"https://dev-media.amazoncloud.cn/beeb992c4064418f89a14f589a828b96_image.png\\" alt=\\"image.png\\" /></p>\n<p>A depiction of the standard approach to data clustering, with cat-related content clustered on just two servers.</p>\n<p>In a <a href=\\"https://www.amazon.science/publications/anytime-ranking-on-document-ordered-indexes\\" target=\\"_blank\\">paper we’re publishing</a> in the journal ACM Transactions on Information Systems (TOIS), my collaborators at the University of Melbourne and I present a new query-processing method that avoids such imbalances by distributing data more uniformly but still limits the amount of data that needs to be considered.</p>\\n<p>Moreover, our method is an anytime query method, which means that it dynamically adjusts to changing user demand, providing at least some results when bandwidth and processing cycles are scarce but improving the quality of the results in accord with the available resources. This ensures that SLAs are met while minimizing resource usage.</p>\n<p>In experiments involving the standard ClueWeb09B document collection and queries from the TREC Million Query Track, our approach outperformed a series of baselines in terms of query result quality, relative to exhaustive query processing, demonstrating that it is capable of meeting strict latency SLAs over large document collections.</p>\n<h4><a id=\\"Selectivesearchbased_anytime_ranking_18\\"></a><strong>Selective-search-based anytime ranking</strong></h4>\\n<p>To preserve resources, selective-search methods target queries to parts of the index that contain topically relevant documents.</p>\n<p>Most selective-search methods distribute all topically related documents to a single server node; by contrast, our method distributes a fraction of each topic to every node. This uniform distribution of documents has load-balancing benefits while at the same time simplifying the overall distributed system.</p>\n<p><img src=\\"https://dev-media.amazoncloud.cn/c5541138f6cd4f47ad299690da4d566a_%E4%B8%8B%E8%BD%BD.gif\\" alt=\\"下载.gif\\" /></p>\n<p>A corpus of data is partitioned into shards, which are distributed across server nodes. Within each shard, data has been clustered according to topic. The new algorithm reorders the data within each topic according to finer-grained classifications (color gradients), and then the topics are concatenated for efficient indexing.</p>\n<p>Within each node, we perform a finer-grained clustering of the documents in each topical shard. The cluster categories are determined automatically, but within the topic “headphones”, for instance, our algorithm might cluster documents related to noise-cancelling headphones, wireless headphones, and so on.</p>\n<p>Within each topic, we reorder documents according to this finer-grained clustering, enabling more targeted and therefore more efficient retrieval. We describe the details of the method in our paper “<a href=\\"https://www.amazon.science/publications/faster-index-reordering-with-bipartite-graph-partitioning\\" target=\\"_blank\\">Faster index reordering with bipartite graph partitioning</a>”, which we presented at this year’s meeting of the ACM Special Interest Group on Information Retrieval (<a href=\\"https://www.amazon.science/conferences-and-events/sigir-2021\\" target=\\"_blank\\">SIGIR</a>).</p>\\n<h4><a id=\\"Anytimeranking_query_processing_32\\"></a><strong>Anytime-ranking query processing</strong></h4>\\n<p>Finer-grained clustering within nodes lets us establish different relevance thresholds for different topic clusters, enabling anytime query processing. Based on the query, our algorithm determines the order in which the clusters within each topic should be visited. If no data within the cluster crosses the threshold for a given query, the cluster is bypassed entirely.</p>\n<p>In the example below, the goal is to retrieve the pink data points. In the diagram at left, our algorithm determines to first visit the data-rich second cluster, going on to the sparser third cluster only if time permits. The first cluster is skipped entirely, as the current score threshold (blue line) is above the cluster relevance threshold (red line). The right-hand diagram shows a more conventional information retrieval algorithm, which must work its way through all documents in the node in a fixed order.</p>\n<p><img src=\\"https://dev-media.amazoncloud.cn/8311f16e84d2446f9e92f47bb5614672_image.png\\" alt=\\"image.png\\" /></p>\n<p>The anytime-query method can bypass less relevant topic clusters (such as cluster 1, at left), improving information retrieval efficiency; a conventional retrieval method (right) must work its way through all documents in a fixed order.</p>\n<p>In experiments, we compared our clustering method, when used in conjunction with two standard information retrieval algorithms (VBMW and MaxScore in the figure below), with an existing anytime-query method (JASS). We also compared it to an oracle model, which explores exactly the right topic clusters in exactly the right order, establishing an upper performance bound.</p>\n<p>To evaluate the methods, we used rank-biased overlap (RBO), which indicates what percentage of the top k results (k = 10 and 1,000 in the diagrams below) the algorithm returns in the right order; a score of 1.0 indicates an optimal ordering. As can be seen in the diagram below, our clustering method enables the algorithm to converge on the optimal ordering more efficiently than existing methods.</p>\n<p><img src=\\"https://dev-media.amazoncloud.cn/0a68f3d8eb504d8da4966c173e1fe1da_image.png\\" alt=\\"image.png\\" /></p>\n<p>These charts compare the performance of two standard information retrieval algorithms (VBMW and MaxScore), when used in conjunction with the researchers’ retrieval method, to those of an oracle method and an existing anytime-query method (JASS).</p>\n<p>Overall, our experiments showed that our proposed indexing and query-processing scheme permits adherence to the strict-latency SLAs that are standard in large-scale information retrieval systems while providing fine-grained trade-offs between latency and query result quality.</p>\n"}