CROSS-REFERENCE

[01] The present application claims conventional priority to Russian Patent Application No 2015125383, filed June 29, 2015, entitled "METHOD OF AND SYSTEM FOR UPDATING A DATA TABLE" the entirety of which is incorporated herein.

FIELD

[02] The present technology relates to systems and methods for updating a data table. In particular, the data table may be a hash table comprising an entrance table pointing to one or more chain of cells, each one of the cells comprising one or more values associated with a key stored in the entrance table.

BACKGROUND

General information regarding hash tables

[03] Data tables taking the form of hash tables are extensively relied upon to provide fast access to values indexed by one or more keys. Typically, a hash table comprise an entrance table pointing to one or more chain of cells. Each one of the cells comprises one or more values associated with a key stored in the entrance table. In many instances, a hash table is relied upon by multiple threats and/or processes and/or applications having to simultaneously access the hash table for either reading and/or writing operations (equally referred to as reading and/or writing threats or reading and/or writing processes). Those simultaneous accesses may require synchronization mechanisms to avoid conflicts between reading and writing operations. Such synchronization mechanisms may result in locking at least one of the cells of the one or more of the cells for a given period of time so as to allow completion of particular operations. As an example, a cell may be locked for writing operations thereby preventing reading operations to occur simultaneously. Even though efficient to preclude conflicts, such approach may result in a performance hit even in the absence of contention due to, as a first example, use of expensive atomic instructions and/or due to, as a second example, bypassing a cache to read from a memory wherein the chain of cells is stored. [04] In addition to the above, some applications may require ensuring that each one of the cells of a particular chain of cells reflects a series of values all "captured" at a same given time. Under a "conventional writing approach", one cell of the chain of cells is updated at a time. Given the fact that once a writing operation of a cell is completed, the cell may become accessible for reading operations, a reading of a chain of cells that is being updated at a same time may therefore result in accessing "inconsistent values". The inconsistency of the values may take the form of cells containing values taken at a different time even though they were from a same chain of cells. For example, if a reading threat is executed on a chain of cells while the chain of cells is being updated with new values, the reading threat may end up accessing a first set of cells which has just being updated by the writing threat and a second set of cells which has no yet being updated by the writing threat. This situation may be a particular concern for data structures comprising multiple chains of cells, each one of the chains of cells reflecting values associated with keys of an entrance table at a particular period of time (i.e., each one of the chains of cells being associated with a particular version of the values associated with the cells of the one of the chains of cells). Some previous attempts to alleviate this concern comprise pausing a reading threat of a chain of cells for as long as a writing threat may need to complete the writing of the complete chain of cells. As a person skilled in the art of the present technology may appreciate, such approach may come at the expense of performance, in particular for cases wherein the chain of cells comprises a high number of cells. Exemplary use of hash tables in a context of search engines

[05] Typically, in building a search-efficient data collection management system such as web search engines, data items are indexed according to some or all of the possible search terms that may be contained in search queries. Thus, conventionally an "inverted index" of the data collection is created, maintained, and updated by the system. The inverted index will comprise a large number of "posting lists" to be reviewed during execution of a search query. Each posting list corresponds to a potential search term and contains "postings", which are references to the data items in the data collection that include that search term (or otherwise satisfy some other condition that is expressed by the search term). For example, if the data items are text documents, as is often the case for Internet (or "Web") search engines, then search terms are individual words (and/or some of their most often used combinations), and the inverted index comprises one posting list for every word that has been encountered in at least one of the documents. [06] Search queries, especially those made by human users, typically have the form of a simple list of one or more words, which are the "search terms" of the search query. Every such search query may be understood as a request to the search engine to locate every data item in the data collection containing each and every one of the search terms specified in the search query. Processing of a search query will involve searching through one or more posting lists of the inverted index. As was discussed above, typically there will be a posting list corresponding to each of the search terms in the search query. Posting lists are searched as they can be easily stored and manipulated in a fast access memory device, whereas the data items themselves cannot (the data items are typically stored in a slower access storage device). This generally allows search queries to be performed at a much higher speed.

[07] Typically, each data item in a data collection is numbered. Rather than being ordered in some chronological, geographical or alphabetical order in the data collection, data items are commonly ordered (and thus numbered) within the data collection in descending order of what is known in the art as their "query- independent relevance" (hereinafter abbreviated to "QIR"). QIR is a system-calculated heuristic parameter defined in such a way that the data items with a higher QIR value are statistically more likely to be considered by a search requester of any search query as sufficiently relevant to them. The data items in the data collection will be ordered so that those with a higher QIR value will be found first when a search is done. They will thus appear at (or towards) the beginning of the search result list (which is typically shown in various pages, with those results at the beginning of the search result list being shown on the first page). Thus, each posting list in the inverted index will contain postings, a list of references to data items containing the term with which that posting list is associated, with the postings being ordered in descending QIR value order. (This is very commonly the case in respect of web search engines.). [08] It should be evident, however, that such a heuristic QIR parameter may not provide for an optimal ordering of the search results in respect of any given specific query, as it will clearly be the case that a data item which is generally relevant in many searches (and thus high in terms of QIR) may not be specifically relevant in any particular case. Further, the relevance of any one particular data item will vary between searches. Because of this, conventional search engines implement various methods for filtering, ranking and/or reordering search results to present them in an order that is believed to be relevant to the particular search query yielding those search results. This is known in the art as "query- specific relevance" (hereinafter abbreviated "QSR"). Many parameters are typically taken into account when determining QSR. These parameters include: various characteristics of the search query; of the search requester; of the data items to be ranked; data having been collected during (or, more generally, some "knowledge" learned from) past similar search queries. [09] Thus, the overall process of executing a search query can be considered as having two broad distinct stages: A first stage wherein all of the search results are collected based (in part) on their QIR values, aggregated and ordered in descending QIR order; and a second stage wherein at least some of the search results are reordered according to their QSR. Afterwards a new QSR-ordered list of the search results is created and delivered to the search requester. The search result list is typically delivered in parts, starting with the part containing the search results with the highest QSR.

