TECHNICAL FIELD

The present disclosure relates to performing a search for potential results from one or more sources based on a search query entered by the user, and to the caching of potential results.

BACKGROUND

Many computer systems and services include a search facility enabling a user to enter a search query seeking a target data record for some target entity, such as contact or profile information for a particular other person or group of people, or product information for some desired product. The data source being searched may be external to the user terminal from which the user performs the search. As such, it is known to cache some of the potential results from the data source locally on the user terminal in advance of the search query. If the search query happens to match one of the cached records, this enables the result to be displayed to the user with a lower latency compared to querying the external data source only reactively after the search query is entered.

For instance, there are two commonly used approaches in people selection. The first may be referred to as small-cached, and the second may be referred to as large-cached. The small-cached approach is often used by mobile clients, whilst the large-cached approach is more commonly used by desktop clients or web-based systems.

The small-cache approach often used on mobile devices employs a directory fall-back mechanism. Upon start-up the client retrieves and caches a set of data either from the device contacts stored locally on the mobile user device, or from the user's top N contacts from the user's mailbox on his/her mailbox server, which means one of these two lists is now readily available for filtering and matching (cached in advance of any search query being entered). Both data sources have a non-commensurable ranking, so that interleaving is commonly not done. As the user types letters of the search query, this pre-cached result-set is filtered locally on the user device (according to either a verbatim match requirement or fuzzy matching) until either a set of one or more matching ones of cached results remains, or the result-set is empty. If the latter, the user is presented with an option to fall back to search a wider directory of contacts on a server, where this directory is a global list of all contacts within an organization to which the user belongs. Entries in this directory are searched directly within the directory and not cached. One therefore is always in one of two modes of search, either local (cached) or external directory (not cached). Also, each time the user adds a letter to the letter-series that he/she is searching, the user has to click search again which discharges any cached results and triggers a completely new search (e.g. if the user types “Joh”, then hits ‘Search Directory’, and this doesn't return the right or sufficient number of people, and then the user types another characters, so the string is “John”, then the user will need to trigger a new search to the search directory to get new results, thus requiring an extra keypress).

For searches performed by desktop clients, or searches by web-hosted clients accessed from a mobile or desktop device, another approach is typically used. Desktop searches commonly use the large-cache, and web-based searches use a hybrid approach. For both desktop and web, the top N contacts are cached on the user device, e.g. where N equals 1500. Typing a search query invokes filtering of this cache. Once the cache is discharged, a fall-back query to the online directory is done. For web searches, there is what is called a hybrid approach. As the user types, the query is submitted to both the pre-cached top-N list in the cache and the online directory (which is not cached). If the query to the online directory takes more than 1000 ms, the local results from the cache are shown to the user without any results from the directory until those become available. This ensures low latency, but sometimes causes results to switch place right before the user selects. In both experiences, the results-list is refreshed for each letter typed.

SUMMARY

According to one aspect disclosed herein, there is provided a method performed by a user terminal. The method comprises: receiving portions of a search query searching for a target entry amongst multiple entries in a set of one or more data sources, the portions being received one after another in a sequence; and triggered by the receipt of each respective one of said portions (e.g. each character), performing a respective caching operating comprising querying each of one or more data sources of the set to retrieve entries matching the search query as composed from the portion or portions received so far in the sequence, and caching the retrieved entries in a corresponding cache group for each of the queried data sources. The method further comprises: rendering an application view displaying a visual representation of at least some of the retrieved entries; and with each caching operation, selecting one or more of any newly retrieved entries in the cache following the retrieval based on the search query as now including the respective portion of the search query, and updating the application view to include the one or more selected entries from the cache.

As the cache is topped up with the entry of each individual portion of the search query (e.g. each letter or character), this may be referred to herein as a “dynamic backfill” of the cache. This enables a better chance of presenting relevant results faster compared to simply caching a fixed list of top N results in advance, but with lower latency than a directory fall-back.

In embodiments, the application view may display the selected entries in an order in which they were received at the user terminal. In some alternative embodiments, the application view may display the selected entries ordered by cache group. As another example, in embodiments the application view may display the selected entries ordered by cache group and then within each cache group in the order they were received at the user terminal.

In embodiments, the set of data sources may be a set of multiple data sources, and the queried data sources may be a plurality of the data sources of said set. In this case the entries retrieved from each of the queried data sources being cached in a different corresponding cache group. In some such embodiments, at least some of the plurality of queried data sources may be external to the user terminal, in which case the entries retrieved from each of the external data sources being retrieved via a network. Further, in embodiments the multiple data sources may each have a different latency to retrieve the entries from the data source to the user terminal.

Combined with the dynamic backfill, the provision of the different cache groups for the different sources means that the different cache groups are filled and their results displayed in parallel, independently from one another, rather than exhausting one source before moving on to the next, etc. I.e. the mechanism does not wait to query and show the results from one data source before doing so for any others of the data sources, nor in any way tie the timing of the querying and display of results from one data source to that of any of the other data sources. The alternative way to handle multiple sources would be to delay the display of results from one source until the query to another sources has been exhausted or timed-out (see the directory fall-back and hybrid approaches discussed in the Background section). However this leads to more delay before potentially relevant results from at least one of the data sources can be output to the user. By applying the dynamic backfill approach to each of a plurality of independent cache groups in parallel on the other hand, this leads to a better chance of relevant results being presented more promptly to the user (i.e. with lower latency).

In embodiments where the selected entries are also displayed in the order they are received, this further improves the latency with which results are output to the user. The trade-off is a loss of “stability”—referring to the expectation of some users that if the same search query is entered on different occasions, the search results for that same search query should be displayed in the same order each time. However it is recognized herein that the loss of stability can be a worthwhile trade-off for reduced latency.

