# DiCuPIT: Distributed Cuckoo Filter-based Pending Interest Table

Arman Mahmoudi<EMAIL_ADDRESS>(A. Mahmoudi) Mahmood Ahmadi
<EMAIL_ADDRESS>(M. Ahmadi) Department of Computer Engineering and
Information Technology, Razi University, Iran.

###### Abstract

Named data networking is one of the recommended architectures for the future
of the Internet. In this communication architecture, the content name is used
instead of the IP address. To achieve this purpose, a new data structure is
added to the nodes of named data networking which is called Pending Interest
Table (PIT). Scalability, memory consumption, and integration are the
significant challenges in PIT design  as it needs to be updated for each
packet, and it saves the name of the packet. This paper introduces a new data
structure for PIT called DiCuPIT. DiCuPIT is a distributed data structure for
the PIT table,  that works based on the Cuckoo filter and can cover the three
features as above-mentioned.  By implementing this PIT,  the lookup time shows
a 36% reduction compared to the methods based on the Bloom filter and 40%
based on hash tables. Moreover, the memory consumption is reduced by 68%
compared to the hash tables-based mechanisms and 31% compared to the methods
based on the Bloom filter.

###### keywords:

Cuckoo filter, Named data networking (NDN), Bloom filter, Pending interest
table, DiCuPIT.

AND

[CorAuth]Mahmood Ahmadi.

##  1 Introduction

NDN is one of the recently proposed architectures for the future Internet that
uses the content name rather than the host address in the network. All
communications in these networks are based on two types of packets: Data and
Interest [1]. Both packets carry a name and are transmitted over the network
based on these names [1]. The consumer sends the content name to the network
into an interest packet. Then, each node forwards in reverse to the consumer
in the network that contains the data packet corresponding to the interest
packet [1]. NDN has a new table for maintaining the interest packet, which the
data packets corresponding to them  have not still arrived at the node of the
NDN network. This table is known as  the PIT [1], [2]. When the interest
packets are received, the PIT table makes an entry or updates it. In return,
upon receipt of a data packet, the node of the NDN network must find the
interest packet corresponding to it in the PIT table, and  forward the data
packet to the incoming interfaces of  the received interest packet, and
finally  remove the intended entry in  the PIT table. Thus, the PIT table is
strongly dynamic [3]. Each entry in the PIT table is stored as  follows;
(content-name, list-faces, list-nonces, expiration) [4], [5]. Searching is
done by content-name in NDN. In the NDN, the content-name is the same as the
URL address, and it does not have a constant length like IP-based networks
[1], so it is more complex and requires more memory.  On the other hand, with
the PIT implementation, as more packets of interest are stored in the PIT
table over time,  less time is spent for searching, which reduces the response
time in the network, thereby reducing response time across the network.
Therefore, using data structures should not require much memory, and it
reduces searching time and overall response time in return. The required
memory for the PIT table is $O(n^{7})$ [6], [3]. Effective implementations  on
this topic have been made in [14] which uses the hashing technique to solve
the PIT problem. Although they have achieved effective results, they have
resolved some of the PIT needs. In [3], the authors  have attempted to design
a distributed PIT table in which each interface  in the network’s node
contains a sub-table based on the Bloom filter. Despite  the good PIT results
with this method, the problem is that  the lookup should be performed on
entire sub-tables, which requires more response time. Generally, the PIT table
has not been considered in this method. For instance, when an interest packet
enters the PIT table, if exactly another packet with the same name enters from
another face, these packets will be stored in different sub-tables, and
information redundancy will happen. To cope with this problem in the PIT
table, we propose a PIT table based on the Cuckoo filter, which is called
DiCuPIT. In  the DiCuPIT designing, PIT is divided into $k$ sub-tables  where
$k$ is the number of NDN router interfaces. In fact, this data structure is a
distributed PIT which allocates a sub-table named $DiCuPIT_{i}$ to each
interface. Each one of these $DiCuPIT_{i}$s has Cuckoo filter properties.
These properties help us to be able to integrate a PIT while having a low
lookup time and less memory consumption than similar ones. Integration means
that the information of the packets of interest is stored in such a way that
other faces avoid storing the same packet in DiCuPIT to get the integration
purpose in the PIT table. In addition to $DiCuPIT_{i}$s, we have  considered
another table called GlobalCu for each sub-table to reduce lookup time named
GlobalCu. According to Cuckoo filter properties and having GlobalCu,
integration of PIT is guaranteed with this method. The results  of the
experiments show that this method can reduce memory consumption by 31 %
compared to DiPIT and by 68% compared to the hash tables-based methods, while
the lookup time is reduced compared to other methods. The novelty of this
paper is explained as follows:

  * •

Proposal of  the distributed DiCuPIT data structure based on the Cuckoo
filters.

  * •

Utilization of the DiCuPPIT data structure to improve the performance of the
PIT table of NDN networks.

  * •

Evaluation of the proposed DiCuPIT data structure in a typical NDN network.

The following sections of this paper were organized as follows: Section 2
reviews recent works on PIT table design. Section 3 presents a brief concept
of name data networking and probabilistic filters. Section 4 describes the
proposed distributed Cuckoo filter-based PIT. Section 5 presents the
evaluation results. Section 6 concludes the paper.

##  2 Related Works

This section, presents a brief review of the most significant works in PIT
tables.

In [7], PIT control management (PITCM) to mitigate PIT overflow and  improve
the PIT utilization is proposed. The PITCM utilizes a thresholding mechanism
in interest lifetime in an intelligent manner, a policy  for determining the
highest lifetime interest, and an adaptive virtualized PIT. The prediction of
PIT conditions e.g., early PIT overflow prediction and reaction, is the
responsibility of the adaptive virtual PIT block. The smart thresholding of
interest lifetime adjusts the lifetime value of received interest packets.
Management of PIT entries in an efficient way is controlled by highest
lifetime latest the request policy. The flow PIT sizing problem of the
forwarding systems in the NDN networks is addressed by this work.

In [8], to increase PIT efficiency by reducing the residence time of non-
responded the PIT entries, round trip time-aware pending interest PIT (RAPIT)
is proposed. The round tripe time-aware pending interest table (RAPIT)
presents an approach to increase the performance of PIT by decreasing the
residence time of non-responded PIT entries. The authors used a technique to
determine the residence time of PIT entries based on the estimation of the
return time of  the data packets. To measure the return time of the data
packet, they mark the initial request and the corresponding data packet, and
then store the measured time in the forwarding information base (FIB) of the
data packet for future use. In addition, they use a PIT replacement strategy
when the PIT is completely filled.

In [3], the DiPIT approach to decrease the  memory consumption of the PIT
table using  the Bloom filter is proposed. The DiPIT implements small Bloom
filters on each interface with a central Bloom filter to control false
positives generated by the existing small Bloom filter on the interfaces.

In [9], an implementation of PIT using a new filter called FTDF-PIT is
proposed. The FTDF-PIT uses a fast two-dimensional filter (FTDF) in  the PIT
implementation. The FTDF performance is better than other proposed filters
like Bloom and Quotient filters. The FTDF has higher performance in terms of
insertion/deletion/ query in comparison to the Bloom and quotient filters. It
also has lower memory consumption and a lower false positive rate when
compared to the other mentioned filters. Therefore, these properties make it
suitable for PIT in NDN networks. In [10], the PIT table of a router is
modeled using queuing theory to achieve  the optimal size. They evaluate the
optimal PIT size to trade-off the network performance and  the PIT table cost.
This model defines an objective function to minimize the PIT size subject to
the interest drop probability as upper bound. In [11], an analytical model of
two PIT replacement approaches is proposed. These approaches are called PIT
replacement without reservation (PRWR) and PIT replacement with reservation
(PRWR). The first approach utilizes the PIT replacement, while the second
approach uses the PIT entry reservation in conjunction with the first one.
Both the approaches utilize Continuous Time Markov Chain (CTMC) and improved
the efficiency in comparison to the basic NDN.

In [12], the 2DNCF-PIT to design the PIT table as a two-dimensional neighbor-
based Cuckoo filter PIT table is introduced which improves the performance of
PIT. In this work, the two-dimensional Cuckoo filter which uses the
neighborhood buckets for the overflowed items is introduced. Using of 2DNCF in
PIT design improves the performance of PIT in NDN networks.

In [13], another data structure based on the Cuckoo filter called CF-PIT is
introduced. The CF-PIT is a two-dimensional Cuckoo filter that increases the
size of the bucket in the standard Cuckoo filter using mini-buckets. The
authors of this paper have claimed that the CF-PIT improves the performance of
the Cuckoo filter. The CF-PIT has some main drawbacks as follows. The concept
of slot and mini-bucket has not fully described. The authors mentioned that
the slots number corresponds to the number of ports in the NDN-router, which
each slot contains a mini-bucket, therefore, some issues is existed in this
data structure, first, how the slot is selected, for example in a router with
16 ingress ports 16 slots need to be checked. The second issue is related to
the structure of the mini-bucket. It seems that the size of the element of
the mini-bucket must be the same as the buckets of the standard Cuckoo filter,
so the mini-buckets must be searched sequentially, these factors increase the
lookup time. In addition, due to the existence of the slots and mini-buckets
in the CF-PIT, the memory usage is higher than other proposed filters. The
third issue is that the paper did not mention the simulation parameters, for
example, the mini-bucket size, the number of slots, the type of hashing
functions, the finger print size, and the name of the dataset, therefore,
simulating the CF-PIT based on the information in paper is not possible, due
to the lack of  the mentioned parameters and finally, we could not compare our
proposed work to the CF-PIT.

Another PIT design technique has been proposed in [14] called MaPIT. MaPIT
consists of two components: Index Table, and Packet Store. Index Table also
has two data structures, a standard Bloom filter, and a mapping array.  The
Index Table is in on-chip memory, and the Packet Store is in off-chip memory.
Both the standard Bloom filter data structure and the mapping array are arrays
of bits. The mapping array has $n$ bits, and the standard Bloom filter is
divided into $n$ parts. To add an item to this data structure, the item using
the $k$ hashing function is first inserted into the Bloom filter. The number
of bits that have been changed to bit one is entered in the mapping array. The
number in the mapping array is where the item is stored in the Packet Store.
This data structure supports deletion, but has additional calculations when
searching and inserting items, and also has a high false positive rate.

In [15], dai et al. used a method called Name Component Coding (NCE). In this
method, each name component of the Interest or Data packet is encoded by an
NCE method, and then the generated code by the Encoding Name Prefix Trie
(ENPT) method is converted to a Name Prefix Trie (NPT). This method has
additional calculations, and the PIT table must also have a special
architecture.

