# Extending JSON CRDT with Move Operations

Liangrun Da
Technical University of Munich
<EMAIL_ADDRESS>Martin Kleppmann
Technical University of Munich
<EMAIL_ADDRESS>
###### Abstract

Conflict-Free Replicated Data Types (CRDTs) for JSON allow users to
concurrently update a JSON document without introducing any conflicts and
automatically merge the updates into a consistent state. However, moving a
subtree in a map or reordering elements in a list for a JSON CRDT is
considered challenging as an algorithm that is not carefully designed may
introduce unexpected results such as duplicates or cycles. In this paper, we
show how to extend Automerge, a CRDT library, by incorporating move operations
and evaluating the performance of our algorithm.

##  1 Introduction

Automerge [1] is a Conflict-Free Replicated Data Type (CRDT) [12], which
allows concurrent changes to data on different devices to be merged
automatically without requiring any central server. It is utilized in the
development of local-first software [5], which includes applications such as
collaborative drawing, text editing, and more.

Automerge uses a _document_ as its data model, which can be viewed as a JSON
data type on local devices. A document can be accessed locally through
operations such as _get_ , _put_ , and _delete_ provided by Automerge library,
resembling how we manipulate JSON in programming languages such as JavaScript.
The modifications made are then replicated to other devices. However, those
operations have limitations when it comes to fulfilling the requirements of
certain applications. Many applications require reordering elements in a list,
moving elements in a map, or even moving elements between lists and maps. For
instance, when an application utilizes a document to represent a file system,
moving a file from one location to another is a very common operation.

Although move operations are straightforward for an unreplicated JSON object,
as they only require deletion and reinsertion, they become challenging when
dealing with CRDTs. If several replicas concurrently delete and reinsert the
same object, the merged result contains duplicates of the moved object [3].
Another issue arises with cycles, as illustrated in Figure 1. In this example,
each device individually executes a move operation without creating a cycle.
However, when merging these operations, a cycle may appear if the algorithm
does not take care to prevent the cycle.

Previous research has demonstrated the possibility of moving elements within
lists and maps [4, 7, 3, 8], but the existing implementations of move
operations are minimal research prototypes that are not integrated with fully-
featured CRDT libraries such as Automerge. To fully support move operation in
a JSON CRDT, we extend the algorithm to enable users to move elements from one
location to any other location, even between a list and a map. In this paper,
we show how to implement a move operation with the desired semantics in
Automerge. Through performance experiments, we demonstrate the practical
feasibility of the move operation. Our move operation provides the following
guarantees:

  * •

No cycles: The document will never be in a cyclic state at any point.

  * •

No duplicates: If two concurrent move operations attempt to move the same
element, only one move operation will take effect, preventing the occurrence
of duplicate elements.

Replica 1:Replica
2:$\mathsf{root}$$A$$C$$B$$\mathsf{root}$$A$$C$$B$$\mathsf{root}$$A$$B$$C$$\mathsf{root}$$B$$A$$C$??
Move $B$ to be a child of $A$ Move $A$ to be a child of $B$
networkcommunication(_a_)$\mathsf{root}$$A$$B$$C$(_b_)$\mathsf{root}$$A$$B$$C$$B^{\prime}$$A^{\prime}$$C^{\prime}$(_c_)$\mathsf{root}$$A$$B$$C$(_d_)$\mathsf{root}$$B$$A$$C$
Figure 1: Initially, nodes $A$ and $B$ are siblings. Replica 1 moves $B$ to be
a child of $A$, while concurrently replica 2 moves $A$ to be a child of $B$.
Boxes (_a_) to (_d_) show possible outcomes after the replicas have
communicated and merged their states. Figure from [4]

##  2 The Core Mechanics of Automerge

In Automerge, although a document is presented in the API as a JSON object,
its internal representation uses a set of _operations_ called _OpSet_. The set
of operations can be exchanged between different peers, and two sets can be
merged without generating any conflicts by taking their union.

When modifying a document, a new operation is added to the OpSet. Operations
are never removed from the OpSet. Each operation has the following fields:

ID: Every operation in Automerge is assigned a unique ID, which is implemented
as a Lamport Clock [6]. The total order of operation IDs is consistent with
the causal order of operations.

Type: Every operation in Automerge has a type that signifies the action it
performs. Although Automerge supports multiple operation types, this paper
will focus on four key types: _make_ , _put_ , _delete_ , and _move_. These
four types provide the necessary functionality to implement a JSON document
with standard operations as well as the ability to perform move operations.

Object ID: Every operation has an object ID that identifies the list or map
object within the JSON document that the operation modifies. In Automerge, a
list or map object is created using a make operation. The ID of this make
operation subsequently serves as the unique identifier for the object it
created.

Key: Every operation has a _key_ that indicates the position within the object
at which the operation operates. In a map object, the key represents the
property name associated with the operation. In a list object, the key
represents the ID of the preceding element.

Value: This field serves to hold the value associated with the operation. For
a make operation, it contains the specific type (map or list type), whereas,
for a put operation, it stores the value that the operation puts.

Predecessors: If an element is deleted, overwritten, or moved by a newly
generated operation, the operation associated with that element becomes a
predecessor of the new operation, and the operation becomes a successor of the
overwritten operation. An operation is invisible if it has one or more
successors. The value of an invisible operation is not returned when querying
the current state of the document, but it might be returned by queries to a
past version of the document.

Figure 2 illustrates the relationship between a JSON document and an OpSet. A
user’s query for the document is translated into a query for the operations
within the OpSet. As an example, the query for “$document.A$” is translated
into a search for the operation where the Key is equal to $A$, and the
ObjectID is equal to $\langle 0,0\rangle$, the ID of the root object.

⬇ A: a, B: [b1, b2, b3], C: { D: d } ID | Type | Object ID | Key | Value | Predecessors
---|---|---|---|---|---
$\langle 1,0\rangle$ | put | $\langle 0,0\rangle$ | A | a |
$\langle 2,0\rangle$ | make | $\langle 0,0\rangle$ | B | list |
$\langle 6,0\rangle$ | make | $\langle 0,0\rangle$ | C | map |
$\langle 7,0\rangle$ | put | $\langle 6,0\rangle$ | D | d |
$\langle 3,0\rangle$ | put | $\langle 2,0\rangle$ | $\langle 0,0\rangle$ | b1 |
$\langle 4,0\rangle$ | put | $\langle 2,0\rangle$ | $\langle 3,0\rangle$ | b2 |
$\langle 5,0\rangle$ | put | $\langle 2,0\rangle$ | $\langle 4,0\rangle$ | b3 |
$\langle 8,0\rangle$ | delete |  |  |  | $\langle 3,0\rangle$
Internal OpSet Figure 2: An example JSON document with its internal OpSet ⬇ A: a,  B: [b1, b2, d, b3],  C: {}  ID | Type | Object ID | Key | Value | Predecessors | MoveID
---|---|---|---|---|---|---
$\langle 1,0\rangle$ | put | $\langle 0,0\rangle$ | A | a |  |
$\langle 2,0\rangle$ | make | $\langle 0,0\rangle$ | B | list |  |
$\langle 6,0\rangle$ | make | $\langle 0,0\rangle$ | C | map |  |
$\langle 7,0\rangle$ | put | $\langle 6,0\rangle$ | D | d |  |
$\langle 3,0\rangle$ | put | $\langle 2,0\rangle$ | $\langle 0,0\rangle$ | b1 |  |
$\langle 4,0\rangle$ | put | $\langle 2,0\rangle$ | $\langle 3,0\rangle$ | b2 |  |
$\langle 5,0\rangle$ | put | $\langle 2,0\rangle$ | $\langle 4,0\rangle$ | b3 |  |
$\langle 8,0\rangle$ | delete |  |  |  | $\langle 3,0\rangle$ |
$\langle 9,0\rangle$ | move | $\langle 2,0\rangle$ | $\langle 4,0\rangle$ | d | $\langle 7,0\rangle$ | $\langle 7,0\rangle$
Internal OpSet Figure 3: Moving d to be an element of list B

##  3 The Moving Algorithm

The moving algorithm consists of two components. Firstly, it involves
generating a move operation to move the target element. Secondly, it
identifies an operation as invalid if it violates the guarantees of “no cycle”
or “no duplicates”.

###  3.1 Generating Move Operations

When the user moves an element from one location to another, a move operation
is generated and added to the OpSet. This move operation identifies the
element being moved and where it is being moved to. The destination of the
move is determined by the ObjectID and Key fields of the move operation. The
ID of a prior put operation or make operation identifies the element being
moved. A move operation has a _MoveID_ field where this ID is stored.

Figure 3 shows an example of moving the scalar value $d$ to be an element of
list $B$. The operation $\langle 7,0\rangle$ is not visible anymore, as it has
a successor move operation.

From the user’s perspective, the move operation is generated by invoking a
function named $move$:

    move(sourceObject, destinationObject,
        sourceKey, destinationKey)

The function searches the operation being moved by the source object and key.
If the source is a multi-value register and does have multiple concurrent
values, the function will take the value with the greatest ID as the element
to be moved. The other values will be deleted from the document.

Consecutive move operations are possible, as the old and new move operations
can share the same MoveID. If the user moves d again to a new location, the
second move operation will have the same MoveID $\langle 7,0\rangle$.

To handle the situation where multiple concurrent move operations are moving
the same element, we define the move operation with the largest ID as the
winner among those operations. In other words, only the winner is considered
as a successful move, while the others behave as if they were not performed.
This rule prevents duplicating the moved element through concurrent moves.

###  3.2 Validity of Move Operations

Algorithm 1 A naive approach for updating validity of operations

1:ops - operations in the OpSet in ascending ID order

2:valid - a map from operation ID to its validity

3:procedure UpdateValidity(ops)

4: tree $\leftarrow\\{\\}$ $\triangleright$ a map from child ID to parent ID

5: winners $\leftarrow\\{\\}$ $\triangleright$ a map from object ID to winner
ID

6: valid $\leftarrow\\{\\}$

7: for op in ops do $\triangleright$ in order of ascending op.ID

8: for pred in op.Predecessors do

9: if pred.Type == move and valid[pred.ID] then

10: tree[pred.MoveID] $\leftarrow$ null

11: else if pred.Type == make then

12: tree[pred.ID] $\leftarrow$ null

13: if op.Type == make then

14: tree[op.ID] $\leftarrow$ op.ObjectID

15: else if op.Type == move then

16: mid $\leftarrow$ op.MoveID