[10] Typically, in the first stage, the collecting of the search results stops after some predefined maximum number of results has been attained or some predefined minimum QIR threshold has been reached. This is known in the art as "pruning"; and it occurs, as once the pruning condition has been reached, it is very likely that the relevant data items have already been located.

[11] Typically, in the second stage, a shorter, QSR-ordered, list (which is a subset of the search results of the first stage) is produced. This is because a conventional web search engine, when conducting a search of its data collection (which contains several billions of data items) for data items satisfying a given search query, may easily produce a list of tens of thousands of search results (and even more in some cases). Obviously the search requester cannot be provided with such an amount of search results. Hence the great importance of narrowing down the search results actually provided to the requester to a few tens of result items that are potentially of highest relevance to the search requester. [12] In order to address the ranking needs required for proper operations of web search engines such as, for example but without being limited thereto, the generation of QIR values and/or QSR values, multiple constructions of ranking models have been developed over the recent years. These ranking models may enable ranking of documents (e.g., web pages, text files, image files and/or video files) according to one or more parameters. Under some approaches, machine-learning algorithms are used for construction and operations of ranking models and are typically referred to as Machine-learned ranking (hereinafter abbreviated to "MLR"). As one person skilled in the art of the present technology may appreciate, MLR is not limited to web search engines per se but may be applicable to a broad range of information retrieval systems.

[13] Under some approaches, the ranking generated by a MLR model may consist of a ranking value associated with a document that may equally be referred to as a "parameter of interest" or "label". The document may equally be referred to as a file. The ranking may consist of an "absolute ranking" of an absolute order of a first document compared to a second document such as, for example, the QIR value. In some other instances, the ranking may consist of a "relative ranking" of a relative order of the first document compared to the second document given a particular context such as, for example, the QSR value. In order to associate documents with parameters of interest, MLR models may, in some instances, be generated and maintained through machine-learning algorithms relying on one or more training samples. The number of MLR models that is required for particular application may greatly vary. Conventional web search engines such as Yandex™ may rely on several thousands of MLR models that may be used in parallel during processing of search queries.

[14] In some instances, MLR models may rely on tree models and feature vectors comprising one or more parameters to associate a document (e.g., a web page) and a parameter of interest (e.g., a ranking value). The one or more parameters of a feature vector may be used to define a specific path in a tree model thereby allowing identification of which parameter of interest is to be associated with a particular document. Under some approaches, the one or more parameters may be of different types such as binary type, integer type and/or category type.

[15] Under some approaches, a system hosting a tree model for the purpose of associating a document to a parameter of interest may receive a feature vector comprising parameters associated with the document. In some instances, the parameters may be implemented as first data associated with the document and second data also associated with the document. As an example, the first data may be of a binary type and/or of a real number type and the second data may be of a category type. The second data may be indicative of multiple features, for example a feature f 1 representative of an URL and a feature f2 representative of a key word. As a person skilled in the art of the present technology may appreciate, upon processing the feature vector, the system hosting the tree model may establish that at least a portion of the feature vector is unknown to the tree model. For the purpose of exemplifying this situation, f2 is established as being the portion of the feature vector that is unknown to the tree model. As a result, the system may establish that it is necessary to add one or more new fields to a data structure representing the tree model, namely f2. Upon facing a similar situation, a conventional approach consists of allocating, in a memory of the system wherein the data modelizing the tree model is stored, additional memory arrays. The size of the memory arrays to be allocated may dependent both from the data modelizing the tree model and f2. The size of the memory arrays to be allocated may depend on a number of possible values that f2 may take. As a person skilled in the art of the present technology may appreciate, such approach may present ineffiencies in how the memory of the system is used as the memory arrays allocated as a result of the number of possible values of f2 may represent a substantial size, in particular if the number of possible values for f2 is high. In addition, the memory arrays being allocated based on the number of possible value of f2, it might often be that the memory arrays have only a limited number of actual entries of f2 therefore resulting in memory arrays being allocated but not actually used at a given time.

[16] The Applicant has previously identified in the '563 application, that there is a need for improved methods and systems aiming at more efficiently managing memory usage of a system wherein data modelizing a tree model is stored. In particular, there is a need for limiting the constraint associated with allocating memory arrays of a memory of the system depending on a number of possible values that a parameter, in particular a parameter of category type, may take. [17] The technology presented in the '563 application proposes some improvements over the prior art by providing a computer-implemented method of generating a hashed complex vector indicative of an association between a document and a parameter of interest. This technology illustrates an example of a hash table relied upon to associate documents and parameter of interests. [18] In some embodiments, in addition to associating documents and parameters of interests by relying upon a hash table, it may be desirable to ensure that a series of parameters of interests associated with documents through the hash table defines a version of the parameters of interests at a given period of time. For example, the series of parameters of interests may be represented by a series of values, each one of the values being stored in a cell of a chain of cells, the chain of cells being associated with a version of the parameters of interest at the given time. Upon modification of one or more parameters of interests, a new version of the chain of cells may need to be created. For at least the reasons detailed in the above paragraphs, conventional approaches may either result in (i) pausing a reading threat of the chain of cells while completing a writing threat of the chain of cells to generate the new version of the chain of cells; and/or (ii) allowing reading threat of the chain of cells while completing a writing of the chain of cells at the expense of potential inconsistencies amongst the values represented by the cells (some being read before the writing threat occurs for a particular cell, some other being reading after the reading threat occurs for a particular cell). Improvement may be therefore desirable, not only for the particular context of hash tables associating documents and parameters of interests, but also for management of any data structures modelized by an association between an entrance table and one or more chains of cells.

SUMMARY