Our proposed DiCuPIT approach utilizes the Cuckoo filters in each interface
and the global Cuckoo filter as a shared area, which achieves  a lower false
positive rate and  a higher performance in comparison to other filters.

##  3 Named Data Networking and Probabilistic Filters

In this section the concept of named data networking and probabilistic filters
e.g. Bloom filter, Cuckoo filter is presented.

###  3.1 Named data networking

In the NDN, the packets have a unique name and routing is performed based on
those packets [14].  Names in the named data networks are hierarchical, which
will be separated by “/” characters based on the components [1]. These names
are like URLs that can be used to identify packets. For example, “/razi/ac/ir”
has three components, which are razi, ac and ir. This is an example of a name
in data networks. The hierarchy of names in this architecture causes a lot of
space to be wasted on memory. There are two types of packets in these
networks: interest packets and data packets that both carry names and are
identified based on these names. Figure 1 depicts the structure of these
packets.

Figure 1: The structure of NDN network packets [6].

When a data agent wants to create an Interest packet,  puts the name of the
data in it and sends it to the network, and when the data producer receives an
Interest packet, it creates a Data packet which includes names of the data and
the required data. Puts it on the Data packet and sends it over the network.
The network routing is done based on these names.

In NDN networking, each router contains three tables; Content Store (CS),
Pending Interest Table (PIT), and Forwarding Information Base (FIB). Figure 2
depicts the architecture of an NDN router with its associated tables and its
strategy when receives an interest packet.

Figure 2: NDN router strategy when receives an interest packet [6].

In an NDN network, CS is the place of data packets that have already been
processed in this router. PIT  is supposed to maintain the interest packets
that have not yet received their response in the form of the data packet and
finally FIB, which is used to forward the interest packets [6]. The data
consumer puts the intended content-name in an interest packet and sends it on
the network. The NDN router first checks the CS. If it contains the data
packet corresponding to the received interest packet, it will be forwarded
directly to the consumer, which leads to an optimally use of network
resources. Otherwise, the router searches the PIT; if it finds a name exactly
the same as the content-name of the received interest packet in one of the
entries, the PIT table will insert the incoming interface of the received
interest packet inside the interfaces list and removes the packet. Otherwise,
it will create a new entry for the received interest packet, then sends it to
the FIB for forwarding, if the router receives the data packet. At first, it
will search the PIT table in order to find the interest packet corresponding
to the received data packet, then it forwards the data packet to its
interfaces list, and removes the desired entry [4].

Eventually, it stores the received data packet in the CS table.  The PIT table
must be able to perform the operations in a short time, support the timer, and
have an algorithm to detect exactly the same [4]. Figure 3 shows a scenario of
a named data network. This example shows three numbers of data consumers and
multiple data producers named P1, and also this scenario has a router  named
R1.

Figure 3: NDN router strategy when receives an interest packet.

In step (1), C1 has a data request named “razi/ac/ir/eng/ computer-
engineering.html”. C1 creates an Interest packet (I1) and sends the name of
requested data through the network. When packet I1 reaches router R1, the
router first checks its CS table, because it does not have packet data for I1,
so it searches the PIT table and  finds no packet similar to I1, subsequently,
it inserts the information of packet I1 into the PIT table and in step (2)
delivers the packet to the FIB table for routing.

In step (3), C2 also requests data called “razi/ac/ir/eng/ computer-
engineering.html” and sends it as an Interest packet (I2) through the network.
Router R1 first checks its CS table as soon as it receives the I2 packet
because it does not find the data corresponding to the I2 packet, so it
searches for the PIT table. Finds a packet similar to packet I2 in the PIT
table. In this case, it  simply inserts the input interface number of packet
I2 in information header of the packet I1.

In step (4) of router R1, the data packet (D1) receives “ razi/ ac / ir / eng
/ computer-engineering.html”. First, to reuse the D1 packet, the packet is
stored in CS and then searches the PIT table. Because there is an entry from
the table that has the same name as D1, the router notices that there are
Interest packets that requested D1 from this router. In this case, the router
sends the D1 packet to the list of interfaces found in the entry, which in
this scenario are interfaces 1 and 2. The entry in the PIT table is then
deleted.

In step (6) C3 sends a request called “razi / ac / ir / eng / computer-
engineering.html” in the form of the Interest packet (I3) to R1 router. In R1,
upon receiving I3, it first searches the CS table because the Data packet (D1)
corresponding to I3 is available in the CS table. In step (7), the router
immediately sends the I3 packet in the opposite direction to C3.

###  3.2 Probabilistic filters

In this subsection, the probabilistic data structures which also called
approximate membership checking data structures including  the Bloom filter
and the Cuckoo filter is introduced.

####  3.2.1 Bloom filter

colorred the Bloom filter (BF) [11] is the most popular probabilistic data
structure, used  for membership query in a set.  The Bloom filter consists of
an $m$ bits bit-array, initially all set to zero and $k$ hash functions
$\\{h_{1},h_{2},...,h_{k}\\}$, each one in range $\\{0...,m-1\\}$. In a Bloom
filter, $n$ items belong to a set $S$, where $S=\\{x_{1},x_{2},...,x_{n}\\}$.
A Bloom filter is constructed in two phases: programming and  querying. In the
programming phase, each item $x\in S$, $k$ hashing functions is calculated and
the corresponding address in bit-array is set to one. In the  querying phase,
for an item $z$, $k$ hashing functions  are calculated and the corresponding
bits in the bit-array are checked. If all the bits have the value one, then
the item exists in the bit-array with high probability, otherwise the item is
not  a member of a set $S$. The false positive colorred can exist in a Bloom
filter depending on the size of the bit-array $m$, the number of items $n$,
and the number of hashing functions $k$. The false positive probability is
calculated as: $P\textsubscript{f}$=${(1-e^{-k*(n/m)})}^{k}$. Figure 4 depicts
a simple example  for inserting three items $\\{X,\ \ Y,\ \ X\\}$ into BF, and
querying the BF for an item $W$.

Figure 4: A simple example to add three items $\\{X,\ \ Y,\ \ Z\\}$ to Bloom
filter, and querying the Bloom filter for an item $W$.

####  3.2.2  Cuckoo filter

The Cuckoo filter (CF) [16] is a fast approximate membership query data
structure in which elements can be inserted and deleted dynamically in $O(1)$
time. The Cuckoo filter supports three main operations: insert, query, and
delete. It builds on the main idea of the Cuckoo hash table, which consists of
an array of buckets in which two hash functions are used to generate the
address of two candidate buckets for an element.

To lookup an element, both buckets are examined to check if either includes
this element. To insert an element, both buckets are considered, and if any of
them is empty, then the element is inserted into that vacant bucket. If both
buckets already contain elements, the element chooses either of these buckets,
moving out the already inserted element and re-inserts this element to its
alternate position. This process an be repeated until an unoccupied bucket is
discovered, or  until reaching the upper limit of displacements. For each
element $x$, this hashing method computes the addresses of the two candidate
buckets as follows:

$\displaystyle f$ $\displaystyle=$ $\displaystyle fingerprint(x)$ (1)
$\displaystyle h_{1}(x)$ $\displaystyle=$ $\displaystyle hash(x)$ (2)
$\displaystyle h_{2}(x)$ $\displaystyle=$ $\displaystyle h_{1}(x)\oplus
hash(f)$ (3)

Utilizing xor operation in Eq. 3 will guarantee a significant feature: $h1(x)$
can also be computed from $h2(x)$ and the fingerprint by employing the same
equation.

A Cuckoo filter with 8 buckets is depicted in Figure 5. In this example, each
bucket can store one item ($k=1$).

Figure 5: (a) Inserting a at bucket (6), (b) Inserting d at bucket (5), (c)
Inserting item e at bucket(6).

Initially, two items $b$, and $c$ have been inserted in the Cuckoo filter.
The insertion of the item “a” into Cuckoo filter is depicted in Figure 5 (a).
Therefore, the calculated addresses are: $h_{1}(a)=1$, and $h_{2}(a)=6$, and
both buckets are checked, if one of them is empty then $f_{h}(a)$ is inserted
into that empty bucket. In this case, both $h_{1}(a)=1$, and $h_{2}(a)=6$
buckets are empty, then one of them is selected randomly (bucket(6)) and
$f_{h}(a)$ is inserted into it. Insertion of the item “d” into Cuckoo filter
is depicted in Figure 5 (b). Therefore, the calculated addresses are:
$h_{1}(d)=2$, and $h_{2}(d)=5$. In this case, one bucket is empty (bucket(5)),
then $f_{h}(d)$ is inserted into that empty bucket.  The insertion of the item
“e” into  the Cuckoo filter is depicted in Figure 5 (c). Therefore, the
calculated addresses are: $h_{1}(e)=2$, and $h_{2}(d)=6$. In this case, both
buckets are occupied, then it is inserted into one of that buckets (bucket 6),
kicks out the existing item (“a”), this old item is reinserted into its own
alternate location (bucket 1). The process of ejecting of existing items and
reinserting them in another locations called  relocation process.

In some cases,  relocating the old item may also require ejecting another
existing item, and this procedure may repeat until an unoccupied bucket is
found or the maximum number of relocations is reached (e.g., 150 times in our
implementation). Even with long sequence of relocation process,  the Cuckoo
filter still has $O(1)$ insertion time and high space occupancy.

To lookup  the Cuckoo filter for a given item $x$, first calculate $x$’s
fingerprint $f_{h}(x)$ and two candidate buckets $h_{1}(x)$, and $h_{2}(x)$,
and then read these two buckets. If there is fingerprint match $f_{h}(x)$ in
these two buckets then returns true. Otherwise, returns false. The Cuckoo
filter has  other useful features such as: it ensures that there is no false
negatives as long as bucket overflow never occurs, it has better lookup
performance and it supports deleting items dynamically [12].

##  4 DiCuPIT: Distributed Cuckoo Filter-based PIT

In this section, a new PIT table is proposed based on the Cuckoo filter, which
can resolve the requirements of the PIT table according to the changes made.
The Cuckoo filter is selected for this table because it has  a better lookup
time compared to other filters such as the Bloom filter, and it can reduce
response time in NDN networks. Another reason to use the Cuckoo filter is
supporting of removing, which is important in the PIT table. DiCuPIT contains
two types of sub-table; one of them for each interface that is called
$DiCuPIT_{i}$ and another that is common between all available $DiCuPIT_{i}$s
in DiCuPIT, which is called GlobalCu. Figure 6 depicts a general view of an
NDN router with eight interfaces and the proposed DiCuPIT table inside it. It
also shows the different steps  involved in the arrival of an interest packet.

Figure 6: A general view of the NDN router with eight interfaces, the proposed
DiCuPIT table and different steps of interest packet arrival.