17: oid $\leftarrow$ op.ObjectID

18: if IsAncestor(tree, oid, mid) then

19: valid[op.ID] $\leftarrow$ false

20: continue

21: valid[op.ID] $\leftarrow$ true

22: tree[mid] $\leftarrow$ oid

23: prevWinner $\leftarrow$ winners[mid]

24: if prevWinner != null then

25: valid[prevWinner] $\leftarrow$ false

26: winners[mid] $\leftarrow$ op.ID

27: return valid

28:function IsAncestor(tree, node, ancestor)

29: while true do

30: if node == ancestor then

31: return true

32: if node == null || node == root then

33: return false

34: node $\leftarrow$ tree[node]

We define a move operation to be valid if and only if there is no concurrent
move operation with a greater ID that moves the same element and it does not
introduce any cycles. If a move operation is invalid, the move operation
itself is invisible and its predecessors will not treat the move operation as
a successor.

The challenge is to ensure a consistent decision among replicas regarding the
validity of the same operation. Consider Figure 1, where Replica 1 moves B to
be a child of A and then receives the change from Replica 2, while Replica 2
moves A to be a child of B and then receives the change from Replica 1. If we
check the validity at the time of applying operations, Replica 1 would
consider the operation of moving A to be a child of B as invalid, while
Replica 2 would say the operation of moving B to be a child of A is invalid,
resulting in inconsistent document states on two replicas.

To ensure consistent decisions on the validity of operations, we can apply
operations in ascending ID order. Whenever an operation is inserted into
OpSet, all the operations in the OpSet are reapplied, and the validity of
operations is updated accordingly. We first show a simple but inefficient
algorithm for computing validity and present an optimized algorithm in Section
3.3.

Algorithm 1 provides details about the process of computing operations’
validity when a new operation is received from a peer. We maintain a map named
tree to keep track of the parent-child relationship between objects. All
objects within a list are considered children of the list object, and the same
applies to map objects. When an object is deleted from the tree, we record
this in the map by setting the deleted object’s parent to _null_. A deletion
can be thought of as similar to a move that moves the deleted object to a
“trash” tree that is separate from the visible document tree.

Additionally, we maintain another map named winner, whose key is the ID of an
element being moved, and the associated value is the greatest ID among
operations that move this element.

By reapplying the operations, we update the tree to reflect any changes in the
parent-child relationship in the document. However, when a put operation is
encountered, the scalar value is not added to the tree, as put operations
cannot introduce cycles. Line 8 to line 12 shifts the objects that are deleted
and overwritten from the document tree to the trash tree, by updating their
parent to null. Furthermore, from line 13 to line 26 we update the validity by
checking for cycles and concurrent moves.

###  3.3 Performance Optimization

Algorithm 1 can ensure the consistency of the move operations by applying them
in the same order on all replicas. However, reapplying the entire set of
operations in the OpSet is very inefficient, especially when the OpSet
contains tens of thousands of operations.

To optimize the algorithm, we can avoid executing the parts that repeat the
previous invocation of _UpdateValidity_. Specifically, during a particular
invocation, we assume that the smallest operation ID in the OpSet is $s$, and
the ID of the newly added operation is $n$. In Algorithm 1, the execution of
the loop for operations within the ID range $[s,n)$ is the same as the
previous invocation. In other words, the validity of operations with IDs in
the range $[s,n)$ are not affected by the newly added operation.

During real-time collaboration among devices that are online, when an
operation is generated on one device, it is propagated to other peers quickly.
This implies that when a device receives a new operation from a peer, only a
few operations in the OpSet with greater IDs are affected. Consequently, we
only need to update the validity of those affected operations. Offline editing
can lead to greater divergence, but for now, we concentrate on the case of
low-latency collaboration.

Algorithm 2 describes an optimized version of Algorithm 1. To insert a new
operation with ID $n$ into OpSet, our algorithm initiates by reverting the
parent-child relationship to a prior state, specifically to a point where only
operations with IDs lower than $n$ are applied. Subsequently, we apply the new
operation, followed by reapplying the operations with IDs greater than $n$.
This sequence of steps is denoted as the _Restore-Apply-Reapply (RAR)_
procedure.

To be able to restore the parent-child relationship to a past state, we store
old parents of overwritten, deleted, and moved objects in parents, in which we
maintain a map from object IDs to the old parent IDs for each operation.

Additionally, to restore the validity status of operations with a lower ID, we
maintain a stack of move operations for every object that is moved. Operations
in a stack are sorted by ID, leading to the top of the stack being the winner
among the concurrent move operations of the same element. To restore to a past
state, all the move operations with IDs greater than that of the past
operation are popped.

Line 10 to line 17 in Algorithm 2 describes the process of restoring, in which
we revert all the effects of the operations greater than that of the newly
inserted operation on $T$. From lines 18 to 48, we update T to reflect any
changes in the parent-child relationship by applying the newly inserted
operation and reapplying the following operations. The validity is updated by
detecting cycles and concurrent move operations during applying and reapplying
operations similarly to Algorithm 1. Additionally, we store the old parent of
objects, ensuring the ability to restore to any past state.

Algorithm 2 The Restore-Apply-Reapply approach for updating validity of
operations

1:procedure UpdateValidity

2: ops $\leftarrow[]$ $\triangleright$ operations in ascending ID order

3: tree $\leftarrow\\{\\}$ $\triangleright$ a map from child ID to its parent
ID

4: moves $\leftarrow\\{\\}$ $\triangleright$ a map from element ID to a stack
of move operation IDs for moving this element

5: parents $\leftarrow[]$ $\triangleright$ a list, where each element is a
map, from object ID to its parent ID

6: valid $\leftarrow\\{\\}$

7: while whenver receives an operation o do

8: Insert o into ops at index i such that all operations at indexes > i have
an ID greater than o.ID, and all operations at indexes < i have an ID less
than o.ID

9: Insert a new map into parents at index i

10: for k $\leftarrow$ |ops| - 1 to i + 1 do $\triangleright$ Revert

11: for (object, location) in parents[k] do

12: tree[object] = location

13: if ops[k].Type is move and valid[ops[k].ID] then

14: moves[ops[k].MoveID].pop()

15: prevMove $\leftarrow$ moves[ops[k].MoveID].peek()

16: if prevMove != null then:

17: valid[prevMove] $\leftarrow$ true

18: for k $\leftarrow$ i to |ops| - 1 do $\triangleright$ Apply and Reapply

19: op $\leftarrow$ ops[k]

20: parent $\leftarrow$ {}

21: prevParent $\leftarrow$ null

22: if op.Type is make then

23: tree[op.ID] $\leftarrow$ op.ObjectID

24: parent[op.ID] $\leftarrow$ null

25: else if op.Type is move then

26: if op.Value == null then $\triangleright$ if it moves a map or list object

27: if IsAncestor(tree, op.ObjectID, op.MoveID) then

28: valid[op.ID] $\leftarrow$ false

29: continue

30: prevParent = tree[op.MoveID]

31: tree[op.MoveID] $\leftarrow$ op.ObjectID

32: valid[op.ID] $\leftarrow$ true

33: if moves[op.MoveID] == null then

34: moves[op.MoveID] $\leftarrow$ new stack

35: prevMove $\leftarrow$ moves[op.MoveID].peek()

36: if prevMove != null then:

37: valid[prevMove] $\leftarrow$ false

38: moves[op.MoveID].push(op.ID)

39: for pred in op.Predecessors do

40: if pred.Type is move and valid[pred.ID] then

41: parent[pred.MoveID] $\leftarrow$ tree[pred.MoveID]

42: tree[pred.MoveID] $\leftarrow$ null

43: else if pred.Type == make then

44: parent[pred.ID] $\leftarrow$ tree[pred.ID]

45: tree[pred.ID] $\leftarrow$ null

46: if prevParent != null then

47: parent[op.MoveID] $\leftarrow$ prevParent

48: parents[k] $\leftarrow$ parent

###  3.4 Further Optimization

####  3.4.1 Bulk Updating

In Automerge, to mutate a document, users can start a _transaction_ and
perform a series of operations. Once a transaction is committed, the
operations within the transaction are consolidated into a single change, which
can then be sent to other devices. Instead of calling UpdateValidity for each
operation, it is more efficient to collectively apply all operations within
the change at once, and thereby amortise the cost of restoring and reapplying
over many operations. Moreover, there exists the option to delay applying
changes until users perform actual query operations. This allows for the
aggregation of operations from multiple changes, facilitating a bulk updating
of these operations all at once.

####  3.4.2 Lifecycle Tracking

In the process of Restore-Apply-Reapply, objects shift between the tree and
the trash. As each operation’s ID is a logical clock, we can create a sequence
of IDs that trace the chronological progression of these shifts for each
object. This sequence of IDs is referred to as the _LifecycleList_ of an
object.

A LifecycleList can be split into two sublists:

  1. 1.

_PresentList_ : a list of operation IDs in ascending ID order, where each
operation creates or moves the object.

  2. 2.

_TrashList_ : a list of operation IDs in ascending ID order, where each
operation overwrites or deletes the object.

Upon receiving an operation, the ID of the new operation is inserted into the
TrashList of objects it deletes or overwrites, as well as the PresentList of
objects it creates or moves.

By maintaining the lifecycle of each object, there is no longer a necessity to
revert and reapply make, delete and put operations. These operations merely
shift objects back and forth between the tree and the trash, without changing
their locations within the tree. By utilizing a list detailing an object’s
lifecycle, we can deduce its existence - whether within the tree or in the
trash - without the need to directly shift the objects between the two.

By adopting lifecycle tracking, we can ensure that the algorithm’s complexity
is only related to the number of move operations in the document, rather than
the overall size of the OpSet. Furthermore, applications that do not use move
operations incur only a constant overhead.

####  3.4.3 Checkpoint

For offline applications, the states of documents could become significantly
divergent. A device might receive severely delayed operations, which means
numerous operations with IDs greater than that of the new operation are
affected. A run of Algorithm 2 is slow, as those affected operations need to
be reverted and reapplied.

To address this issue, checkpoint files can be used to reduce the number of
operations to be reverted. When applying operations, snapshots of T are
created for every $n$ operation and persisted in checkpoint files, where $n$
could be hundreds or thousands, depending on the application. To restore to a
particular past state, we can locate the nearest checkpoint and reach the
state by either reapplying or reverting fewer than $n/2$ operations.

##  4 Evaluation