[19] Embodiments of the present technology have been developed based on developers' appreciation of at least one shortcoming associated with the prior art. Even though method and systems for managing reading and writing threats of data tables, and particularly hash tables, have been developed, improvements may still be desirable, in particular improvements aiming at (i) reducing and, in some instances, eliminating, an amount of time during which at least some portions of the data tables (e.g., some cells of a chain of cells) may not be accessible during writing operations in a memory of a device; and/or (ii) improving consistency amongst values represented by a specific version of a chain of cells stored in the memory of the device.

[20] The present technology arises from an observation made by the inventor(s) that while a new chain of cells of a data table (which may correspond to a new version of an existing chain of cells) is being created, an entrance table of the data table may direct a reading threat to a previously existing chain of cells of the data table (which may correspond to a current version of the chain of cells), at least until a determination is made that the new chain of cells of the data table is ready to be released. The present technology may therefore allow to (i) avoid that some cells of a chain of cells may not be accessible during writing operations as the previously existing chain of cells remains accessible while the new chain of cells is being created; and/or (ii) provide consistency of values represented by a specific version of a chain of cells as the values associated with the new chain of cells are all released at a same time (e.g., upon determination that the new chain of cells is ready to be released). In some embodiments, the present technology may provide what could be referred to as a lock-free mechanism allowing reading and/or writing operations at any point of time without having to at least partially lock a data table for a certain period of time. [21] Thus, in one aspect, various implementations of the present technology provide computer-implemented method of updating a data table, the method for execution by a processor, the method comprising:

• acquiring, from a non-transitory computer-readable medium, a new data element based on which the data table is to be updated;

• creating, in the non-transitory computer-readable medium, a new chain of cells being associated with a new version reference corresponding to a new version of the data table, the new chain of cells comprising a first cell, a last cell and at least one cell associated with a value generated based on the new data element;

• while the new chain of cells is being created, directing an entrance table of the data table to a current chain of cells being associated with a current version reference corresponding to a current version of the data table, the current version reference being anterior to the new version reference;

• upon determining that the new chain of cells is ready to be released:

- allowing the entrance table to access the new chain of cells; and

- causing the new version reference to become the current version reference.

[22] In some aspects of the present technology, creating the new chain of cells further comprises:

• accessing, from the non-transitory computer-readable medium, the current chain of cells;

• duplicating, in the non-transitory computer-readable medium, at least a portion of the current chain of cells; and

• updating, in the non-transitory computer-readable medium, at least one cell of the at least the portion of the current chain of cells, the updating comprising generating a new value to be associated with the at least one cell based on a value of the at least one cell in the current chain of cells and the new data element. [23] In some other aspects of the present technology, the new chain of cells comprises at least one cell associated with a pointer pointing to a corresponding cell in the previous chain of cells.

[24] In some aspects of the present technology, at least one cell of the new chain of cells is associated with at least one of a key, a version reference, a previous cell of the new chain of cells and a next cell of the new chain of cells.

[25] In some other aspects of the present technology, the version reference corresponds to a version reference of the new chain of cells.

[26] In some aspects of the present technology, the entrance table comprises at least one pointer pointing to a first cell of the current chain of cells while the new chain of cells is being created.

[27] In some other aspects of the present technology, the at least one pointer is caused to point to the first cell of the new chain of cells once determination that the new chain of cells is ready to be released is made. [28] In some aspects of the present technology, the data table is a hash table.

[29] In some other aspects of the present technology, the entrance table is a list of keys, each one of the keys pointing to at least one cell of the current chain of cells assigned by a hash function.

[30] In some aspects of the present technology, the current version reference and the new version reference corresponds to a current revision and a new revision respectively.

[31] In some other aspects of the present technology, determining that the new chain of cells is ready to be released comprises at least one of (i) determining that the new chain of cells is complete; and (ii) determining that a predefined period of time has lapsed.

[32] In some aspects of the present technology, the entrance table does not have access to the new chain of cells while the new chain of cells is being created.

[33] In some aspects of the present technology, the current version reference and the new version reference establishes a chronological sequence reflecting values of the data table at a given time. [34] In some other aspects of the present technology, the current version reference and the new version reference are each associated with an integer and wherein the new version reference corresponds to the current version reference incremented by "1".

[35] In some aspects of the present technology, the current chain of cells include values associated with a first given time and the new chain of cells include updated values associated with a second given time, the updated values being reflective of a modification of the values between the first given time and the second given time.

[36] In other aspects, various implementations of the present technology provide a non- transitory computer-readable medium storing program instructions for updating a data table, the program instructions being executable by a processor of a computer-based system to carry out one or more of the above-recited methods.

[37] In other aspects, various implementations of the present technology provide a computer-based system, such as, for example, but without being limitative, an electronic device comprising at least one processor and a memory storing program instructions for updating a data table, the program instructions being executable by one or more processors of the computer-based system to carry out one or more of the above-recited methods.

[38] In the context of the present specification, unless expressly provided otherwise, an "electronic device", an "electronic device", a "server", a, "remote server", and a "computer- based system" are any hardware and/or software appropriate to the relevant task at hand. Thus, some non-limiting examples of hardware and/or software include computers (servers, desktops, laptops, netbooks, etc.), smartphones, tablets, network equipment (routers, switches, gateways, etc.) and/or combination thereof.

[39] In the context of the present specification, unless expressly provided otherwise, the expression "computer-readable medium" and "memory" are intended to include media of any nature and kind whatsoever, non-limiting examples of which include RAM, ROM, disks (CD- ROMs, DVDs, floppy disks, hard disk drives, etc.), USB keys, flash memory cards, solid state- drives, and tape drives.