In Figure 6,  in the first step, an interest packet enters from an interface,
in the second step, it is checked against the content store, if a match is
found the requested data packet is fetched and the NDN node responds by
sending back the data packet through the interface which the interest packet
has received. Otherwise, in the third step NDN name is added to the DiCuPIT
table and in the fourth step  the Interest packet  will be sent to the FIB
table, and in the last step it is forwarded to its destination

###  4.1  Structure of interface’s sub-tables

Each $DiCuPIT_{i}$ is a table containing $e$ buckets, and each bucket contains
$b$ entries. Each entry in $DiCuPIT_{i}$ includes the fingerprint and
expiration field and does not require storing the interface-list, since a
$DiCuPIT_{i}$ is considered for each interface in the router. Each
$DiCuPIT_{i}$ sub-table works based on the Cuckoo filter, using the name of
the incoming interest packet, the memory position of the packet in the table,
and  the fingerprint will be computed. If it is not in the table, it will be
stored in the fingerprint field and its expiration date in the expiration
field. For  the incoming data packet is also computed by the name of memory
position and  the fingerprint. If there is a similar fingerprint in calculated
position, the incoming data packet will be forwarded from the related face.
All of $DiCuPIT_{i}$s are the same and using a kind of hash function, but they
work independently. This approach helps to make a general lookup among all
$DiCuPIT_{i}$s. In this way, by doing hash on $DiCuPIT_{i}$ it is possible to
know the existence of the name of the same packet in another $DiCuPIT_{i}$.
This is done  using the GlobalSearch algorithm.

###  4.2 GlobalCu subtable structure

In DiCuPIT, a table is used for the connection between $DiCuPIT_{i}$s in PIT
which is called GlobalCu. The GlobalCU works based on the Cuckoo filter. The
GlobalCU and $DiCuPIT_{i}$ have the same size, this means that GlobalCU
includes $e$ buckets, each bucket has the $b$ entry. The only difference
between GlobalCU and $DiCuPIT_{i}$ is that the GlobalCU stores the list of
incoming interfaces. When an interest packet enters the named data network
router, the received information of the packet is stored in the corresponding
$DiCuPIT_{i}$. The problem is that an interest packet with the same content
name may have entered the router from another interface, in this case, the
information about the same interface is stored in two or more DiCuPITs, which
consumes memory in the PIT table. To address this, DiCuPIT uses a common table
between all DiCuPITs called GlobalCU. GlobalCu is the storage of interest
packets coming into the router from several different faces and is exactly the
same as the sub-table, except that it also stores the list of interfaces. The
GlobalCu sub-table in DiCuPIT supports the aggregation feature. This reduces
the search time in this table but requires more memory. The main idea of
GlobalCu is that GlobalSearch can be done on all $DiCuPIT_{i}$ using Cuckoo
filter features. This is because $DiCuPIT_{i}$ are exactly the same and use
the same hash functions, so it can be said that when searching in a
$DiCuPIT_{i}$, if the name is in the entry with the value $h$, it is existed
in all $DiCuPIT_{i}$ in the entry in the number $h$, so in total the hash
function only once, but it searches the whole $DiCuPIT_{i}$ and this is done
in parallel. This algorithm receives an interest packet as input and
calculates the fingerprint values $h1$ and $h2$, which represent the selected
locations, because all sub-tables are the same. In this algorithm, if the
desired value is found, then the value of $h1$ and the interface number are
returned, otherwise the value of -1 is returned as  absent. The GlobalSearch
pseudo-code is shown in Fig. 7.

Figure 7: GlobalSearch (packet).

###  4.3 Architecture of DiCuPIT

DiCuPIT is a distributed data structure that allocates the $DiCuPIT_{i}$ sub-
table to each entry face of router. Each of $DiCuPIT_{i}$s stores the
information related to the corresponding interface. For instance,
$DiCuPIT_{m}$ stores the information of face number $m$. Given that DiCuPIT is
distributed, so the memory consumption reduces in PIT because it is no longer
necessary to keep the list of interfaces in the PIT table. DiCuPIT is a fast
data structure with a low memory consumption that matches the PIT table
requirement. In DiCuPIT designing the cases of integration, scalability and
algorithms are considered to detect exactly the same. In original PIT, the
information related to interfaces are centralized, which can guarantee the
integration of PIT, but a table is considered for each face in DiCuPIT to
reduce the redundancy of information related to interfaces-list which result
in the reduction of memory consumption. As shown in Fig. 8, this schematic is
intended for a router with eight ports which includes 8 $DiCuPIT_{i}$sub-
tables and a sub-table named GlobalCu. In PITs containing distributed tables,
the integration feature is not supported. To solve this problem. In DiCuPIT,
another table named GlobalCu is used, which can guarantee that DiCuPIt
supports the integration feature by using this table which makes lookup faster
in PIT.

Figure 8: DiCuPIT architecture for a NDN router with eight ports and fields of
each entry.

When an interest packet enters the NDN router, the first lookup will be done
on the GlobalCu table. If the same name as  received interest packet is found
in this table, the interface information of this packet will be inserted in
the GlobalCu table and the packet will be ignored; otherwise, a GlobalSearch
is done on all $DiCuPIT_{i}$s to see whether the interest packet with the same
name has been already entered  the router from another interface. If the
answer is yes, the information related to the received interest packet will be
stored in the GlobalCu table along with the numbers of interfaces which the
packet has been entered from it. If the answer is negative, it means the
received interest packet enters this router for the first time and  the
information will be stored in dedicated $DiCuPIT_{i}$ for forwarding, the
packet is delivered to the FIB table. Fig. 9 shows the reaction of DiCuPIT
when it receives an interest packet. First, the packet name is received. The
containGlobalCu function gets the name of the packet, then searches for it in
GlobalCu. If it was in GlobalCu,  the related information to the field would
be updated, and the received packet will be removed; otherwise, the entire
$DiCuPIT_{i}$ sub-tables will be searched by the GlobalSearch technique. If
found in some value, the received interest packet will be inserted in GlobalCu
table along with the received interest and interfaces-list; otherwise, the
received interest packet will be inserted in the corresponding sub-table to
entry face. Fig. 10 shows the reaction of DiCuPIT when a data packet is
entered.

Figure 9:  Received Interest Packet (interest_packet). Figure 10: Received
Interest Packet (data_packet).

$~{}content\\_name=getContent\\_name(interest\\_packet)$

If the data packet enters the router, first, the GlobalCu table will be
examined. In this case, it means the corresponding interest packet to received
data packet has been entered  the router from several different faces and the
data packet will be sent to  the interfaces-list. The intended entry will be
removed and the data packet will be stored in  the CS table. If the intended
name is not found in GlobaCu, it is possible to find the interface which
receives the corresponding interest packet to the data packet, then it sends
the packet, and removes the intended entry and the received data packet will
be stored in CS.

Similar to the DiPIT [3], the DiCuPIT, utilizes a $DiCuPIT_{i}$ in each
interface in conjunction with a GlobalCU as a shared Cuckoo filter. In the
DiCuPIT, for all tables including all $DiCuPIT_{i}$ and GlobalCU, only  two
hashing functions are calculated. Therefore, the time complexity is $O(1)$.

The lookup time complexity of DiCuPIT is O(1). This table is exactly like the
DiCuPIT sub-tables, and once the functions $h1$ and $h2$ are calculated. By
calculating the functions $h1$ and $h2$, the desired sub-table and the desired
bucket can be accessed. For example, if the router has 8 sub-tables, the first
3 bits determines the sub-table, and the remaining bits determines the desired
bucket). With these descriptions, we can say that the search time is equal to
$O(1)$. It should be noted each interface of the NDN router includes a DiCuPIT
data structure that have been implemented in hardware and concurrently
performs  a lookup operation. In the other words, the lookup time has $O(1)$
complexity while $k$ access is performed simultaneously.

The number of accesses is $k$ access and one access for GlobalCU, therefore
the order of number of accesses is $O(k+1)$ which is showed as $O(k)$, where
$k$ is the number of interfaces of the NDN router. In DiCuPIT, all
$DiCuPIT_{i}$ and GlobalCU utilize  the same hashing functions (two hashing
functions). Therefore, the computational cost is lower than the DiPIT that
uses 5 hashing functions for each Bloom filter. In addition, the Cuckoo filter
used in the DiCuPIT make possible the removing items with lower false
positive, while the Bloom filter used in DiPIT the removing item is not
possible and has  a higher false positive rate in the same conditions as the
Cuckoo filter.  In addition, the DiPIT uses a Bloom filter which each DiPIT
utilized 5 hashing functions for each Bloom filter  which means the time
complexity is $O(5)=O(1)$. Furthermore, in an NDN router with $k$ interface
based on the DiPIT, the number of accesses is $O(5k)=O(k)$. As expected for
the analysis, the achieved results show that the DiCuPIT improves the lookup
time 36% in comparison to the DiPIT.

##  5 Evaluation

To evaluate DiCuPIT, it will be compared to three techniques named chain hash
in [14], a 32-bit hash for centralized PIT, and DiPIT in [3]. To implement
DiCuPIT, an NDN network is considered with three routers, 8 ports, four nodes,
and the incoming packet rate for each port are assumed between 10Mpcs (Mega
package per second) to 100Mpcs. It should be noted that the network topology
is useful when the routing algorithms need to be evaluated. In this case which
a table like PIT is evaluated a huge number of names is needed. Therefore, we
used a simple network topology with three routers.

The size of $DiCuPIT_{i}$ contains the numbers  from 8000 to 8000000 entries
based on the incoming bandwidth. Finally, the intended RTT is 80ms in these
experiments [17]. The used dataset for the experiment of the CNC dataset is
the one used in [18]. The specifications of the system used in this work  are:
AsusX299 Delux h1 equipped with Core i-9 7900 CPU, 64 GB DDR4 3200 g-skill
(4*16)RAM, and 1080 11GB DDR5 GPU. The Python programming language has been
used in the implementation. The bucket and fingerprint sizes have been set to
4 entries and 6 bits[16], respectively.

The Table 1 shows the simulation parameters and  the system specification
which used in this work.

Table 1: Simulation parameters. Number of routers | 3
---|---
Number of ports in each router | 16
Packet rate of each port | 10MpcS-100 Mpcs
Number of entries of DiCuPIT | 8000-8000000
Round trip time (RTT) | 80 Msec
Dataset |  CNC dataset [18]
system specification | AsusX299 delux h1
| equipped with Core i-9 7900 CPU
| 64 GB DDR4 3200 g-skill (4*16)RAM
| 1080 11GB DDR5 GPU
Programming language | Python
Bucket size |  4 entries [16]
Fingerprint size |  6 bits [16]
Expiration size | 16 bits
Hash function of chain hashing | MurMur (32 bits)
Number of hashing function in DiPIT | 5