In this section, we demonstrate the feasibility of the algorithm through
performance experiments. We study (1) the complexity and performance of
convergence when two actors generate move operations concurrently; (2) the
overhead caused by adding support for move operations; (3) the comparison with
an unreplicated JSON object. Additionally, we provide a correctness evaluation
of the algorithm.

We deployed the experiments on AWS c5.large instances, with each instance
having 4vCPU and 2GB RAM. The first two experiments were conducted on two
machines within a local area network, as network latency had no impact on the
results. The third experiment was conducted on three AWS instances in
different regions across the continents, namely California (us-west-1), Tokyo
(ap-northeast-1) and London (eu-west-2).

We implemented the move algorithm in a standalone Automerge prototype, which
is a simplified version of Automerge. We haven’t integrated the move algorithm
into the rust implementation of Automerge [1]. The source code is available on
GitHub111https://github.com/LiangrunDa/AutomergeWithMove.

Figure 4: Average convergence time of two actors that diverge by move
operations Figure 5: Average convergence time of two actors that diverge by
non-move operations. The disabling of the move extension is achieved by
turning off the UpdateValidity procedure

###  4.1 Convergence Complexity and Performance

We experimented to measure the time it takes for two divergent actors to
converge. In this experiment, both actors start with identical documents
containing 100 map objects. They generate $N$ move operations concurrently,
and then send the operations to each other. A move operation is generated by
choosing a random object to be moved, and a random object as the destination.
As $N$ grows larger, the actors diverge further.

To apply a remote move operation, the actors must revert and reapply the
operations with greater IDs. Without bulk updating mentioned in Section 3.4.1,
each actor needs to reapply operations at most $N(N+1)/2$ times. It takes
$O(d)$ time to reapply a move operation, where $d$ is the depth of the
destination object. Therefore, the time complexity for achieving convergence
is $O(N^{2}d)$. However, with bulk updating, the UpdateValidity procedure is
executed only once for all newly added remote operations. Through this
amortization of costs, the time complexity for adding a remote operation is
reduced to $O(d)$, and the convergence complexity is subsequently reduced to
$O(Nd)$.

Figure 4 shows the result of the experiment, which aligns well with our
complexity analysis. With bulk updating, when N = 100, it takes about 1 ms to
converge, which is acceptable for most real-time collaborative applications.
Regarding the offline applications, the number of operations diverged is
uncontrollable, as the actors can be offline for a long time. However the
convergence complexity is still acceptable, and it is the best we can achieve
for adding $N$ remote operations.

###  4.2 Overhead Caused by Move Support

Even when an application does not use any move operations, our algorithm needs
to perform additional work on operations that modify the parent-child
relationship of objects by creating, deleting or overwriting objects. To
quantify this overhead, we measure the time to achieve convergence on our
implementation with support for move operations enabled, and compare it to a
version of the same implementation with support for move operations disabled.
Initially, both actors have identical documents containing 100 map objects.
They then concurrently generate and exchange a set of $N$ make operations.

With move operations disabled, the time complexity of achieving convergence is
$O(N)$, as we don’t need to revert and reapply any operations. However, when
the move support is enabled without lifecycle tracking and bulk updating, the
time complexity of achieving convergence is $O(N^{2})$, as the algorithm needs
to reapply all the operations with greater IDs, even when there are no move
operations necessitating validity updates. When lifecycle tracking is
utilized, the time complexity of convergence is reduced back to $O(N)$, as the
algorithm only needs to revert and reapply the move operations.

Figure 5 shows the results. Without lifecycle tracking, the impact of move
support on system overhead becomes evident when $N>1000$, and the overhead is
proportional to $N^{2}$. For applications that don’t rely heavily on move
operations, the overhead can’t be overlooked. However, with lifecycle
tracking, the overhead is reduced to a constant, as the difference between the
curve of move support disabled and the curve of lifecycle tracking enabled is
negligible.

Another noteworthy advantage of lifecycle tracking is its efficient handling
of scenarios where two actors converge with unbalanced concurrent non-move
operations. For instance, if one actor generates $N$ non-move operations while
the other actor generates only one non-move operation, the convergence
complexity is $O(1)$ for the actor receiving only one remote operation from
its peer.

###  4.3 Comparison to Unreplicated JSON Object

Figure 6: Average response time of move operation on JSON CRDT and
unreplicated JSON object

In this experiment, we compare the move operation performance of the JSON CRDT
to an unreplicated JSON object.

To put the JSON CRDT to the test, we set up three AWS instances located in
different regions across the continents: us-west-1, ap-northeast-1, and eu-
west-2. These instances communicate with one another over the internet, with
an average network latency of 169 ms between them. The three actors start with
identical documents containing 100 map objects. They then concurrently
generate $N$ move operations per second and send the operations to each other
immediately. We measure the time it takes for the instances to apply both
local and remote operations.

The unreplicated JSON object is implemented using a plain JavaScript object.
It does not support concurrent operations so we only tested its performance
with local operations. The actor starts with an object containing 100 map
objects. It then randomly moves $N$ objects from one location to another per
second. We measure the time required to execute a local move in JavaScript.

The results, shown in Figure 6, indicate that it takes less than 1 $\mu s$ for
the unreplicated JSON object to apply a local move operation, whereas the JSON
CRDT takes approximately 100 $\mu s$ to perform both local and remote move
operations. Although there is a noticeable cost associated with using the JSON
CRDT, it remains within an acceptable range in the order of microseconds. As a
result, the users pay a 100 $\mu s$ overhead for replicating the JSON object
and gain the benefits of real-time and offline collaboration.

###  4.4 Correctness Testing

We run the system in a real environment, and the correctness of the system is
checked by randomly generating operations on different actors to see if the
actors can converge to the same state. This approach is inspired by Jepsen
[2], a framework for distributed systems verification.

With this approach, we found several bugs during the design of the move
algorithm. Those bugs were caused by not taking care of the corner cases with
combinations of inputs that are rarely encountered during normal execution.
Therefore, even if this approach cannot prove the correctness of the system,
it can uncover some subtle corner cases and provide confidence in correctness.

##  5 Related Work

###  5.1 CRDTs for Trees

Many CRDTs designed for trees have been put forth, and the following represent
a selection that includes support for move operations.

  * •

Previous work by Nair et al. [7] proposed a conflict-free replicated tree type
with move operations. They categorized these moves into up-moves (towards the
root) and down-moves (away from the root). The study formally verifies the
safety of concurrent up-moves while resolving cycle-causing problems arising
from other move operations through the selection of a definitive winner among
concurrent moves.

  * •

Najafzadeh et al. [8] proposed a fully asynchronous file system that supports
concurrent move operations. They replace the move operation with copy-delete
operations if a cycle occurs, leading to duplication of directories. They also
proposed a mostly asynchronous file system that uses locks to coordinate
concurrent move operations but this approach is not available under network
partition.

  * •

Kleppmann et al. [4] proposed an undo-do-redo algorithm to resolve the cycles
introduced by concurrent move operations for replicated trees. It is similar
to our approach used for detecting cycles in CRDTs for JSON, but we change the
name to Revert-Apply-Reapply to avoid confusion with a user-facing undo
feature.

The previous tree CRDTs focus on managing the parent-child relationship,
without integrating the map or list CRDT data types that occur in JSON trees
like Automerge. In contrast, our algorithm handles more complex features, such
as overwriting in map objects, moving multi-value registers within map and
list objects, and reordering elements within list objects. These features make
the algorithm significantly more complicated. Furthermore, we introduce the
concept of lifecycle tracking to reduce the overhead of the algorithm, which
is not considered in previous work.

###  5.2 CRDTs for Lists

There are many CRDTs for lists, such as Treedoc [11], WOOT [10], Logoot [13],
and LSEQ [9]. However, none of them support move operations.

Kleppmann introduced an algorithm to extend existing List CRDTs with move
operations [3]. The algorithm uses an LWW register for each element to track
the location of the element. We incorporate the algorithm into the Revert-
Apply-Reapply procedure by tracking concurrent move operations that move the
same element and selecting the move operation with the greatest ID as the
winner.

##  6 Conclusions

In this paper, we present an implementation of move operations in a JSON CRDT.
We introduce the Revert-Apply-Reapply procedure, to handle move operations
efficiently and guarantee correctness. The procedure is optimized by utilizing
further optimizations namely bulk updating, and lifecycle tracking.

Performance experiments demonstrate the practical feasibility of the move
operation, even in scenarios with high levels of concurrent operations. The
algorithm’s overhead is shown to be within an acceptable range for real-time
collaborative applications. Additionally, the paper provides a correctness
evaluation through random testing, ensuring that the algorithm converges to
the same state across different actors.

Overall, we provide a comprehensive overview of implementing move operations
in JSON CRDTs, addressing both theoretical and practical aspects, and
demonstrating its feasibility.

## References

  * [1] Automerge CRDT.  https://automerge.org.  Accessed: 2023-07-26.
  * [2] Distributed systems safety research.  https://jepsen.io.  Accessed: 2023-09-24.
  * [3] Martin Kleppmann.  Moving elements in list CRDTs.  In Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data, pages 1–6, 2020.
  * [4] Martin Kleppmann, Dominic P Mulligan, Victor BF Gomes, and Alastair R Beresford.  A highly-available move operation for replicated trees.  IEEE Transactions on Parallel and Distributed Systems, 33(7):1711–1724, 2021.
  * [5] Martin Kleppmann, Adam Wiggins, Peter Van Hardenberg, and Mark McGranaghan.  Local-first software: you own your data, in spite of the cloud.  In Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software(Onward!), pages 154–178, 2019.
  * [6] Leslie Lamport.  Time, clocks, and the ordering of events in a distributed system.  In Concurrency: the Works of Leslie Lamport, pages 179–196. 2019\.
  * [7] Sreeja Nair, Filipe Meirim, Mário Pereira, Carla Ferreira, and Marc Shapiro.  A coordination-free, convergent, and safe replicated tree.  arXiv preprint arXiv:2103.04828, 2021.
  * [8] Mahsa Najafzadeh, Marc Shapiro, and Patrick Eugster.  Co-design and verification of an available file system.  In International Conference on Verification, Model Checking, and Abstract Interpretation, pages 358–381. Springer, 2017.
  * [9] Brice Nédelec, Pascal Molli, Achour Mostefaoui, and Emmanuel Desmontils.  Lseq: an adaptive structure for sequences in distributed collaborative editing.  In Proceedings of the 2013 ACM symposium on Document engineering, pages 37–46, 2013.
  * [10] Gérald Oster, Pascal Urso, Pascal Molli, and Abdessamad Imine.  Data consistency for p2p collaborative editing.  In Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, pages 259–268, 2006.
  * [11] Nuno Preguiça, Joan Manuel Marquès, Marc Shapiro, and Mihai Letia.  A commutative replicated data type for cooperative editing.  In 2009 29th IEEE International Conference on Distributed Computing Systems, pages 395–403. IEEE, 2009.
  * [12] Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski.  Conflict-free replicated data types.  In Stabilization, Safety, and Security of Distributed Systems: 13th International Symposium, SSS 2011, Grenoble, France, October 10-12, 2011\. Proceedings 13, pages 386–400. Springer, 2011.
  * [13] Stéphane Weiss, Pascal Urso, and Pascal Molli.  Logoot: A scalable optimistic replication algorithm for collaborative editing on p2p networks.  In 2009 29th IEEE International Conference on Distributed Computing Systems, pages 404–412. IEEE, 2009.