[40] In the context of the present specification, unless expressly provided otherwise, an "indication" of an information element may be the information element itself or a pointer, reference, link, or other indirect mechanism enabling the recipient of the indication to locate a network, memory, database, or other computer-readable medium location from which the information element may be retrieved. For example, an indication of a document could include the document itself (i.e. its contents), or it could be a unique document descriptor identifying a file with respect to a particular file system, or some other means of directing the recipient of the indication to a network location, memory address, database table, or other location where the file may be accessed. As one skilled in the art would recognize, the degree of precision required in such an indication depends on the extent of any prior understanding about the interpretation to be given to information being exchanged as between the sender and the recipient of the indication. For example, if it is understood prior to a communication between a sender and a recipient that an indication of an information element will take the form of a database key for an entry in a particular table of a predetermined database containing the information element, then the sending of the database key is all that is required to effectively convey the information element to the recipient, even though the information element itself was not transmitted as between the sender and the recipient of the indication. [41] In the context of the present specification, unless expressly provided otherwise, the words "first", "second", "third", etc. have been used as adjectives only for the purpose of allowing for distinction between the nouns that they modify from one another, and not for the purpose of describing any particular relationship between those nouns. Thus, for example, it should be understood that, the use of the terms "first server" and "third server" is not intended to imply any particular order, type, chronology, hierarchy or ranking (for example) of/between the server, nor is their use (by itself) intended imply that any "second server" must necessarily exist in any given situation. Further, as is discussed herein in other contexts, reference to a "first" element and a "second" element does not preclude the two elements from being the same actual real- world element. Thus, for example, in some instances, a "first" server and a "second" server may be the same software and/or hardware, in other cases they may be different software and/or hardware.

[42] Implementations of the present technology each have at least one of the above- mentioned object and/or aspects, but do not necessarily have all of them. It should be understood that some aspects of the present technology that have resulted from attempting to attain the above-mentioned object may not satisfy this object and/or may satisfy other objects not specifically recited herein. [43] Additional and/or alternative features, aspects and advantages of implementations of the present technology will become apparent from the following description, the accompanying drawings and the appended claims.

BRIEF DESCRIPTION OF THE DRAWINGS [44] For a better understanding of the present technology, as well as other aspects and further features thereof, reference is made to the following description which is to be used in conjunction with the accompanying drawings, where:

[45] Figure 1 is a diagram of a computer system suitable for implementing the present technology and/or being used in conjunction with implementations of the present technology; [46] Figure 2 is a diagram of a networked computing environment in accordance with an embodiment of the present technology;

[47] Figure 3 is a diagram illustrating a data table in accordance with an embodiment of the present technology;

[48] Figure 4 is a diagram illustrating a data table in accordance with another embodiment of the present technology; and

[49] Figure 5 is a diagram illustrating a flowchart illustrating a computer-implemented method implementing embodiments of the present technology.

[50] It should also be noted that, unless otherwise explicitly specified herein, the drawings are not to scale. DETAILED DESCRIPTION

[51] The examples and conditional language recited herein are principally intended to aid the reader in understanding the principles of the present technology and not to limit its scope to such specifically recited examples and conditions. It will be appreciated that those skilled in the art may devise various arrangements which, although not explicitly described or shown herein, nonetheless embody the principles of the present technology and are included within its spirit and scope. [52] Furthermore, as an aid to understanding, the following description may describe relatively simplified implementations of the present technology. As persons skilled in the art would understand, various implementations of the present technology may be of a greater complexity. [53] In some cases, what are believed to be helpful examples of modifications to the present technology may also be set forth. This is done merely as an aid to understanding, and, again, not to define the scope or set forth the bounds of the present technology. These modifications are not an exhaustive list, and a person skilled in the art may make other modifications while nonetheless remaining within the scope of the present technology. Further, where no examples of modifications have been set forth, it should not be interpreted that no modifications are possible and/or that what is described is the sole manner of implementing that element of the present technology.

[54] Moreover, all statements herein reciting principles, aspects, and implementations of the present technology, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof, whether they are currently known or developed in the future. Thus, for example, it will be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the present technology. Similarly, it will be appreciated that any flowcharts, flow diagrams, state transition diagrams, pseudo-code, and the like represent various processes which may be substantially represented in computer-readable media and so executed by a computer or processor, whether or not such computer or processor is explicitly shown.

[55] The functions of the various elements shown in the figures, including any functional block labeled as a "processor" or a "graphics processing unit", may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. In some embodiments of the present technology, the processor may be a general purpose processor, such as a central processing unit (CPU) or a processor dedicated to a specific purpose, such as a graphics processing unit (GPU). Moreover, explicit use of the term "processor" or "controller" should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, network processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), read-only memory (ROM) for storing software, random access memory (RAM), and non-volatile storage. Other hardware, conventional and/or custom, may also be included.

[56] Software modules, or simply modules which are implied to be software, may be represented herein as any combination of flowchart elements or other elements indicating performance of process steps and/or textual description. Such modules may be executed by hardware that is expressly or implicitly shown.

[57] With these fundamentals in place, we will now consider some non-limiting examples to illustrate various implementations of aspects of the present technology. [58] Referring to FIG 1, there is shown a computer system 100 suitable for use with some implementations of the present technology, the computer system 100 comprising various hardware components including one or more single or multi-core processors collectively represented by processor 110, a graphics processing unit (GPU) 111, a solid-state drive 120, a random access memory 130, a display interface 140, and an input/output interface 150. [59] Communication between the various components of the computer system 100 may be enabled by one or more internal and/or external buses 160 (e.g. a PCI bus, universal serial bus, IEEE 1394 "Firewire" bus, SCSI bus, Serial-ATA bus, etc.), to which the various hardware components are electronically coupled. The display interface 140 may be coupled to a monitor 142 (e.g. via an HDMI cable 144) visible to a user 170, and the input/output interface 150 may be coupled to a touchscreen (not shown), a keyboard 151 (e.g. via a USB cable 153) and a mouse 152 (e.g. via a USB cable 154), each of the keyboard 151 and the mouse 152 being operable by the user 170.

[60] According to implementations of the present technology, the solid-state drive 120 stores program instructions suitable for being loaded into the random access memory 130 and executed by the processor 110 and/or the GPU 111 for processing activity indications associated with a user. For example, the program instructions may be part of a library or an application.

