Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
SEARCH REGION DECREASING FOR RECOMMENDATION SYSTEMS
Document Type and Number:
WIPO Patent Application WO/2018/044189
Kind Code:
A1
Abstract:
The present disclosure refers to an apparatus, comprising at least one processing unit configured to receive a request to identify items in a data set, wherein the request specifies an objective function, decompose the objective function into a plurality of subfunctions, determine constant bounds for at least one subfunction of the plurality of subfunctions, use the constant bounds of the at least one subfunction for calculating bounds of the objective function, define a search region of the data set using the calculated bounds, and evaluate items in the search region of the data set by processing the objective function on the items in the search region. Furthermore, a recommendation system and a method for recommending items are disclosed.

Inventors:
KLINOV, Maxim Sergeevich (Huawei Administration Building, Bantian Longgang District, Shenzhe, Guangdong 9, 518129, CN)
FILIPPOV, Alexander Nikolaevich (Huawei Administration Building, Bantian Longgang District, Shenzhe, Guangdong 9, 518129, CN)
SMIRNOV, Viktor Vladimirovich (Huawei Administration Building, Bantian Longgang District, Shenzhe, Guangdong 9, 518129, CN)
Application Number:
RU2016/000582
Publication Date:
March 08, 2018
Filing Date:
August 29, 2016
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
HUAWEI TECHNOLOGIES CO., LTD. (Huawei Administration Building, Bantian Longgang District Shenzhe, Guangdong 9, 518129, CN)
KLINOV, Maxim Sergeevich (Huawei Administration Building, Bantian Longgang District, Shenzhe, Guangdong 9, 518129, CN)
International Classes:
G06F17/30
Other References:
ANONYMOUS: "Recommender system - Wikipedia, the free encyclopedia", 30 July 2016 (2016-07-30), Internet, pages 1 - 15, XP055365594, Retrieved from the Internet [retrieved on 20170419]
None
Attorney, Agent or Firm:
MITS, Alexander Vladimirovich (LAW FIRM "GORODISSKY & PARTNERS" LTD, Bolshaya Spasskaya str. 25, bldg., Moscow 0, 12909, RU)
Download PDF:
Claims:
CLAIMS

An apparatus, comprising:

at least one processing unit configured to:

receive a request to identify items in a data set, wherein the request specifies an objective function;

decompose the objective function into a plurality of subfunctions; determine constant bounds for at least one subfunction of the plurality of subfunctions;

use the constant bounds of the at least one subfunction for calculating bounds of the objective function;

define a search region of the data set using the calculated bounds; and evaluate items in the search region of the data set by processing the objective function on the items in the search region.

The apparatus of claim 1 , wherein the at least one processing unit is configured to eliminate one or more of the plurality of subfunctions that are invariant to a change of size of the search region.

The apparatus according to one of the preceding claims, wherein the constant bounds for the at least one subfunction are determined using maximal and/or minimal values of input parameters for the at least one subfunction.

The apparatus according to one of the preceding claims, wherein the constant bounds are determined by executing a procedure.

The apparatus according to one of the preceding claims, wherein the at least one processing unit is further configured to measure a size of the search region and if the measured size exceeds a threshold, the at least one processing unit is further configured to determine other constant bounds for another at least one subfunction of the plurality of subfunctions.

6. The apparatus according to claim 5, wherein the at least one processing unit is further configured to use the other constant bounds for calculating other bounds of the objective function, and to define the search region using the other calculated bounds.

The apparatus according to claim 5 or 6, wherein the other at least one subfunction includes the at least one subfunction and at least one further subfunction of the plurality of subfunctions.

The apparatus according to one of the preceding claims, wherein the at least one processing unit is configured to decompose the objective function into a sum of the plurality of subfunctions.

The apparatus according to one of the preceding claims, wherein the objective function corresponds to a class of requests to a recommendation system.

The apparatus according to one of the preceding claims, wherein the query is a Top-N or a Bottom-N search, wherein a result of the search includes a set of N items having a best or worst rating for one or more users, based on the objective function.

The apparatus according to one of the preceding claims, further comprising at least one data interface coupled to at least one database to retrieve the items of the data set.