# The Potential of AutoML for Recommender Systems

Tobias Vente University of Siegen  Joeran Beel University of Siegen

###### Abstract

Automated Machine Learning (AutoML) has greatly advanced applications of
Machine Learning (ML) including model compression, machine translation, and
computer vision. Recommender Systems (RecSys) can be seen as an application of
ML. Yet, AutoML has found little attention in the RecSys community; nor has
RecSys found notable attention in the AutoML community. Only few and
relatively simple Automated Recommender Systems (AutoRecSys) libraries exist
that adopt AutoML techniques. However, these libraries are based on student
projects and do not offer the features and thorough development of AutoML
libraries. We set out to determine how AutoML libraries perform in the
scenario of an inexperienced user who wants to implement a recommender system.
We compared the predictive performance of $60$ AutoML, AutoRecSys, ML, and
RecSys algorithms from $15$ libraries, including a mean predictor baseline, on
$14$ explicit feedback RecSys datasets. To simulate the perspective of an
inexperienced user, the algorithms were evaluated with default
hyperparameters. We found that AutoML and AutoRecSys libraries performed best.
AutoML libraries performed best for six of the $14$ datasets ($43\%$), but it
was not always the same AutoML library performing best. The single-best
library was the AutoRecSys library Auto-Surprise, which performed best on five
datasets ($36\%$). On three datasets ($21\%$), AutoML libraries performed
poorly, and RecSys libraries with default parameters performed best. Although,
while obtaining $50\%$ of all placements in the top five per dataset, RecSys
algorithms fall behind AutoML on average. ML algorithms generally performed
the worst.

##  1 Introduction

The application of Machine Learning (ML) was made more accessible by Automated
Machine Learning (AutoML) (Hutter et al.,, 2019). AutoML enables users with
little ML knowledge to apply ML algorithms relatively easily and effectively
in various fields. Sometimes, AutoML libraries may achieve even better
performance than human experts with ML libraries (Hanussek et al.,, 2020).

ML is often used to implement Recommender Systems (RecSys) (Zhang et al.,,
2019). The goal of RecSys is, among others, to predict the rating that a
customer would give to an item (e.g., a movie or e-commerce product); or to
predict the preference of a customer for an item ("like" / "dislike").
Implementing RecSys with ML or non-ML algorithms is as challenging as
implementing any other ML pipeline. Many different algorithms with many
hyperparameters exist. A user of RecSys algorithms must select algorithms and
features, tune hyperparameters, and conduct time-consuming evaluations. If the
user is inexperienced and implements the pipeline sub-optimally, then the
recommendations wont satisfy customers and harm the business’s success.

The success of AutoML has resulted in the development of a few Automated
Recommender Systems (AutoRecSys) libraries that adopt AutoML techniques to
RecSys (Anand and Beel,, 2020; Wang et al.,, 2020; Sonboli et al.,, 2021;
Gupta and Beel,, 2020). However, these AutoRecSys libraries are based on
student projects and not developed as professionally as many AutoML libraries.
A user could also use AutoML by formulating a RecSys task as a ML
classification or regression task.

Using ML or RecSys libraries is challenging for inexperienced users. To
satisfy customers, inexperienced users would need to find a suitable
configuration. To do so, AutoML or AutoRecSys could help inexperienced users
and make RecSys more accessible. AutoML for RecSys could have potential
because no holistic and easily usable (Auto)RecSys libraries exist. This is in
stark contrast to the plenty holistic and easily usable AutoML libraries.

Many RecSys libraries exist. RecSys libraries are often designed for
particular RecSys applications (e.g., only explicit feedback); built with a
focus on specific types of algorithms (e.g., neural networks); and, depending
on its community, actively maintained or not maintained at all. State-of-the-
art algorithms could be too complicated to reproduce for an inexperienced user
or not reproducible at all, see (Dacrema et al.,, 2019). Using AutoRecSys can
be problematic since users’ needs, like implicit feedback, are not supported
yet.

It is an open question whether an inexperienced user can achieve suitable
performance with AutoML compared to AutoRecSys, ML, or RecSys algorithms. We
understand an inexperienced user to be a user that only employs default
hyperparameters. This motivates our research question: _What is the
performance of AutoML algorithms on RecSys tasks compared to AutoRecSys, ML,
and RecSys algorithms using default hyperparameters?_

In this study, we do not explore the reasons for the differences in
performance between algorithms. So far, nobody investigated the potential of
AutoML for RecSys. Hence, we are first interested in an assessment of the
state-of-the-art for inexperienced users as an initial exploratory study. A
detailed analysis of the performance differences is too extensive for this
paper and left for future work.

To answer our research question, we compare $7$ AutoML-, $28$ ML-, $23$ RecSys
algorithms, $1$ AutoRecSys algorithm, and a mean predictor baseline on $14$
RecSys datasets. We used default values for all hyperparameters to simulate
the perspective of an inexperienced user. We limit this comparison to explicit
feedback, a RecSys rating prediction task, and offline evaluation.

We hope that this work directs the interest of the AutoML community towards
RecSys. Moreover, we hope that this work shows the special application of
automated approaches in RecSys and the need thereof. We contribute insights
into the potential of AutoML for an applied field like RecSys. Furthermore, we
collected and preprocessed $14$ datasets for predicting explicit feedback.
Code for the comparison and for preprocessing the datasets can be found in our
GitHub repository111https://github.com/ISG-
Siegen/AutoML_for_Recommender_Systems.

##  2 Related Work

To the best of our knowledge, no one has evaluated AutoML libraries on a
relatively large number of RecSys datasets. The work closest to ours is the
usage of AutoML to generate ensembles for RecSys (Gupta and Katarya,, 2021).
RecSys algorithms were used for AutoML in, for example, model selection (Yang
et al.,, 2019). AutoML has been applied to other fields like computer vision
(Yang et al.,, 2021; Saikia et al.,, 2019; Lopes et al.,, 2021), machine
translation (Viswanathan et al.,, 2019), model compression (He et al.,, 2018),
and education (Tsiakmaki et al.,, 2020; Lee et al.,, 2020). To compare
different AutoML frameworks, an AutoML benchmark was created (Gijsbers et
al.,, 2019). Moreover, in the AutoML community, large dataset collections
exist (Bischl et al.,, 2017; Balaji and Allen,, 2018). For example,
benchmarking suites222https://docs.openml.org/benchmark/ on OpenML (Vanschoren
et al.,, 2013). No such dataset collections exist in the recommender system
community. Furthermore, there is no standardized benchmark framework to
compare RecSys algorithms.

##  3 Methods

We evaluated the predictive performance of $7$ AutoML-, $28$ ML-, $23$ RecSys
algorithms, $1$ AutoRecSys algorithm, and a mean predictor baseline on $14$
RecSys datasets. Each RecSys dataset contains explicit feedback, which
represents a rating prediction task. Our implementation made the datasets
usable by (Auto)RecSys and (Auto)ML algorithms. To capture the predictive
performance, we computed the Root Mean Squared Error (RMSE) using hold-out
validation (random test split: $25\%$). For our inexperienced-user-scenario,
the algorithms are evaluated with default hyperparameters. To compare the $60$
algorithms, we created a Docker-based evaluation tool. Moreover, we created
preprocessing scripts for all $14$ RecSys datasets. All $840$ evaluation runs
($60$ algorithms times $14$ datasets) were done on a workstation with an AMD
Ryzen Threadripper PRO 3975WX CPU, 32 Cores (64 threads), SSD storage, and 528
GB RAM. The evaluations were run sequentially to guarantee that each run can
utilize all resources. In total, it took 25 days to run all evaluations.

We did not reuse the AutoML benchmark (Gijsbers et al.,, 2019) for two
reasons. First, the benchmark’s support for regression is a work in progress,
which is, however, required for the task of predicting ratings. Second, the
benchmark does not fully control runtime and memory limits independently from
the evaluated frameworks. It assumes that the frameworks constrain the
resources themselves. For example, the maximum runtime for an evaluation is
passed to the framework and only if this constraint is not respected after
twice the maximum runtime, the evaluation is
aborted333https://github.com/openml/automlbenchmark/blob/master/docs/HOWTO.md.
Moreover, it is not a requirement that the frameworks limit memory. For our
use case of regression and our need of resource limits due to budget
constraints, the AutoML benchmark was not appropriate.

All $14$ RecSys datasets are publicly available. However, we can not
redistribute the datasets due to their licenses. We only provide our
preprocessing scripts so that others can replicate the evaluated datasets.
RecSys datasets for explicit feedback differ from normal ML datasets in that
RecSys datasets contain customer-, item-IDs, and timestamps as features. The
timestamp, or a feature that can be transformed into a timestamp (e.g.: date
of rating), represents the point in time a customer rated an item. Additional
features are optional and not necessarily used by RecSys algorithms. The $23$
RecSys algorithms included in our comparison only use customer-, item-IDs, and
optionally timestamps. Consequently, we compare (Auto)RecSys using two or
three features with (Auto)ML algorithms using all features. RecSys datasets
are not synthetic but derived from real-world applications including human-
derived data. In the following, we first present the selected datasets. Then,
we detail the compared libraries. Lastly, we talk about our experiment setup
by detailing the preprocessing, hyperparameters, and resource limits.

###  3.1 Datasets

We selected the following $14$ RecSys datasets for explicit feedback444The
URLs to and licenses of all datasets can be found in the appendix A.. These
datasets are some of the most common and public rating-related RecSys tasks,
which we found through the dataset survey by Beel and Brunel, (2019) and
papers from RecSys conferences.

  * •