[61] In FIG 2, there is shown a networked computing environment 200 suitable for use with some implementations of the present technology, the networked computing environment 200 comprising a master server 210 in communication with a first slave server 220, a second slave server 222 and a third slave server 224 (also referred to as the slave servers 220, 222, 224 hereinafter) via a network (not depicted) enabling these systems to communicate. In some non- limiting embodiments of the present technology, the network can be implemented as the Internet. In other embodiments of the present technology, the network may be implemented differently, such as any wide-area communications network, local-area communications network, a private communications network and the like.

[62] The networked computing environment 200 may contain more or less slave servers without departing from the scope of the present technology. In some embodiments, no "master server - slave server" configuration may be required, a single server may be sufficient. The number of servers and the type of architecture is therefore not limitative to the scope of the present technology.

[63] In one embodiment, a communication channel (not depicted) between the master server 210 and the slave servers 220, 222, 224 may be established to allow data exchange. Such data exchange may occur on a continuous basis or, alternatively, upon occurrence of certain events. For example, in the context of crawling webpages and/or processing a search query, a data exchange may occur as a result of the master server 210 receiving data associated with a document for which association with a parameter of interest is to be made by the networked computing environment. In some embodiments, the master server 210 may receive the data from a frontend search engine server (not depicted) and send the data to one or more of the slave servers 220, 222, 224. Once received from the master server 210, the one or more slave servers 220, 222, 224 may process the data in accordance with the present technology to update a data table indicative of an association between the document and the parameter of interest. In some embodiments, the data table may take the form of one or more hash tables such as one or more hash tables 230, 232, 234 associated with the one or more slave servers 220, 222, 224. Other embodiments may also become apparent to the person skilled in the art of the present technology. The number of data tables, the distribution of the data tables and the storage localisation of the data tables are not limitative and multiple variations may be envisioned without departing from the scope of the present technology.

[64] The master server 210 can be implemented as a conventional computer server and may comprise some or all of the features of the computer system 100 depicted at FIG. 1. In an example of an embodiment of the present technology, the master server 210 can be implemented as a Dell™ PowerEdge™ Server running the Microsoft™ Windows Server™ operating system. Needless to say, the master server 210 can be implemented in any other suitable hardware and/or software and/or firmware or a combination thereof. In the depicted non-limiting embodiment of present technology, the master server 210 is a single server. In alternative non-limiting embodiments of the present technology, the functionality of the master server 210 may be distributed and may be implemented via multiple servers.

[65] The implementation of the master server 210 is well known to the person skilled in the art of the present technology. However, briefly speaking, the master server 210 comprises a communication interface (not depicted) structured and configured to communicate with various entities (such as the frontend search engine server and/or the slave servers 220, 222, 224, for example and other devices potentially coupled to the network) via the network. The master server 210 further comprises at least one computer processor (e.g., a processor 110 of the master server 210) operationally connected with the communication interface and structured and configured to execute various processes to be described herein.

[66] In an exemplary embodiment relating to the crawling of webpages and/or the processing of search queries, the general purpose of the master server 210 may be to coordinate the processing of the data associated with the document by the slave servers 220, 222, 224. As previously described, in an embodiment, the data may be transmitted to some or all of the slave servers 220, 222, 224 so that the slave servers 220, 222, 224 may conduct associations between the document and a parameter of interest by updating the data tables 230, 232, 234. In return, the master server 210 may receive, from the slave servers 220, 222, 224, the parameter of interest to be associated with the document based on a reading of the data tables 230, 232, 234. In some other embodiments, the master server 210 may be limited to sending the data without receiving any parameter of interest in return. Other variations as how the master server 210 interacts with the slave servers 220, 222, 224 may be envisioned without departing from the scope of the present technology and may become apparent to the person skilled in the art of the present technology. In addition, it should be also expressly understood that in order to simplify the description presented herein above, the configuration of the master server 210 has been greatly simplified. It is believed that those skilled in the art will be able to appreciate implementational details for the master server 210 and for components thereof that may have been omitted for the purposes of simplification of the description.

[67] The slave servers 220, 222, 224 can be implemented as conventional computer servers and may comprise some or all of the features of the computer system 100 depicted at FIG. 1. In an example of an embodiment of the present technology, the slave servers 220, 222, 224 can be implemented as a Dell™ PowerEdge™ Server running the Microsoft™ Windows Server™ operating system. Needless to say, the slave servers 220, 222, 224 can be implemented in any other suitable hardware and/or software and/or firmware or a combination thereof. In the depicted non-limiting embodiment of present technology, the slave servers 220, 222, 224 operate on a distributed architecture basis. In alternative non-limiting embodiments, a single slave server may be relied upon to operate the present technology.

[68] The implementation of the slave servers 220, 222, 224 is well known to the person skilled in the art of the present technology. However, briefly speaking, each one of the slave servers 220, 222, 224 may comprise a communication interface (not depicted) structured and configured to communicate with various entities (such as the frontend search engine server and/or the master server 210, for example and other devices potentially coupled to the network) via the network. Each one of the slave servers 220, 222, 224 further comprises at least one computer processor (e.g., similar to the processor 110 depicted at FIG. 1) operationally connected with the communication interface and structured and configured to execute various processes to be described herein. Each one of the slave servers 220, 222, 224 further may comprise one or more memories (e.g., similar to the solid-state drive 120 and/or the random access memory 130 depicted at FIG. 1).

[69] The general purpose of the slave servers 220, 222, 224 is to manage the storing, reading and writing of the hash tables 230, 232, 234. As previously described, in an embodiment, the data may be received from the master server 210 and/or the frontend server. Once received, the slave servers 220, 222, 224 may conduct associations between the document and a parameter of interest. Once the associations have been conducted, the slave servers 220, 222, 224 may update the hash tables 230, 232, 234 accordingly for later access by the master server 210 and/or the slave servers 220, 222, 224. Other variations as how the slave servers 220, 222, 224 interact with the master server 210 and/or the hash tables 230, 232, 234 may be envisioned without departing from the scope of the present technology and may become apparent to the person skilled in the art of the present technology. In addition, it should be also expressly understood that in order to simplify the description presented herein above, the configuration of the slave servers 220, 222, 224 has been greatly simplified. It is believed that those skilled in the art will be able to appreciate implementational details for the slave servers 220, 222, 224 and for components thereof that may have been omitted for the purposes of simplification of the description.