###  5.1 Evaluation of memory consumption

To calculate the memory consumption. First, the incoming rate of different
interest packets is considered for each interface. Generally, for a
centralized PIT, the amount of required memory without considering the CS is
equivalent to $RTT*bandwidth$ based on the thumb rule [3], which RTT is round
tripe time. While the list of interfaces  is not stored in $DiCuPIT_{i}$,
however the values of 6-bit as fingerprint and 16-bit for the expiration in
$DiCuPIT_{i}$ are considered for each entry. In GlobalCu 6-bit fingerprint,
16-bit for expiration, and 8-bit for interfaces list are assumed. In doing the
experiments a 32-bit hash function and 16-bit for expiration, 8-bit for  the
interfaces list of each entry and finally another 32-bit hash for chain is
used. For HT32, a 32-bit hash with 16-bit expiration and 8-bit for interfaces
list is used as well. Also, for DiPIT, a Bloom filter with seven hash
functions for each $PIT_{i}$ is used. In the chain hash method, to make the
chain, the value of another hash is also stored, which shows the next value of
the other chain, and more memory is consumed. As shown in Fig. 11, DiCuPIT
consumes less memory.

Figure 11: Memory used by DiCuPIT and its comparison with other methods.

Table 2 depicts memory consumption of DiCuPIT in compared to DiPIT as one the
most relevant works and its improvement rate.

Table 2: Memory consumption of DiCuPIT in compared to DiPIT and its improvement rate. Packet arrival rate (Mpsec) |  DiPIT memory consumption |  DiCuPIT memory consumption |  Memory improvement rate (%)
---|---|---|---
10 |  55 |  45 |  18
20 |  98 |  56 |  42
30 |  164 |  96 |  41
40 |  210 |  145 |  30
50 |  305 |  197 |  35
60 |  372 |  256 |  31
70 |  426 |  300 |  30
80 |  510 |  380 |  25
90 |  593 |  426 |  28
100 |  689 |  495 |  28

As can be seen in Table 2, the average lookup time improvement of DiCuPIT in
comparison to DiPIT is 31%. This is because, the DiPIT utilizes five hashing
functions, therefore, it needs five accesses to the bit-array of Bloom filter
and needs another hashing function to access the packet in hash table, while
the DiCuPIT utilizes at most two hashing functions which result two accesses.

###  5.2 Lookup time

The lookup time is expected to decrease in DiCuPIT. At first,  the interest
packets are inserted in PIT tables which are implemented with different
techniques and a lookup is done on them. Fig. 12 shows that the DiCuPIT method
with the GlobalSearch technique has the least time in the chain hash
experiment, because the hash function should be applied twice on names and the
created chain contains the most lookup time. HT32bit-technique has a high
lookup time as well because it probably searches another entry for searching
elements. In DiPIT, seven hash functions are used for the elements. DiPIT has
better lookup time compared to DiCuPIT without the GlobalSearch technique, and
eventually, DiCuPIT with the GlobalSearch technique explained above, has
better time compared to other mentioned techniques.

Figure 12: Average lookup time in DicuPIT and other methods.

Table 3 depicts lookup time of DiCuPIT in compared to DiPIT as one the most
relevant works and its improvement rate.

Table 3: Lookup time of DiCuPIT in compared to DiPIT and its improvement rate. Number of names (Million) |  DIPIT |  DiCuPIT |  Improvement rate(%)
---|---|---|---
1 |  272.8614 |  194.6903 |  28
2 |  340.708 |  213.8643 |  37
3 |  395.2802 |  247.7876 |  37
4 |  473.4513 |  288.2006 |  39
5 |  538.3481 |  340.708 |  37
10 |  1165.192 |  691.7404 |  40

As can be seen in Table 3, the average lookup time improvement of DiCuPII in
comparison to DiPIT is 36%. This is because, the number of hashing functions
in DiPIT is five while the number of hashing functions in the DiCuPIT in the
worst case is two. From  the Tables 2, and table3, it can be observed that the
DiCuPIt can improve both memory consumption and  the lookup time in comparison
to the DiPIt approach. In addition, the improvement rate of lookup time of the
DiCuPIt is higher than the memory consumption rate.

###  5.3  False positive evaluation

Two types of false positive may occur in NDN networks [3]. When an interest
packet enters the router, if it finds a similar incoming packet in one face in
the table by mistake, the incoming interest packet will not be forwarded, and
the packet will be lost. This type of false positive is critical. If the data
packet enters the router, the router finds the faces at first, which the
corresponding interest packet to this data packet enters the router from them,
then forwarded the data packet to these faces. If the interest packet
corresponding to incoming data packet is found in one face by mistake, this
data packet will be sent in a fake way and the related information to the
interest packet will be removed, so when the real data packet reaches the
router, it does not find the interest packet and the incoming data packet will
not be forwarded from the face. This false positive type is not critical
because the extra propagate has no harm, just using network resources a little
more. So, only the loss of the interest packet has been investigated in
DiCuPIT. As seen in Fig. 13 for two million records, it contains less than 1%
false positive, which is acceptable for a filter. For this, PIT tables are
implemented at first with different techniques, and different names are
inserted in the table, at the end, to obtain false positives, the query is
taken from PIT tables. Since the chain hash resolves the collision in the form
of a chain contains the least false positive, DiCuPIT also has an acceptable
value of less than 0.1%.

Figure 13:  Possible false positives in DiCuPIT and other methods.

From the evaluation results, the DiCuPIT improves the false positive rate %19
in comparison to DiPIT. It should be noted that the precise theoretical
analysis for DiCUPIT is not easy, but as it can be observed, the DiPIT uses a
counting Bloom filter whose false positive result is identical to the standard
Bloom filter,  while the DiCuPIT uses a set of the Cuckoo filters which has
the lower false positive than the Bloom filter and finally the DiPIT. This
means that the false positive of the DiCuPIT is lower than the DiPiT in the
analytical aspect too.

##  6 Conclusion

In this paper, a new data structure named DiCuPIT for the PIT table was
presented in NDN networks which could reduce lookup time and memory
consumption. In addition, the false positive value is acceptable in this data
structure for the named data network. In DiCuPIT, the distributed tables are
used for each face, and another sub-table called GlobalCu is used to guarantee
the integration. These sub-tables and  the GlobalCu sub-table are the same.
The risk in DiCuPIT is due to the relation of the GlobalCu sub-table with
other sub-tables, which may be filled in before the other sub-tables. This
risk can be overcome if the size of the sub-tables be assumed large enough. On
the other hand, the sub-tables can be scaled and set to a larger size,
gradually, for the possible overflow of the GlobalCu sub-table.

## References

  * Zhang et al. [2014] Lixia Zhang, Alexander Afanasyev, Jeffrey Burke, Van Jacobson, kc claffy, Patrick Crowley, Christos Papadopoulos, Lan Wang, and Beichuan Zhang.  Named data networking.  _SIGCOMM Comput. Commun. Rev._ , 44(3):66–73, July 2014.
  * Li et al. [2014] Zhuo Li, Kaihua Liu, Yang Zhao, and Yongtao Ma.  Mapit: An enhanced pending interest table for ndn with mapping bloom filter.  _IEEE Communications Letters_ , 18(11):1915–1918, 2014.
  * You et al. [2012] Wei You, Bertrand Mathieu, Patrick Truong, Jean-Francois Peltier, and Gwendal Simon.  Dipit: A distributed bloom-filter based pit table for ccn nodes.  In _2012 21st International Conference on Computer Communications and Networks (ICCCN)_ , pages 1–7, 2012.
  * Varvello et al. [2013] Matteo Varvello, Diego Perino, and Leonardo Linguaglossa.  On the design and implementation of a wire-speed pending interest table.  In _2013 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , pages 369–374, April 2013.  10.1109/INFCOMW.2013.6970719.
  * Ahlgren et al. [2012] Bengt Ahlgren, Christian Dannewitz, Claudio Imbrenda, Dirk Kutscher, and Borje Ohlman.  A survey of information-centric networking.  _IEEE Communications Magazine_ , 50(7):26–36, 2012.
  * So et al. [2013] Won So, Ashok Narayanan, and David Oran.  Named data networking on a router: Fast and dos-resistant forwarding with hash tables.  In _Architectures for Networking and Communications Systems_ , pages 215–225, 2013.
  * Alubady et al. [2018] Raaid Alubady, Suhaidi Hassan, and Adib Habbal.  Pending interest table control management in named data network.  _Journal of Network and Computer Applications_ , 111:99–116, 2018.
  * Tan et al. [2015] Yalei Tan, Qing Li, Yong Jiang, and Shutao Xia.  Rapit: Rtt-aware pending interest table for content centric networking.  In _2015 IEEE 34th International Performance Computing and Communications Conference (IPCCC)_ , pages 1–8, 2015.
  * Shubbar and Ahmadi [2019] Roaa Shubbar and Mahmood Ahmadi.  A filter-based design of pending interest table in named data networking.  _J. Netw. Syst. Manag._ , 27(4):998–1019, 2019\.
  * Sivaraman et al. [2020] Vignesh Sivaraman, Dibyajyoti Guha, and Biplab Sikdar.  Optimal pending interest table size for icn with mobile producers.  _IEEE/ACM Transactions on Networking_ , 28(4):1615–1628, 2020.
  * Buragohain and Nandi [2020] Madhurima Buragohain and Sukumar Nandi.  Quality of service provisioning in named data networking via pit entry reservation and pit replacement policy.  _Computer Communications_ , 155:166–183, 2020.
  * Gupta and Breitinger [2015] Vikas Gupta and Frank Breitinger.  How cuckoo filter can improve existing approximate matching techniques.  In Joshua I. James and Frank Breitinger, editors, _Digital Forensics and Cyber Crime - 7th International Conference, ICDF2C 2015, Seoul, South Korea, October 6-8, 2015, Revised Selected Papers_ , volume 157 of _Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering_ , pages 39–52. Springer, 2015\.
  * Alhisnawi [2021] Aladdin Alhisnawi, Mohammad; Abdulhassan.  Designing cuckoo based pending interest table for ccn networks.  _International Journal of Interactive Mobile Technologies_ , 15(7):140–153, 2021.
  * Yuan and Crowley [2014] Haowei Yuan and Patrick Crowley.  Scalable pending interest table design: From principles to practice.  In _IEEE INFOCOM 2014 - IEEE Conference on Computer Communications_ , pages 2049–2057, 2014.
  * Dai et al. [2012] Huichen Dai, Bin Liu, Yan Chen, and Yi Wang.  On pending interest table in named data networking.  In _2012 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS)_ , pages 211–222, 2012.
  * Fan et al. [2014] Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher.  Cuckoo filter: Practically better than bloom.  CoNEXT ’14, page 75–88, 2014.
  * Carofiglio et al. [2015] Giovanna Carofiglio, Massimo Gallo, Luca Muscariello, and Diego Perino.  Pending interest table sizing in named data networking.  In _Proceedings of the 2nd ACM Conference on Information-Centric Networking_ , ACM-ICN ’15, page 49–58. Association for Computing Machinery, 2015\.
  * Group [2014] NDN Group.  Ndn name data, October 2014.  URL http://www.icn-names.net/.
  * Yuan et al. [2017] Haowei Yuan, Patrick Crowley, and Tian Song.  Enhancing scalable name-based forwarding.  In _Proceedings of the Symposium on Architectures for Networking and Communications Systems_ , ANCS ’17, page 60–69. IEEE Press, 2017.  ISBN 9781509063864.