MovieLens Data: We have used the MovieLens 100k, MovieLens 1M, and MovieLens
Latest 100k (9/2018) datasets (Harper and Konstan,, 2016).

  * •

Amazon Review Data: The datasets based on the following categories were used:
Electronics; Digital Music; Toys and Games; Movies and TV; Fashion;
Appliances; Industrial and Scientific; Software. We used the 5-core versions
combined with meta-data (Ni et al.,, 2019).

  * •

Other: We have also used the Yelp Open Dataset (Yelp,, 2014); the Netflix
Prize Dataset (Bennett et al.,, 2007)555We randomly subsampled this dataset to
ten million instances due to our budget constraints.; and the Food.com Recipes
and Interactions Dataset (Majumder et al.,, 2019).

###  3.2 Libraries

All selected libraries are open source and can predict explicit feedback666The
versions, URLs to, and licenses of all libraries can be found in the appendix
A..

  * •

RecSys: Surprise (Hug,, 2020), LensKit (Ekstrand,, 2020), Spotlight (Kula,,
2017), AutoRec (Wang et al.,, 2020)

  * •

AutoRecSys: Auto-Surprise (Anand and Beel,, 2020)

  * •

ML: scikit-learn (Pedregosa et al.,, 2011), XGBoost (Chen and Guestrin,,
2016), ktrain (Maiya,, 2020)

  * •

AutoML: Auto-sklearn (Feurer et al.,, 2015), FLAML (Wang et al.,, 2021), GAMA
(Gijsbers and Vanschoren,, 2019), H2O (LeDell and Poirier,, 2020), TPOT (Olson
et al.,, 2016; Le et al.,, 2020), AutoGluon (Erickson et al.,, 2020), Auto-
PyTorch (Zimmer et al.,, 2021; Mendoza et al.,, 2018)

The Auto-Surprise (Anand and Beel,, 2020) library is an extension of the
Surprise (Hug,, 2020) library. Auto-Surprise uses the Tree of Parzen
Estimators of Hyperopt (Bergstra et al.,, 2015) to solve the Combined
Algorithm and Hyper-parameter Selection (CASH) problem for a search space
created from the algorithms and hyperparameter of Surprise. Auto-Surprise is
currently the only library that we labeled as AutoRecSys because it is
automated and sophisticated enough.

We labeled the library AutoRec as a RecSys library and not as an AutoRecSys
library. AutoRec provides an interface to use AutoKeras (Jin et al.,, 2019;
Chollet et al.,, 2015) without automating the additional overhead of the
interface itself. For example, AutoRec does not enable the usage of a time
limit for the neural architecture search nor does it automatically setup the
input interaction matrix. Hence, we deem AutoRec to be not automated enough to
be called AutoRecSys. Besides Auto-Surprise and AutoRec, two other projects
related to AutoRecSys exist: Librec-Auto777https://github.com/that-recsys-
lab/librec-auto (Sonboli et al.,, 2021) and Auto-
CaseRec888https://github.com/BeelGroup/Auto-CaseRec (Gupta and Beel,, 2020).

Librec-Auto takes as input one or more algorithms and their configurations
defined in a XML-file and evaluates them. It can optionally optimize the
algorithms’ numeric hyperparameters. Librec-Auto, however, does not return a
trained model nor does it perform algorithm selection. It is an evaluation
tool for a set of predefined algorithms. Auto-CaseRec is an early prototype of
an AutoRecSys framework. It solves the CASH problems the Case Recommender
library (da Costa et al.,, 2018). Yet, it does not offer the features and
thorough development of a normal automated library. Mainly, its file-based
usage and missing installation support (like a requirements file) are
problematic. As a result, it was not usable as a part of our comparison
without first reimplementing some of its functionalities. Consequentily, Auto-
CaseRec and Librec-Auto are not sophisticated enough to be AutoRecSys.

All algorithms in a library are integrated into our comparison if possible. We
have used $10$ algorithms from LensKit, $11$ from Surprise, $26$ from scikit-
learn, and $1$ algorithm from each other library. Details on which algorithms
are used per library are listed in the Appendix B. Additionally, a baseline
$B_{mean}$ was added. $B_{mean}$ always predicts the mean of the ratings
calculated using the training data. $B_{mean}$ is part of its own category
"Baseline". In total, $60$ algorithms are compared.

###  3.3 Experiment Setup

#### Preprocessing

We preprocessed the RecSys datasets such they are usable by (Auto)RecSys and
(Auto)ML algorithms and as close as possible to the original dataset. Details
on the chosen preprocessing steps can be found in the Appendix C. To present
an overview of the resulting datasets, see Table 1 for details on the
datasets’ statistics. Table 1 shows the number of customers, items, and
instances of each preprocessed dataset. It also shows the number of additional
features. Additional features are all features excluding customer-, item-ID
and timestamp. Furthermore, the table details how many ratings each customer
has done on average and the minimum/maximum number of ratings by a single
customer.

Table 1: Dataset Statistics For each dataset, the number of customers, items,
instances, and additional features are shown. Additional features represent
the number of features besides customer-, item-ID, and timestamp. Statistics
about the Ratings per Customer (RpC) are also shown.

Dataset | #customers | #items | #instances | #$add_{features}$ | Avg. RpC | Min. RpC | Max. RpC
---|---|---|---|---|---|---|---
amazon-appliances | $47$ | $47$ | $190$ | $4$ | $4.042\,553\,191\,489\,362$ | $1$ | $8$
amazon-digital-music | $1485$ | $185$ | $2243$ | $4$ | $1.510\,437\,710\,437\,710\,5$ | $1$ | $14$
amazon-fashion | $406$ | $31$ | $3076$ | $4$ | $7.576\,354\,679\,802\,955\,5$ | $1$ | $16$
amazon-software | $1826$ | $802$ | $11\,981$ | $4$ | $6.561\,336\,254\,107\,339$ | $1$ | $52$
amazon-industrial-and-scientific | $11\,041$ | $5327$ | $72\,431$ | $4$ | $6.560\,184\,765\,872\,656$ | $1$ | $92$
movielens-100K | $943$ | $1682$ | $100\,000$ | $44$ | $106.044\,538\,706\,256\,63$ | $20$ | $737$
movielens-latest-small | $610$ | $9724$ | $100\,836$ | $20$ | $165.304\,918\,032\,786\,87$ | $20$ | $2698$
movielens-1M | $6039$ | $3705$ | $998\,080$ | $22$ | $165.272\,396\,092\,068\,22$ | $19$ | $2314$
foodCom | $226\,570$ | $231\,637$ | $1\,132\,367$ | $12$ | $4.997\,868\,208\,500\,684$ | $1$ | $7671$
amazon-toys-and-games | $208\,180$ | $78\,698$ | $1\,759\,314$ | $4$ | $8.450\,927\,082\,332\,596$ | $1$ | $718$
amazon-movies-and-tv | $297\,529$ | $60\,110$ | $3\,293\,658$ | $4$ | $11.070\,040\,231\,372\,404$ | $1$ | $3398$
amazon-electronics | $728\,719$ | $159\,935$ | $6\,537\,585$ | $4$ | $8.971\,338\,746\,485\,271$ | $1$ | $576$
yelp | $2\,189\,457$ | $160\,585$ | $8\,635\,384$ | $58$ | $3.944\,075\,631\,537\,865\,3$ | $1$ | $6073$
netflix | $458\,382$ | $17\,759$ | $10\,000\,000$ | $1$ | $21.815\,865\,369\,931\,63$ | $1$ | $1779$

#### Hyperparameter Settings

For all algorithms, the default values for hyperparameters are used. If an
implementation does not provide default parameters, the parameter values of
the sample code from the implementation’s documentation were used, e.g.,
values in the getting started section.

For automated libraries, resource parameters were set to have the same memory,
job count, time passed to the framework (called search time), and optimization
metrics across all libraries. We set the memory to all available memory (528
GB), the number of jobs to the maximal number of cores (64 - one for each CPU
thread), the search time to $4$ hours elapsed real (wall-clock) time, and the
metric to the RMSE. Not all automated libraries support the RMSE. In such
cases, the library was adjusted to optimize the MSE. Furthermore, not all
libraries provide parameters to control memory or job count. In these cases,
the behavior of the library is to use all memory or cores.

RecSys and ML libraries do not necessarily allow a user to set a time limit or
tolerance for stopping the training of an algorithm. Instead, libraries rely
on a user-controlled parameter to define the maximum number of trials or
epochs for training. The default training parameters are not necessarily
representative for the given algorithm while being faithful to our use case of
an inexperienced user. To include an alternative in our analysis, we made an
exception for AutoRec and set it to use $75$ search trials and $1000$ epochs
with early stopping for all datasets.

#### Resource Limits

We implemented a runtime limit. If an algorithm takes more than $4$ hours and
$30$ minutes for its evaluation, its execution is terminated. For automated
libraries, this runtime limit is extended by the search time. Hence, totaling
a limit of $8$ hours and $30$ minutes. An algorithm is also terminated if its
evaluation exceeds $528$ GB, the maximal available memory of our system.

#### Predictive Performance Evaluation

To compare the predictive accuracy across datasets, we transformed the RMSE
into a rank. A lower rank is better (e.g.: 1 is the best rank). All algorithms
that ran into a limit were ranked last. Equally well-performing algorithms are
assigned the average of their combined ranks.

##  4 Results

We first present the impact of our chosen resource limits. Next, we evaluate
the predictive performance of the algorithms and their associated categories.

###  4.1 Impacts of Resource Limits

Each evaluation run was limited in terms of memory and time. $7.50\%$ of all
evaluation runs failed. The memory limit was reached in $3.81\%$ and the time
limit in $3.69\%$ of all runs. This, however, depends very much on the
dataset. See Table 2 for an overview over the different datasets.

Table 2: Failure of Algorithms per Category per Datasets Shown are the
absolute failure counts and the failure frequencies for each dataset per
category. The number next to the category name shows the number of algorithms
in this category. The baseline $B_{mean}$ is not shown, it did not run into
any limits. However, it is part of the total count of algorithms for the last
column.