[70] Still referring to FIG. 2, the slave servers 220, 222, 224 may each be communicately coupled to databases, each one of the databases hosting the hash table 230, the hash table 232 and the hash table 234. In some embodiments, one of the hash tables 230, 232, 234 may be hosted in multiple databases. In some other embodiments, one database may host at least two of the hash tables 230, 232, 234. The databases hosting the hash tables 230, 232, 234 may be part of the slave servers 220, 222, 224 (e.g., stored in the memories of the slave servers 220, 222, 224 such as the solid-state drive 120 and/or the random access memory 130) or be hosted on distinct database servers. In some embodiments, a single database accessed by the slave servers 220, 222, 224 may be sufficient. The number of databases and the arrangement of the databases are therefore not limitative to the scope of the present technology. The databases may be used to access and/or store data relating to one or more hash tables representative of tree models generated in accordance with the technology depicted in the '563 application. In some embodiments, the databases may be accessed by the slave servers 220, 222, 224 to identify a parameter of interest to be associated with the document further to the processing of the data by the slave servers 220, 222, 224 by conducting a reading operation on the hash tables 230, 232, 234. In some other embodiments, the databases may be accessed by the slave servers 220, 222, 224 to store a new entry (also referred to as a "hashed complex vector" and/or "key" hereinafter) in the hash tables 230, 232, 234, the new entry having been generated further to the processing of the data and being representative of a parameter of interest to be associated with the document.

[71] More details regarding how the hash tables 230, 232, 234 are structured and processed will be provided in connection with the description of FIG. 3 and 4. [72] Turning now to FIG. 3, a data table is depicted. In this embodiment, the data table is embodied as a hash table. As previously discussed, the data table may be embodied by a data structure different than a hash table without departing from the scope of the present technology. In the embodiment depicted in FIG. 3, the hash table comprises an entrance table 310, a chain of cells "Rev_l" 320, a chain of cells "Rev_2" 330, a chain of cells "Rev_3" 340 and a chain of cells "Rev_4" 350. In some embodiments, the entrance table 310 comprises multiple cells, each pointing to at least one cell of at least one of the chain of cells 320, 330, 340, 350. For example, a cell 312 of the entrance table 310 points to a cell 342 of the chain of cells 340. In an alternative embodiment, the cell 312 may point to a first cell of the chain of cells 340. In the illustrated embodiment, the cell 312 may be representative of a key and the cell 342 may be representative of a value associated with the key. In an exemplary embodiment, the value may be representative of a parameter of interest associated with a document similar to the association between a parameter of interest and a document depicted in the '563 application. In such exemplary embodiment, each one of the cells may be representative of a parameter of interest thereby forming a collection of parameters of interest associated with multiple documents at a same given time. Upon comparing parameters of interest associated with two distinct documents, a consistent comparison of the parameters of interest may be obtained as the chain of cells 340 provides a "snapshot" of the parameters of interest at a given time.

[73] In some embodiments, the hash table may be structured so that the entrance table 310 comprises a collection of keys each associated with a Uniform Resource Locator (URL), a search query, and/or a search query associated with an URL. In such embodiment, the URL, the search query and/or the search query associated with the URL is hashed to generate a key. The generated key is then use to identify a corresponding key in the entrance table 310 thereby allowing to access one or more value associated with the corresponding key by looking up the chain of cells 340 and/or a previous revision of the chain of cells, such as the chain of cells 330 or 320. In some embodiments, the one or more values may be a number of clicks, a search result prediction, a probability of click, a document relevance, and/or a user interest. As it may become apparent to the person skilled in the art of the present technology, this exemplary embodiments, including the embodiment referring to the '563 application, are provided to illustrate an example as to what kind of data may be stored by the chain of cells 340. The present technology is not limited to such embodiment and any kind of data may be stored by the chain of cells 340 in association with the entrance table 310 and may be used for various type of applications (i.e., applications not limited to search engine technology), as it will become apparent to the person skilled in the art of the present technology.