# Pareto Optimal Proxy Metrics

Lee Richardson111Corresponding author. Email<EMAIL_ADDRESS>Google Inc.,
San Bruno, CA, USA  Alessandro Zito  Google Inc., San Bruno, CA, USA
Department of Statistical Science, Duke University, Durham, NC, USA  Jacopo
Soriano  Google Inc., San Bruno, CA, USA  Dylan Greaves  Google Inc., San
Bruno, CA, USA

###### Abstract

North star metrics and online experimentation play a central role in how
technology companies improve their products. In many practical settings,
however, evaluating experiments based on the north star metric directly can be
difficult. The two most significant issues are 1) low sensitivity of the north
star metric and 2) differences between the short-term and long-term impact on
the north star metric. A common solution is to rely on proxy metrics rather
than the north star in experiment evaluation and launch decisions. Existing
literature on proxy metrics concentrates mainly on the estimation of the long-
term impact from short-term experimental data. In this paper, instead, we
focus on the trade-off between the estimation of the long-term impact and the
sensitivity in the short term. In particular, we propose the Pareto optimal
proxy metrics method, which simultaneously optimizes prediction accuracy and
sensitivity. In addition, we give an efficient multi-objective optimization
algorithm that outperforms standard methods. We applied our methodology to
experiments from a large industrial recommendation system, and found proxy
metrics that are eight times more sensitive than the north star and
consistently moved in the same direction, increasing the velocity and the
quality of the decisions to launch new features.

##  1 Introduction

North star metrics are central to the operations of technology companies like
Airbnb, Uber, and Google, amongst many others [4]. Functionally, teams use
north star metrics to align priorities, evaluate progress, and determine if
features should be launched [18].

Although north star metrics are valuable, there are issues using north star
metrics in experimentation. To understand the issues better, it is important
to know how experimentation works at large tech companies. A standard flow is
the following: a team of engineers, data scientists and product managers have
an idea to improve the product; the idea is implemented, and an experiment on
a small amount of traffic is run for 1-2 weeks. If the metrics are promising,
the team takes the experiment to a launch review, which determines if the
feature will be launched to all users. The timescale of this process is
crucial – the faster one can run and evaluate experiments, the more ideas one
can evaluate and integrate into the product. Two main issues arise in this
context. The first is that the north star metric is often not sufficiently
sensitive [6]. This means that the team will have experiment results that do
not provide a clear indication of whether the idea is improving the north star
metric. The second issue is that the north star metric can be different in the
short and long term [14] due to novelty effects, system learning, and user
learning, amongst other factors.

A solution to deal with this problem is to use a _proxy metric_ , also
referred to as a _surrogate metric_ , in place of the north star [8]. The
ideal proxy metric is short-term sensitive, and an accurate predictor of the
long-term impact of the north star metric. Figure 1 visualizes the ideal proxy
metric in two scenarios where it helps teams overcome the limitations of the
north star metric.

Figure 1: A simulated example of two cases where a proxy metric is useful. The
left figure shows the case where the north star metric is positive, but is too
small relative to the noise to measure accurately. The right figure shows the
case where the north star metric is significantly different in the short and
long term, and the proxy metric reflects the long-term impact early in the
experiment.

Existing literature on proxy metrics [9, 1] has focused more on predicting the
long-term effect, but has not focused on its trade-off with short-term
sensitivity. In this paper, we fulfill both goals with a method that optimizes
both objectives simultaneously, called Pareto optimal proxy metrics. To our
knowledge, this is the first method that explicitly optimizes sensitivity.

The paper is divided as follows. Section 2 discusses how to measure the
objectives and their empirical trade-off. Section 3 covers our methodology and
algorithms. Section 4 discusses our results, and we conclude in Section 5 with
some observations on how to use proxy metrics effectively.

##  2 How to measure proxy metric performance

The two key properties for metrics are _metric sensitivity_ and
_directionality_ [6]. The first refers to the ability of a metric to detect a
statistically significant effect, while the second measures the level of
agreement between the metric and the long-term effect of the north star. This
Section discusses each property individually, and proposes metrics to quantify
them. We conclude with our empirical observation regarding the trade-off
between sensitivity and directionality, which motivated the methodology in
this paper (see Figure 2).

###  2.1 Metric sensitivity

Metric sensitivity is commonly associated with statistical power. However, it
can be expressed as a broader concept [17]. In simple terms, metric
sensitivity measures the ability to detect a significant effect for a metric.
Following [5], we can write this as

$P(\text{Reject $H_{0}$})=\int P(\text{Reject
$H_{0}$}|\delta)\mathrm{d}P(\delta),$ (1)

where $\delta$ is the true treatment effect, $P(\text{Reject }H_{0}|\delta)$
is the statistical power, and $\mathrm{d}P(\delta)$ is the distribution of
true treatment effects in a population of related experiments. Sensitivity
depends heavily on the type of experiments. This is captured in the
$\mathrm{d}P(\delta)$ term in Equation 1, and is sometimes referred to as the
_moveability_ of the metric. For example, metrics related to Search quality
will be more sensitive in Search experiments, and less sensitive in
experiments from other product areas (notifications, home feed
recommendations, etc.). Although each experiment is unique, our analysis
groups together experiments with similar treatments, and we assume that the
underlying treatment effects are independent and identically distributed draws
from a common distribution of treatment effects.

We need to define quantities that summarize how sensitive a metric is. Our
intuition is that we can estimate the probability a metric will detect a
statistically significant effect by seeing how often such an effect was
statistically significant in historical experiments. Suppose that there are
$J$ experiments whose outcome is recorded by $M$ metrics. In each experiment,
the population is randomly partitioned into $N\approx 100$ equal groups, and
within each group, users are independently assigned to a treatment and a
control group. We refer to these groups as _independent hash buckets_ [3].

Let $X_{i,j,m}^{Tr}$ and $X_{i,j,m}^{Ct}$ with $m=1,\ldots,M$ and
$j=1,\ldots,J$ denote the short-term recorded values for metric $m$ in
experiment $j$ in the treatment and in the control group, respectively, and
let $X_{i,j,m}=100\%\times(X_{i,j,m}^{Tr}-X_{i,j,m}^{Ct})/X_{i,j,m}^{Ct}$
their percentage differences, in hash bucket $i=1,\ldots,N$. We refer to these
metrics as _auxiliary metrics_ , since their combination will be used to
construct a proxy metric in Section 3. The within hash bucket sample sizes are
typically large enough that we can use the central limit theorem to assume
that
$X_{i,j,m}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}N(\theta_{j,m},\sigma^{2}_{j,m})$
for $i=1,\ldots,N$, where $\theta_{j,m}$ and $\sigma^{2}_{j,m}$ are unknown
mean and variance parameters, and test

$H_{0,j,m}:\theta_{j,m}=0\quad\text{vs}\quad H_{1,j,m}:\theta_{j,m}\neq 0.$

Calling $\bar{X}_{j,m}=N^{-1}\sum_{i=1}^{N}X_{i,j,m}$ the mean percentage
difference between the two groups and $se_{j,m}$ the standard error,
calculated at Google via the Jackknife method [3], the null hypothesis
$H_{0,j,m}$ is rejected at the $\alpha$ level if the test statistics
$t_{j,m}=\bar{X}_{j,m}/se_{j,m}$ is larger than a threshold
$\tau_{\alpha,N-1}$ in absolute value. The common practice is to let
$\alpha=0.05$.

From the above, it naturally follows that metric sensitivity should be
directly related to the value of the test statistic $t_{j,m}$. For instance,
we call binary sensitivity for metric $m$ the quantity

$\texttt{BS}(\bar{X}_{\cdot,m})=\frac{1}{J}\sum_{j=1}^{J}\mathds{1}(|t_{j,m}|>\tau_{\alpha,N-1}),\quad(m=1,\ldots,M),$
(2)

where $\bar{X}_{\cdot,m}=\\{\bar{X}_{1,m},\ldots,\bar{X}_{J,m}\\}$. Equation
(2) measures the proportion of statistically significant experiments in our
pool of experiments for every metric $m$. Another characteristic of equation
(2) is that it takes on a discrete set of values. This is an issue when the
number of experiments $J$ is low. In this case, one can resort to smoother
versions of binary sensitivity, such as the _average sensitivity_ , defined as

$\texttt{AS}(\bar{X}_{\cdot,m})=\frac{1}{J}\sum_{j=1}^{J}|t_{j,m}|,\quad(m=1,\ldots,M).$
(3)

The above quantity is the average absolute value of the test statistic across
experiments. It has the advantage of being continuous and thus easier to
optimize, but it pays a cost in terms of lack of interpretability and is also
more susceptible to outliers. In the case of large outliers, one effective
strategy is to cap the value of the t-statistic.

Which measure of sensitivity to use depends on the application. When a large
pool of experiments is available, we recommend using equation (2) due to its
interpretation and intrinsic simplicity. Equation (3) should be invoked when
optimizing over a discrete quantity yields unstable results.

###  2.2 Directionality

The second key metric property we need to quantify is called _directionality_.
Through directionality, we want to capture the alignment between the increase
(decrease) in the metric and long-term improvement (deterioration) of the user
experience. While this is ideal, getting ground truth data for directionality
can be complex. A few existing approaches either involve running degradation
experiments or manually labeling experiments, as discussed in [6, 7]. Both
approaches are reasonable, but suffer from scalability issues.

Our method measures directionality by comparing the short-term value of a
metric against the long-term value of the north star. The advantage of this
approach is that we can compute the measure in every experiment. The
disadvantage is that the estimate of the treatment effect of the north star
metric is noisy, which makes it harder to separate the correlation in noise
from the correlation in the treatment effects. This can be handled, however,
by measuring correlation across repeated experiments.