Dataset | AutoML (7) | AutoRecSys (1) | ML (28) | RecSys (23) | Total (60)
---|---|---|---|---|---
amazon-appliances | - | - | - | - | -
amazon-digital-music | - | - | - | - | -
amazon-fashion | - | - | - | - | -
amazon-software | - | - | - | - | -
amazon-industrial-and-scientific | - | - | - | - | -
movielens-100K | - | - | 1 (3.57%) | - | 1 (1.67%)
movielens-latest-small | - | - | 1 (3.57%) | - | 1 (1.67%)
movielens-1M | - | - | 3 (10.71%) | - | 3 (5.00%)
foodCom | - | - | 3 (10.71%) | 2 (8.70%) | 5 (8.33%)
amazon-toys-and-games | 1 (14.29%) | - | 3 (10.71%) | 5 (21.74%) | 9 (15.00%)
amazon-movies-and-tv | - | - | 3 (10.71%) | 5 (21.74%) | 8 (13.33%)
amazon-electronics | - | - | 3 (10.71%) | 6 (26.09%) | 9 (15.00%)
yelp | 4 (57.14%) | - | 4 (14.29%) | 8 (34.78%) | 16 (26.67%)
netflix | 1 (14.29%) | - | 4 (14.29%) | 6 (26.09%) | 11 (18.33%)

The majority of AutoML tools failed on the yelp dataset. The yelp dataset
requires at least ${\sim}1.6$ GB memory. This was too much for AutoPyTorch,
AutoSklearn, and TPOT. Both AutoPytorch and AutoSklearn limit the memory per
job. For the yelp dataset, the memory limit per job is quickly exceeded if the
memory (528 GB) is split between all 64 jobs. TPOT also runs in a job-related
memory limit. All other AutoML failures were timeouts. In these cases, GAMA,
TPOT, and AutoGluon were not able to build a model from the training data and
generate the final predictions for the test data in the provided $4$ hours and
$30$ minutes after the $4$-hour-long search.

Assuming an inexperienced user would randomly pick an algorithm to solve a
dataset, the algorithm would not produce any result within our resource
limitations in $7.50\%$ of all cases. For yelp, this would occur with a
probability of $26.67\%$.

Recall, we made an exception for AutoRec, a RecSys library, and let it run for
more epochs and trials than the default values. This made AutoRec run in a
timeout for all six datasets with more than a million instances. Another deep
learning RecSys library, Spotlight, which only runs for ten iterations by
default, did run in a timeout for netflix and yelp. Yet, in all eight cases
where both did not run into a limit, AutoRec and Spotlight are tied for the
number of better predictive accuracy scores. In other words, neither default
values nor static custom values are dominant.

###  4.2 Predictive Performance

To inspect the categories’ performance, see Table 4 for the categories’
average rank. This data indicates the category ranking:
$AutoRecSys\>(3.57)>AutoML\>(18.64)>RecSys\>(28.03)>ML\>(36.20)>Baseline\>(37.64)$.
Since the AutoRecSys category contains only one library (AutoSurprise), the
average of the AutoRecSys category equals the result of AutoSurprise.
AutoSurprise did run on all datasets and did neither experience memory limits
nor timeouts. Next, we switch to an algorithm-specific perspective.

Refer to Table 4 for an overview of the top 10 ranked algorithms. The top 10
includes all categories except for the baseline. The AutoRecSys library Auto-
Surprise allocates the first place with a substantial average rank difference
to the second place. Auto-Surprise is followed by the two AutoML tools FLAML
and H2O. The majority of algorithms within the top 10 are from RecSys
libraries. One ML algorithm, XGBoost, reached the top 10. FLAML’s average rank
is exactly twice the average rank of Auto-Surprise. In contrast, the rest of
the average ranks differ only marginally between subsequent placings.

Table 3: Average Rank per Category The number next to the category shows the amount of algorithms in the category.  Category | Average rank | Failure $\%$
---|---|---
AutoRecSys (1) | $3.571\,428\,571\,428\,571\,6$ | -
AutoML (7) | $18.642\,857\,142\,857\,142$ | 6.12%
RecSys (23) | $28.032\,608\,695\,652\,176$ | 9.94%
ML (28) | $36.197\,704\,081\,632\,65$ | 6.38%
Baseline (1) | $37.642\,857\,142\,857\,146$ | -

Table 4: Top 10 Average Ranked Algorithms Algorithm | Average rank
---|---
Auto-Surprise | $3.571\,428\,571\,428\,571\,6$
FLAML | $7.142\,857\,142\,857\,143$
H2OAutoML | $7.214\,285\,714\,285\,714$
SVDpp (Surprise) | $8.071\,428\,571\,428\,571$
FunkSVD (LensKit) | $9.357\,142\,857\,142\,858$
BiasedSVD (LensKit) | $11.178\,571\,428\,571\,429$
SVD (Surprise) | $11.285\,714\,285\,714\,286$
BaselineOnly (Surprise) | $13.071\,428\,571\,428\,571$
ALSBiasedMF (LensKit) | $13.571\,428\,571\,428\,571$
XGBoostRegressor | $15.5$

For more detailed ranking information per dataset, see Figure 1 for a rank
plot of algorithms per dataset. The datasets’ top 5 are dominated by RecSys
algorithms, which are most often a variation of SVD. 35 out of 70 are RecSys
algorithms and 11 out of 70 are AutoRecSys. In total, 46 out of 70 are RecSys
or AutoRecSys (65.7%). Yet, RecSys algorithms are only able to secure the
first place three times. The first place is dominated by AutoRecSys (5 times)
and AutoML (6 times).

Datasets with a lot of additional features, like yelp or movielens-latest-
small, are mostly dominated by ML approaches except for movielens-1M and
movielens-100k. Movielens-1M and movielens-100k are extremely popular
evaluation datasets in the RecSys community (Beel and Brunel,, 2019) and thus
a lot of tools are tuned to work best on these datasets by default. Similar,
datasets with almost no additional features like netflix are dominated by
RecSys algorithms. For datasets with some additional features, the results are
mixed.

Besides an algorithm rank perspective, a category rank perspective is
relevant. See Figure 2 for a rank plot of categories per dataset. Our chosen
baseline is, as expected, always the worst category. This is closely followed
by ML, which is in the fourth place 10 out of 14 times. Automated libraries
are never in the fourth place. The first and second place are dominated by
AutoRecSys and AutoML, with AutoRecSys being in the first or second place 11
times and AutoML 7 times. This follows the category ranking indicated by the
tables above, while the first place is more disputed.

Figure 1: Top 5 Algorithms per Dataset For each dataset, the top 5 algorithms
are shown. They are color coded for their category. Moreover, the RMSE and
name of the algorithm are shown. A larger, more readable version of this
figure is located in the appendix.  Figure 2: Order of Categories per Dataset
For each dataset, the 5 categories are shown sorted by their best performing
algorithm’s RMSE. They are color coded for their category. Moreover, the RMSE
and name of the best performing algorithm are shown. A larger, more readable
version of this figure is located in the appendix.

##### Comparison to the Baseline

Many outliers exist in the collected error values999See Appendix D for more
details.. Such outliers are expected since all algorithms with default values
within a library were used. However, it is unexpected that the baseline
$B_{mean}$, which only predicts the mean, outperforms other algorithms
frequently. On average across all datasets, $B_{mean}$ outperforms $26.90\%$
of all algorithms.

##  5 Discussion

Given our results, we can answer the research question: _What is the
performance of AutoML algorithms on RecSys tasks compared to AutoRecSys, ML,
and RecSys algorithms using default hyperparameters?_ The results indicate the
following performance ranking for default hyperparameters: $AutoRecSys\geq
AutoML>RecSys>ML>Baseline$ whereby the first place is disputed between
AutoRecSys and AutoML. In other words, we recommend AutoML or AutoRecSys
libraries to an inexperienced user. AutoML is a promising approach to RecSys
with a lot of potential considering that AutoML is not (over)fitted to RecSys
tasks and much more accessible than RecSys libraries.

Given that RecSys algorithms often outperform ML algorithms but AutoML still
outperforms RecSys, the need for more sophisticated AutoRecSys libraries is
shown. Likewise, extensions of AutoML frameworks to RecSys have a lot of
potential, given that AutoML is able to outperform the application-specific
AutoRecSys or RecSys in $6$ of $14$ RecSys datasets. Moreover, the
accessibility of RecSys libraries is in stark contrast to the accessibility of
AutoRecSys or AutoML libraries (see our code for examples).

In general, the percentage of failed runs and bad performances is surprisingly
high. Assuming an inexperienced user would randomly pick an algorithm, the
algorithm would not produce any result within our resource limits or perform
worse than the simple baseline $B_{mean}$ in $34.40\%$ of all cases. While
this perspective is biased by bad performing algorithms and our resource
limits, it is still truthful to our inexperienced-user-scenario. An
inexperienced user does not know which algorithms are inappropriate or badly
implemented. Furthermore, an inexperienced user has almost no guidelines about
which algorithm to use in RecSys. Likewise, the impact of hyperparameter
values on the performance and failure, like the number of training iterations
for AutoRec and Spotlight, further illustrates the need for automated
libraries to make RecSys more accessible.

Using benchmarking suites is a standard practice in AutoML. In RecSys, methods
are evaluated on a few (potentially not diverse) datasets. However, we can see
that a difference in performance of methods between such common datasets (like
movielens-1M, movielens-100k, netflix) and more uncommon datasets (like
Food.com and Yelp with our preprocessing) exist. The need for a diverse and
complete benchmarking suite for RecSys is apparent.

##  6 Conclusion

To conclude our work, we first recap and discuss the broader impact of our
work. Then, we detail the potential directions of improvement. Next, the
limitations of our work are explicitly stated. Finally, the future work is
addressed.

#### Summary and Broader Impact Statement

We compared the predictive performance of $60$ AutoML, AutoRecSys, ML, and
RecSys algorithms, including a baseline, on $14$ RecSys datasets with explicit
feedback. The open-source implementation of our comparison tool allows others
to evaluate algorithms’ performance on RecSys datasets. We presented algorithm
performance through a ranking calculated using RMSEs obtained by hold-out
validation. The presented results allow users to compare algorithms for a
real-world RecSys application. Specifically, the results indicated
$AutoRecSys\geq AutoML>RecSys>ML>Baseline$ as a performance ranking. Moreover,
we have shown that it is likely to encounter worse-than-baseline performing
algorithms.

A positive impact of the presented results is that users are able to select an
appropriate algorithm or category of algorithms without being RecSys experts.
The results could lead more users to AutoML or AutoRecSys. AutoML or
AutoRecSys can help users to create real-world RecSys applications without
deep RecSys knowledge. Yet, if users do not know the risks of RecSys, their
models could lead to biased, unfair, or offensive recommendations. Such misuse
could create filter bubbles and bubbles that support malicious content.