[74] In some embodiments, each one of the cells of the chain of cells 340, such as the cell 342 may comprise, in addition to one or more value, a revision reference (e.g., Rev_3), a indication of a previous cell and/or an indication of a next cell thereby forming a linked chain of cells. In some embodiments, at least one of the cells of the chain of cells, such as the cell 342 may point to a cell of a different chain of cells such as, for example, a cell 332 of the chain of cells 330. In turn, the cell 332 may point to a cell 322 of the chain of cells 320. In some embodiments, the cells 342, 332, 322 may relate to one another. For example, a value associated with the cell 342 is same as or based on a value associated with the cell 332. In a similar fashion, a value associated with the cell 332 is same as or based on a value associated with the cell 322. As a result, a reading threat first accessing the entrance table 310 and identifying the cell 312 as a corresponding key may then be pointed to the cell 342, then the cell 332 and finally the cell 322 to access a value associated with the corresponding key. In some embodiments, the entrance table 310 contains reference to a first cell of the chain of cells 340. The reading threat then accesses the first cell of the chain of cells 340 and look up across the chain of cells 340 until it accesses the cell 342. As each one of the cells of the chain of cells 340 contains information identifying a next cell in the chain, the reading threat may be properly directed while looking up across the chain of cells 340. In some embodiments, because a value associated with the cell 312 of the entrance table 310 did not change between a generation of the chain of cells 320 and the chain of cells 340, the value is not duplicated during the creation of the cell 332 and the cell 342. Instead, a pointer from the cell 332 to the cell 322 and a pointer from cell 342 to cell 332 are created. As a result the value "contained" in the cell 312 does not need to be duplicated in the cell 322 and in the cell 332 and the reading threat may access the value by first reading the cell 342, then the cell 332 and may finally access the value stored in the cell 322. In yet some other embodiments, a value associated with the cell 312 of the entrance table 310 may be "reconstructed" by a reading threat (i) accessing the cell 342 and a portion of a value associated therewith; then (ii) accessing the cell 332 and another portion of a value associated therewith; and then (iii) accessing the cell 322 and yet another portion of a value associated therewith. The value associated with the cell 312 may then be "reconstructed" by successively accessing the cells 342, 332 and 322 and by applying a combining function to the data accessed in the cells 342, 332 and 322. As a person skilled in the art of the present technology may appreciate, this embodiment aims at exemplified an exemplary data structure and should not be construed as being limitative. Other variations, including, but not limited thereto, duplicating the value upon creating the cell 332 and then the cell 342 or associating newly created value with the cell 342 independently of the value associated with the cell 332 may be envisioned without departing form the scope of the present technology. [75] Still referring to FIG. 3, the chain of cells 350 is illustrated as being created but not yet released and therefore not yet accessible through the entrance table 310. The chain of cells 350 includes a cell 352. In some embodiments, the cell 352 may be created based on a previous version of a cell of a previously created chain of cells. For example, the cell 352 may comprise a value duplicated from the cell 342 of the chain of cells 340. The cell 352 may also include a pointer to the cell 342 so that a reading threat accessing the cell 352 is directed to the cell 342. As illustrated in FIG. 3, because the chain of cells 350 is being created (e.g., a writing threat aiming at creating a new revision of the chain of cells is on-going), it is not yet released and therefore not accessible by a reading threat accessing the entrance table 310. Instead, the entrance table 310 directs the reading threat to the chain of cells 340 at least until the creation of the chain of cells is completed. As previously depicted, in some embodiments, the entrance table 310 directs the reading threat to the first cell of the chain of cells 340. As a result, as a person skilled in the art of the present technology may appreciate, a writing threat in a process of creating the chain of cells 350 does not interfere with a reading threat in a process of accessing one or more values through the entrance table 310.

[76] Turning now to FIG. 4, the hash table is illustrated with the chain of cells 350 released and now accessible to a reading threat through the entrance table 310. In some embodiments, releasing the chain of cells 350 may be further to a determination that the writing threat creating the chain of cells 350 is completed. In some other embodiments, releasing the chain of cells 350 may be further to a determination that a predefined period of time has lapsed. In some embodiments, upon releasing the chain of cells 350, the entrance table 310 is at least partially updated so as be able to direct a reading threat to a first cell of the chain of cells 350. In some other embodiments, the entrance table 310 may be updated so that the cell 312 of the entrance table 310 points to the cell 352 of the chain of cells 350. In addition, upon releasing the chain of cells 350 a revision number may be incremented and may be transmitted to a service managing the reading threat. For example, upon releasing the chain of cells 350, the revision number is incremented so as to be equal to "4". The service may then refer to the chain of cells 350 as being the latest version of the chain of cells and therefore the latest version of values and/or data stored by the chain of cells. In some embodiments, the cell 352 points to the cell 342 of the chain of cells 340 thereby allowing to direct a reading threat to the cell 342.

[77] Having described, with reference to FIG. 1 to FIG. 4, some non-limiting example instances of systems and computer-implemented methods used in connection with the problem of updating a data table, we shall now describe general solutions to the problem with reference to FIG. 5.

[78] More specifically, FIG. 5 shows a flowchart illustrating a computer-implemented method 500 of updating a data table. In some embodiments, the data table is a hash table. [79] The method 500 starts at step 502 by acquiring, from a non-transitory computer- readable medium, a new data element based on which the data table is to be updated. In some embodiments, the new data element may be based on one or more previous data elements stored in a current or a previous version of the data table. In some other embodiments, the new data element may be acquired independently from the one or more previous data elements stored in the current or the previous version of the data table. Then, at a step 504, a new chain of cells is created in the non-transitory computer-readable medium. The new chain of cells is associated with a new version reference corresponding to a new version of the data table. The new chain of cells comprises a first cell, a last cell and at least one cell associated with a value generated based on the new data element. It should be understood that the term "value" is not limitative and may encompass various types of data as it may become apparent to a person skilled in the art of the present technology. In some embodiments, creating the new chain of cells includes

(i) accessing, from the non-transitory computer-readable medium, the current chain of cells;

(ii) duplicating, in the non-transitory computer-readable medium, at least a portion of the current chain of cells; (iii) updating, in the non-transitory computer-readable medium, at least one cell of the at least the portion of the current chain of cells, the updating comprising generating a new value to be associated with the at least one cell based on a value of the at least one cell in the current chain of cells and the new data element.

[80] In yet some embodiments, the new chain of cells comprises at least one cell associated with a pointer pointing to a corresponding cell in the previous chain of cells. In some embodiments, the at least one cell of the new chain of cells is associated with at least one of a key, a version reference, a previous cell of the new chain of cells and a next cell of the new chain of cells. The version reference may correspond to a version reference of the new chain of cells. [81] In some embodiments, while the step 504 is being executed, a step 506 is also executed. The step 506, while the new chain of cells is being created in accordance with the step 504, directs an entrance table of the data table to a current chain of cells being associated with a current version reference corresponding to a current version of the data table, the current version reference being anterior to the new version reference. In some embodiments, the entrance table comprises at least one pointer pointing to a first cell of the current chain of cells while the new chain of cells is being created. In some embodiments, the entrance table is a list of keys, each one of the keys pointing to at least one cell of the current chain of cells assigned by a hash function. In some embodiments, the current version reference corresponds to a current revision and the new version reference corresponds to a new revision. The current version reference and the new version reference establish a chronological sequence reflecting values of the data table at a given time. In yet some other embodiments, the current version reference and the new version reference are each associated with an integer and the new version reference corresponds to the current version reference incremented by "1". In some embodiments, the current chain of cells include values associated with a first given time and the new chain of cells include updated values associated with a second given time, the updated values being reflective of a modification of the values between the first given time and the second given time.