There are various ways to quantify the directionality of a metric. In this
paper, we consider two measures: the first is the _mean squared error_ , while
the second is the _empirical correlation_. Following the setting of Section
2.1, let $Y_{i,j}^{Tr}$ and $Y_{i,j}^{Ct}$ define the long-term value of the
north star in the treatment and in the control group for every cookie bucket
$i$ and experiment $j$. The resulting recorded percentage difference is
$Y_{i,j}=100\%(Y_{i,j}^{Tr}-Y_{i,j}^{Ct})/Y_{i,j}^{Ct}$. Then we can define
the mean squared error as

$\texttt{MSE}(\bar{X}_{\cdot,m})=\frac{1}{J}\sum_{j=1}^{J}(\bar{Y}_{j}-\bar{X}_{j,m})^{2},\quad(m=1,\ldots,M),$
(4)

where again $\bar{Y}_{j}=N^{-1}\sum_{i=1}^{N}Y_{i,j}$ is the long-term mean of
the north star in experiment $j$. Equation (4) measures how well metric $m$
predicts the long-term north star on average. Such a measure depends on the
scale of $X$ and $Y$ and may require standardization of the metrics. For a
scale-free measure, one instead may adopt correlation, which is defined as
follows

$\texttt{Cor}(\bar{X}_{\cdot,m})=\frac{\sum_{j=1}^{J}(\bar{Y}_{j}-\bar{Y})(\bar{X}_{j,m}-\bar{X})}{\sqrt{\sum_{j=1}^{J}(\bar{Y}_{j}-\bar{Y_{m}})^{2}\sum_{j=1}^{J}(\bar{X}_{j,m}-\bar{X}_{m})^{2}}},\quad(m=1,\ldots,M),$
(5)

where $\bar{X}_{m}=J^{-1}\sum_{j=1}^{J}\bar{X}_{j,m}$ and
$\bar{Y}=J^{-1}\sum_{j=1}^{J}\bar{Y}_{j}$ are the grand mean of metric $m$ and
the north star across all experiments.

Equations (4) and (5) quantify the agreeableness between a metric $m$ and the
north star, and their use is entirely dependent on the application. Notice
that equation (5) measures the linear relationship, but other measures of
correlation may be employed, such as Spearman correlation. It is possible to
use different measures of correlation because our methodology is agnostic to
specific measures of sensitivity and directionality, as detailed in Section 3.

###  2.3 The trade-off between sensitivity and directionality

So far, we have established two key properties for a metric: sensitivity and
directionality. Empirically, we observe an inverse relationship between these
two properties. This can be clearly seen from Figure 2, where we plot the
value of the binary sensitivity in equation (2) and the correlation with the
north star in equation (5) for over 300 experiments on a large industrial
recommendation system.

Figure 2: The relationship between correlation and sensitivity for 70
auxiliary metrics across over 300 experiments. Each metric is either a gray or
black dot. We highlight several auxiliary metrics that trade-off between
sensitivity and correlation in black. Notably, the short-term value of the
north star is in the bottom right, which is the least sensitive metric, but
the most correlated with the long-term impact of the north star.

As such, there is a trade-off between sensitivity and directionality: the more
we increase sensitivity, the less likely our metric will be related to the
north star. Thus, our methodology aims to combine auxiliary metrics into a
single proxy metric to balance such trade-off in an optimal manner.

##  3 Pareto optimal proxy metrics

Our core idea is to use multi-objective optimization to learn the optimal
trade-off between sensitivity and directionality. Our algorithm learns a set
of proxy metrics with the optimal trade-off, known as the Pareto front. The
proxy metrics in the Pareto front are linear combinations of auxiliary
metrics. Each proxy in the Pareto front is Pareto optimal, in that we can not
increase sensitivity without decreasing correlation, and vice versa.

In this section, we first describe the proxy metric problem, and we later cast
the proxy metric problem into the Pareto optimal framework. Then we discuss
algorithms to learn the Pareto front and compare their performance.

###  3.1 The proxy metric problem

We define a proxy metric as a _linear combination_ between the auxiliary
metrics $m=1,\ldots,M$. Let
$\boldsymbol{\omega}=(\omega_{1},\ldots,\omega_{M})$ be a vector of weights. A
proxy metric is obtained as

$Z_{i,j}(\boldsymbol{\omega})=\sum_{m=1}^{M}\omega_{m}X_{i,j,m},$ (6)

for each $i=1,\ldots,N$ and each experiment $j=1,\ldots,J$. Here, $\omega_{m}$
defines the weight that metric $m$ has on the proxy $Z_{i,j}$. For
interpretability reasons, it is useful to consider a normalized version of the
weights, namely imposing that $\sum_{m=1}^{M}\omega_{m}=1$ with each
$\omega_{m}\geq 0$. In doing so, we require that a positive outcome is
associated with an increase in the auxiliary metrics. This means we must swap
the sign of metrics whose decrease has a positive impact. These include, for
example, metrics that represent bad user experiences, like abandoning the page
or refining a query, and which are negatively correlated with the north star
metric. Within such a formulation, the proxy metric becomes a weighted average
across single metrics where $\omega_{m}$ measures the importance of metric
$m$. Un-normalized versions of the proxy weights can also be considered,
depending on the context and the measures over which the optimization is
carried over. In general, the binary sensitivity in equation (2) and the
correlation in equation (5) are invariant to the scale of $\omega_{m}$, which
implies that they remain equal irrespective of whether the weights are
normalized or not.

Within such a framework, our goal is to find the weights in equation (6). Let
$\bar{Z}_{j}(\boldsymbol{\omega})=J^{-1}\sum_{i=N}^{J}Z_{i,j}$ be the average
values for the proxy metric in experiments $j=1,\ldots,J$ and
$\bar{Z}_{\cdot}(\boldsymbol{\omega})=\\{\bar{Z}_{1}(\boldsymbol{\omega}),\ldots,\bar{Z}_{J}(\boldsymbol{\omega})\\}$
their collection. When binary sensitivity and correlation are used as measures
for sensitivity and directionality, multi-objective optimization is performed
via the following problem

$\boldsymbol{\omega}^{*}={\arg\max}_{\boldsymbol{\omega}=(\omega_{1},\ldots,\omega_{m})}\\{\texttt{BS}(\bar{Z}_{\cdot}(\boldsymbol{\omega})),\texttt{Cor}(\bar{Z}_{\cdot}(\boldsymbol{\omega}))\\}.$
(7)

The solution to the optimization in equation (7) is not available in an
explicit analytical form, which means that we need to resort to multi-
objective optimization algorithms to find $\boldsymbol{\omega}^{*}$. We
discuss these algorithms after first introducing the concept of Pareto
optimality.

###  3.2 Pareto optimality for proxy metrics

A Pareto equilibrium is a situation where any action taken by an individual
toward optimizing one outcome will automatically lead to a loss in other
outcomes. In this situation, there is no way to improve both outcomes
simultaneously. If there was, then the current state is said to be _Pareto
dominated_. In the context of our application, the natural trade-off between
correlation and sensitivity implies that we cannot unilaterally maximize one
dimension without incurring in a loss in the other. Thus, our goal is to look
for weights that are not dominated in any dimension. In reference with
equation (7), we say that the set of weights $\boldsymbol{\omega}$ is Pareto
dominated if there exists another set of weight $\boldsymbol{\omega}^{\prime}$
such that
$\texttt{BS}(\bar{Z}_{\cdot}(\boldsymbol{\omega}^{\prime}))\geq\texttt{BS}(\bar{Z}_{\cdot}(\boldsymbol{\omega}))$
and
$\texttt{Cor}(\bar{Z}_{\cdot}(\boldsymbol{\omega}^{\prime}))\geq\texttt{Cor}(\bar{Z}_{\cdot}(\boldsymbol{\omega}))$
at the same time. We write
$\boldsymbol{\omega}\prec\boldsymbol{\omega}^{\prime}$ to indicate the
dominance relationship. Then, the set of non-dominated points is called
_Pareto set_. We indicate it as
$\mathcal{W}=\\{\boldsymbol{\omega}_{1},\ldots,\boldsymbol{\omega}_{q}\\}$,
where for all $\boldsymbol{\omega},\boldsymbol{\omega}^{\prime}\in\mathcal{W}$
neither $\boldsymbol{\omega}\prec\boldsymbol{\omega}^{\prime}$ not
$\boldsymbol{\omega}^{\prime}\prec\boldsymbol{\omega}$. The objective values
associated with the Pareto set are called the _Pareto front_.

Figure 3: An example of the Pareto front in the proxy metric problem. Each
gray dot represents evaluations of the objective in a randomized search. The
red dots are points on the Pareto front. The green dot is a point that is
Pareto dominated, and the gray shaded area shows where the green dot is Pareto
dominated.

Figure 3 shows an example of what the Pareto front and the Pareto set look
like. The grey points represent the value of the objectives for a set of
weights generated at random, while the red points are the ones in the Pareto
set. The green dot is an example point that is Pareto dominated by the area
highlighted in grey. It is easy to see that any point in the grey area is
strictly better than the green dot. The purpose of multi-objective
optimization is to efficiently identify the Pareto front and the weights in
the Pareto set. Algorithms to estimate the Pareto front are reported in the
next Section.

###  3.3 Algorithms for Pareto optimal proxies

Multi-objective optimization is a well-studied problem that can be solved via
a wealth of efficient algorithms. Common methods to extract the Pareto front
combine Kriging techniques with expected improvement minimization [11, 20], or
black box methods via transfer learning [19, 13]. These methods are
particularly suitable for cases where the objective functions are
intrinsically expensive to calculate, and therefore one wishes to limit the
number of evaluations required to extract the front. In our case, however,
both objective functions can be calculated with minimal computational effort.
As such, we propose two algorithms to efficiently extract the front that rely
on sampling strategies and nonlinear optimization routines. We then compare
our algorithms against a standard Kriging-based implementation.

Our first method to extract the Pareto front involves a simple randomized
search, as described in Algorithm 1 below. The mechanism is relatively
straightforward: at each step, we propose a candidate weight
$\boldsymbol{\omega}$ and calculate the associated proxy $Z_{i,j}$ for every
$i=1,\ldots,N$ and every experiment $j=1,\ldots,J$. Then, we evaluate the
desired objective functions, such as the binary sensitivity and the
correlation in equations (2) and (5). These allow us to tell whether
$\boldsymbol{\omega}$ is dominated. In the second case, we update the Pareto
front by removing the Pareto dominated weights and then by including the new
one in the Pareto set.

Algorithm 1 Randomized search

1:Input: Number of samples $T$, single metrics $X$, north start $Y$

2:Output: Pareto set $\mathcal{W}$

3:Initialize the Pareto set to be empty: $\mathcal{W}=\emptyset$.

4:for $t=1\ldots,T$ do

5: Sample $\boldsymbol{\omega}=\\{\omega_{1},\ldots,\omega_{M}\\}$ uniformly
in $[0,1]$.

6: Calculate $Z_{i,j}(\boldsymbol{\omega})$ as in equation (6).