A recommendation system comprising:

an apparatus according to one of the preceding claims; and

at least one database configured to store the items of the data set.

The recommendation system according to claim 12, wherein the apparatus is connected to or arranged in a computing cloud configured to process at least a part of the request. A method for recommending items, comprising:

receiving a request to identify items in a data set, wherein the request specifies an objective function;

decomposing the objective function into a plurality of subfunctions;

determining constant bounds for at least one subfunction of the plurality of subfunctions;

using the constant bounds of the at least one subfunction for calculating bounds of the objective function;

defining a search region of the data set using the calculated bounds; and evaluating items in the search region of the data set by processing the objective function on the items in the search region.

One or more computer-readable media storing instructions thereon, wherein the instructions when executed on a computing device configure the computing device to perform a method according to claim 14.

Description:
SEARCH REGION DECREASING FOR RECOMMENDATION SYSTEMS

TECHNICAL FIELD The present invention relates to an apparatus, a recommendation system and a method for recommending items. The present invention also relates to a computer-readable storage medium storing instructions thereon for configuring a computing device to perform such a method. BACKGROUND

Recommendation systems are essential components of current communication and information processing systems. The huge amount of information and data that may be retrieved, processed and uploaded by users requires a pre-selection or reduction of the amount of information or data to a suitable number or size which can be handled by users. However, to generate meaningful recommendations, large data sets have to be analyzed and processed, which requires extensive computing resources and computation time. Search approaches have been proposed for individual sets of data to handle specific tasks. However, it is difficult to adapt these approaches to different recommendation setups. With different data sets, these approaches may not decrease the number of computing resources or improve computation time at all and may even provide inaccurate results.

SUMMARY OF THE INVENTION

The objective of the present invention is to provide an apparatus, a recommendation system and a method for recommending items, wherein the apparatus, the recommendation system and the method overcome one or more of the above- mentioned problems of the prior art.

A first aspect of the invention provides an apparatus with at least one processing unit configured to receive a request to identify items in a data set, wherein the request specifies an objective function, to decompose the objective function into a plurality of subfunctions, to determine constant bounds for at least one subfunction of the plurality of subfunctions, to use the constant bounds of the at least one subfunction for calculating bounds of the objective function, to define a search region of the data set using the calculated bounds, and to evaluate items in the search region of the data set by processing (i.e., calculating or applying) the objective function on the items in the search region.

The apparatus of the first aspect is applicable to any type of data sets and queries. The received request defines an evaluation of the items of the data set by specifying the objective function. However, since the evaluation of the objective function on all items of the data set would be too costly in terms of both the computing resources and the computation time, the apparatus is configured to decompose the objective function and use constant bounds for at least one subfunction of the objective function to approximate the objective function, which effectively results in a decreased search region. The search region may be used to identify candidate items (within the search region) for calculating the relatively costly (original) objective function on the items in the search region. The results of the query, such as recommendation results, may include a subset of the evaluated items according to the objective function. For example, the results may include one or more of the best or worst items according to their value (or metric) as defined by the objective function, in any combination.

The approach is highly flexible since the objective function may represent a broad variety of query types applicable to any kind of data sets. Furthermore, by approximating at least some subfunctions with constant bounds, such as subfunctions with increased computational costs, the search region may be effectively reduced and, yet, efficiently delivers precise approximations even for non-monotone objective functions. Furthermore, the decomposition of the objective function into a plurality of subfunctions is advantageous since individual parts may be processed on dedicated processing units of the apparatus or on external processing unit, such as in a computing cloud or cluster, which enables a balancing of computing resources and a speed-up of handling of the query. In a first implementation of the apparatus according to the first aspect, the at least one processing unit is configured to eliminate one or more of the plurality of subfunctions that are invariant to a change of size of the search region. The elimination of at least some of the subfunctions that are invariant to the change of size of the search region leads to a further speed-up of subsequent computations based on the objective function. Preferably, the processing unit may be configured to determine, whether such invariant subfunctions are present and eliminate the identified subfunctions from the decomposed objective function. The remaining subfunctions of the objective function may also be referred to, in combination, as a simplified objective function throughout this disclosure.