Generally, our work is a first step towards fair and comparable benchmarking
in RecSys. Initiatives to make data more standardized and easily shareable
would be highly impactful for the RecSys community. Likewise, extending AutoML
libraries to RecSys applications can create a positive impact. Alternatively,
an initiative to support and produce sophisticated AutoRecSys libraries would
help as well. The downsides of comparing different algorithms and making it
easier to select appropriate algorithms, like automated approaches, could be
reduced by increasing the awareness about the risks of automated approaches in
RecSys.

#### Limitations

Our comparison focused on RecSys datasets with explicit feedback. Therefore,
we did not include datasets with implicit feedback. The preprocessed datasets
used for evaluation are basic by design and without natural language
processing. These preprocessed datasets are not redistributed. Only scripts to
prepossess the original datasets are provided. The selected RecSys algorithms
can only use a user-ID, item-ID, rating, and optionally timestamps from a
dataset. We did not constrain (Auto)ML algorithms to use a subset of the
available features. As a result, RecSys algorithms use fewer features than ML
algorithms. We worked with resource limitations and not all evaluations were
able to finish within our limits. Additional datasets, libraries, and more
expensive validation methods (like cross-validation) are missing in this first
version of our comparison.

#### Directions of Improvement

Our results hint at the effectiveness of automated libraries for inexperienced
users in RecSys. Moreover, we have only found one suitable automated library
that explicitly focused on RecSys. Consequently, there is a clear need for
better and more sophisticated automated libraries for RecSys. We think that
the sophisticated AutoML libraries need to get extensions for RecSys or better
AutoRecSys libraries need to be made. Improvements in these directions shall
end the manual and not systematically automated search for suitable
configurations in RecSys. Thus, bringing the advances from the AutoML
community to the RecSys community. Such that, in turn, the RecSys community
will focus more on AutoML in the future.

#### Future Work

In future work, a better comparison between AutoML, AutoRecSys, ML, and RecSys
algorithms can be achieved. Firstly, extending our comparison to perform
cross-validation with a bigger resource budget is necessary. Thus, reducing
the noise of randomness and to get more meaningful results. Secondly, the
comparison needs to include more datasets and algorithms. Lastly, the
comparison of algorithms and categories must be extended to implicit feedback
datasets. Besides achieving a better comparison, a detailed analysis of such a
comparison is future work. Determining the reason for the difference in the
performance of compared algorithms can help to improve existing algorithms or
foster the creation of new algorithms.

## References

  * Anand and Beel, (2020) Anand, R. and Beel, J. (2020).  Auto-surprise: An automated recommender-system (autorecsys) library with tree of parzens estimator (TPE) optimization.  In Santos, R. L. T., Marinho, L. B., Daly, E. M., Chen, L., Falk, K., Koenigstein, N., and de Moura, E. S., editors, RecSys 2020: Fourteenth ACM Conference on Recommender Systems, Virtual Event, Brazil, September 22-26, 2020, pages 585–587. ACM.
  * Balaji and Allen, (2018) Balaji, A. and Allen, A. (2018).  Benchmarking automatic machine learning frameworks.  arXiv preprint arXiv1808.06492.
  * Beel and Brunel, (2019) Beel, J. and Brunel, V. (2019).  Data pruning in recommender systems research best-practice or malpractice.  ACM RecSys.
  * Bennett et al., (2007) Bennett, J., Lanning, S., et al. (2007).  The netflix prize.  In Proceedings of KDD cup and workshop, volume 2007, page 35. New York, NY, USA.
  * Bergstra et al., (2015) Bergstra, J., Komer, B., Eliasmith, C., Yamins, D., and Cox, D. D. (2015).  Hyperopt: a python library for model selection and hyperparameter optimization.  Computational Science & Discovery, 8(1):014008.
  * Bischl et al., (2017) Bischl, B., Casalicchio, G., Feurer, M., Hutter, F., Lang, M., Mantovani, R. G., van Rijn, J. N., and Vanschoren, J. (2017).  Openml benchmarking suites and the openml100.  CoRR, abs/1708.03731.
  * Chen and Guestrin, (2016) Chen, T. and Guestrin, C. (2016).  Xgboost: A scalable tree boosting system.  In Krishnapuram, B., Shah, M., Smola, A. J., Aggarwal, C. C., Shen, D., and Rastogi, R., editors, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 785–794. ACM.
  * Chollet et al., (2015) Chollet, F. et al. (2015).  Keras.  https://keras.io.
  * da Costa et al., (2018) da Costa, A., Fressato, E., Neto, F., Manzato, M., and Campello, R. (2018).  Case recommender: A flexible and extensible python framework for recommender systems.  In Proceedings of the 12th ACM Conference on Recommender Systems, RecSys ’18, pages 494–495, New York, NY, USA. ACM.
  * Dacrema et al., (2019) Dacrema, M. F., Cremonesi, P., and Jannach, D. (2019).  Are we really making much progress? A worrying analysis of recent neural recommendation approaches.  In Bogers, T., Said, A., Brusilovsky, P., and Tikk, D., editors, Proceedings of the 13th ACM Conference on Recommender Systems, RecSys 2019, Copenhagen, Denmark, September 16-20, 2019, pages 101–109. ACM.
  * Ekstrand, (2020) Ekstrand, M. D. (2020).  Lenskit for python: Next-generation software for recommender systems experiments.  In d’Aquin, M., Dietze, S., Hauff, C., Curry, E., and Cudré-Mauroux, P., editors, CIKM ’20: The 29th ACM International Conference on Information and Knowledge Management, Virtual Event, Ireland, October 19-23, 2020, pages 2999–3006. ACM.
  * Erickson et al., (2020) Erickson, N., Mueller, J., Shirkov, A., Zhang, H., Larroy, P., Li, M., and Smola, A. (2020).  Autogluon-tabular robust and accurate automl for structured data.  arXiv preprint arXiv2003.06505.
  * Feurer et al., (2015) Feurer, M., Klein, A., Eggensperger, K., Springenberg, J. T., Blum, M., and Hutter, F. (2015).  Efficient and robust automated machine learning.  In Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R., editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2962–2970.
  * Gijsbers et al., (2019) Gijsbers, P., LeDell, E., Thomas, J., Poirier, S., Bischl, B., and Vanschoren, J. (2019).  An open source automl benchmark.  arXiv preprint arXiv1907.00909.
  * Gijsbers and Vanschoren, (2019) Gijsbers, P. and Vanschoren, J. (2019).  GAMA genetic automated machine learning assistant.  Journal of Open Source Software, 4(33):1132.
  * Gupta and Katarya, (2021) Gupta, G. and Katarya, R. (2021).  Enpso: An automl technique for generating ensemble recommender system.  Arabian Journal for Science and Engineering, 46(9):8677–8695.
  * Gupta and Beel, (2020) Gupta, S. and Beel, J. (2020).  Auto-caserec: Automatically selecting and optimizing recommendation-systems algorithms.  OSF Preprints,.
  * Hanussek et al., (2020) Hanussek, M., Blohm, M., and Kintz, M. (2020).  Can automl outperform humans an evaluation on popular openml datasets using automl benchmark.  arXiv preprint arXiv2009.01564.
  * Harper and Konstan, (2016) Harper, F. M. and Konstan, J. A. (2016).  The movielens datasets: History and context.  ACM Trans. Interact. Intell. Syst., 5(4):19:1–19:19.
  * He et al., (2018) He, Y., Lin, J., Liu, Z., Wang, H., Li, L., and Han, S. (2018).  AMC: automl for model compression and acceleration on mobile devices.  In Ferrari, V., Hebert, M., Sminchisescu, C., and Weiss, Y., editors, Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part VII, volume 11211 of Lecture Notes in Computer Science, pages 815–832. Springer.
  * Hug, (2020) Hug, N. (2020).  Surprise a python library for recommender systems.  Journal of Open Source Software, 5(52):2174.
  * Hutter et al., (2019) Hutter, F., Kotthoff, L., and Vanschoren, J., editors (2019).  Automated Machine Learning - Methods, Systems, Challenges.  The Springer Series on Challenges in Machine Learning. Springer.
  * Jin et al., (2019) Jin, H., Song, Q., and Hu, X. (2019).  Auto-keras: An efficient neural architecture search system.  In Teredesai, A., Kumar, V., Li, Y., Rosales, R., Terzi, E., and Karypis, G., editors, Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 1946–1956. ACM.
  * Kula, (2017) Kula, M. (2017).  Spotlight.  https://github.com/maciejkula/spotlight.
  * Le et al., (2020) Le, T. T., Fu, W., and Moore, J. H. (2020).  Scaling tree-based automated machine learning to biomedical big data with a feature set selector.  Bioinformatics, 36(1):250–256.
  * LeDell and Poirier, (2020) LeDell, E. and Poirier, S. (2020).  H2O AutoML scalable automatic machine learning.  7th ICML Workshop on Automated Machine Learning (AutoML).
  * Lee et al., (2020) Lee, S. B., Gui, X., and Hamilton, E. (2020).  Application of automl in the automated coding of educational discourse data.  In Interdisciplinarity in the Learning Sciences: Proceedings of the 14th International Conference of the Learning Sciences, ICLS 2020, [Nashville, Tennessee, USA], Online Conference, June 19-23, 2020. International Society of the Learning Sciences.
  * Lopes et al., (2021) Lopes, V., Gaspar, A., Alexandre, L. A., and Cordeiro, J. (2021).  An automl-based approach to multimodal image sentiment analysis.  In International Joint Conference on Neural Networks, IJCNN 2021, Shenzhen, China, July 18-22, 2021, pages 1–9. IEEE.
  * Maiya, (2020) Maiya, A. S. (2020).  ktrain: A low-code library for augmented machine learning.  CoRR, abs/2004.10703.
  * Majumder et al., (2019) Majumder, B. P., Li, S., Ni, J., and McAuley, J. (2019).  Generating personalized recipes from historical user preferences.  In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 5976–5982, Hong Kong, China. Association for Computational Linguistics.
  * Mendoza et al., (2018) Mendoza, H., Klein, A., Feurer, M., Springenberg, J. T., Urban, M., Burkart, M., Dippel, M., Lindauer, M., and Hutter, F. (2018).  Towards automatically-tuned deep neural networks.  In Hutter, F., Kotthoff, L., and Vanschoren, J., editors, AutoML Methods, Sytems, Challenges, chapter 7, pages 141–156. Springer.
  * Ni et al., (2019) Ni, J., Li, J., and McAuley, J. (2019).  Justifying recommendations using distantly-labeled reviews and fine-grained aspects.  In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 188–197, Hong Kong, China. Association for Computational Linguistics.
  * Olson et al., (2016) Olson, R. S., Bartley, N., Urbanowicz, R. J., and Moore, J. H. (2016).  Evaluation of a tree-based pipeline optimization tool for automating data science.  In Proceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO ’16, pages 485–492, New York, NY, USA. ACM.
  * Pedregosa et al., (2011) Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011).  Scikit-learn machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830.
  * Saikia et al., (2019) Saikia, T., Marrakchi, Y., Zela, A., Hutter, F., and Brox, T. (2019).  Autodispnet: Improving disparity estimation with automl.  In 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 - November 2, 2019, pages 1812–1823. IEEE.
  * Sonboli et al., (2021) Sonboli, N., Mansoury, M., Guo, Z., Kadekodi, S., Liu, W., Liu, Z., Schwartz, A., and Burke, R. (2021).  librec-auto: A tool for recommender systems experimentation.  In Demartini, G., Zuccon, G., Culpepper, J. S., Huang, Z., and Tong, H., editors, CIKM ’21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1 - 5, 2021, pages 4584–4593. ACM.
  * Tsiakmaki et al., (2020) Tsiakmaki, M., Kostopoulos, G., Kotsiantis, S., and Ragos, O. (2020).  Implementing automl in educational data mining for prediction tasks.  Applied Sciences, 10(1):90.
  * Vanschoren et al., (2013) Vanschoren, J., van Rijn, J. N., Bischl, B., and Torgo, L. (2013).  Openml networked science in machine learning.  SIGKDD Explorations, 15(2):49–60.
  * Viswanathan et al., (2019) Viswanathan, A., Wang, V., and Kononova, A. (2019).  Controlling formality and style of machine translation output using automl.  In Lossio-Ventura, J. A., Condori-Fernández, N., and Valverde-Rebaza, J. C., editors, Information Management and Big Data - 6th International Conference, SIMBig 2019, Lima, Peru, August 21-23, 2019, Proceedings, volume 1070 of Communications in Computer and Information Science, pages 306–313. Springer.
  * Wang et al., (2021) Wang, C., Wu, Q., Weimer, M., and Zhu, E. (2021).  Flaml a fast and lightweight automl library.  In MLSys.
  * Wang et al., (2020) Wang, T., Hu, X., Jin, H., Song, Q., Han, X., and Liu, Z. (2020).  Autorec: An automated recommender system.  In Santos, R. L. T., Marinho, L. B., Daly, E. M., Chen, L., Falk, K., Koenigstein, N., and de Moura, E. S., editors, RecSys 2020: Fourteenth ACM Conference on Recommender Systems, Virtual Event, Brazil, September 22-26, 2020, pages 582–584. ACM.
  * Yang et al., (2019) Yang, C., Akimoto, Y., Kim, D. W., and Udell, M. (2019).  OBOE: collaborative filtering for automl model selection.  In Teredesai, A., Kumar, V., Li, Y., Rosales, R., Terzi, E., and Karypis, G., editors, Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 1173–1183. ACM.
  * Yang et al., (2021) Yang, J., Shi, R., and Ni, B. (2021).  Medmnist classification decathlon: A lightweight automl benchmark for medical image analysis.  In 18th IEEE International Symposium on Biomedical Imaging, ISBI 2021, Nice, France, April 13-16, 2021, pages 191–195. IEEE.
  * Yelp, (2014) Yelp (2014).  Yelp open dataset.  www.yelp.com/dataset.  Accessed 2022-02-21.
  * Zhang et al., (2019) Zhang, S., Yao, L., Sun, A., and Tay, Y. (2019).  Deep learning based recommender system: A survey and new perspectives.  ACM Comput. Surv., 52(1):5:1–5:38.
  * Zimmer et al., (2021) Zimmer, L., Lindauer, M., and Hutter, F. (2021).  Auto-pytorch tabular multi-fidelity metalearning for efficient and robust autodl.  IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 3079 – 3090.  also available under httpsarxiv.orgabs2006.13799.