7: Evaluate $\texttt{BS}(\bar{Z}_{\cdot}(\boldsymbol{\omega}))$ and
$\texttt{Cor}(\bar{Z}_{\cdot}(\boldsymbol{\omega}))$ (or any other objective
function).

8: If $\boldsymbol{\omega}$ is not dominated by any other
$\boldsymbol{\omega}^{\prime}\in\mathcal{W}$, add $\boldsymbol{\omega}$ to
$\mathcal{W}$.

9: Remove the weights in $\mathcal{W}$ that are dominated.

10:end for

The advantage of Algorithm 1 is that it explores the whole space of possible
weights and can be performed online with minimum storage requirements.
However, such exploration is often inefficient, since the vast majority of
sampled weights are not on the Pareto front. Moreover, the method may suffer
from a curse of dimensionality: if the total number of auxiliary metrics $M$
is large, then a massive number of candidate weights is required to explore
the hypercube $[0,1]^{M}$ exhaustively. A standard solution to such a problem
relies on a more directed exploration of the space of weights via Kriging,
where the weight at one iteration is sampled from normal distributions whose
mean and variance are obtained by minimizing an in-fill criterion [11]. Refer
to [2] for a practical overview. Since evaluating sensitivity and correlation
is a relatively simple operation, we propose a more directed algorithm, which
we now illustrate.

Consider the bivariate optimization problem in equation (7). If we fix one
dimension, say sensitivity, to a certain threshold and later optimize with
respect to the other dimension in a _constrained_ manner, then varying the
threshold between 0 and 1 should equivalently extract the front. In practice,
this procedure is approximated by _binning_ the sensitivity in disjoint
intervals, say $[u_{b},u_{b+1})$ with $b=1,\ldots,B-1$, with $u_{1}=0$ and
$u_{B}=1$, and then solving

$\begin{split}\boldsymbol{\omega}^{*}_{b}={\arg\max}_{\boldsymbol{\omega}:\
\texttt{BS}(\bar{Z}_{\cdot}(\boldsymbol{\omega}))\in[u_{b},u_{b+1})}\
\texttt{Cor}(\bar{Z}_{\cdot}(\boldsymbol{\omega})),\end{split}$ (8)

for each $b=1,\ldots,B-1$. The resulting Pareto front is composed of a length
$B$ set of weights. We summarize this in Algorithm 2 below.

Algorithm 2 Constrained optimization via binning

1:Input: Number of samples $T$, single metrics $X$, north start $Y$,
sensitivity bins $[u_{b},u_{b+1})$

2:Output: Pareto set $\mathcal{W}$ (approximation)

3:Initialize the Pareto set to be empty: $\mathcal{W}=\emptyset$.

4:for $b=1\ldots,B-1$ do

5: Solve the constrained optimization in equation (8) via nlopt.

6: Add $\boldsymbol{\omega}_{b}$ to $\mathcal{W}$

7:end for

The optimization problem in equation (7) and Algorithm 2 can be solved via
common nonlinear optimization methods such as the ones in the nlopt package.
See [15] and references therein.

Each algorithm produces a set of Pareto optimal proxy metrics. However, we
typically rely on a single proxy metric for experiment evaluation and launch
decisions. This means we need to select a proxy from the Pareto front. In
practice, we use the Pareto set to reduce the space of candidate proxies, and
later choose the final weights based on statistical properties and other
product considerations.

###  3.4 Algorithm performance

This Section evaluates the performance of our proposed algorithms. The task is
extracting the Pareto front between binary sensitivity and correlation from a
set of over 300 experiments. Details on the data are described in Section 4.
We test three different algorithms:

  1. 1.

Randomized search (Algorithm 1). We let the algorithm run for $M\times 4000$
iterations.

  2. 2.

Constrained optimization via binning (Algorithm 2). We split sensitivity into
14 discrete bins, ranging from $0$ to the maximum sensitivity of a single
metric in our data set. From the nlopt package, we rely on the locally biased
dividing rectangles algorithm [12].

  3. 3.

Kriging and minimization of the expected increase in hyper-volume [11], using
the R package GPareto [2]. We let the algorithm run for $M\times 40$
iterations.

We estimate the Pareto front for $M=5,10,\text{ and }15$ metrics to understand
how algorithm performance scales in the number of metrics. Figure 4 compares
the Pareto front extracted by each algorithm. Each algorithm yields a similar
Pareto front. We notice that constrained optimization detects points in high
sensitivity and high correlation regions better than the other two methods,
especially as the number of metrics increases. However, the middle of these
extracted curves are very similar.

Figure 4: Pareto front extracted under the three methods.

A more direct comparison is reported in Figure 5. Here, we quantify the
extracted Pareto Front using the _Area under the Pareto Front_ metric (larger
values are better). We also compare the run-time of each algorithm. The clear
takeaway from Figure 5 is that the choice of algorithms does not matter much
for a small number of metrics (5). However, constrained optimization is the
best trade-off between accuracy and speed when the number of metrics is large.

Figure 5: The left plot shows the Area under the Pareto curve for each
algorithm, the right plot shows how long each algorithm took to extract the
Pareto front in Figure 4

##  4 Results

We implemented our methodology on over 300 experiments in a large industrial
recommendation system. We then evaluated the performance of the resulting
proxy on over 500 related experiments that ran throughout the subsequent six
months. Specifically, we compare the proxy with the short-term north star
metric, since its precise goal is to improve upon the sensitivity of the
short-term north star itself. As success criteria, we use Binary Sensitivity
in equation (2) and the _proxy score_ , which is a one-number statistic that
evaluates proxy quality. See Appendix A for a detailed definition.

Table 1 compares our short-term proxy metric against the short-term north star
metric. Our proxy metric was 8.5 times more sensitive. In the cases where the
long-term north star metric was statistically significant, the proxy was
statistically significant 72% of the time, compared to just 40% of the time
for the short-term north star. In this set of experiments, we did not observe
any case where the proxy metric was statistically significant in the opposite
direction as the long-term north star metric. We have, however, seen this
occur in different analyses. But the occurrence is rare and happens in less
than 1% of experiments. Finally, our proxy metric has a 50% higher proxy score
than the short-term north star. Our key takeaway is that we can find proxy
metrics that are dramatically more sensitive while barely sacrificing
directionality.

Table 1: Comparison of using the short-term north star metric and the Pareto optimal proxy metric. This table was constructed on a set of experiments that ran for six months after we implemented our proxy. The sensitivity of our proxy is 8.5X%, compared to just X% for the north star. | short term north star | proxy
---|---|---
Proxy Score | 0.41 | 0.72
Binary Sensitivity | X% | 8.5X%
Recall | 0.41 | 0.72
Precision | 1.0 | 1.0

Table 1 only evaluates the relationship between the proxy and north star
metric when the north star is statistically significant. These experiments are
useful because we have a clear direction from the north star metric. However,
it is also important to assess the proxy metric when the long-term north star
metric is neutral. For this, we can look at the magnitude of the north star
metric when the long-term effect is not statistically significant, split by
whether the proxy is negative, neutral, or positive. We display this in Figure
6, which shows that, although we may not get statistically significant results
for the north star metric, making decisions based on the proxy will be
positive for the north star on average. In practice, we are careful when
rolling out these cases, and have tools to catch any launch that does not
behave as expected.

Figure 6: The magnitude of the long-term north star treatment effect, when the
long-term treatment effect is neutral, depending on if the proxy metric is
negative, neutral, or positive.

Finally, it is instructive to analyze how the weights of the proxy metrics
vary as we move along the Pareto front from directionality to sensitivity, as
illustrated in the example in Figure 7. As expected, when we select points
that emphasize correlation, our proxy metric puts more weight on the short-
term north star. But when we choose points that emphasize sensitivity, we put
much more weight on sensitive, local metrics.

Figure 7: Weights of the proxy metrics in the Pareto set as a function of both
objectives. We include three metrics, the short-term north star and two
metrics that are more sensitive, capturing different elements of the user
experience. The optimal weights are highlighted in red for both objectives. In
this example, we choose the point that optimized the Area under the Pareto
Curve.

##  5 Discussion

This paper proposes a new method to find proxy metrics that optimizes the
trade-off between sensitivity and directionality. To our knowledge, this is
the first approach that explicitly incorporates metric sensitivity into the
objective. In our experiments, we found proxy metrics that were 6-10 times
more sensitive than the short-term north star metric, and minimal cases where
the proxy and the north star moved in opposite directions.

Our experience developing proxy metrics with multiple teams across multiple
years has spurred many thoughts on their pros, cons, and things to watch out
for. These considerations go beyond the mathematical framework discussed in
this paper, and we list them in the next section. We then discuss some other
benefits of using proxy metrics. Finally, we’ll discuss some limitations in
our methodology and future areas of improvement.

###  5.1 Considerations beyond Pareto optimality

Below are other important considerations we learned from deploying proxy
metrics in practice:

  * •

Make sure you need proxies before developing them. Proxies should be motivated
by an insensitive north star metric, or one that is consistently different
between the short and long term. It is important to validate that you have
these issues before developing proxies. To assess sensitivity, you can compute
the Binary Sensitivity in a set of experiments. To assess short and long-term
differences, one possibility is to compare the treatment effects at the
beginning and end of your experiments.

  * •

Try better experiment design before using proxies. Proxies are one way to
increase sensitivity, but they are not the only way. Before you create proxy
metrics, you should assess if your sensitivity problems can be solved with a
better experiment design. For example, you may be able to run larger
experiments, longer experiments, or narrower triggering to only include users
that were actually impacted by the treatment. Solving at the design stage is
ideal because it allows us to target the north star directly.

  * •

Choose proxies with common sense. The best auxiliary metrics in our proxy
metric captured intuitive, critical aspects of the specific user journey
targeted by that class of experiments. For example, whether a user had a
satisfactory watch from the homepage is a good auxiliary metric for
experiments changing the recommendations on the home feed. In fact, many of
the best auxiliary metrics were already informally used by engineers,
suggesting that common sense metrics have superior statistical properties.

  * •

Validate and monitor your proxies, ideally using holdbacks. It is important to
remember that proxy metrics are not what we want to move. We want to move the
north star, and proxies are a means to this end. The best tool we have found
for validating proxies is the cumulative long-term holdback, including all
launches that were made based on the same proxy metric. It is also helpful to
regularly repeat the model fitting process on recent data, and perform out-of-
sample testing, to ensure your proxy is still at an optimal point.

###  5.2 Other benefits of proxy metrics

Developing proxies had many unplanned benefits beyond their strict application
as a tool for experiment evaluation. The first major benefit is the sheer
educational factor: the data science team and our organizational partners
developed a much deeper intuition about our metrics. We learned baseline
sensitivities, how the baseline sensitives vary across different product
areas, and the correlations between metrics.