In a second implementation of the apparatus according to the first aspect as such or according to the first implementation of the first aspect, the constant bounds for the at least one subfunction are determined using maximal and/or minimal values of input parameters for the at least one subfunction. Preferably, the at least one subfunction may be identified as a part of the objective function that requires the most computing resources or computation time. Accordingly, the at least one subfunction may also be referred to throughout this disclosure as a computationally intensive part (OP) of the objective function or of the simplified objective function. The CIP may be limited by the maximal and minimal values or bounds, which may be reachable or not. The maximal and/or minimal values may be estimated by using minimal/maximal values of input values and/or mathematical methods of constructing lower and upper functions for the CIP. These values may be further refined. The maximal and/or minimal values (or their refinement) may be controlled by at least one parameter characterizing a trade-off between the time required to estimate the maximal and/or minimal values and their accuracy. For example, as an initial step, the maximal and/or minimal values may be estimated on a coarse level, which may be further refined to construct refined constant bounds that more closely approximate limits of the at least one subfunction.

In a third implementation of the apparatus according to the first aspect as such or according to any of the preceding implementations of the first aspect, the constant bounds are determined by executing a procedure. The constant bounds may be determined using a procedural approach that may be automatically executed on the apparatus. In a fourth implementation of the apparatus according to the first aspect as such or according to any of the preceding implementations of the first aspect, the at least one processing unit is further configured to measure a size of the search region and if the measured size exceeds a threshold, the at least one processing unit is further configured to determine other constant bounds for another at least one subfunction of the plurality of subfunctions. The determined constant bounds are used to calculate the bounds of the objective function, which influence the search region. If the size of the search region exceeds the threshold, an iterative approach may be initiated, which may result in a more accurate search region by determining other constant bounds for the at least one subfunction, for another subfunction or for a combination or permutation thereof. Accordingly, if the decreased search region is too large, another subfunction or combination of subfunctions of the plurality of subfunctions may be identified and respective constant bounds for the other subfunction or combination may be determined. This enables an automatic refinement of the search region by identifying more suitable subfunctions until the search region has an acceptable size. Furthermore, the at least one processing unit may be configured to determine constant bounds for at least a set of the subfunctions of the objective function in parallel and evaluate the size of the respective search regions in order to determine a search region with an acceptable size. This enables full utilization of computing resources. In a fifth implementation of the apparatus according to the first aspect as such or according to any of the preceding implementations of the first aspect, the at least one processing unit is further configured to use the other constant bounds for calculating other bounds of the objective function, and to define the search region using the other calculated bounds. This leads to a refinement of the search region that may be controlled by pre-configured thresholds for a suitable size of the search region.

In a sixth implementation of the apparatus according to the first aspect as such or according to any of the preceding implementations of the first aspect, the other at least one subfunction includes the at least one subfunction and at least one further subfunction of the plurality of subfunctions. The other at least one subfunction may represent a bigger fragment of the objective function than that of the originally considered at least one subfunction. However, it is to be understood that in one or more other implementations the other at least one subfunction may also represent a smaller fragment or a completely different part of the objective function that may be used for further refinement of the search region. In a seventh implementation of the apparatus according to the first aspect as such or according to any of the preceding implementations of the first aspect, the at least one processing unit is configured to decompose the objective function into a sum of the plurality of subfunctions. This enables a simplified processing of the individual components of the sum and combinations thereof to determine a suitable decomposition into the CIP and the remaining part.

In an eighth implementation of the apparatus according to the first aspect as such or according to any of the preceding implementations of the first aspect, the objective function corresponds to a class of requests to a recommendation system. Preferably, the query is a Top-N or a Bottom-N search, wherein a result of the search includes a set of N items having a best or worst rating for one or more users, based on the objective function. Further classes of request may include an interval-based search, wherein values may be inside (or outside) of an interval (of any kind), objective functions of many variables, such as groups of users or items, and other conditions or requests, and respective subtasks.