##  Appendix A Versions, URLs, and Licenses of all used Libraries and Datasets

###  A.1 Libraries

Surprise, github.com/NicolasHug/Surprise, 1.1.1, BSD 3-Clause; LensKit,
lenskit.org, 0.13.1, Custom; Spotlight, github.com/maciejkula/spotlight,
0.1.6, MIT; AutoRec, github.com/datamllab/AutoRec, 0.0.2, None; Auto-Surprise,
github.com/BeelGroup/Auto-Surprise, 0.1.7, MIT; scikit-learn, scikit-
learn.org, 1.0.1, BSD 3-Clause; XGBoost, github.com/dmlc/xgboost, 1.5.1,
Apache-2.0; ktrain, github.com/amaiya/ktrain, 0.28.3, Apache-2.0; Auto-
sklearn, automl.github.io/auto-sklearn, 0.14.2, BSD 3-Clause; FLAML,
github.com/microsoft/FLAML, 0.9.1, MIT; GAMA, github.com/openml-labs/gama,
21.0.1, Apache-2.0; H2O, h2o.ai/products/h2o-automl, 3.34.0.3, Apache-2.0;
TPOT, github.com/EpistasisLab/tpot, 0.11.7, LGPL-3.0; AutoGluon,
auto.gluon.ai/stable/index.html, 0.3.1, Apache-2.0; Auto-PyTorch,
github.com/automl/Auto-PyTorch, 0.1.1, Apache-2.0;

###  A.2 Datasets

MovieLens 100k, grouplens.org/datasets/movielens/100k/, Custom; MovieLens 1M
grouplens.org/datasets/movielens/1m/, Custom; MovieLens Latest 100k (9/2018),
grouplens.org/datasets/movielens/latest/, Custom; Amazon Review Data,
nijianmo.github.io/amazon/index.html, N/A; Yelp Open Dataset,
yelp.com/dataset, Custom; Netflix Prize Dataset, www.kaggle.com/netflix-
inc/netflix-prize-data, Custom; Food.com Recipes and Interactions Dataset,
https://www.kaggle.com/shuyangli94/food-com-recipes-and-user-interactions,
Data files © Original Authors (ODC-ODbL);

##  Appendix B Used Algorithms

The following algorithms of different libraries were used:

Surprise:

SVD, KNNBasic, KNNBaseline, KNNWithZScore, KNNWithMeans, CoClustering,
BaselineOnly, SlopeOne, SVDpp, NMF, NormalPredictor

LensKit:

ItemItem, UserUser, Bias, ALSBiasedMF, FunkSVD, BiasedSVD, TFBiasedMF, BPR,
IntegratedBiasMF, HPF

Sklearn:

LinearRegression, Ridge, SGDRegressor, ElasticNet, LassoLars,
OrthogonalMatchingPursuit, ARDRegression, BayesianRidge, Lars, Lasso,
HuberRegressor, TheilSenRegressor, PoissonRegressor, GammaRegressor,
TweedieRegressor, RANSACRegressor, RandomForestRegressor, AdaBoostRegressor,
BaggingRegressor, ExtraTreesRegressor, GradientBoostingRegressor, SVR,
KNeighborsRegressor, MLPRegressor, KernelRidge, DecisionTreeRegressor

All other libraries only have one relevant implementation for regression.

##  Appendix C Preprocessing

The goal of all preprocessing steps was to to keep the data as close to the
original as possible. Only features that would cause errors were preprocessed.
All datasets were converted into CSV files. Such a CSV file shall be usable by
RecSys and ML libraries. To achieve this, several decisions on how to
transform features had to be made.

In general, we differentiate between categorical and text features. Text
features can contain any free-text input (e.g., text of a review), while
categorical features are limited to a specific range of possible categories.
For this paper, it was decided to not include any text features. In other
words, Natural Language Processing was not used to transform text features
into any type of usable tabular features. Categorical features have been One-
Hot encoded.

Based on the assumption to keep the data as close to the original as possible,
an already encoded feature was used and not reencoded. For example, if the
gender of a user was encoded through a dummy variable, it was not transformed
to one-hot encoding. This also applies to customer- and item-IDs. If the ID
was given as an integer, it was used as an integer. Only if the dataset used a
different format, like a UUID in the form of a string which would prompt
errors in ML or RecSys algorithms, the IDs were encoded as increasing
integers. Any other numeric feature is used without processing.

Similar to the previous assumption, we decided against creating new features
from existing data to stick as close to the original data as possible. To
illustrate, a feature representing URLs related to an item was removed instead
of using these URLs to potentially fetch additional information about an item.

Sometimes features were in the dataset but not in the dataset’s documentation.
In such cases, the undocumented features were removed.

Removing features, like a review’s text, can cause two reviews of an
individual customer to become identical. Moreover, some datasets have multiple
entries for the same review if a property of the review differs. For example,
in the Amazon datasets the "summary" of a review can be different and thus
result in two distinct entries. Likewise, (presumably) bugs can cause that the
timestamp of a review and the timestamp of an edited version are the same. In
the Yelp dataset, multiple duplicates exist, because all features (including
the timestamp) are identical but the text differs. We drop duplicates such
that the combination of resulting features from previous preprocessing steps
is unique.

Several algorithms can not handle ratings to be zero. For these specific
cases, we add a small $\epsilon$ to all zero-ratings such that the algorithm
is still usable.

The defined preprocessing steps were applied to all features. If features were
spread across multiple files, all files are used.

##  Appendix D Dataset Boxplot

Figure 3 shows the boxplots of the error values of the used algorithms for
each category specific to each dataset. The error values of most algorithms
are between 0.8 and 1.3. Some error values for datasets stick out. The error
values of the amazon-fashion datasets are comparatively low. The lowest values
for the amazon-fashion dataset shown in figure Dataset Boxplot are lower than
0.25. In comparison with the amazon-fashion- and other datasets, the error
values of food.com are comparatively high.

Figure 3: RMSE Boxplots for each category specific to each dataset The
distribution of error values for each category specific to each dataset is
visualized. The distribution is represented by boxplots. This excludes 61
error values that are greater than 2.

##  Appendix E Larger Plots

Figure 4: Top 5 Algorithms per Dataset For each dataset, the top 5 algorithms
are shown. They are color coded for their category. Moreover, the RMSE and
name of the algorithm are shown.

Figure 5: Order of Categories per Dataset For each dataset, the 5 categories
are shown sorted by their best performing algorithm’s RMSE. They are color
coded for their category. Moreover, the RMSE and name of the best performing
algorithm are shown.