Another unplanned benefit is that the proxy metric development process
highlighted several areas to improve the way we run experiments. We started to
do better experiment design, and to collect data from experiments more
systematically, now that the experiments can also be viewed as training data
for proxy metrics.

Finally, the most important benefit is that we uncovered several auxiliary
metrics that were correlated with the north star, but not holistic enough to
be included in the final proxy. We added these signals directly into our
machine-learning systems, which resulted in several launches that directly
improved the long-term user experience.

###  5.3 Discussion, limitations, and future directions

This methodology is an important milestone, but there are still many areas to
develop, and our methodology is sure to evolve over time.

The first area to explore is causality. Our approach relies on the assumption
that the treatment effects of the experiments are independent draws from a
common distribution of treatment effects, and that future experiments come
from the same generative process. Literature from clinical trials [16, 10],
however, has more formal notions of causality for surrogate metrics, and we
plan to explore this area and see if there’s anything we can glean.

Another important improvement would be a more principled approach to select
the final proxy metric. Some initial work along these lines revolves around
our proxy score (Appendix A) and Area under the Pareto curve (Figure 4). We
hope to have a more refined perspective on this topic in the future.

We also did not explore more classic model-building improvements in detail.
For example, we do not address non-linearity and feature selection. Non-
linearity is particularly important, because it helps in cases where two
components of the proxy metric move in opposite directions. For feature
selection, we currently hand-pick several auxiliary metrics to include in the
proxy metric optimization. However, we should be able to improve upon this by
either inducing sparsity when estimating the Pareto front, or adopting a more
principled feature selection approach.

To conclude, let’s take a step back and consider the practical implications of
our results. Essentially, we found that the appropriate local metrics, that
are close to the experiment context, are vastly more sensitive than the north
star, and rarely move in the opposite direction. The implication is that using
the north star as a launch criterion is likely too conservative, and teams can
learn more and faster by focusing on the relevant local metrics.

Faster iteration has also opened our eyes to other mechanisms we can use to
ensure that our launches are positive for the user experience. We mentioned
earlier that launches using proxies should be paired with larger and longer
running holdbacks. In fact, through such holdbacks we were able to catch small
but slightly negative launches (case 1 in Figure 1, but with the opposite
sign), and further refine our understanding of the differences between the
short and long term impact on the north star metric (case 2 in Figure 1, but
with the opposite sign).

##  Appendix A The proxy score

It is useful to have a single metric that quantifies the performance of a
proxy metric. We have relied on a measure called _proxy score_. The proxy
score rewards properties of an ideal proxy metric: short-term sensitivity, and
moving in the same long-term direction as the north star (Figure 1). The
motivation behind our specific definition comes from the contingency table
visualized in Figure 8, which is generated from 1000 simulated experiments.

Figure 8: There are nine combinations of statistical significance between the
proxy metric and the north star metric, based on if the proxy and north star
are negative, neutral, or positive.

The green cells in Figure 8 represent cases where the proxy is statistically
significant in the short-term, the north star is significant in the long-term,
and the proxy and north star move in the same direction. These are
unambiguously good cases, and we refer to them as _Detections_. The red cells
are unambiguously bad cases: both the short-term proxy and north star are
statistically significant, but they move in opposite directions. We call these
_Mistakes_. Informally, we define the proxy score as

Proxy Score $\displaystyle=$
$\displaystyle\frac{\text{Detections}-\text{Mistakes}}{\text{Number of
experiments where the north star is significant}}.$

The key idea is that the proxy score rewards both sensitivity, and accurate
directionality. More sensitive metrics are more likely to be in the first and
third rows, where they can accumulate reward. But metrics in the first and
third rows can only accumulate reward if they are in the correct direction.
Thus, the proxy score rewards both sensitivity and directionality. Microsoft
independently developed a similar score, called _Label Agreement_ [7].

More formally, and following the notation in Section 2, we can define the
proxy score using hypothesis tests for the proxy metric and the north star
metric, defined as

North Star: $\displaystyle\qquad
H_{0,j}^{ns}:\theta_{j}^{ns}=0\quad\text{vs}\quad
H_{1,j}^{ns}:\theta^{ns}_{j}\neq 0,$ (9) Proxy: $\displaystyle\qquad
H_{0,j}^{z}:\theta_{j}^{z}=0\quad\text{vs}\quad H_{1,j}^{z}:\theta^{z}_{j}\neq
0.$ (10)

If we let
$D_{j}=\\{\theta_{j}^{ns},\sigma_{j}^{ns},\theta_{j}^{z},\theta_{j}^{z}\\}$ be
data required to compute the hypothesis tests, then the proxy score for
experiment $j$ can be written as

$\displaystyle\texttt{PS}(D_{j})$ $\displaystyle=$
$\displaystyle\mathbf{1}(H^{z}_{0,j}\text{ rejected})\qquad(\text{Proxy
Significant})$ $\displaystyle\times$
$\displaystyle\mathbf{1}(H^{ns}_{0,j}\text{ rejected})\qquad(\text{North Star
Significant})$ $\displaystyle\times$
$\displaystyle\Big{[}\mathbf{1}(\theta_{j}^{ns}>0\text{ and
}\theta_{j}^{z}>0)+\mathbf{1}(\theta_{j}^{ns}<0\text{ and
}\theta_{j}^{z}<0)\Big{]}\quad(\text{Agree})$ $\displaystyle\times$
$\displaystyle\Big{[}-\mathbf{1}(\theta_{j}^{ns}>0\text{ and
}\theta_{j}^{z}<0)-\mathbf{1}(\theta_{j}^{ns}<0\text{ and
}\theta_{j}^{z}>0)\Big{]},\ \ (\text{Disagree})$

where $\mathbf{1}(\cdot)$ is an indicator equal to one if its argument is
true, and zero otherwise.

We can aggregate these values across all experiments in our data, and scale by
the number of experiments where the north star is significant, to compute the
final proxy score for a set of experiments. The scaling factor ensures that
the proxy score is always between -1 and 1.

$\displaystyle\texttt{PS}(D)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{J}\frac{\texttt{PS}(D_{j})}{\mathbf{1}(H^{ns}_{0,j}\text{
rejected})}.$ (11)

Similar to Binary sensitivity, there can be issues with the proxy score when
the north star metric is rarely significant. We have explored a few ways to
make this continuous, for example by substituting indicators for Bayesian
posterior probabilities.

## References

  * [1] Susan Athey, Raj Chetty, Guido W Imbens, and Hyunseung Kang.  The surrogate index: Combining short-term proxies to estimate long-term treatment effects more rapidly and precisely.  Technical report, National Bureau of Economic Research, 2019.
  * [2] Mickaël Binois and Victor Picheny.  GPareto: An R package for gaussian-process-based multi-objective optimization and analysis.  Journal of Statistical Software, 89(8):1–30, 2019.
  * [3] Nicholas Chamandy, Omkar Muralidharan, Amir Najmi, and Siddartha Naidu.  Estimating uncertainty for massive data streams.  Technical report, Google, 2012.
  * [4] Albert C. Chen and Xin Fu.  Data + intuition: A hybrid approach to developing product north star metrics.  In Proceedings of the 26th International Conference on World Wide Web Companion, WWW ’17 Companion, page 617–625, Republic and Canton of Geneva, CHE, 2017. International World Wide Web Conferences Steering Committee.
  * [5] Alex Deng.  Metric Sensitivity Decomposition. Causal Inference and Its Applications in Online Industry.  https://alexdeng.github.io/causal/sensitivity.html#metric-sensitivity-decomposition.  [Online; accessed 21-December-2022].
  * [6] Alex Deng and Xiaolin Shi.  Data-driven metric development for online controlled experiments: Seven lessons learned.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 77–86, 2016.
  * [7] Pavel Dmitriev and Xian Wu.  Measuring metrics.  In Proceedings of the 25th ACM international on conference on information and knowledge management, pages 429–437, 2016.
  * [8] Weitao Duan, Shan Ba, and Chunzhe Zhang.  Online experimentation with surrogate metrics: Guidelines and a case study.  In Proceedings of the 14th ACM International Conference on Web Search and Data Mining. ACM, mar 2021.
  * [9] Weitao Duan, Shan Ba, and Chunzhe Zhang.  Online experimentation with surrogate metrics: Guidelines and a case study.  In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 193–201, 2021.
  * [10] Michael R Elliott, Anna SC Conlon, Yun Li, Nico Kaciroti, and Jeremy MG Taylor.  Surrogacy marker paradox measures in meta-analytic settings.  Biostatistics, 16(2):400–412, 2015.
  * [11] Michael T. M. Emmerich, André H. Deutz, and Jan Willem Klinkenberg.  Hypervolume-based expected improvement: Monotonicity properties and exact computation.  In 2011 IEEE Congress of Evolutionary Computation (CEC), pages 2147–2154, 2011.
  * [12] Joerg M Gablonsky and Carl Tim Kelley.  A locally-biased form of the direct algorithm.  Technical report, North Carolina State University. Center for Research in Scientific Computation, 2000.
  * [13] Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and D. Sculley.  Google vizier: A service for black-box optimization.  In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13 - 17, 2017, pages 1487–1495. ACM, 2017.
  * [14] Henning Hohnhold, Deirdre O’Brien, and Diane Tang.  Focus on the long-term: It’s better for users and business.  In Proceedings 21st Conference on Knowledge Discovery and Data Mining, Sydney, Australia, 2015.
  * [15] Steven G. Johnson.  The NLopt nonlinear-optimization package.  https://github.com/stevengj/nlopt, 2007.
  * [16] Ross L. Prentice.  Surrogate endpoints in clinical trials: definition and operational criteria.  Statistics in medicine, 8(4):431–440, 1989.
  * [17] W. Qin, W. Machmouchi, and Martins A. M.  Beyond power analysis: Metric sensitivity analysis in A/B tests.  https://www.microsoft.com/en-us/research/group/experimentation-platform-exp/articles/beyond-power-analysis-metric-sensitivity-in-a-b-tests/.
  * [18] Lenny Rachitsky.  Choosing Your North Star Metric.  https://future.com/north-star-metrics/.
  * [19] Xingyou Song, Sagi Perel, Chansoo Lee, Greg Kochanski, and Daniel Golovin.  Open source vizier: Distributed infrastructure and api for reliable and flexible black-box optimization.  In Automated Machine Learning Conference, Systems Track (AutoML-Conf Systems), 2022.
  * [20] Kaifeng Yang, Michael Emmerich, André Deutz, and Thomas Bäck.  Multi-objective bayesian global optimization using expected hypervolume improvement gradient.  Swarm and Evolutionary Computation, 44:945–956, 2019.