In a ninth implementation of the apparatus according to the first aspect as such or according to any of the preceding implementations of the first aspect, the apparatus further comprises at least one data interface coupled to at least one database to retrieve the items of the data set. The apparatus may access the items of the data set through the data interface via one or more interfaces of the database, which may be configured to enable identification, retrieval or storage of items in the database. For example, the interface may enable an identification of items based on a search region and/or the objective function. Preferably, the at least one database may be included in a computing cloud. The computing cloud may be a dedicated cloud or the same cloud or cluster as used for processing at least parts of the request.

A second aspect of the invention refers to a recommendation system comprising an apparatus according to the first aspect or one of the implementations of the first aspect, and at least one database configured to store the items of the data set.

In a first implementation of the recommendation system according to the second aspect, the apparatus is connected to or arranged in a computing cloud configured to process at least a part of the request. The computing cloud may be provided with sufficient computing resources in order to support the apparatus for handling the query. For example, the apparatus may offload one or more processing tasks of the request to the computing cloud. The computing cloud may be configured to calculate the bounds of the objective function and/or to evaluate the objective function on at least some of the items. The apparatus may be further configured to evaluate a complexity of the request. Based on a result of the evaluation, the apparatus may perform simple requests and offload requests for larger sets of data to the computing cloud. If the constant bounds for at least one subfunction are computed in the computing cloud, the computing cloud may keep the calculated computed constant bounds for further processing. The size of computing cloud (and of the processing resources of the cloud) may be adapted to an estimated workload or a number of users of the recommendation system. This provides for a fast and efficient provision of recommendations with regards to very large data sets that may be further adapted to the amount of expected users.

A third aspect of the invention refers to a method for recommending items, comprising the steps of receiving a request to identify items in a data set, wherein the request specifies an objective function, decomposing the objective function into a plurality of subfunctions, determining constant bounds for at least one subfunction of the plurality of subfunctions, using the constant bounds of the at least one subfunction for calculating bounds of the objective function, defining a search region of the data set using the calculated bounds, and evaluating items in the search region of the data set by processing the objective function on the items in the search region. The methods according to the third aspect of the invention can be performed by the apparatus according to the first aspect or the recommendation system according to the second aspect of the invention. Further features or implementations of the method according to the third aspect of the invention can perform the functionality of the apparatus according to the first aspect or of the recommendation system according to the second aspect of the invention and their different implementation forms.

A fourth aspect of the invention refers to one or more computer-readable media, such as a computer-readable storage medium, storing instructions or program code thereon that when executed on a computing device configure the computing device to perform a method of the third aspect or one of respective implementations of the third aspect.

BRIEF DESCRIPTION OF THE DRAWINGS

To illustrate the technical features of embodiments of the present invention in more detail, the accompanying drawings provided for describing the embodiments are introduced briefly in the following. The accompanying drawings merely represent some embodiments of the present invention and modifications on these embodiments are possible without departing from the scope of the present invention as defined in the claims.

FIG. 1 is a block diagram illustrating an apparatus in accordance with an embodiment of the present invention, is a schematic illustration of a recommendation system in accordance with a further embodiment of the present invention,

FIG. 3 is a flow chart of a method for recommending items in accordance with an embodiment of the present invention,

FIG. 4 illustrates approximations of an objective function and a decreased search region used in a method for recommending items in accordance with a further embodiment of the present invention, and

FIG. 5 shows yet another flow chart of a method for recommending items in accordance with another embodiment of the present invention.

DETAILED DESCRIPTION OF EMBODIMENTS

FIG. 1 is a block diagram illustrating an apparatus in accordance with an embodiment of the present invention. The apparatus 100 may include at least one processing unit 102, which may be configured to process requests for items in a data set, such as search, identification or recommendation requests, which may be used to generate recommendations of items of the data set. The apparatus 100 may comprise an interface 104, which may connect the apparatus 100 to a computing cloud 106. The apparatus 100 may comprise a data interface 108 to connect the apparatus 100 to at least one database 1 10. As indicated by the dotted line, it is to be understood that the interface 104 and the data interface 108 may be optional components.