[82] The method 500 also comprises a step 508 which may be executed in parallel to the steps 504 and 506 to ensure that a timely determination that the new chain of cells is ready to be released is made. The step 508, upon determining that the new chain of cells is ready to be released is made causes the execution of a step 510 and the execution of a step 512. The step 510 comprises allowing the entrance table to access the new chain of cells. The step 512 comprises causing the new version reference to become the current version reference. In some embodiments, the at least one pointer is caused to point to the first cell of the new chain of cells once determination that the new chain of cells is ready to be released is made. In some embodiments, determining that the new chain of cells is ready to be released comprises (i) determining that the new chain of cells is complete and/or (ii) determining that a predefined period of time has lapsed. In some embodiments, the entrance table does not have access to the new chain of cells while the new chain of cells is being created.

[83] While the above-described implementations have been described and shown with reference to particular steps performed in a particular order, it will be understood that these steps may be combined, sub-divided, or re-ordered without departing from the teachings of the present technology. Accordingly, the order and grouping of the steps is not a limitation of the present technology.

[84] As such, the methods and systems implemented in accordance with some non-limiting embodiments of the present technology can be represented as follows, presented in numbered clauses. [85] [Clause 1] A computer-implemented method (500) of updating a data table, the method for execution by a processor (110), the method comprising: acquiring (502), from a non-transitory computer-readable medium (120, 130), a new data element based on which the data table is to be updated; creating (504), in the non-transitory computer-readable medium (120, 130), a new chain of cells (350) being associated with a new version reference corresponding to a new version of the data table, the new chain of cells (350) comprising a first cell, a last cell and at least one cell associated with a value generated based on the new data element; while the new chain of cells (350) is being created, directing (506) an entrance table of the data table (310) to a current chain of cells (340) being associated with a current version reference corresponding to a current version of the data table, the current version reference being anterior to the new version reference; upon determining (508) that the new chain of cells (350) is ready to be released: allowing (510) the entrance table (310) to access the new chain of cells (350); and causing (512) the new version reference to become the current version reference.

[86] [Clause 2] The method of clause 1, wherein creating the new chain of cells (350) further comprises: accessing, from the non-transitory computer-readable medium (120, 130), the current chain of cells (340); duplicating, in the non-transitory computer-readable medium (120, 130), at least a portion of the current chain of cells (340); and updating, in the non-transitory computer-readable medium (120, 130), at least one cell of the at least the portion of the current chain of cells (340), the updating comprising generating a new value to be associated with the at least one cell based on a value of the at least one cell in the current chain of cells and the new data element. [87] [Clause 3] The method of clause 1, wherein the new chain of cells (350) comprises at least one cell (352) associated with a pointer pointing to a corresponding cell (342) in the previous chain of cells (340).

[88] [Clause 4] The method of clause 1, wherein at least one cell of the new chain of cells (350) is associated with at least one of a key, a version reference, a previous cell of the new chain of cells and a next cell of the new chain of cells (350).

[89] [Clause 5] The method of clause 4, wherein the version reference corresponds to a version reference of the new chain of cells (350).

[90] [Clause 6] The method of clause 1, wherein the entrance table (310) comprises at least one pointer pointing to a first cell of the current chain of cells while the new chain of cells (350) is being created.

[91] [Clause 7] The method of clause 6, wherein the at least one pointer is caused to point to the first cell of the new chain of cells (350) once determination that the new chain of cells (350) is ready to be released is made. [92] [Clause 8] The method of clause 1, wherein the data table is a hash table.

[93] [Clause 9] The method of clause 8, wherein the entrance table (310) is a list of keys, each one of the keys pointing to at least one cell of the current chain of cells (340) assigned by a hash function.

[94] [Clause 10] The method of clause 1, wherein the current version reference and the new version reference corresponds to a current revision and a new revision respectively.

[95] [Clause 11] The method of clause 1, wherein determining that the new chain of cells (350) is ready to be released comprises at least one of (i) determining that the new chain of cells (350) is complete; and (ii) determining that a predefined period of time has lapsed.

[96] [Clause 12] The method of clause 1, wherein the entrance table (310) does not have access to the new chain of cells (350) while the new chain of cells (350) is being created.

[97] [Clause 13] The method of clause 1, the current version reference and the new version reference establishes a chronological sequence reflecting values of the data table at a given time. [98] [Clause 14] The method of clause 1, wherein the current version reference and the new version reference are each associated with an integer and wherein the new version reference corresponds to the current version reference incremented by "1".

[99] [Clause 15] The method of clause 1, wherein the current chain of cells (340) include values associated with a first given time and the new chain of cells (350) include updated values associated with a second given time, the updated values being reflective of a modification of the values between the first given time and the second given time.

[100] [Clause 16] A computer-implemented system (100, 210, 220, 222, 224) configured to perform the method of any one of clauses 1 to 15. [101] [Clause 17] A non-transitory computer-readable medium (120, 130), comprising computer-executable instructions that cause a system (100, 210, 220, 222, 224), to execute the method according to any one of clauses 1 to 15.

[102] It should be expressly understood that not all technical effects mentioned herein need to be enjoyed in each and every embodiment of the present technology. For example, embodiments of the present technology may be implemented without the user enjoying some of these technical effects, while other embodiments may be implemented with the user enjoying other technical effects or none at all.

[103] Some of these steps and signal sending-receiving are well known in the art and, as such, have been omitted in certain portions of this description for the sake of simplicity. The signals can be sent-received using optical means (such as a fibre-optic connection), electronic means (such as using wired or wireless connection), and mechanical means (such as pressure-based, temperature based or any other suitable physical parameter based).

[104] Modifications and improvements to the above-described implementations of the present technology may become apparent to those skilled in the art. The foregoing description is intended to be exemplary rather than limiting. The scope of the present technology is therefore intended to be limited solely by the scope of the appended claims.