The at least one processing unit 102 may be configured to receive a request to identify items in the data set and may retrieve an objective function from the request. The objective function may define a class of requests, such as a Top-N or a Bottom-N search. The at least one processing unit 102 may be configured to decompose the objective function into a plurality of subfunctions, determine constant bounds for at least one subfunction of the plurality of subfunctions, and use the constant bounds of the at least one subfunction for calculating bounds of the objective function of the search request. Using the calculated bounds, the processing unit 102 may define a search region of the data set and may evaluate items in the search region of the data set by processing (or calculating) the objective function on the items in the search region. The apparatus 100 may offload at least some of the processing tasks to the computing cloud 106. For example, the processing unit 102 may submit at least some of the constant bounds to the computing cloud 106, which may be configured to calculate the bounds of the objective function based on the submitted constant bounds. The computing cloud 106 may be configured to calculate the objective function for the items in a preferred embodiment. However, it is to be understood that the apparatus 100 is not limited by offloading of particular tasks. Rather, the processing unit 102 may be configured to offload any suitable tasks to the computing cloud 106, which may preferably take into account all data transfers that are required to offload the respective tasks to the computing cloud 106.

The apparatus 100 may efficiently approximate the objective function and decrease the search region to perform accurate requests for recommendations for any class of objective functions in an efficient manner. The apparatus 100 may find exact solutions for monotone objective functions and non-monotone objective functions for any kind of requests.

FIG. 2 shows a schematic illustration of a recommendation system according to one embodiment of the present invention. The system 200 may include a recommendation server 202, which may correspond to an apparatus according to one embodiment of the present disclosure, such as the apparatus 100 of FIG. 1. The recommendation server 202 may communicate with a computing cloud 204, which may be defined as a network or cluster of computing devices or computing units 206 and a cluster or array of storage devices 208. The recommendation server 202 may be accessed by one or more client devices 210 operated by respective users 212. It is to be understood that even though only one client device 210 is shown, the recommendation server 202 may be accessed by any number of client devices operated by respective users.

The user 212 may retrieve, process and upload data and/or content of any kind, such as audio, video or media as well as other information, documents, files and streams, which may be generally referred to throughout this disclosure as items. The user 212 may, for example, play movies or music files or streams, rate them, browse further documents and information and the like. Furthermore, the user 212 may explicitly or implicitly interact with the recommendation server 202, for example via the user interface or an API provided by client device 210, to receive recommendations of items. The recommendation server 202 may also receive information from the user 212 and may store the information as a data set 214.

The recommendation server 202 may apply machine learning algorithms to train and build a model 216 used for subsequent recommendations. The recommendation server 202 may be accessed by an administrator 218, who may supply further data, such as training data 220 in order to control the quality of the training and of the model 216, for example, based on various metrics, such as RMSE (root-mean-square deviation) and the like. The recommendation server 202 may communicate with the computing cloud 204 to outsource or offload various operations. For example, the recommendation server 202 may use the computing cloud 204 to predict items that are presented to the user 212 as recommendations . The recommendation request may be formulated as a query specifying an objective function to evaluate the respective items of the data set 214. For example, a Top-N or Bottom-N query may be performed, which may result in N best or worst items based on the objective function. The recommendation server 202 may process the objective function of the requests using a method according to one or more embodiments of the present invention, for example, as discussed with regard to FIGs. 3 and 5 below. FIG. 3 shows a flow chart of a method for recommending items according to one embodiment of the present disclosure. The method 300 may be applicable in the apparatus 100 of FIG. 1 or the recommendation server 202 of FIG. 2. In particular, the apparatus 100 or the recommendation server 202 may be configured to recommend items for users based on an optimized and flexible handling of request according to method 300. Furthermore, one or more of the processing steps of the method 300 may be offloaded to the computing cloud 106 of FIG. 1 or the computing cloud 204 of FIG.

The method 300 may start in item 302 and may proceed with item 304, wherein a request to identify items in a data set may be received. The request specifies an objective function, which may represents a metric or score for the individual items of the data set. The objective function may (implicitly or explicitly) specify a type of the request, such as a Top-N request, a Bottom-N request, an interval -based request specifying values within intervals, and any other kind of request, combinations of conditions in one request, and the like. The objective function may be defined as a plurality of subfunctions, such as by a sum f(x) wherein fi (x) represent subfunctions of the objective function.

For a Top-N request directed at items with respective ratings from a plurality of users, the objective function may be formulated as the following rating formula, for example, in a SVD++ method for recommendations: where w and / ' are indices related to users and items, respectively, and

μ is an average rating over all (real) ratings,

w is a number of latent factors, parameter of training,

b u is an w-indexed element of a dense vector of users' biases from μ, b; is an /-indexed element of a dense vector of items' biases from μ, p u is an w-indexed column of a dense matrix P of users' latent factors, with height equal to w and width equal to the number of users, N(u) is an w-indexed row of a sparse matrix of users' implicit, non-rated data over items, with height equal to the number of users and width equal to the number of items, it can be data of all viewed by user items, y t is an j ' -indexed column of a dense matrix Y of latent factors implicit preferences over items, with height equal to w and width equal to the number of items, and

(?(· is an /-indexed column of a dense matrix Q of items' latent factors, with height equal to w and width equal to the number of items.

The rating formula may be used during training of the recommendation system and for recommending the top-N items. However, it is to be understood that the present disclosure is not limited to a particular rating formula, objective function or a type of query. Rather, the rating formula for the Top-N request is an example only.

The method 300 may proceed with item 306, wherein the objective function may be decomposed into a plurality of subfunctions. The decomposition in item 306 may serve the purpose of eliminating those parts (or subfunctions) of the objective function that are invariant to a decrease of the search region. The processing of the request may be composed of at least two subtasks, the first subtask being directed at finding candidate items and the second subtask being directed at evaluating the objective function on them. Hence, if at least one subfunction only influences the second subtask and is not needed for identifying the candidate items (the first subtask), it may be disregarded in the optimization steps.

For example, with regard to the above-identified example, the subfunction μ + b u can be eliminated because it is invariant for items and has no influence on the resulting set of items. By eliminating at least one subfunction of the plurality of subfunctions, the remaining subfunctions may also be referred to as a simplified objective function (SOF). In the above-identified example, the SOF may be given as:

The decomposition may also serve the purpose to identify a computationally intensive part (CIP) of the objective function that is subsequently limited using constant bounds. For example, the CIP may be identified in the SOF. The CIP may be represented by one of the remaining subfunctions or a combination of the remaining subfunctions of the plurality of subfunctions of the decomposition of the objective function.

With regard to the above example, the CIP may be given as:

Accordingly, an objective function f(u, i) = c + g(u) + h(i) + r u, i) may be decomposed into at least one invariant part c + g(u), at least one CIP r(u, i) and at least one remaining subfunction h(i), wherein / ' represents an index over items and u an index over users. Since the exact value of f(u, i) for all items is unknown and would be too costly to compute, h(i) may be calculated instead with lower and/or upper bounds used for r(u, i) as constant values. Accordingly, f(u, i) may be estimated inside a reduced search region.

In order to approximate the CIP, the method 300 may proceed with item 308, wherein constant bounds for the at least one subfunction of the plurality of subfunctions, representing the CIP, may be determined. The lower and upper constant bounds for the CIP may be estimated and refined using any suitable technique. One example of a procedural approach is given in subsequent Table 1. Since the CIP will generally be a function of user IDs and item IDs, the input parameter x may be regarded as a tuple of a user ID and an item ID. mp = 0

my = 0

mq = 0

mrcz = 0

for every entry e in P II P, Y, Q, N are matrices

mp = max(wp, abs(e))

for every entry e in Y

my = m&x(my, abs(e))

for every entry e m Q

mq = max(mq, abs(e))

for every entry row in N

mm = max(tfwz, get_number_of_non_zeros_in_row(row))

upper jstep3 = w * (mp + sqrt(wwz) * my) * mq // w is a width of columns p u , y jt q t lower _step3 = - upper All compute_Iimits_step3 (user id, itemjd)

return (lower _step3, upper _step3)

Table 1 : Algorithm for determining constant bounds of CIP The estimation of the constant bounds is based on maximal values of vectors, which may result in an estimation of a sum of vectors, scalar products, and non-monotone summands, which results in the monotone sqrt(mnz) * my in the procedural approach shown in Table 1. This shows the correctness of using a maximum number of non-zero elements in a row of a matrix for estimating the upper bound and afterwards the lower bound.

In the example above, the same values for lower and upper bounds are used for all items and users. According to one preferred embodiment, estimations of the constant bounds may be performed separately for each item/user or for groups of items/users. This may be influenced by one or more parameters, which may reflect the trade-off between accuracy of bounds and duration of computation of the bounds.

Using constant bounds for the CIP as determined in item 308, the method 300 may proceed with item 310, wherein bounds of the objective function are calculated using the constant bounds of the CIP. Subsequently, the lower and upper bound functions may be computed, for example, using the branch and bound approach, or any other suitable technique. With regard to the Top-N approach according to one example, for each user, the N best items have to be identified. This may be optimized by finding k items, wherein N < k « #i, where #i is the number of items. If the CIP is limited by [r 1( r 2 ] as the constant bounds, the following assumption should hold for the remainder of the SOF: h{i) + r 1 > h(V) + r 2 . This enables to find the N best items using h, wherein a minimal value for them is /i n , m m, wherein the requested items are identified among such items as h i) > h n min — (r 2 — r x ).

In one example, computation of the lower and upper limits of the SOF may be done using the procedure shown in Table 2. for every entry e in items

(lower(e), upper(e)) = compute_limits_step3(0, e)

(lower _step4(e), upper _step4(e)) = (bi(e) + lower(e), bi(e) + upper(e)) compute_limits_step4 (user id, item id)

return (lower _step4(item_id), upper _step4(item id))

Table 2. Algorithm for computing lower and upper limits of SOF In Table 2, the same limits are used for all users, thereby enabling a call of compute_limits_step3 of Table 1 once per item.

The method 300 may proceed with item 312, wherein a search region of the data set may be defined using the calculated bounds of the objective function. The search region may be decreased by eliminating those items/users that will not form part of the result. This may depend on the type of the search request. For example, for a Top-N request, the top-N lower bounds may be found and the lowest among them may be identified. The lowest bounds may be denoted as b. Thereafter, items whose upper bounds are bigger than b are identified. Even though the exact value of the objective function on these items is unknown, they are most likely to be among the Top-N items. The number of items that are eliminated by decreasing the search region may also take into account training data, which may define how big intervals between lower and upper bounds may be and how much b, may vary from one item to another. In an optional step (not shown) the size of the search region may be determined and if the search region is found to be unsuitable or inaccurate, another decomposition of the SOF or another selection of subfunctions of the plurality of subfunctions may be used to identify another CIP in order to arrive at a more suitable search region. For example, a bigger fragment of the SOF including another subfunction or another selection of subfunctions from the plurality of subfunctions may be considered as the CIP. If a bigger fragment of the SOF is considered, this may result in a wider interval between the lower and upper bounds, but less exact computation of the remainder of the objective function. The wider interval may, however, lead to more computations in evaluating the SOF for the decreased search region. As an alternative, a smaller fragment of the SOF, which may be another subfunction or a part of the previously considered subfunction(s), may be considered as the CIP. This may increase the amount of computations in subsequent steps, however, on the other hand this may exclude more items from further considerations since the search region is effectively decreased, thereby reducing the overall computational requirements. Since based on rough estimates of the CIP, the check of how significantly the search region can be decreased may be performed quickly; this may further improve the processing efficiency of the method 300. The method 300 may proceed with item 314, wherein the exact objective function may be calculated on all items in the search region to evaluate the items and to provide the search or recommendation results in response to the request.

The influence of the constantly bound CIP on the identification of candidate items in the reduced search region according to one or more embodiments is shown in a schematic illustration of FIG. 4. The objective function may be estimated and the search region may be decreased using a method according to one embodiment of the present invention, such as the method 300 as described with regard to FIG. 3. FIG. 4 shows a number of items 402, wherein the inner circle represents the exact value of the objective function f(x). Even though a particular number of items 402 are shown in FIG. 4, it is to be understood that the present invention is not restricted to a particular number of items. Since the evaluation of the objective function for each item is computationally too intensive, the computation may be approximated by restricting a CIP of the objective function by constant bounds. This approximation for each item 402 is depicted as regions 404. Even though these regions do not correspond to the exact values, they may be calculated in a more efficient manner. Rather than using the exact values, suitable items are identified using the regions 404, by determining whether the regions 404 fall inside (or overlap with) a search region 406. For resulting candidate items 408 the exact values of the objective function may be calculated. The advantageous processing and effective speed-up of the recommendations using the approach according to one or more embodiments of the present disclosure is demonstrated in the following results of a Top-N request.

The results were calculated on a system using a SVD++ method to construct the model for recommendations, wherein a Spark GraphX implementation of S VD++ training has been used. The results are calculated on the MovieLens data set with 20M ratings for 13 OK users and 27K items. The approach according to one embodiment of the present disclosure resulted in a speedup of 2.6 for a Top- 10 query and a speedup of 2.1 for a Top- 1000 query over a baseline version applying a standard Top-N query. Further performance comparison results were calculated on bigger data sets, which are represented by sparse matrices taken from matrix collections that are known as nlpkkt80 and nlpkkt200, wherein speedup rates of 90 and approximately 2,000 have been achieved using the approach according to one embodiment of the present disclosure. Further details are shown in the Table 3.

Table 3 : Performance for all users for nlpkkt matrices On the nlpkkt200 data set, the overall computation time for all users took approximately 18 min in total, whereas the baseline would have to spend approximately more than 13 days of total computation time to evaluate all items for all users in the entire data set.

FIG. 5 shows yet another flow chart of a method according to one embodiment of the present disclosure. The method may be applicable in the apparatus 100 of FIG. 1 or the recommendation server 202 of FIG. 2. Furthermore, individual processing steps of method 500 may be combined with processing steps of method 300, and vice versa, in any combination.

The method 500 may be based on a request, which may include an objective function. The method 500 may start in item 502, wherein a simplified objective function (SOF) may be defined based on the objective function by eliminating those parts of the objective function that are invariant to search region decreasing. If there are no such parts, the SOF may be equal to the original objective function.

The method may proceed with item 504, wherein a computationally intensive part (CIP) may be selected in the SOF. This may lead to decomposition into the CIP 506 and the remaining part 508 of the SOF.

In item 510, constant lower and upper limits or bounds (that can be reachable or not) are determined for the CIP 506. Item 510 reduces the computational intensiveness of CIP greatly by approximating the CIP with constant values. Furthermore, processing in item 510 can be used to control the trade-off between time of computing the bounds and accuracy of computation. The processing in item 510 may be performed using a procedural approach. The method 500 may proceed with item 512, wherein lower and upper limits or bounds of the entire SOF may be calculated. The computation in item 512 may be based on results of processing in item 510. The processing in item 512 may be performed using a procedural approach.

In item 514, the search region may be decreased using the results from item 512 by eliminating those items/users that will most likely not form part of the recommendation result according to the computed lower and upper bounds of the SOF.

In item 516, the size of the decreased search region may be determined or measured. If the size is still large, the method 500 may proceed with item 504, wherein another decomposition of the SOF or another selection of parts of the SOF may be used to determine another CIP for subsequent processing in a next iteration.

The decreased search region may be used to perform the request, in item 518, wherein candidate items may be identified and the exact values of the objective function may be calculated for all candidate items to generate the response to the request.

One or more steps or items of method 500 may be computed on an apparatus according to one embodiment of the present disclosure and/or on a computing cloud of a recommendation system according to one or more embodiments of the present disclosure. It is to be understood that any suitable tasks may be offloaded from the apparatus or the recommendation server to the computing cloud, in any combination.

The foregoing descriptions are only implementation manners of the present invention and the scope of the present invention is not limited to the disclosed examples and embodiments. Rather, any variations or replacements can be easily made by a person skilled in the art. Therefore, the scope of protection of the present invention should be subject to the scope of protection of the attached claims.