# MWS and FWS Codes for Coordinate-Wise Weight Functions

Tim Alderson The author acknowledges the support of the NSERC of Canada
Discovery Grant program. University of New Brunswick, Canada  Benjamin Morine
University of New Brunswick, Canada

###### Abstract

A combinatorial problem concerning the maximum size of the (hamming) weight
set of an $[n,k]_{q}$ linear code was recently introduced. Codes attaining the
established upper bound are the Maximum Weight Spectrum (MWS) codes. Those
$[n,k]_{q}$ codes with the same weight set as $\mathbb{F}_{q}^{n}$ are called
Full Weight Spectrum (FWS) codes. FWS codes are necessarily “short”, whereas
MWS codes are necessarily “long”. For fixed $k,q$ the values of $n$ for which
an $[n,k]_{q}$-FWS code exists are completely determined, but the
determination of the minimum length $M(H,k,q)$ of an $[n,k]_{q}$-MWS code
remains an open problem. The current work broadens discussion first to general
coordinate-wise weight functions, and then specifically to the Lee weight and
a Manhattan like weight. In the general case we provide bounds on $n$ for
which an FWS code exists, and bounds on $n$ for which an MWS code exists. When
specializing to the Lee or to the Manhattan setting we are able to completely
determine the parameters of FWS codes. As with the Hamming case, we are able
to provide an upper bound on $M(\mathcal{L},k,q)$ (the minimum length of Lee
MWS codes), and pose the determination of $M(\mathcal{L},k,q)$ as an open
problem. On the other hand, with respect to the Manhattan weight we completely
determine the parameters of MWS codes.

Keywords— linear codes, Lee weight, Manhattan weight, maximum weight spectrum,
full weight spectrum

MSC 2020— 94B05,05A99

##  1 Introduction

In 1973 Delsarte studied the number of distinct distances held by a code
$\mathcal{C}$, which in the case of linear codes equates to studying the
number of distinct weights [12]. Discussions on the set of distinct weights of
a code can be traced in [24], where the author tackled the following question.
Given a set of positive integers, $S$, is it possible to construct a code
whose set of non-zero weights is $S$? Partial solutions were presented, and
necessary conditions were established.

In [36] Shi et. al. consider a combinatorial problem concerning the maximum
number $L(k,q)$ of distinct non-zero (hamming) weights a linear code of
dimension $k$ over $\mathbb{F}_{q}$ may possess. Specifically they propose

$L(k,q)\leq\frac{q^{k}-1}{q-1}.$ (1)

In [2], linear codes meeting this bound were shown to exist for all $k$ and
$q$, and such codes were named maximum weight spectrum (MWS) codes.

A further refinement was also investigated in [36] by the introduction of the
function $L(n,k,q)$, denoting the maximum number of non-zero (Hamming) weights
a linear $[n,k]_{q}$ code may have. Since an arbitrary vector of length $n$
has hamming weight at most $n$, an immediate upper bound is $L(n,k,q)\leq n$.
In [1], the parameters of linear codes meeting this bound were completely
determined, and were named full weight spectrum (FWS) codes.

The bound (1) was previously shown to be sharp for binary codes by Haily and
Harzalla [19]. In [36], the binary case is proved independently and the bound
is further shown to be sharp for all $q$-ary linear codes of dimension $k=2$.
The authors went on to conjecture that the bound is sharp for all $q$ and $k$.
This conjecture was proved correct in [2], where it is shown that linear MWS
codes exist for all $q$ and $k$. For fixed $k$ and $q$ only sufficient
conditions on $n$ are known for which an MWS code exists [2, 11, 25] . The
questions relating to maximal weight spectra are explored in [34] as they
relate to cyclic codes, and in [35] as they relate to quasi-cyclic codes. In
both cases existence results are established. The problem of determining the
minimum value of $n$ for which an $[n,k]_{q}$ MWS code exists has attracted
some attention [2, 11, 25] but remains remains open.

In this work we expand discussions to linear codes equipped with general
coordinate-wise weight functions, with a view towards Lee weight and a
Manhattan type weight. With linear codes, all scalar multiples of any codeword
also belongs to the code. Non-zero scalar multiples of a codeword have the
same Hamming weight, but in general have differing Lee weights and differing
Manhattan weights. Hence, under these new weight functions we might expect
bounds regarding respective weight spectra to differ from those established
under the Hamming metric.

In the sequel we establish necessary and sufficient conditions on $n$ under
which FWS codes with respect to these weight functions exist. We are also able
to establish the existence of MWS codes for each $k$ and $q$, and for the
Manhattan weight we are able to determine the minimal length $n$ for which
these MWS codes exist. On the other hand, determining minimal length of an MWS
code under the Lee metric remains as elusive as it is in the case of the
Hamming metric.

The research on codes in the Manhattan metric is not extensive. This metric is
popular in psychology and related areas but not well known in communications
where such channels appear when a signal limiter is used at the receiver [17].
The literature on codes in the Lee metric is comparatively richer, though not
entirely extensive, e.g., [5, 10, 15, 18, 27, 31, 32]. Lee-codes were first
introduced by C. Y. Lee in [23], and were found to be advantageous for certain
types of data transmission. For example, the input alphabet may correspond to
phases of a sinusoidal signal of fixed amplitude and frequency, to which white
Guassian noise is added. Such a channel has an inherent ordering of the
letters of the input alphabet, and transitions between adjacent letters are
much more likely than transitions between distant input letters. Corrupted
digits of phase-modulated signals are more likely to have only a slightly
different phase in comparison to the original signal. For such channels, the
Lee metric is a much more useful notion than the Hamming metric [8, 7].

The properties of Lee-codes and, in particular, the question of existence (or
nonexistence) of perfect codes in the Lee metric has been studied by numerous
authors, for example, [3, 4, 13, 14, 18, 20, 28]. More recent interest in Lee
codes has been spurred on due to further development of applications for these
codes. Some examples include constrained and partial-response channels [31],
interleaving schemes [9], orthogonal frequency-division multiplexing [33],
multidimensional burst-error-correction [16], error-correction in the rank
modulation scheme for flash memories [22], and VLSI decoders and fault-
tolerant logic [31, 6]. There have also been more recent attempts to settle
the existence question of perfect codes in the Lee metric [20, 21, 29].

##  2 Preliminaries

Let $\mathcal{A}$ be an alphabet of size $q$ which without loss of generality
is the set $\\{0,1,\ldots,q-1\\}$. An $(n,M)_{q}$-code, $\mathcal{C}$ is a a
subset of $\mathcal{A}^{n}$ with $|\mathcal{C}|=M$. The elements of
$\mathcal{A}^{n}$ are called words or vectors, while elements of $\mathcal{C}$
are called codewords. In the case that $M=q^{k}$ we denote $\mathcal{C}$ as an
$(n,k)_{q}$-code, and in the case that $\mathcal{A}=\mathbb{F}_{q}$ (the
finite field with $q$ elements) and $\mathcal{C}$ is a subspace of dimension
$k$, $\mathcal{C}$ is a linear code, denoted an $[n,k]_{q}$-code. We only
consider linear codes having no coordinate which is identically zero. The
Hamming distance, $d_{H}(a,b)$, between two words is the number of coordinates
in which they differ. A _generator matrix_ $G$ for an $[n,k]_{q}$-code
$\mathcal{C}$ is a $k\times n$ matrix over $\mathbb{F}_{q}$ whose row vectors
generate $\mathcal{C}$. The support of a word $c$ is the set $supp(c)=\\{i\mid
c_{i}\neq 0\\}$.

Throughout we shall adopt standard notation regarding vector spaces. In
particular if $S$ is a set of vectors then $\langle S\rangle$ shall denote the
span of $S$, by $e_{i}$ we shall denote the standard basis vector with $i$’th
entry $1$ and all other entries $0$, and given $n$ $k$-vectors
$\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$ we shall denote by
$G=[\lambda_{1}^{\alpha_{1}}|\lambda_{2}^{\alpha_{2}}|,\cdots,|\lambda_{n}^{\alpha_{n}}]$
the $k\times(\alpha_{1}+\alpha_{2}+\cdots+\alpha_{n})$ matrix obtained by
repeating the $i$’th column $\alpha_{i}$ times.

###  2.1 Component-wise Metrics and Weight Functions, MWS and FWS Codes

For our purposes a weight function on $\mathbb{F}_{q}^{n}$ is a mapping
$w_{\mu}:\mathbb{F}_{q}^{n}\to{\mathbb{R}}^{+}$ with $w_{\mu}(x)=0$ if and
only if $x=0$; $w_{\mu}(u)$ is referred to as the $\mu$-weight of $u$. In the
special case that $w_{\mu}:\mathbb{F}_{q}\to{\mathbb{R}}^{+}$ and
$w_{\mu}(u)=w_{\mu}(u_{1})+w_{\mu}(u_{2})+\cdots+w_{\mu}(u_{n})$ we say that
$w_{\mu}$ is a component-wise weight function. For any subset
$\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ we define the $\mu-$_weight set of
$\mathcal{C}$_ as

$w_{\mu}(\mathcal{C})=\left\\{w_{\mu}(c)\mid
c\in\mathcal{C}\setminus\\{0\\}\right\\}.$

For $u\in\mathbb{F}_{q}^{n}$, the Hamming weight of $u$ is given by
$w_{H}(u)=d_{H}(u,0)$, the (Hamming) distance between $u$ and $0$. Likewise,
given any metric on $\mathbb{F}_{q}^{n}$ one has, mutatis mutandis an
associated weight function.

If $d_{\mu}:\mathcal{A}^{n}\times\mathcal{A}^{n}\to\mathbb{Z}^{+}$ is a metric
then we denote by $d_{\mu}(u,v)$ the $\mu$-distance between $u$ and $v$, and
similarly $w_{\mu}(u)$ denotes the $\mu$-weight (distance from $0$) of $u$. By
$S_{\mu}(u,t)$ we denote the $\mu$-sphere of radius $t$ around $u$, and by
$\mathcal{S}_{\mu}(u,t)$ it’s boundary, that is

$S_{\mu}(u,t)=\\{x\mid d_{\mu}(u,x)\leq t\\},\text{ and
}\mathcal{S}_{\mu}(u,t)=\\{x\mid d_{\mu}(u,x)=t\\}.$

We say $d_{\mu}$ is a component-wise metric if
$d_{\mu}(u,v)=\sum\limits_{i=1}^{n}d_{\mu}(u_{i},v_{i})$, and note that
$d_{\mu}$ then corresponds to a component-wise weight function $w_{\mu}$. The
Hamming metric is an example of component-wise metric, as are both the Lee and
Manhattan metrics.

Analogous to the Hamming case, for fixed $k,q$ we denote by $L_{\mu}(k,q)$ the
maximum cardinality of $w_{\mu}(\mathcal{C})$ as $\mathcal{C}$ ranges over all
$q$-ary linear codes of dimension $k$. If $n$ is also fixed then this quantity
is denoted by $L_{\mu}(n,k,q)$. Since an $[n,k]_{q}$ code $\mathcal{C}$ is a
subset of $\mathbb{F}_{q}^{n}$ it follows that
$|w_{\mu}(\mathcal{C})|\leq|w_{\mu}(\mathbb{F}_{q}^{n})|$ motivating the
following definition.

######  Definition 2.1.

If $\mathcal{C}$ is a linear $[n,k]_{q}$-code then $\mathcal{C}$ is a
$\mu$-Full Weight Spectrum ($\mu$-FWS) code if
$w_{\mu}(\mathcal{C})=w_{\mu}(\mathbb{F}_{q}^{n})$.

Note that $|w_{H}(\mathbb{F}_{q}^{n})|=n$, so the definition above subsumes
that of FWS codes with respect to Hamming weight. Clearly, if $n=k$ then
$\mathcal{C}$ is necessarily FWS, so the task at hand is that of determining
the maximum length $n$ of a $k$-dimensional $q$-ary $\mu$-FWS code. The
following inequality also follows from the respective definitions:

$L_{\mu}(n,k,q)\leq L_{\mu}(k,q).$ (2)

An open problem posed in [36] is that of determining the sharpness of (2) for
the Hamming weight; to determine parameters for which the inequality is
strict. This is also of interest when widening discussions to other types of
weight functions.

The following is easily established and provides definitions we shall make
reference to throughout this work.

######  Proposition 2.2.

Let $w_{\mu}$ be a component-wise weight function on $\mathcal{A}^{n}$ where
$|\mathcal{A}|=q$, and let $m=\max w_{\mu}(\mathcal{A})$.

  1. 1.

$|w_{\mu}(\mathcal{A}^{n})|\leq n\cdot m$.

  2. 2.

If $w_{\mu}(\mathcal{A})=\\{1,2,\ldots,m\\}$ then
$|w_{\mu}(\mathcal{A}^{n})|=n\cdot m$.

  3. 3.

If $w_{\mu}(\mathcal{A})=\\{1,2,\ldots,m\\}$ then an $(n,M)_{q}$ code
$\mathcal{C}$ over $\mathcal{A}$ is $\mu$-FWS if and only if
$|w_{\mu}(\mathcal{C})|=n\cdot m$.

  4. 4.

If $\mathcal{A}=\mathbb{F}_{q}$ and $\Delta=\max\limits_{n\geq
k}\\{|w_{\mu}(\langle u\rangle)|\;\mid u\in\mathbb{F}_{q}^{n}\\}$ then
$L_{\mu}(k,q)\leq\frac{q^{k}-1}{q-1}\cdot\Delta$ .

######  Definition 2.3.

Let $w_{\mu}$ be a component-wise weight function on $\mathbb{F}_{q}^{n}$ and
let $\Delta=\max\limits_{n\geq k}\\{|w_{\mu}(\langle u\rangle)|\;\mid
u\in\mathbb{F}_{q}^{n}\\}$. A linear $[n,k]_{q}$-code $\mathcal{C}$ is a
$\mu$-Maximum Weight Spectrum ($\mu$-MWS) code if

$|w_{\mu}(\mathcal{C})|=\frac{q^{k}-1}{q-1}\cdot\Delta.$

######  Remark 2.4.

A few observations regarding the previous proposition and definition:

  1. 1.

If $w_{\mu}(\mathcal{A})=\\{1,2,\ldots,m\\}$ then we may characterize
$\mu$-FWS codes as those having at least one codeword of each $\mu$-weight
from $1$ to $mn$.

  2. 2.

We may characterize linear $\mu$-MWS codes as those linear codes in which
every one dimensional subspace has a $\mu$-weight set of size $\Delta$, and
the $\mu$-weight sets of one dimensional subspaces are mutually disjoint.

  3. 3.

For the Hamming weight, $m=1=\Delta$, and as such the terminology agrees with
that of [36].

In all of the above notations we may drop the subscript $\mu$ if the
metric/weight of concern is clear from the context. In the sequel we will find
the following to be of use.

######  Lemma 2.5.

Let $\mathcal{C}$ be an $[n,k]_{q}$-code, let $w_{\mu}$ be a component-wise
weight function defined on $\mathbb{F}_{q}^{n}$ with
$w_{\mu}(\mathbb{F}_{q})=\\{1,2,\ldots,m\\}$ and let $\Delta$ be as in
Proposition 2.2.

  1. 1.

If $\mathcal{C}$ is $\mu$-FWS then $n\cdot m\leq L_{\mu}(k,q)$.

  2. 2.

If $\mathcal{C}$ is both $\mu$-FWS and $\mu$-MWS, then
$n=\frac{q^{k}-1}{q-1}\cdot\frac{\Delta}{m}$.

###### Proof.

The first part follows from the equation (2) and Proposition 2.2. For the
second part, observe that the FWS property gives
$n=\frac{|w_{\mu}(\mathcal{C})|}{m}$, whereas the MWS property gives
$|w_{\mu}(\mathcal{C})|=\frac{q^{k}-1}{q-1}\cdot\Delta$. ∎

######  Lemma 2.6.

Let $\mathcal{C}$ be an $(n,M)_{q}$-code, let $w_{\mu}$ be a component-wise
metric weight function, let $m$ and $\Delta$ be as in Proposition 2.2, and let
$r=\max\limits_{\delta}|\\{u\in\mathcal{C}\mid w_{\mu}(u)=\delta\\}|$. It
holds that

$\frac{M-1}{r}\leq|w_{\mu}(\mathcal{C})|\leq m\cdot n,$

with equality throughout if and only if $|\\{u\in\mathcal{C}\mid
w_{\mu}(u)=\delta\\}|=r$ for all $1\leq\delta\leq mn$.

###### Proof.

The first inequality arises by counting ordered pairs $(u,w(u))$ where $0\neq
u\in\mathcal{C}$ in two ways to give $M-1\leq|w_{\mu}(\mathcal{C})|\cdot r$,
and the second inequality is from Proposition 2.2. The equality part follows
from simple counting. ∎

Given the lower and upper bounds inherent in the above it behooves us to
investigate optimality with respect to code length. To this end we define
$M(\mu,k,q)$ and $N(\mu,k,q)$ as follows:

$M(\mu,k,q)=\min\\{n\mid C\text{ is an }[n,k]_{q}\;\;\mu-MWS\text{ code }\\}$
(3) $N(\mu,k,q)=\max\\{n\mid C\text{ is an }[n,k]_{q}\;\;\mu-FWS\text{ code
}\\}$ (4)

The following tables will perhaps place some of the results that follow in
context.

Hamming Weight | Reference
---|---
$M(H,k,2)=2^{k}-1$ | [1, 36]
$M(H,3,3)\leq 32$ | [2]
$\frac{q}{2}\cdot\frac{q^{k}-1}{q-1}\leq M(H,k,q)$ | [1]
$M(H,k,q)\leq\frac{q}{2}\cdot\frac{q^{k}-1}{q-1}\cdot\left(\frac{q^{k-1}-1}{q-1}\right)$ | [2]
$M(H,2,q)=\frac{q(q+1)}{2}$ | [1]
$N(H,k,q)=2^{k}-1$ | [1]
Manhattan Weight | Reference
---|---
$M(\mathcal{M},k,q)=\frac{q^{k}-1}{q-1}$ |  Th’m 4.11
$N(\mathcal{M},k,q)=\frac{q^{k}-1}{q-1}$ |  Th’m 4.12

Lee Weight | Reference
---|---
$\frac{q^{k}-1}{q-1}+\left\lceil\frac{2(k-1)}{q-1}\right\rceil\leq M(\mathcal{L},k,q>2)$ |  Lem. 4.5
$2^{k}-1\leq M(\mathcal{L},k,2)$ |  Lem. 4.5
$M(\mathcal{L},k,q)\leq\frac{(\frac{q+1}{2})^{2k^{2}-3k+1}-1}{\frac{q+1}{2}-1}$ |  Th’m 4.7
$M(\mathcal{L},2,7)\leq 16$ | [26]
$M(\mathcal{L},2,11)\leq 34$ | [26]
$M(\mathcal{L},2,13)\leq 46$ | [26]
$M(\mathcal{L},2,17)\leq 76$ | [26]
$M(\mathcal{L},2,19)\leq 86$ | [26]
$M(\mathcal{L},2,23)\leq 126$ | [26]
$N(\mathcal{L},k,q)=\frac{\left(\frac{q+1}{2}\right)^{k}-1}{\left(\frac{q+1}{2}\right)-1}$ |  Lem. 4.8

In the next section we focus on determining $N(\mu,k,q)$.

##  3 Generalized Full Weight Spectrum Codes

We can in fact determine $N(\mu,k,q)$ when
$w_{\mu}(\mathbb{F}_{q})=\\{1,2,\ldots,m\\}$. To do this, the following will
be of use.

######  Lemma 3.1.

Suppose $w_{\mu}$ is a coordinate-wise weight function on
$\mathbb{F}_{q}^{n}$, where
$\mathbb{F}_{q}=\\{0,\alpha_{1}=1,\alpha_{2},\ldots,\alpha_{q-1}\\}$, and
$w_{\mu}(\mathbb{F}_{q})=\\{1,2,\ldots,m\\}$.
Let $\mathcal{C}$ be a linear $[n,k]_{q}$ code with basis
$B=\\{v_{1},v_{2},\ldots,v_{k}\\}$. Let $S=supp(v_{1})$, $\displaystyle
T=\bigcup_{i=2}^{k}supp(v_{i})$, $S^{\prime}=S\setminus T$, with
$s=|S|,t=|T|$, and $s^{\prime}=|S^{\prime}|$. If $C$ is $\mu$-FWS then

$s^{\prime}\leq m\cdot t+1$

###### Proof.

If $s^{\prime}=0$ then the result holds, so assume $s^{\prime}\geq 1$. Let
$x\in\mathcal{C}$. If $supp(x)\cap S^{\prime}=\emptyset$ then
$supp(x)\subseteq T$, so $|supp(x)|\leq t$ giving

$w_{\mu}(x)\leq m\cdot t.$ (5)

If $supp(x)\cap S^{\prime}\neq\emptyset$ then it follows that
$S^{\prime}\subseteq supp(x)$, so $|supp(x)|\geq s^{\prime}$ giving

$w_{\mu}(x)\geq s^{\prime}.$ (6)

Since $n=t+s^{\prime}$ (by assumption no coordinate is identically zero) we
see that if $\mathcal{C}$ is $\mu$-FWS then

$w_{\mu}(\mathcal{C})=\left\\{1,2,\ldots,(t+s^{\prime})\cdot m\right\\},$

and since $m,s^{\prime}\geq 1$ there exists a codeword $u$ with
$w_{\mu}(u)=t\cdot m+1$. From (5) and 6 we may conclude that

$w_{\mu}(u)=t\cdot m+1\geq s^{\prime}$

giving the desired inequality. ∎

######  Theorem 3.2.

Let $m$ be as in Lemma 3.1. If $\mathcal{C}$ is a linear $[n,k]_{q}$ $\mu$-FWS
code then

$n\leq\sum\limits_{i=0}^{k-1}\left(m+1\right)^{i}=\frac{(m+1)^{k}-1}{m}.$

###### Proof.

Let $\mathcal{C}$ be an $[n,k]_{q}$ $\mu$-FWS code. It suffices to show that
we may select a basis $\\{\lambda_{1},\lambda_{2},\ldots,\lambda_{k}\\}$ of
$\mathcal{C}$ such that

$\left|\bigcup_{i=1}^{t}supp(\lambda_{i})\right|\leq
1+(m+1)+\cdots+(m+1)^{t-1},\text{ for }1\leq t\leq k.$ (7)

To this end first note that since $\mathcal{C}$ is $\mu$-FWS, there is a
codeword of weight $1$. Assume without loss of generality that $w_{\mu}(1)=1$,
so we may take $\lambda_{1}=e_{1}$, so (7) holds for $t=1$. Assume
$\lambda_{1},\lambda_{2},\ldots,\lambda_{k-1}$ have been selected in
accordance with (7), and let $\lambda_{k}$ be a codeword such that
$\\{\lambda_{1},\lambda_{2},\ldots,\lambda_{k}\\}$ is a basis for
$\mathcal{C}$. From the Lemma 3.1 we have

$\displaystyle\left|\bigcup_{i=1}^{k}supp(\lambda_{i})\right|$
$\displaystyle\leq\left|\bigcup_{i=1}^{k-1}supp(\lambda_{i})\right|+m\cdot\left|\bigcup_{i=1}^{k-1}supp(\lambda_{i})\right|+1$
$\displaystyle=(m+1)\cdot\left|\bigcup_{i=1}^{k-1}supp(\lambda_{i})\right|+1$
$\displaystyle\leq\sum\limits_{i=0}^{k-1}\left(m+1\right)^{i}.$

∎

We now show the bound in Theorem 3.2 is sharp.

######  Theorem 3.3.

Let $m$ be as in Lemma 3.1. There exists an $[n,k]_{q}$ $\mu$-FWS code if and
only if

$k\leq n\leq\frac{(m+1)^{k}-1}{m}.$

In particular $N(\mu,k,q)=\frac{(m+1)^{k}-1}{m}.$

###### Proof.

That $k\leq n\leq\frac{(m+1)^{k}-1}{m}$ is necessary is given in Theorem 3.2.
For sufficiency, let $k$ be fixed and let $G$ be the following matrix:

$G=\left[\begin{pmatrix}1\\\ 0\\\ 0\\\ \vdots\\\ \vdots\\\
0\end{pmatrix}\begin{pmatrix}0\\\ 1\\\ 0\\\ \vdots\\\ \vdots\\\
0\end{pmatrix}\begin{pmatrix}0\\\ 1\\\ 0\\\ \vdots\\\ \vdots\\\
0\end{pmatrix}\cdots\begin{pmatrix}0\\\ 1\\\ 0\\\ \vdots\\\ \vdots\\\
0\end{pmatrix}\begin{pmatrix}0\\\ 0\\\ 1\\\ \vdots\\\ \vdots\\\
0\end{pmatrix}\begin{pmatrix}0\\\ 0\\\ 1\\\ \vdots\\\ \vdots\\\
0\end{pmatrix}\cdots\begin{pmatrix}0\\\ 0\\\ 1\\\ \vdots\\\ \vdots\\\
0\end{pmatrix}\cdots\cdots\begin{pmatrix}0\\\ 0\\\ 0\\\ \vdots\\\ \vdots\\\
1\end{pmatrix}\right]$
$=\left[e_{1}\left|(e_{2})^{m+1}\left|(e_{3})^{(m+1)^{2}}\right|\cdots\right|(e_{k})^{(m+1)^{k-1}}\right]$

Denote the rows of $G$ by $\lambda_{1},\lambda_{2},\ldots\lambda_{k}$ and let
$\mathcal{C}$ be the code generated by $G$. The supports of the
$\lambda_{i}$’s are mutually disjoint, and as such for any
$\alpha_{1},\alpha_{2},\ldots,\alpha_{k}\in\mathbb{F}_{q}$,

$\displaystyle
w_{\mu}(\alpha_{1}\lambda_{1}+\alpha_{2}\lambda_{2}+\cdots+\alpha_{k}\lambda_{k})$
$\displaystyle=\mathrm{w}_{\mu}(\alpha_{1})+\mathrm{w}_{\mu}(\alpha_{2})\left(m+1\right)+\cdots+\mathrm{w}_{\mu}(\alpha_{k})\left(m+1\right)^{k-1}$
$\displaystyle=\sum_{i=1}^{k}\mathrm{w}_{\mu}(\alpha_{i})\left(m+1\right)^{i-1}.$

Since $\mathrm{w}_{\mu}(\mathbb{F}_{q})=\\{1,2,\ldots,m\\}$ we obtain
$|w_{\mu}(\mathcal{C})|=n$ and $\mathcal{C}$ is FWS.

Now consider $n<\sum\limits_{i=0}^{k-1}\left(m+1\right)^{i}$. Let $t$ be
maximal such that $n\leq\left(m+1\right)^{t}$. Construct a new generator
matrix $G^{\prime}$ by recursively removing the last (rightmost) column of $G$
such that it’s removal preserves rank (so there will always be at least one
occurrence of each $e_{i}$ in the new matrix) until $G^{\prime}$ is $n\times
k$. So

$G^{\prime}=\left.\left.\left.\left[e_{1}\left|(e_{2})^{m+1}\left|(e_{3})^{(m+1)^{2}}\right|\cdots\right|(e_{t})^{(m+1)^{t-1}}\left|(e_{t+1})^{n-(m+1)^{t}+1-k+t}\right|e_{t+2}\right|e_{t+3}\right|\cdots\right|e_{k}\right]$

If $\mathcal{C}^{\prime}$ is the code with generator $G^{\prime}$ then the
vectors from $\mathbb{F}_{q}^{k}$ with support being a subset of the first $t$
coordinates correspond a set of codewords having at least one of each
$\mu$-weight from $1$ to $(m+1)^{t}-1$, while the remaining vectors in
$\mathbb{F}_{q}^{k}$ correspond to a set of codewords with at least one of
each weight between $n\cdot m$ and $n-(m+1)^{t}+1$. ∎

######  Corollary 3.4.

Let $m$ and $\Delta$ be as in Proposition 2.2. If $\mathcal{C}$ is an
$[n,k]_{q}$ code that is both $\mu$-MWS and $\mu$-FWS, then $\Delta=m=q-1$,
and in particular $n=\frac{q^{k}-1}{q-1}$

###### Proof.

First observe that since $w_{\mu}$ is a component-wise weight function,
$w_{\mu}(\mathbb{F}_{q})=w_{\mu}(\left\langle e_{1}\right\rangle)$, giving
$m\leq\Delta$. Next we observe that

$n=\frac{q^{k}-1}{q-1}\cdot\frac{\Delta}{m}\leq\frac{(m+1)^{k}-1}{m}\leq\frac{q^{k}-1}{q-1}.$
(8)

The first equality follows from Lemma 2.5 , the first inquality follows from
Theorem 3.3, and the final inequality holds since $m\leq q-1$. From (8) it
follows that $\Delta\leq m$ whence $\Delta=m$ and the result follows. ∎

Corollary 3.4 tells us that if we seek codes that are both MWS and FWS then
the particular weight function must have a rather strict structure. Via a
Manhattan type weight function we will exhibit infinite families of codes that
are both MWS and FWS.

##  4 Codes with the Lee and Manhattan Weight Functions

Roughly following the notation and terminology as established in [30] we let
$\mathbb{Z}_{q}=\\{0,1,\ldots,q-1\\}$ denote the ring of integer residues
modulo the positive integer $q$. The Lee weight of an element
$\alpha\in\mathbb{Z}_{q}$, denoted by $\mathrm{w}_{\mathcal{L}}(\alpha)$ or
$|\alpha|$, takes non-negative integer values and is defined by

$\mathrm{w}_{\mathcal{L}}(\alpha)=|\alpha|=\begin{cases}\alpha&\text{ if
}0\leq\alpha\leq q/2\\\ q-\alpha&\text{ otherwise }\end{cases}$ (9)

We refer to the elements $1,2,\ldots,\lfloor q/2\rfloor$ as the “positive”
elements of $\mathbb{Z}_{q}$ and denote the set of such elements
$\mathbb{Z}_{q}^{+}$ ; the remaining elements in
$\mathbb{Z}_{q}\setminus\\{0\\}$ compose the “negative” elements, denoted
$\mathbb{Z}_{q}^{-}$.

######  Example 4.1.

In $\mathbb{Z}_{7}$, $\mathbb{Z}_{7}^{+}=\\{1,2,3\\}$ and $|2|=|5|=2$, whereas
in $\mathbb{Z}_{8}$, $\mathbb{Z}_{8}^{+}=\\{1,2,3,4\\}$ and $|2|=|6|=2$.

For a word ${c}=\left(c_{1},c_{2},\ldots,c_{n}\right)$ in
$\mathbb{Z}_{q}^{n}$, we define the Lee weight of ${c}$ by

$w_{\mathcal{L}}({c})=\sum_{j=1}^{n}\left|c_{j}\right|$

(with the summation being integer summation). The Lee distance (metric)
between two words ${x},{y}\in\mathbb{Z}_{q}^{n}$ is defined as
$w_{\mathcal{L}}({x}-{y})$; we denote that distance by
$\mathrm{d}_{\mathcal{L}}({x},{y})$. We note that for $q=2,3$ the Hamming and
Lee metrics coincide.

In keeping with the notation introduced in the previous section we shall adopt
the following:

$L_{\mathcal{L}}(k,q)=\max\limits_{C}|\mathrm{w}_{\mathcal{L}}(\mathcal{C})|$
(10)

where the maximum is taken over all $k$-dimensional codes over
$\mathbb{F}_{q}$, and

$L_{\mathcal{L}}(n,k,q)=\max\limits_{C}|\mathrm{w}_{\mathcal{L}}(\mathcal{C})|$
(11)

where the maximum is taken over all (linear) $[n,k]_{q}$ codes.

The minimum Lee distance of an $(n,M)$ code $\mathcal{C}$ over
$\mathbb{Z}_{q}$ with $M>1$ is defined by

$\mathrm{d}_{\mathcal{L}}(\mathcal{C})=\min_{{c}_{1},{c}_{2}\in\mathcal{C}:{c}_{1}\neq{c}_{2}}\mathrm{~{}d}_{\mathcal{L}}\left({c}_{1},{c}_{2}\right).$

We note that for a linear code, the minimum distance is also the minimum
weight, that is

$\mathrm{d}_{\mathcal{L}}(\mathcal{\mathcal{C}})=\min
w_{\mathcal{L}}(\mathcal{C}).$

The Manhattan metric (or Taxicab metric), is defined for alphabet letters
taken from the integers. For two words
${{x}=(x_{1},x_{2},\ldots,x_{n})},{y}=(y_{1},y_{2},\ldots,y_{n})\in\mathbb{Z}^{n}$
the Manhattan distance between ${x}$ and $y$ is defined as

$d_{\mathcal{M}}({x},{y})=\sum\limits_{i=1}^{n}|x_{i}-y_{i}|.$ (12)

The Manhattan weight of a vector in $\mathbb{Z}^{n}$ is it’s distance from
zero. As we have chosen $\mathbb{Z}_{q}=\\{0,1,\ldots,q-1\\}$ we may adapt the
Manhattan weight to $\mathbb{Z}_{q}^{n}$ by treating coordinate entries as
integers. Doing so we define the Manhattan weight of a vector
$x\in\mathbb{Z}_{q}^{n}$ as the integer sum:

$\mathrm{w}_{\mathcal{M}}({x})=\sum_{i=1}^{n}x_{i}.$ (13)

The Lee and Manhattan weights are defined to work over the ring
$\mathbb{Z}_{q}$. If the size of the alphabet is not prime then
$\mathbb{Z}_{q}$ is not a field. As our focus here shall be on linear codes we
shall (unless otherwise stated) discuss only codes over fields
$\mathbb{Z}_{q}$, where $q=p$ is prime.

###  4.1 Lee MWS Codes

Let $\mathcal{C}$ be a linear $[n,k]_{q}$ code over $\mathbb{Z}_{q}$. From the
definition of Lee weight it follows that if ${x}\in\mathbb{Z}_{q}^{n}$ then
$\mathrm{w}_{\mathcal{L}}({x})=\mathrm{w}_{\mathcal{L}}({-x})$ (i.e.
,$|{x}|=|{-x}|$). With reference to the Proposition 2.2 we therefore have
$\Delta\leq\frac{q-1}{2}$. One may quickly verify that since $q$ is prime,
$|w_{\mathcal{L}}(\langle e_{1}\rangle)|=\frac{q-1}{2}$ whence
$\Delta=\frac{q-1}{2}$ giving the following.

######  Theorem 4.2.

A linear $[n,k]_{q}$ code is $\mathcal{L}$-MWS if and only if
$w_{\mathcal{L}}(\mathcal{C})=\frac{q^{k}-1}{2}$.

From the definition it is clear that if $\mathcal{C}$ is $\mathcal{L}$-MWS
then two codewords $u,v$ have the same $\mathcal{L}$-weight if and only if
$u=\pm v$. Hence, in Lemma 2.6 we have $m=\frac{q-1}{2},r=2,$ and $M=q^{k}$
giving

$\mathcal{C}\text{ an }[n,k]_{q}\;\mathcal{L}\text{-MWS code }\implies
n\geq\frac{q^{k}-1}{q-1}.$ (14)

We can make a slight improvement to the lower bound (14).

######  Lemma 4.3.

If $\mathcal{C}$ is an $[n,k]_{q}$ $\mathcal{L}$-MWS code, $q>2$, then any two
non-zero codewords have at least one support position in common.

###### Proof.

If $u,v\in\mathcal{C}$ have disjoint supports then

$\mathrm{w}_{\mathcal{L}}(u+v)=\mathrm{w}_{\mathcal{L}}(u)+\mathrm{w}_{\mathcal{L}}(v)=\mathrm{w}_{\mathcal{L}}(u-v)=\mathrm{w}_{\mathcal{L}}(-u+v)=\mathrm{w}_{\mathcal{L}}(-u-v).$

Since $q>2$ we have $1\neq-1$, and thus by the $\mathcal{L}$-MWS property we
must have $u=0$ or $v=0$. ∎

######  Corollary 4.4.

If $\mathcal{C}$ is an $[n,k]_{q}$ $\mathcal{L}$-MWS code, $q>2$, and $0\neq
c\in\mathcal{C}$, then $|supp(c)|\geq k$. In particular,
$d_{\mathcal{L}}(\mathcal{C})\geq k$.

###### Proof.

Let $c$ be a codeword with minimal support in $\mathcal{C}$, say
$|supp(c)|=\delta$. Since $\mathcal{C}$ is a linear code, in any fixed $t\leq
k$ positions there are at least $q^{k-t}$ codewords with $0$ in each of these
coordinate position. If $\delta<k$ then Lemma 4.3 gives a contradiction. ∎

######  Lemma 4.5.

If $\mathcal{C}$ is a linear $[n,k]_{q}$ $\mathcal{L}-$MWS code with $q>2$
then $n\geq\frac{q^{k}-1}{q-1}+\left\lceil\frac{2(k-1)}{q-1}\right\rceil$. A
linear $(n,k)_{2}$ $\mathcal{L}-$MWS code satisfies $n\geq 2^{k}-1$.

###### Proof.

The case $q=2$ follows from (14). Assume $q>2$. The number of possible
distinct non-zero Lee weights of a vector $c$ of length $n$ is
$\left\lceil\frac{q-1}{2}\right\rceil\cdot n$, moreover, if $c\in\mathcal{C}$
then we may reduce this number by $k-1$ (Cor. 4.4) and the LMWS property gives

$\frac{q-1}{2}\cdot n-k+1\geq\frac{q^{k}-1}{2}.$

∎

###  4.2 Existence of $\mathcal{L}$-MWS codes for small $k,q$

For small values of $k$ and $q$ we now provide some values of $L(n,k,q)$ and
$L(k,q)$. For dimension $k=1$ we simply observe that for all prime $q$,
$w_{\mathcal{L}}(\langle e_{1}\rangle)=\frac{q-1}{2}=L(1,q)$ and we thus
obtain (rather trivial) MWS codes for any $q$. For $q=2$, and $q=3$ the
Hamming and Lee metrics coincide, so [2] and [36] do provide some results. For
small values of $q$ and $k$, computations were carried out by Morine in [26],
see Table 1.

Table 1: Optimal bounds for the Lee Metric, small values of $q$ prime, $n\geq 1$ Bound | Reference | Bound | Reference
---|---|---|---
$L_{\mathcal{L}}(n,1,q)=\frac{q-1}{2}$ ($\star$) | See above | $L_{\mathcal{L}}(k,2)=2^{k}-1$ | [36]
$L_{\mathcal{L}}(32,3,3)=13$ $(\star)$ | [2] | $L_{\mathcal{L}}(2,3)=6$ | [2]
$L_{\mathcal{L}}(16,2,7)=24$ $(\star)$ | [26] |  |
$L_{\mathcal{L}}(46,2,13)=84$ $(\star)$ | [26] | $L_{\mathcal{L}}(2,2,5)=4$ | [26]
$L_{\mathcal{L}}(86,2,19)=180$ $(\star)$ | [26] | $L_{\mathcal{L}}(3,2,5)=6$ | [26]
$L_{\mathcal{L}}(11,2,5)=12$ $(\star)$ | [26] | $L_{\mathcal{L}}(4,2,5)=8$ | [26]
$L_{\mathcal{L}}(34,2,11)=60$ $(\star)$ | [26] | $L_{\mathcal{L}}(5,2,5)=8$ | [26]
$L_{\mathcal{L}}(76,2,17)=144$ $(\star)$ | [26] | $L_{\mathcal{L}}(6,2,5)=9$ | [26]
$L_{\mathcal{L}}(126,2,23)=264$ $(\star)$ | [26] | $L_{\mathcal{L}}(7,2,5)=9$ | [26]

Entries marked with a $\star$ indicate codes that are MWS. In the table, the
bounds in [26] were found using exhaustive computer search. Note that based on
Table 1 we have

$8\leq M(\mathcal{L},2,5)\leq 11.$

###  4.3 Existence of $\mathcal{L}$-MWS codes

Having seen some examples of $\mathcal{L}$-MWS codes for specific values of
$q$ and $k$, we now provide a general construction for $\mathcal{L}$-MWS
codes, establishing their existence for all $q,k$. We shall find the following
to be of use in our construction.

######  Lemma 4.6.

Let $u_{i},v_{i}\in\mathbb{Z}_{q}$, $1\leq i\leq k$, where $q$ is odd.

  1. 1.

If $|u_{1}-u_{2}|=|u_{1}+u_{2}|$ then $u_{1}=0$ or $u_{2}=0$.

  2. 2.

If $|u_{i}|=|v_{i}|$, and $|u_{i}+u_{j}|=|v_{i}+v_{j}|$ for all $i,j$ then
$(u_{1},u_{2},\ldots,u_{k})=\pm(v_{1},v_{2},\ldots,v_{k})$.

###### Proof.

For the first part we have

$\displaystyle|u_{1}-u_{2}|=|u_{1}+u_{2}|$ $\displaystyle\iff
u_{1}-u_{2}=u_{1}+u_{2}\text{ or }u_{1}-u_{2}=-u_{1}-u_{2}$ $\displaystyle\iff
2u_{2}=0\text{ or }2u_{1}=0$ $\displaystyle\iff u_{2}=0\text{ or }u_{1}=0$
$\displaystyle\text{(since $q$ is odd)}.$

For the second part we note that the case of $k=1$ is patently true, so let
$k=2$. If either $u_{1}=0$ or $u_{2}=0$ then the result holds, so assume
otherwise. The hypothesis becomes $v_{1}=\pm u_{1}$, $v_{2}=\pm u_{2}$, and

$|u_{1}+u_{2}|=|v_{1}+v_{2}|=|\pm u_{1}\pm u_{2}|,$

so from part 1 we obtain $(u_{1},u_{2})=\pm(v_{1},v_{2})$. Induction completes
the proof. ∎

We now show that MWS Lee codes exist for all $q$ and $k$.

######  Theorem 4.7.

$L_{\mathcal{L}}(k,q)=\frac{q^{k}-1}{2}$, and $\displaystyle
M(\mathcal{L},k,q)\leq\frac{(\frac{q+1}{2})^{2k^{2}-3k+1}-1}{\frac{q+1}{2}-1}$.

###### Proof.

For $q=2$ see [1]. Assume $q>2$. Our proof is constructive. Let
$\alpha=\frac{q+1}{2}$ and define the generator matrix $G(k,q)$ by

$G_{k,q}=\left[e_{1}\left|(e_{2})^{\alpha}\left|\cdots\left|(e_{k})^{\alpha^{k-1}}\left|(e_{1}+e_{2})^{\alpha^{k}}\left|(e_{1}+e_{2}+e_{3})^{\alpha^{k+1}}\left|\cdots\left|(e_{1}+e_{2}+\cdots+e_{k})^{\alpha^{2k-2}}\right.\right.\right.\right.\right.\right.\right.\right]$

Recall, $e_{i}$ denotes the unit column vector with $1$ in entry $i$ and
exponents correspond to repetition numbers. The length of $\mathcal{C}$ is
$n=\sum_{i=0}^{t}\alpha^{i}$ where $t=2k-2$. From the form of $G_{k,q}$ it
follows that the Lee weight of any codeword $uG_{k,q}$ may be expressed in
base $\alpha$ as

$w_{\mathcal{L}}(uG_{k,q})=|u_{1}|+|u_{2}|\alpha+|u_{3}|\alpha^{3}+\cdots+|u_{1}+u_{2}+\cdots+u_{k}|\alpha^{2k-2}.$

If two codewords $uG_{k,q}$ and $vG_{k,q}$ have the same weight then
$|u_{i}|=|v_{i}|$, for all $i$ and $|u_{1}+u_{2}|=|v_{1}+v_{2}|$. From the
Lemma 4.6 we obtain $(u_{1},u_{2})=\pm(v_{1},v_{2})$. Likewise, since
$|u_{1}+u_{2}+u_{3}|=|v_{1}+v_{2}+v_{3}|$ and $|u_{1}+u_{2}|=|v_{1}+v_{2}|$,
Lemma 4.6 gives $(u_{1},u_{2},u_{3})=\pm(v_{1},v_{2},v_{3})$. Continuing
inductively we obtain $\mathcal{C}$ is $\mathcal{L}$-MWS.

∎

Example: If $k=2$ and $q=5$ then the generator matrix as in the proof of
Theorem 4.7 is

$G_{2,5}=\left[\begin{array}[]{c}1\\\ 0\end{array}\begin{array}[]{c}0\\\
1\end{array}\begin{array}[]{c}0\\\ 1\end{array}\begin{array}[]{c}0\\\
1\end{array}\begin{array}[]{c}1\\\ 1\end{array}\begin{array}[]{c}1\\\
1\end{array}\begin{array}[]{c}1\\\ 1\end{array}\begin{array}[]{c}1\\\
1\end{array}\begin{array}[]{c}1\\\ 1\end{array}\begin{array}[]{c}1\\\
1\end{array}\begin{array}[]{c}1\\\ 1\end{array}\begin{array}[]{c}1\\\
1\end{array}\begin{array}[]{c}1\\\ 1\end{array}\right].$

###  4.4 Lee FWS Codes

Recall from the definition that for $q$ odd, an $[n,k]_{q}$-code is
$\mathcal{L}$-FWS if $|w_{\mathcal{L}}(\mathcal{C})|=n\cdot\frac{q-1}{2}$.
Table 1 provides some examples of FWS codes for small values of $q$ and $k$.
Based simply on the properties of a component-wise metric we get an initial
upper bound on the length of $\mathcal{L}$-FWS codes. Indeed, from part 1 of
Lemma 2.5 and Proposition 2.2 we obtain $n\leq\frac{q^{k}-1}{q-1}$. By
considering Theorem 3.2 we can get a significantly better bound than this.

######  Lemma 4.8.

There exists an $[n,k]_{q}$ $\mathcal{L}$-FWS code if and only if

$n\leq\sum\limits_{i=0}^{k-1}\left(\frac{q+1}{2}\right)^{i}\;\;\;\;\left(=\frac{\left(\frac{q+1}{2}\right)^{k}-1}{\left(\frac{q+1}{2}\right)-1}\right).$

In particular
$N(\mathcal{L},k,q)=\frac{\left(\frac{q+1}{2}\right)^{k}-1}{\left(\frac{q+1}{2}\right)-1}.$

###### Proof.

Follows from Theorem 3.2 by observing that for the Lee metric
$m=\Delta=\lceil(q-1)/2\rceil$. ∎

Comparing the bounds in the Lemmata 4.8 and 4.5 we obtain the following non-
existence result.

######  Corollary 4.9.

There exists an $[n,k]_{q}$ code that is both $\mathcal{L}$-MWS and
$\mathcal{L}$-FWS if and only if $q=2$ .

###### Proof.

The Hamming and Lee metrics are the same for binary codes, so for the binary
case see [1]. The case $q>3$ follows from Lemma 4.8 and Corollary 3.4. ∎

###  4.5 Manhattan MWS Codes

If $u\in\mathbb{F}_{q}^{n}$ is a nonzero vector then $|\langle u\rangle|=q$,
so $|w_{\mathcal{M}}(\langle u\rangle)|\leq q-1$. One may show that strict
inequality may occur only if $q$ is a divisor of $w_{\mathcal{M}}(u)$. As
such, an immediate bound on the $\mathcal{M}$-weight spectrum of a linear code
is

$L_{\mathcal{M}}(k,q)\leq q^{k}-1.$ (15)

It is clear that for $e_{1}\in\mathbb{F}_{q}^{n}$, $|w_{M}(\langle
e_{1}\rangle)|=q-1$, so for $n\geq 1$ we have

$L_{M}(n,1,q)=L_{M}(1,q)=q-1.$ (16)

In [26] values of $L_{M}(n,k,q)$ were explicitly computed for $q=3,5$ and
$k=2$, these values appear in Table 2. Recall that for $q=2$ the Manhattan,
Hamming, and Lee weights coincide, so we refer to section 4.2 for the binary
case.

Table 2: Optimal bounds for for the Manhattan Weight Bound |  $\mathcal{M}$-MWS |  $\mathcal{M}$-FWS
---|---|---
$L_{\mathcal{M}}(3,2,3)=6$ | No | Yes
$L_{\mathcal{M}}(4,2,3)=8$ | Yes | Yes
$L_{\mathcal{M}}(3,2,5)=12$ | No | Yes
$L_{\mathcal{M}}(4,2,5)=16$ | No | Yes
$L_{\mathcal{M}}(5,2,5)=20$ | No | Yes
$L_{\mathcal{M}}(6,2,5)=24$ | Yes | Yes

Since the Manhattan weight is a coordinate-wise weight function the maximum
weight of an $n$-vector is $n(q-1)$. If $\mathcal{C}$ is an $[n,k]_{q}$ code
then $|w_{\mathcal{M}}(\mathcal{C})|\leq\max w_{\mathcal{M}}(\mathcal{C})\leq
n(q-1)$, giving the following.

######  Lemma 4.10.

If $\mathcal{C}$ is an $[n,k]_{q}$ code then
$n\geq\frac{|w_{\mathcal{M}}(\mathcal{C})|}{q-1}$. In particular, if
$\mathcal{C}$ is an $[n,k]_{q}$ $\mathcal{M}$-MWS code then
$n\geq\frac{L_{\mathcal{M}}(k,q)}{q-1}$ with equality if and only if
$w_{\mathcal{M}}(\mathcal{C})=\\{1,2,\ldots,n(q-1)\\}$.

######  Theorem 4.11.

For $q$ prime and $k\geq 1$,

$L_{\mathcal{M}}(k,q)=q^{k}-1,\text{ and
}M(\mathcal{M},k,q)=\frac{q^{k}-1}{q-1}.$

###### Proof.

For $q=2$ see Table 2. Assume $q>2$. Our proof is constructive. Define the
generator matrix $G(k,q)$ by

$G_{k,q}=\left[e_{1}\left|(e_{2})^{q}\left|\cdots\left|(e_{k})^{q^{k-1}}\right.\right.\right.\right]$

An argument entirely similar to that in the proof of Theorem 4.7 shows that
two codewords $uG_{k,q}$ and $vG_{k,q}$ have the same weight if and only if
$u=v$, whence $\mathcal{C}$ is $\mathcal{M}$-MWS. For the second part we
observe that the length of the code generated by $G$ is $\frac{q^{k}-1}{q-1}$
and appeal to Lemma 4.10.
∎

###  4.6 Manhattan FWS codes

It is readily verified that $w_{\mathcal{M}}(F^{n}_{q})=n(q-1)$, so
$\mathcal{M}$-FWS codes are those with $w_{\mathcal{M}}(\mathcal{C})=n(q-1)$.
Table 2 exhibits examples of such codes for small $k,q$. The following shows
that in contrast to MWS codes, we may completely determine the optimal lengths
of FWS codes.

######  Theorem 4.12.

There exists an $[n,k]_{q}$ $\mathcal{M}$-FWS code if and only if $k\leq
n\leq\frac{q^{k}-1}{q-1}$. In particular,

$N(\mathcal{M},k,q)=\frac{q^{k}-1}{q-1}.$

###### Proof.

That $n\leq\frac{q^{k}-1}{q-1}$ follows directly from part 1 of Lemma 2.5 and
Proposition 2.2 by observing that $m=q-1=\Delta$. The codes with generator
$G_{k,q}$ as described in the proof of Theorem 4.11 are $[n,k]_{q}$-codes with
$w_{\mathcal{M}}(\mathcal{C})=\frac{q^{k}-1}{q-1}=n$ and are thus
$\mathcal{M}$-FWS.
Generator matrices obtained by deleting columns of $G_{k,q}$ in the manner
described in the proof of Theorem 3.3 show the existence of $\mathcal{M}$-FWS
codes for $k\leq n\leq\frac{q^{k}-1}{q-1}$. ∎

##  5 Conclusion, future work, and open problems

Here we have investigated the combinatorial problem of maximizing the number
of distinct weights that a linear code may obtain. The literature relating to
this problem has thus far focused on FWS and MWS codes with respect to Hamming
weight. Under the Hamming metric, FWS codes are necessarily “short”, and $MWS$
codes are necessarily “long”. The existence question and in particular the
maximum length $N(H,k,q)$ of an $[n,k]_{q}$ FWS code has been determined.
However, the determination of $M(H,k,q)$, the minimum length of an $[n,k]_{q}$
MWS code remains an open problem.
Here, we have generalized to the setting of component-wise weight functions,
with a particular focus on the Lee, and Manhattan type weights. For a certain
class of component-wise weight functions (which subsumes the Hamming, Lee, and
Manhattan weight functions) we determine the necessary and sufficient
conditions for the existence of $\mu$-FWS codes (Theorem 3.3). We establish
through construction the existence of $\mu$-MWS codes for all $q,k$ (Theorem
4.7 ), and thus an upper bound on $M(\mathcal{L},k,q)$. Computational examples
show our bound on $M(\mathcal{L},k,q)$ is not generally tight, thus the
determination of $M(\mathcal{L},k,q)$ remains an open problem. On the other
hand, for Manhattan weights we were able to determine both
$N(\mathcal{M},k,q)$ and $M(\mathcal{M},k,q)$ and provided a construction
showing that in fact $N(\mathcal{M},k,q)=M(\mathcal{M},k,q)$ (Theorem 4.12).
The determination of $M(H,k,q)$, $M(\mathcal{L},k,q)$, and more generally
$M(\mu,k,q)$ (for an arbitrary component-wise weight function $w_{\mu}$ on
$\mathbb{F}_{q}^{n}$) may be an attractive endeavour for the community.

## References

  * [1] Tim L. Alderson.  A note on full weight spectrum codes.  Trans. Comb., 8(3):15–22, 2019.
  * [2] Tim L. Alderson and Alessandro Neri.  Maximum weight spectrum codes.  Advances in Mathematics of Communications, 13(1):101–119, 2018\.
  * [3] C. Araujo, I. Dejter, and P. Horak.  A generalization of Lee codes.  Designs, Codes and Cryptography. An International Journal, 70(1-2):77–90, 2014.
  * [4] Jaakko Astola.  On perfect Lee-codes over small alphabets of odd cardinality.  In The very knowledge of coding, pages 40–42. Univ. Turku, Turku, 1987.
  * [5] Jaakko T. Astola.  Concatenated codes for the Lee metric.  Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 28(5):778–779, 1982.
  * [6] Jaakko T. Astola, Pekka Astola, Radomir S. StankoviÄ‡, and Ioan Tabus.  Algebraic and combinatorial methods for reducing the number of variables of partially defined discrete functions.  pages 167–172, Novi Sad, Serbia, 2017. IEEE.
  * [7] Elwyn Berlekamp.  Algebraic coding theory.  World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, revised edition, 2015.
  * [8] Elwyn R. Berlekamp.  Negacyclic codes for the Lee metric.  In Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967), pages 298–316. Univ. North Carolina Press, Chapel Hill, N.C., 1969.
  * [9] Mario Blaum, Jehoshua Bruck, and Alexander Vardy.  Interleaving schemes for multidimensional cluster errors.  Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 44(2):730–743, 1998.
  * [10] J. Chung Yaw Chiang and Jack K. Wolf.  On channels and codes for the Lee metric.  Information and Control, 19:159–173, 1971.
  * [11] Gerard D Cohen and Ludo Tolhuizen.  Maximum weight spectrum codes with reduced length.  CoRR, June 2018.
  * [12] Philippe Delsarte.  Four fundamental parameters of a code and their combinatorial significance.  Information and Control, 23(5):407–438, 1973.
  * [13] Tuvi Etzion.  Product constructions for perfect Lee codes.  Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 57(11):7473–7481, 2011.
  * [14] Tuvi Etzion, Alexander Vardy, and Eitan Yaakobi.  Dense error-correcting codes in the lee metric.  pages 1–5, Dublin, Ireland, 2010. IEEE.
  * [15] Tuvi Etzion, Alexander Vardy, and Eitan Yaakobi.  Coding for the Lee and Manhattan metrics with weighing matrices.  Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 59(10):6712–6723, 2013.
  * [16] Tuvi Etzion and Eitan Yaakobi.  Error-correction of multidimensional bursts.  Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 55(3):961–976, 2009.
  * [17] Ernst Gabidulin.  A brief survey of metrics in coding theory.  In Michel Petitjean Michel Deza and Krassimir Markov, editors, Mathematics of Distances and Applications (MDA), pages 66–84. 2012.
  * [18] S. W. Golomb and L. R. Welch.  Perfect codes in the Lee metric and the packing of polyominoes.  SIAM Journal on Applied Mathematics, 18:302–317, 1970.
  * [19] Abdelfattah Haily and Driss Harzalla.  On binary linear codes whose automorphism group is trivial.  Journal of Discrete Mathematical Sciences and Cryptography, 18(5):495–512, 2015.
  * [20] P. Horak.  On perfect Lee codes.  Discrete Mathematics, 309(18):5551–5561, 2009.
  * [21] Peter Horak and Dongryul Kim.  50 years of the Golomb-Welch conjecture.  Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 64(4, part 2):3048–3061, 2018.
  * [22] Anxiao Jiang, Moshe Schwartz, and Jehoshua Bruck.  Correcting charge-constrained errors in the rank-modulation scheme.  Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 56(5):2112–2120, 2010.
  * [23] C. Y. Lee.  Some properties of nonbinary error-correcting codes.  IRE Trans., IT-4:77–82, 1958.
  * [24] Jessie MacWilliams.  A theorem on the distribution of weights in a systematic code.  The Bell System Technical Journal, 42(1):79–94, 1963.
  * [25] Alessio Meneghetti and Wrya K. Kadir.  Characterisation of the parameters of maximum weight spectrum codes according to their spread.  June 2020.
  * [26] Benjamin Morine.  MWS and FWS codes in the Lee and Manhatten metrics.  MSc. thesis, University of New Brunswick, Saint John, NB, July 2022\.
  * [27] Alon Orlitsky.  Interactive communication of balanced distributions and of correlated files.  SIAM Journal on Discrete Mathematics, 6(4):548–564, 1993.
  * [28] K. A. Post.  Nonexistence theorems on perfect Lee codes over large alphabets.  Information and Control, 29:369–380, 1975.
  * [29] Claudio Qureshi.  On the non-existence of linear perfect Lee codes: the Zhang-Ge condition and a new polynomial criterion.  European Journal of Combinatorics, 83:103022, 21, 2020.
  * [30] Ron Roth.  Introduction to Coding Theory.  Cambridge University Press, New York, NY, USA, 2006.
  * [31] Ron M. Roth and Paul H. Siegel.  Lee-metric BCH codes and their application to constrained and partial-response channels.  Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 40(4):1083–1096, 1994.
  * [32] Chandra Satyanarayana.  Lee metric codes over integer residue rings.  Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 25(2):250–254, 1979.
  * [33] Kai-Uwe Schmidt.  Complementary sets, generalized Reed-Muller codes, and power control for OFDM.  Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 53(2):808–814, 2007.
  * [34] M. Shi, X. Li, A. Neri, and P. Sole.  How many weights can a cyclic code have ?  IEEE Transactions on Information Theory, 2019.
  * [35] Minjia Shi, Alessandro Neri, and Patrick Solé.  How many weights can a quasi-cyclic code have?  Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 66(11):6855–6862, 2020.
  * [36] Minjia Shi, Hongwei Zhu, Patrick Solé, and Gérard D. Cohen.  How many weights can a linear code have?  Designs, Codes and Cryptography, 87(1):87–95, 2019.


# Generative Relevance Feedback and Convergence of Adaptive Re-Ranking:
University of Glasgow Terrier Team at TREC DL 2023

Andrew Parry<EMAIL_ADDRESS>1234-5678-9012 University of
GlasgowGlasgowUK ,  Thomas Jänich<EMAIL_ADDRESS>University
of GlasgowGlasgowUK ,  Sean MacAvaney  and  Iadh Ounis
<EMAIL_ADDRESS>University of GlasgowGlasgowUK

###### Abstract.

This paper describes our participation in the TREC 2023 Deep Learning Track.
We submitted runs that apply generative relevance feedback from a large
language model in both a zero-shot and pseudo-relevance feedback setting over
two sparse retrieval approaches, namely BM25 and SPLADE. We couple this first
stage with adaptive re-ranking over a BM25 corpus graph scored using a
monoELECTRA cross-encoder. We investigate the efficacy of these generative
approaches for different query types in first-stage retrieval. In re-ranking,
we investigate operating points of adaptive re-ranking with different first
stages to find the point in graph traversal where the first stage no longer
has an effect on the performance of the overall retrieval pipeline. We find
some performance gains from the application of generative query reformulation.
However, our strongest run in terms of P@10 and nDCG@10 applied both adaptive
re-ranking and generative pseudo-relevance feedback, namely uogtr_b_grf_e_gb.

##  1\. Introduction

The University of Glasgow Terrier team participated in the TREC 2023 Deep
Learning track to further explore new generative approaches to retrieval and
validate existing approaches by a deeper exploration of their performance. We
investigate generative approaches to relevance feedback utilising both
generative query reformulation (Gen-QR) and pseudo-relevance feedback (Gen-
PRF) (Wang et al., 2023) as well as conducting a further evaluation of
adaptive re-ranking (MacAvaney et al., 2022) on the MS MARCO-v2 corpus (Nguyen
et al., 2016). Both of these approaches overcome the lexical mismatch problem
of many classic retrieval approaches, albeit in different ways. A re-ranker is
normally constrained by the texts that could be retrieved by a first-stage
model. Generative relevance feedback alleviates this problem by adding
expansion terms to the query text attempting to improve the recall of first-
stage retrieval models. Adaptive re-ranking instead expands the initial
ranking with candidate documents found by traversal of a corpus graph to find
the nearest neighbours of highly ranked texts.

We explored the following research questions: (1) Can we validate the
performance improvements from generative relevance feedback on a different
test set and downstream ranking model? (2) What type of queries are most
improved or harmed by generative relevance feedback? and (3) Can the use of a
sufficiently large corpus graph allow a lightweight first-stage ranker to
converge to identical performance of a first-stage learned retrieval function?

To answer these questions, we used our PyTerrier Information Retrieval (IR)
toolkit (Ounis et al., 2005), which allows for the composition of both lexical
and neural retrieval components into flexible pipelines. We apply two forms of
generative relevance feedback over two sparse first-stage ranking models.
Moreover, we apply adaptive re-ranking with monoELECTRA (Pradeep et al., 2022)
in this setting to assess the need for complex first-stage pipelines (learned
models or weighted expansion terms) given a sufficiently large corpus graph.
Specifically, we use a large search budget of 5000 over a 32 nearest-neighbour
BM25 corpus graph.

The structure of the remainder of this paper is as follows: Section 2 details
the notation of retrieval pipelines composed in PyTerrier. Section 3 describes
the methods used in our experiments and the particular models used in these
methods. We then outline our experiment setup. Section 4 summarises our
submitted baseline and group runs. In Section 5 we present our results and
analysis before providing some concluding remarks in Section 6.

##  2\. Pyterrier Retrieval Pipelines

Our experiments and submitted runs for the TREC 2023 Deep Learning Track have
been built upon PyTerrier, Python bindings for the Terrier search engine
(Ounis et al., 2005). The key abstraction of PyTerrier is the Transformer
object, of which all retrieval components are a sub-class. Using Pandas
dataframes, a transformer object transforms one dataframe to another. To
create multi-stage retrieval pipelines, PyTerrier overloads the bitwise shift
operators (<< and >>) to allow the chaining of multiple transformers into a
single component where the output of each transformer is directly passed into
the next sequentially.

We express all ranking features described in the rest of this paper as
pipelines of transformers using this sequential operator. For more information
about the PyTerrier platform and the operators’ flexibility, we refer the
reader to the documentation, which can be found at
https://pyterrier.readthedocs.io/en/latest/.

##  3\. Methods

In this section, we outline the background knowledge of Generative Relevance
Feedback (Section 3.1) and Adaptive Re-Ranking (Section 3.2), followed by our
experimental setup in Section 3.3.

###  3.1. Generative Query Reformulation & Pseudo-Relevance Feedback

Generative query reformulation (Gen-QR) and generative pseudo-relevance
feedback (Gen-PRF) are mechanisms for the expansion of query terms in ranking
pipelines (Wang et al., 2023). Originally proposed with both a weakly
supervised fine-tuned variant as well as a zero-shot prompted instruction-
tuned variant, we only cover the latter as we do not utilise any fine-tuned
checkpoints in our generative expansion stage.

Recent developments in language model pre-training (Radford et al., 2017;
Touvron et al., 2023; Taori et al., 2023) have led to a new paradigm in
language modelling known as prompting (Brown et al., 2020) in which a task is
described with some input in a zero-shot setting to a language model. Due to
extensive pre-training and additional fine-tuning on instruction style inputs
(Chung et al., 2022), these models can perform a task that has not been
observed in training data (Brown et al., 2020). This zero-shot generalisation
poses some benefits in retrieval as the labelling of ground truth by experts
for neural models is an expensive process (Althammer et al., 2023).

Following Wang et al. (2023), we define query reformulation as a process
$\mathcal{P}$ which, given a user query $q^{0}$, reformulates it as $q^{r}$
potentially conditioned on some additional context to improve the retrieval
effectiveness of the downstream retrieval pipeline.

(1) $q^{r}=\mathcal{P}(q^{0},\dots)$

In equation 1, $\dots$ is any additional context, such as an initial ranking
in the case of pseudo-relevance feedback. Generative relevance feedback
prompts a large language model (LLM) to suggest expansion terms to improve the
performance of a retrieval model 111Prompt for Gen-PRF: Improve the search
effectiveness by suggesting expansion terms for the query:{input_query}, based
on the given context information: {context}. In the case of Gen-QR, no
additional context is supplied to the generative model. However, when applying
Gen-PRF, a ranking of $K$ documents from a corpus $D$ by some score function
$s$, {$s(d,q^{0});\forall d\in D$} is provided as topical context for the
expansion and/or re-weighting of query terms.

The authors propose multiple pruning criteria to reduce the context size
provided to the Gen-PRF model. We use the approach Top-P and outline its
method as follows. To select $M$ context pieces from documents in an initial
ranking $R$ (this process is simplified for passage ranking as we do not
further split passages), each document $d$ is split into passages. The context
$C$ of length $M$ is then chosen as follows:

(2) $C_{\textit{Top-P}}(R,q^{0})=\operatorname*{arg\,max}_{p\in R}^{M}\ s\
s(p,q^{0})$

Example pipelines are as follows: Gen-QR with FLAN-T5 can be applied before
BM25 retrieval, re-ranked with monoELECTRA:

(3) $\textsf{QR}(\textsf{FLAN-T5})>>\textsf{BM25}>>\textsf{monoELECTRA}$

Where in Equation 3, $\textsf{QR}(\textsf{FLAN-T5})$ is the generative
reformulation of a query using FLAN-T5. Alternatively, Top-P context Gen-PRF
with FLAN-T5 can be applied to a first-stage retrieval by BM25, re-ranked by
monoELECTRA:

(4)
$\textsf{BM25}>>\textsf{PRF}_{\textit{Top-P}}(\textsf{FLAN-T5})>>\textsf{BM25}>>\textsf{monoELECTRA}$

###  3.2. Graph-based Adaptive Re-Ranking (GAR)

We utilise graph-based adaptive re-ranking (GAR), which is an efficient
approach to improving re-ranking performance (MacAvaney et al., 2022). GAR
works within a cascading retrieval pipeline in which new candidate documents
are found by traversing a nearest-neighbour graph $G=(V,E)$ where each node in
$V$ represents a document in the corpus. Each edge in $E$ is weighted by some
heuristic, either a lexical or semantic similarity score between two nodes.
Online latency is unaffected by the chosen number of nearest neighbours.
However, due to the graph structure’s quadratic time and space complexity, we
limit the number of nearest neighbours to a small number and prune by sorting
edge weights in descending order. An online traversal of this corpus graph is
performed by scoring the nearest neighbours of the initial ranking using some
score model $S$. The highest-ranking document neighbours from the current
corpus graph frontier are added to a re-ranking pool. The initial pool is then
revisited to update the graph frontier. This process alternates between
scoring pools until a predefined compute budget is met.

An example pipeline is as follows: A first-stage BM25 retrieval is adaptively
re-ranked using GAR with a BM25 corpus graph and a monoELECTRA scoring model:

(5) $\textsf{BM25}>>\textsf{GAR}_{\textsf{BM25}}(\textsf{monoELECTRA})$

Where in Equation 5, $\textsf{GAR}_{\textsf{BM25}}(\textsf{monoELECTRA})$
represents adaptive re-ranking over a BM25 corpus graph using monoELECTRA.

###  3.3. Experimental Setup

We use the following retrieval components, grouped into methods that perform
retrieval or re-ranking and methods that perform query expansion in the form
of query reformulation (QR), pseudo-relevance feedback (PRF), or adaptive re-
ranking (GAR).

#### Retrieval:

  * •

DPH (Amati, 2006) & BM25 (Robertson et al., 1994): Lexical retrieval from a
Terrier inverted index over the msmarco-passage-v2 corpus.

  * •

SPLADE222naver/splade-cocondenser-ensembledistil: A distilled SPLADE++ learned
sparse model (Formal et al., 2021b, a).

  * •

monoELECTRA333crystina-z/monoELECTRA_LCE_nneg31: A cross-encoder pre-trained
with ELECTRA-style objectives (Clark et al., 2020) and fine-tuned with 31
localized negatives (Pradeep et al., 2022).

#### Query Expansion:

  * •

Bo1 : Pseudo-relevance feedback using the DFR Bo1 model (Amati, 2003) over a
Terrier index.

  * •

Gen-QR (QR(LLM)): Using the generative encoder-decoder
FLAN-T5444google/flant5-xxl (Chung et al., 2022) to provide zero-shot query
expansion terms with term weights controlled uniformly by the parameter
$\beta=0.5$. In all cases, we use tuned generation hyperparameters from Wang
et al. (2023).

  * •

Gen-PRF (PRFC(LLM)): Using the generative encoder-decoder FLAN-T5 to provide
query expansion terms using a first-stage ranking as context $C$. Term weights
are again controlled uniformly by the parameter $\beta=0.5$.

  * •

GAR${}_{G}(S)$ : Graph-based Adaptive Re-Ranking using corpus graph $G$ and
scoring function $S$ (MacAvaney et al., 2022). We use a BM25-based corpus
graph with a re-ranking budget of 5000 and 32 nearest neighbours.

All experiments were conducted in PyTerrier using the ir-datasets package for
corpora and additional test sets (DL-2021 (Craswell et al., 2021), DL-2022
(Craswell et al., 2022)). PyTerrier is available from
https://github.com/terrier-org/pyterrier and the implementation of monoELECTRA
is available from https://github.com/terrierteam/pyterrier_dr. The
implementation of GAR is available from
https://github.com/terrierteam/pyterrier_adaptive and the implementation of
Generative QR and PRF are available from https://github.com/Parry-
Parry/pyterrier_GenerativeQR. We perform all experiments on a de-duped
msmarco-v2 corpus due to the added benefits for GAR corpus graph traversal
preventing duplicate nearest neighbours. We then added duplicates before
submission. All experiment code is available from https://github.com/Parry-
Parry/terrier_trec_2023.

##  4\. Submitted Runs

We submitted six group runs to the passage ranking task. We also submitted
five baseline runs. We did not participate in the document ranking task.

###  4.1. Baseline Runs

As baseline runs submitted to the 2023 Deep Learning passage ranking track, we
chose two sparse retrieval models, one learned and one non-parametric model,
one sparse retrieval model with query expansion and two sparse retrieval
models re-ranked by a monoELECTRA cross-encoder. All baselines are summarised
as follows:

  * •

uofg_tr_dph: Performs DPH retrieval on our passage sparse index.

  * •

uofg_tr_s : Performs SPLADE retrieval retrieval on an msmarco-passage-v2
SPLADE learned sparse index.

  * •

uofg_tr_dph_bo1: Performs Bo1 divergence from randomness query expansion over
DPH retrieval on our passage sparse index.

  * •

uofg_tr_be: Re-Ranks a first-stage BM25 retrieval using a monoELECTRA cross-
encoder.

  * •

uofg_tr_se: Re-Ranks a first-stage SPLADE retrieval using monoELECTRA.

###  4.2. Submitted Group Runs

For the 2023 Deep Learning passage ranking track, we submitted the following
three group runs:

  * •

uofg_tr_se_gb: Performs SPLADE retrieval, adaptively re-ranked by monoELECTRA
and a BM25 graph.

  * •

uofg_tr_qr_be_gb: Performs Generative Query Reformulation before BM25
retrieval, adaptively re-ranked by monoELECTRA and a BM25 graph.

  * •

uofg_tr_b_grf_e_gb: Performs Generative Relevance Feedback over a first-stage
BM25 retrieval re-ranked by monoELECTRA and a BM25 graph.

###  4.3. Additional Runs

For the 2023 Deep Learning passage ranking track, we submitted the following
additional three runs:

  * •

uofg_tr_qr_be: Performs Generative Query Reformulation before BM25 retrieval
re-ranked by monoELECTRA.

  * •

uofg_tr_b_grf_e: Performs Generative Relevance Feedback over a first-stage
BM25 retrieval re-ranked by monoELECTRA.

  * •

uofg_tr_be_gb: Performs BM25 retrieval, adaptively re-ranked by monoELECTRA
and a BM25 graph.

##  5\. Results & Analysis

Table 1. Results on the TREC Deep Learning 2023 Passage Ranking task. Best and Median performance is an aggregate over the best-performing model for each topic. Runs that outperform the median are denoted with $\diamond$. The strongest performance in each metric is denoted bold, the second strongest is underlined. Run ID | Pipeline | P@10 | NDCG@10 | MRR | MAP | R@100
---|---|---|---|---|---|---
Best (Per-topic aggregate) | $0.7000\phantom{\diamond}$ | $0.7892\phantom{\diamond}$ | $0.9939\phantom{\diamond}$ | $0.3839\phantom{\diamond}$ | -
Median (Per-topic aggregate) | $0.4085\phantom{\diamond}$ | $0.5329\phantom{\diamond}$ | $0.7803\phantom{\diamond}$ | $0.2159\phantom{\diamond}$ | -
Baseline Runs
uogtr_dph | DPH | $0.1805\phantom{\diamond}$ | $0.2825\phantom{\diamond}$ | $0.4320\phantom{\diamond}$ | $0.0840\phantom{\diamond}$ | $0.2310\phantom{\diamond}$
uogtr_s | SPLADE | $0.3549\phantom{\diamond}$ | $0.4706\phantom{\diamond}$ | $0.6725\phantom{\diamond}$ | $0.1925\phantom{\diamond}$ | $0.4144\phantom{\diamond}$
uogtr_dph_bo1 | DPH >> Bo1 >> DPH | $0.1317\phantom{\diamond}$ | $0.2377\phantom{\diamond}$ | $0.3613\phantom{\diamond}$ | $0.0600\phantom{\diamond}$ | $0.1288\phantom{\diamond}$
uogtr_be | BM25 >> monoELECTRA | $0.3939\phantom{\diamond}$ | $0.5227\phantom{\diamond}$ | $0.7881\diamond$ | $0.1940\phantom{\diamond}$ | $0.3558\phantom{\diamond}$
uogtr_se | SPLADE >> monoELECTRA | $0.4256\diamond$ | $0.5364\diamond$ | $0.7938\diamond$ | $\underline{0.2348}\diamond$ | $\underline{0.4531}\phantom{\diamond}$
Additional Runs
uogtr_qr_be | QR(FLAN-T5) >> BM25 >> monoELECTRA | $0.3963\phantom{\diamond}$ | $0.5316\phantom{\diamond}$ | $\underline{0.8018}\diamond$ | $0.1994\phantom{\diamond}$ | $0.3668\phantom{\diamond}$
uogtr_b_grf_e | BM25 >> PRF${}_{\textit{Top-P}}$(FLAN-T5) >> BM25 >> monoELECTRA | $0.4122\diamond$ | $0.5376\diamond$ | $0.7790\phantom{\diamond}$ | $0.1996\phantom{\diamond}$ | $0.3770\phantom{\diamond}$
uogtr_be_gb | BM25 >> GARBM25(monoELECTRA) | $0.4159\diamond$ | $0.5451\diamond$ | $\textbf{0.8046}\diamond$ | $0.2285\diamond$ | $0.4240\phantom{\diamond}$
Group Runs
uogtr_se_gb | SPLADE >> GARBM25(monoELECTRA) | $\underline{0.4293}\diamond$ | $0.5394\diamond$ | $0.7934\diamond$ | $\textbf{0.2401}\diamond$ |  0.4706
uogtr_qr_be_gb | QR(FLAN-T5) >> BM25 >> GARBM25(monoELECTRA) | $0.4244\diamond$ | $\underline{0.5488}\diamond$ | $0.7953\diamond$ | $0.2315\diamond$ | $0.4248\phantom{\diamond}$
uogtr_b_grf_e_gb | BM25 >> PRF${}_{\textit{Top-P}}$(FLAN-T5) >> BM25 >> GARBM25(monoELECTRA) | $\textbf{0.4305}\diamond$ | $\textbf{0.5489}\diamond$ | $0.7885\diamond$ | $0.2314\diamond$ | $0.4328\phantom{\diamond}$

In Table 1, we present the performance of each of our runs contrasting group
runs with baseline runs555Due to an issue with indexing, expansion terms
degrade DPH (uogtr_dph_bo1). and the Best and Median results averaged across
all judged topics. Across all metrics, our group runs improve over the median,
with our additional runs also improving over the median in some cases, notably
when adaptive re-ranking is applied with monoELECTRA over BM25 (uogtr_be_gb).

#### Generative methods versus SPLADE

Our SPLADE baseline re-ranked with monoELECTRA (uogtr_se) outperforms all runs
with BM25 first stages in terms of Recall@100 and MAP even when adaptive re-
ranking is applied and outperforms all Gen-QR runs in terms of nDCG@10. As
generative relevance feedback is a completely zero-shot method, this is not
unexpected and consistent performance improvements are observed across all
metrics. Comparing uogtr_be and uogtr_qr_be, the diversification of query
terms by Gen-QR is effective in improving first-stage lexical ranking models
but fails to outperform the expansions of the learned SPLADE model. We observe
improvements over SPLADE when applying Gen-PRF in nDCG@10, MAP, and R@100,
suggesting that the context provided from the first-stage ranking is
sufficient to ground expansion terms to suitable topics.

#### GAR is a stronger standalone method

Contrasting the use of generative relevance feedback (uogtr_qr_be and
uogtr_b_grf_e) against the use of GAR (uogtr_be_gb) we observe that GAR alone
provides stronger candidates to the re-ranking stage than Gen-QR or Gen-PRF
improving both precision and recall based metrics. Furthermore, measured by 4
of 5 metrics, the use of GAR is more effective in improving performance than
the use of SPLADE expansions. We propose that this is due to the rank bias of
the GAR algorithm, as candidate texts are chosen from the neighbourhood of the
highest-ranking documents aligning well with the cluster hypothesis in
contrast to the zero-shot expansion terms provided by generative relevance
feedback. However, the computational expense of GAR is determined by a compute
budget, and further research is warranted to find the Pareto-optimal approach
for smaller budgets.

#### Gen-PRF with GAR is most effective

Our most effective run by P@10 and nDCG@10 uses Gen-PRF and adaptive re-
ranking. We observe improvements in nDCG@10 over SPLADE expansions (0.5489
versus 0.5394) when using GAR, suggesting that the diversification provided by
generative expansion terms can be more effective in providing a strong initial
pool for GAR corpus graph traversal. We note that SPLADE-based runs (uogtr_se
and uogtr_se_gb) have greater recall and MAP than any generative relevance
feedback pipelines. However, the zero-shot nature of these approaches coupled
with user tendencies to only interact with the top 10 results of a search
(Kelly and Azzopardi, 2015) reinforces generative relevance feedback as a
compelling approach compared to learned first-stage models. Furthermore,
addressing RQ (1), we find that Gen-QR and Gen-PRF generalise to a new test
set and improve the retrieval performance of a monoELECTRA-based pipeline with
and without adaptive re-ranking.

###  5.1. Generative Relevance Feedback

(a)  (b)  (c)

Figure 1. Results for each main query type comparing BM25 >> monoELECTRA,
QR(FLAN-T5) >> BM25 >> monoELECTRA, BM25 >> PRF${}_{\textit{Top-P}}$(FLAN-T5)
monoELECTRA and SPLADE >> monoELECTRA.

To assess where generative relevance feedback is most effective, we compare
generative expansions with learned expansions via SPLADE as well as a standard
re-ranking pipeline across different query types. We refer users to the query
type definitions proposed by Broder (Broder, 2002) and expanded by Rose and
Levinson (2004). We focus on directed queries and advice, as the majority of
test queries can be grouped into these classes. As defined by Rose and
Levinson (2004), directed queries aim to learn a particular piece of
information about a topic. They can be either closed when there is "a single,
unambiguous answer" to a query or open when the query is an "open-ended
question or one with unconstrained depth". Advice queries are requests for
"advice, ideas, suggestion or instructions". We manually classified each Deep
Learning 2023 test query into the groupings mentioned above. From 82 queries,
we found that 31 fell in the directed closed class, 23 in the directed open
class and 21 in the advice class. We investigate the performance of our runs
within these query groupings.

As shown in Figure 1 (a), in open-directed queries, we find that Gen-QR is
more effective than Gen-PRF or SPLADE in terms of nDCG@10. As the zero-shot
expansions of Gen-QR are not grounded by either training in-domain or few-shot
context from a first-stage ranker we hypothesize that in cases where the
information need is broad, the relatively unconstrained diversification
provided by such expansion terms leads to an improvement in both P@10 and
nDCG@10 over other methods. A SPLADE first-stage retrieval (uogtr_se) shows
the strongest performance in terms of MRR, MAP, and R@100, suggesting that the
in-domain training of SPLADE allows for the retrieval of more partially
relevant documents than a generative approach.

In Figure 1 (b) we present performance on closed-directed queries. We observe
that any linear trend in metric performance across all official evaluation
metrics observed in Table 1 does not hold for queries with an unambiguous
intent. We consider that diversification of terms may be unnecessary in such
cases with Gen-PRF (uogtr_b_grf_e) actually degrading performance over a
standard monoELECTRA re-ranker (uogtr_be) in terms of MRR. Furthermore, we
observe that in terms of R@100 the grounding of Gen-PRF using first-stage
ranking context does not improve recall over Gen-QR, reinforcing that pseudo-
relevance feedback is unnecessary in these cases.

In Figure 1 (c) we present performance on advice queries. We observe that Gen-
QR generally performs worse than Gen-PRF and SPLADE in terms of P@10 and
nDCG@10. Upon inspection of generated expansions by Gen-QR, we observe that
without either fine-tuning or first-stage context to ground expansion terms,
the LLM directly generated advice instead of expansion terms. As we removed
stopwords post-generation, much of the semantic structure was not used.
However, many terms formed a part of an answer as opposed to more general
terms for expansion. Inherently this is an artefact of the instruction-tuning
of FLAN-T5, it does not appear to affect search more generally, as we still
observe strong performance across other query types. However, this finding may
explain the margin between Gen-QR and Gen-PRF. In future applications, either
fine-tuning or the use of a stronger LLM may alleviate this issue. In the case
of question-style or conversational-style queries, the LLM misunderstands the
full instruction and instead attempts to answer the question directly which is
not always conducive to the generation of effective expansion terms.

Concerning RQ (2), we find that generative relevance feedback can improve
directed queries with both clear and ambiguous intent. However, performance
can be harmed when a query is posed as a conversational style question, as the
underlying LLM can attempt to answer the question instead of generating
suitable expansion terms.

###  5.2. Convergence of Adaptive Re-Ranking

(a)  (b)

Figure 2. Contrasting adaptive re-ranking over BM25 and SPLADE first stages
with full re-ranking at different budgets on TREC Deep Learning 2022 queries.
Rankings are truncated to the top 100 results. Post-ranking, duplicates were
added to the rankings to follow the current TREC procedure on MS MARCO-v2.
Error bands are omitted from Figure (b) for clarity.

Observing similar performance (identical top 10 texts for multiple test
queries) when adaptive re-ranking is applied with a large corpus graph and
budget regardless of first-stage ranker (uogtr_be_gb and uogtr_se_gb), we
consider that by using GAR, the need for complex first-stage retrieval may be
reduced. As relevance judgements are not available at the time of analysis, we
instead use Deep Learning 2022 relevance judgements and test queries for this
analysis. To assess the effect of compute budget on GAR, we apply adaptive
ranking with a compute budget ranging from 100 to 5000 texts. Following TREC
Deep Learning assessments, we truncate the final rankings to 100 texts. We
contrast GAR with full re-ranking, allowing the first-stage retriever to rank
up to 5000 texts.

We observe in Figure 2 (a) that rankings by Rank Biased Overlap (RBO) become
increasingly correlated as budget increases, with the trend plateauing around
a budget of 4000. Around a budget of 1000, variance begins to increase as
rankings converge, whereas, below this point, BM25 and SPLADE rankings are
almost completely diverging. As one would expect, the correlation between full
re-rankings of BM25 and SPLADE is not as strong, however does follow a similar
trend to adaptive re-ranking.

We also observe that from a budget of 2000, it can be seen in Figure 2 (b)
that BM25 and SPLADE first stages are within a small margin of each other in
terms of nDCG@10, we found that on both P@10 and R@100, a similar trend was
present. We observe that SPLADE is only marginally improved by adaptive re-
ranking, as is shown by contrast with full re-ranking and performance measured
on the Deep Learning 2023 test queries (uogtr_se versus uogtr_se_gb) in Table
1. We observe that full re-ranking of BM25 fails to show continuous
improvement with nDCG@10 performance plateauing around a budget of 2000,
similar to adaptive re-ranking, however, at a significantly lower value
(t-test, p < 0.05). This can be attributed to lexical mismatch as full re-
ranking is limited by term overlap with a query, whereas GAR can make
document-wise term overlap comparisons. We find that metric performance
between SPLADE and BM25 using adaptive re-ranking is insignificant from a
budget of 2000 (t-test, p < 0.05). Addressing RQ (3), in cases where labelled
data is unavailable or financially infeasible to collect, this finding is
compelling as the performance of a learned sparse model can be closely
replicated by BM25 when using adaptive re-ranking with the caveat that one
must have a suitable re-ranker.

##  6\. Conclusions

In summary, our participation in the TREC 2023 Deep Leaning track has been
insightful in validating recent approaches to the expansion of both query
terms and first-stage rankings. In answering our research questions, we have
found that generative relevance feedback can transfer to a monoELECTRA cross-
encoder and is further bolstered by adaptive re-ranking. We find that though
generative relevance feedback can be generally effective, the approach is
sensitive to the form of the query being direct as opposed to conversational,
in which case performance can degrade due to artefacts from instruction-
tuning. We also find that with sufficient compute budget and corpus graph
size, a first-stage lexical model can closely replicate the metric performance
of a learned sparse retrieval model, with both models’ rankings becoming
increasingly correlated by RBO reaching a maximum correlation of 0.80.

## References

  * (1)
  * Althammer et al. (2023) Sophia Althammer, Guido Zuccon, Sebastian Hofstätter, Suzan Verberne, and Allan Hanbury. 2023.  Annotating Data for Fine-Tuning a Neural Ranker? Current Active Learning Strategies are not Better than Random Selection.  _CoRR_ abs/2309.06131 (2023).  https://doi.org/10.48550/ARXIV.2309.06131 arXiv:2309.06131
  * Amati (2003) Giambattista Amati. 2003.  _Probability models for information retrieval based on divergence from randomness_.  PhD. University of Glasgow.  https://eleanor.lib.gla.ac.uk/record=b2151999
  * Amati (2006) Giambattista Amati. 2006.  Frequentist and Bayesian Approach to Information Retrieval. In _Advances in Information Retrieval, 28th European Conference on IR Research, ECIR 2006, London, UK, April 10-12, 2006, Proceedings_ _(Lecture Notes in Computer Science, Vol. 3936)_ , Mounia Lalmas, Andy MacFarlane, Stefan M. Rüger, Anastasios Tombros, Theodora Tsikrika, and Alexei Yavlinsky (Eds.). Springer, 13–24.  https://doi.org/10.1007/11735106_3
  * Broder (2002) Andrei Z. Broder. 2002.  A taxonomy of web search.  _SIGIR Forum_ 36, 2 (2002), 3–10.  https://doi.org/10.1145/792550.792552
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language Models are Few-Shot Learners.  _CoRR_ abs/2005.14165 (2020).  arXiv:2005.14165 https://arxiv.org/abs/2005.14165
  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Y. Zhao, Yanping Huang, Andrew M. Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei. 2022\.  Scaling Instruction-Finetuned Language Models.  _CoRR_ abs/2210.11416 (2022).  https://doi.org/10.48550/ARXIV.2210.11416 arXiv:2210.11416
  * Clark et al. (2020) Kevin Clark, Minh-Thang Luong, Quoc V. Le, and Christopher D. Manning. 2020.  ELECTRA: Pre-training Text Encoders as Discriminators Rather Than Generators.  _CoRR_ abs/2003.10555 (2020).  arXiv:2003.10555 https://arxiv.org/abs/2003.10555
  * Craswell et al. (2021) Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, and Jimmy Lin. 2021.  Overview of the TREC 2021 Deep Learning Track. In _Proceedings of the Thirtieth Text REtrieval Conference, TREC 2021, online, November 15-19, 2021_ _(NIST Special Publication, Vol. 500-335)_ , Ian Soboroff and Angela Ellis (Eds.). National Institute of Standards and Technology (NIST).  https://trec.nist.gov/pubs/trec30/papers/Overview-DL.pdf
  * Craswell et al. (2022) Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, Jimmy Lin, Ellen M. Voorhees, and Ian Soboroff. 2022.  Overview of the TREC 2022 Deep Learning Track. In _Proceedings of the Thirty-First Text REtrieval Conference, TREC 2022, online, November 15-19, 2022_ _(NIST Special Publication, Vol. 500-338)_ , Ian Soboroff and Angela Ellis (Eds.). National Institute of Standards and Technology (NIST).  https://trec.nist.gov/pubs/trec31/papers/Overview_deep.pdf
  * Formal et al. (2021a) Thibault Formal, Carlos Lassance, Benjamin Piwowarski, and Stéphane Clinchant. 2021a.  SPLADE v2: Sparse Lexical and Expansion Model for Information Retrieval.  _CoRR_ abs/2109.10086 (2021).  arXiv:2109.10086 https://arxiv.org/abs/2109.10086
  * Formal et al. (2021b) Thibault Formal, Benjamin Piwowarski, and Stéphane Clinchant. 2021b.  SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking. In _SIGIR ’21: The 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, Virtual Event, Canada, July 11-15, 2021_ , Fernando Diaz, Chirag Shah, Torsten Suel, Pablo Castells, Rosie Jones, and Tetsuya Sakai (Eds.). ACM, 2288–2292.  https://doi.org/10.1145/3404835.3463098
  * Kelly and Azzopardi (2015) Diane Kelly and Leif Azzopardi. 2015.  How many results per page?: A Study of SERP Size, Search Behavior and User Experience. In _Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, Santiago, Chile, August 9-13, 2015_ , Ricardo Baeza-Yates, Mounia Lalmas, Alistair Moffat, and Berthier A. Ribeiro-Neto (Eds.). ACM, 183–192.  https://doi.org/10.1145/2766462.2767732
  * MacAvaney et al. (2022) Sean MacAvaney, Nicola Tonellotto, and Craig Macdonald. 2022.  Adaptive Re-Ranking with a Corpus Graph.  _CoRR_ abs/2208.08942 (2022).  https://doi.org/10.48550/ARXIV.2208.08942 arXiv:2208.08942
  * Nguyen et al. (2016) Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016.  MS MARCO: A Human Generated MAchine Reading COmprehension Dataset. In _Proceedings of the Workshop on Cognitive Computation: Integrating neural and symbolic approaches 2016 co-located with the 30th Annual Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain, December 9, 2016_ _(CEUR Workshop Proceedings, Vol. 1773)_ , Tarek Richard Besold, Antoine Bordes, Artur S. d’Avila Garcez, and Greg Wayne (Eds.). CEUR-WS.org.  https://ceur-ws.org/Vol-1773/CoCoNIPS_2016_paper9.pdf
  * Ounis et al. (2005) Iadh Ounis, Gianni Amati, Vassilis Plachouras, Ben He, Craig Macdonald, and Douglas Johnson. 2005.  Terrier Information Retrieval Platform. In _Advances in Information Retrieval, 27th European Conference on IR Research, ECIR 2005, Santiago de Compostela, Spain, March 21-23, 2005, Proceedings_ _(Lecture Notes in Computer Science, Vol. 3408)_ , David E. Losada and Juan M. Fernández-Luna (Eds.). Springer, 517–519.  https://doi.org/10.1007/978-3-540-31865-1_37
  * Pradeep et al. (2022) Ronak Pradeep, Yuqi Liu, Xinyu Zhang, Yilin Li, Andrew Yates, and Jimmy Lin. 2022.  Squeezing Water from a Stone: A Bag of Tricks for Further Improving Cross-Encoder Effectiveness for Reranking. In _Advances in Information Retrieval - 44th European Conference on IR Research, ECIR 2022, Stavanger, Norway, April 10-14, 2022, Proceedings, Part I_ _(Lecture Notes in Computer Science, Vol. 13185)_ , Matthias Hagen, Suzan Verberne, Craig Macdonald, Christin Seifert, Krisztian Balog, Kjetil Nørvåg, and Vinay Setty (Eds.). Springer, 655–670.  https://doi.org/10.1007/978-3-030-99736-6_44
  * Radford et al. (2017) Radford, Narasimhan, Saliman, and Sutskever. 2017.  Improving language understanding with unsupervised learning.  https://openai.com/research/language-unsupervised
  * Robertson et al. (1994) Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu, and Mike Gatford. 1994.  Okapi at TREC-3. In _Proceedings of The Third Text REtrieval Conference, TREC 1994, Gaithersburg, Maryland, USA, November 2-4, 1994_ _(NIST Special Publication, Vol. 500-225)_ , Donna K. Harman (Ed.). National Institute of Standards and Technology (NIST), 109–126.  http://trec.nist.gov/pubs/trec3/papers/city.ps.gz
  * Rose and Levinson (2004) Daniel E. Rose and Danny Levinson. 2004.  Understanding user goals in web search. In _Proceedings of the 13th international conference on World Wide Web, WWW 2004, New York, NY, USA, May 17-20, 2004_ , Stuart I. Feldman, Mike Uretsky, Marc Najork, and Craig E. Wills (Eds.). ACM, 13–19.  https://doi.org/10.1145/988672.988675
  * Taori et al. (2023) Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. 2023.  Stanford Alpaca: An Instruction-following LLaMA model.  https://github.com/tatsu-lab/stanford_alpaca Publication Title: GitHub repository.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023.  LLaMA: Open and Efficient Foundation Language Models.  _CoRR_ abs/2302.13971 (2023).  https://doi.org/10.48550/ARXIV.2302.13971 arXiv:2302.13971
  * Wang et al. (2023) Xiao Wang, Sean MacAvaney, Craig Macdonald, and Iadh Ounis. 2023.  Generative Query Reformulation for Effective Adhoc Search.  _CoRR_ abs/2308.00415 (2023).  https://doi.org/10.48550/ARXIV.2308.00415 arXiv:2308.00415


Data Trading and Monetization: Challenges and
Open Research Directions

Qusai Ramadan

Institute of Software Engineering
University of Koblenz

Zeyd Boukhers

Fraunhofer Institute for Applied
Information Technology FIT, and
Uniklinik Köln

Muath AlShaikh

College of Computing and Informatics
Saudi Electronic University
Kingdom of Saudi Arabia

Christoph Lange

Fraunhofer Institute for Applied
Information Technology FIT, and
RWTH Aachen University

Jan Jürjens

University of Koblenz, and
Fraunhofer-Institute for Software and Systems Engineering ISST

Traditional data monetization approaches face challenges related to data protection and logistics. In response, digital data marketplaces have emerged as intermediaries simplifying data transactions. Despite the growing establishment and acceptance of digital data marketplaces, significant challenges hinder efficient data trading. As a result, few companies can derive tangible value from their data, leading to missed opportunities in understanding customers, pricing decisions, and fraud prevention. In this paper, we explore both technical and organizational challenges affecting data monetization. Moreover, we identify areas in need of further research, aiming to expand the boundaries of current knowledge by emphasizing where research is currently limited or lacking.

§ INTRODUCTION

§ BACKGROUND

§ STATE OF THE ART

§ CHALLENGES AND OPEN RESEARCH DIRECTIONS

§ RESEARCH LIMITATIONS

§ CONCLUSIONS

§ ACKNOWLEDGMENT

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Abraham et al(2023)]
authorpersonRene Abraham, personJohannes Schneider, and personJan vom Brocke. year2023.
A taxonomy of data governance decision domains in data marketplaces.
journalElectronic Markets volume33, number1 (year2023), pages22.

[Ahmadian et al(2018)]
authorpersonAmir Shayan Ahmadian, personJan Jürjens, and personDaniel Strüber. year2018.
Extending model-based privacy analysis for the industrial data space by exploiting privacy level agreements. In booktitleProceedings of the 33rd annual ACM symposium on applied computing. pages1142–1149.

[Bhujel and Rahulamathavan(2022)]
authorpersonSangam Bhujel and personYogachandran Rahulamathavan. year2022.
A survey: Security, transparency, and scalability issues of nft’s and its marketplaces.
journalSensors volume22, number22 (year2022), pages8833.

[Boukhers et al(2023)]
authorpersonZeyd Boukhers, personChristoph Lange, and personOya Beyan. year2023.
Enhancing Data Space Semantic Interoperability through Machine Learning: a Visionary Perspective. In booktitleCompanion Proceedings of the ACM Web Conference 2023. pages1462–1467.

[Braud et al(2021)]
authorpersonArnaud Braud, personGaël Fromentoux, personBenoit Radier, and personOlivier Le Grand. year2021.
The road to European digital sovereignty with Gaia-X and IDSA.
journalIEEE network volume35, number2 (year2021), pages4–5.

[Calancea and Alboaie(2021)]
authorpersonCristina Georgiana Calancea and personLenuța Alboaie. year2021.
Techniques to improve b2b data governance using fair principles.
journalMathematics volume9, number9 (year2021), pages1059.

[Catalini and Gans(2020)]
authorpersonChristian Catalini and personJoshua S Gans. year2020.
Some simple economics of the blockchain.
journalCommun. ACM volume63, number7 (year2020), pages80–90.

[Charitsis et al(2018)]
authorpersonVassilis Charitsis, personDetlev Zwick, and personAlan Bradshaw. year2018.
Creating worlds that create audiences: Theorising personal data markets in the age of communicative capitalism.

[Chaudhry and Yousaf(2018)]
authorpersonNatalia Chaudhry and personMuhammad Murtaza Yousaf. year2018.
Consensus algorithms in blockchain: Comparative analysis, challenges and opportunities. In booktitle2018 12th International Conference on Open Source Systems and Technologies (ICOSST). IEEE, pages54–63.

[Chen et al(2019)]
authorpersonLingjiao Chen, personHongyi Wang, personLeshang Chen, personParaschos Koutris, and personArun Kumar. year2019.
Demonstration of Nimbus: Model-based Pricing for Machine Learning in a Data Marketplace. In booktitleProceedings of the 2019 International Conference on Management of Data. pages1885–1888.

[Colli et al(2021)]
authorpersonMichele Colli, personJonas Nygaard Uhrenholt, personOle Madsen, and personBrian Vejrum Waehrens. year2021.
Translating transparency into value: an approach to design IoT solutions.
journalJournal of Manufacturing Technology Management volume32, number8 (year2021), pages1515–1532.

authorpersonMatthew Crain. year2018.
The limits of transparency: Data brokers and commodification.
journalnew media & society volume20, number1 (year2018), pages88–104.

authorpersonBarbara J Evans. year2011.
Much ado about data ownership.
journalHarv. JL & Tech.  volume25 (year2011), pages69.

authorpersonDavid S Evans. year2014.
Economic aspects of Bitcoin and other decentralized public-ledger currency platforms.
journalUniversity of Chicago Coase-Sandor Institute for Law & Economics Research Paper number685 (year2014).

[Hynes et al(2018)]
authorpersonNick Hynes, personDavid Dao, personDavid Yan, personRaymond Cheng, and personDawn Song. year2018.
A demonstration of sterling: a privacy-preserving data marketplace.
journalProceedings of the VLDB Endowment volume11, number12 (year2018), pages2086–2089.

authorpersonGeorgy Ishmaev. year2020.
The ethical limits of blockchain-enabled markets for private IoT data.
journalPhilosophy & Technology  volume33 (year2020), pages411–432.

[Jacobsen et al(2020)]
authorpersonAnnika Jacobsen, personRicardo de Miranda Azevedo, personNick Juty, personDominique Batista, personSimon Coles, personRonald Cornet, personMélanie Courtot, personMercè Crosas, personMichel Dumontier, personChris T Evelo, et al year2020.
titleFAIR principles: interpretations and implementation considerations.
, numpages10–29 pages.

[Koutroumpis et al(2017)]
authorpersonPantelis Koutroumpis, personAija Leiponen, and personLlewellyn DW Thomas. year2017.
booktitleThe (unfulfilled) potential of data marketplaces.
typeTechnical Report. institutionETLA working papers.

[Koutroumpis et al(2020)]
authorpersonPantelis Koutroumpis, personAija Leiponen, and personLlewellyn DW Thomas. year2020.
Markets for data.
journalIndustrial and Corporate Change volume29, number3 (year2020), pages645–660.

[Lawrenz et al(2019)]
authorpersonSebastian Lawrenz, personPriyanka Sharma, and personAndreas Rausch. year2019.
Blockchain technology as an approach for data marketplaces. In booktitleProceedings of the 2019 international conference on blockchain technology. pages55–59.

[Li et al(2020)]
authorpersonYuzheng Li, personChuan Chen, personNan Liu, personHuawei Huang, personZibin Zheng, and personQiang Yan. year2020.
A blockchain-based decentralized federated learning framework with committee consensus.
journalIEEE Network volume35, number1 (year2020), pages234–241.

[Liu et al(2019)]
authorpersonKang Liu, personWuhui Chen, personZibin Zheng, personZhenni Li, and personWei Liang. year2019.
A novel debt-credit mechanism for blockchain-based data-trading in internet of vehicles.
journalIEEE Internet of Things Journal volume6, number5 (year2019), pages9098–9111.

[Mao et al(2019)]
authorpersonWeichao Mao, personZhenzhe Zheng, and personFan Wu. year2019.
Pricing for revenue maximization in iot data markets: An information design perspective. In booktitleIEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, pages1837–1845.

[Mingxiao et al(2017)]
authorpersonDu Mingxiao, personMa Xiaofeng, personZhang Zhe, personWang Xiangwei, and personChen Qijun. year2017.
A review on consensus algorithm of blockchain. In booktitle2017 IEEE international conference on systems, man, and cybernetics (SMC). IEEE, pages2567–2572.

[Niebel et al(2022)]
authorpersonCrispin Niebel, personAbel Reiberg, and personPeter Kraemer. year2022.
booktitleGaia-X for SMEs.
typeWhite Paper. institutionGaia-X Hub Germany.

[Niu et al(2020)]
authorpersonChaoyue Niu, personZhenzhe Zheng, personFan Wu, personShaojie Tang, and personGuihai Chen. year2020.
Online pricing with reserve price constraint for personal data markets.
journalIEEE Transactions on Knowledge and Data Engineering volume34, number4 (year2020), pages1928–1943.

[Oh et al(2019)]
authorpersonHyeontaek Oh, personSangdon Park, personGyu Myoung Lee, personHwanjo Heo, and personJun Kyun Choi. year2019.
Personal data trading scheme for data brokers in IoT data marketplaces.
journalIEEE Access  volume7 (year2019), pages40120–40132.

[Otto et al(2019)]
authorpersonBoris Otto, personMichael ten Hompel, and personStefan Wrobel. year2019.
International Data Spaces: Reference architecture for the digitization of industries.
journalDigital transformation (year2019), pages109–128.

[Pettenpohl et al(2022)]
authorpersonHeinrich Pettenpohl, personMarkus Spiekermann, and personJan Ruben Both. year2022.
International data spaces in a nutshell.
journalDesigning Data Spaces; Springer: Cham, Switzerland (year2022), pages29–40.

[Ramachandran et al(2018)]
authorpersonGowri Sankar Ramachandran, personRahul Radhakrishnan, and personBhaskar Krishnamachari. year2018.
Towards a decentralized data marketplace for smart cities. In booktitle2018 IEEE International Smart Cities Conference (ISC2). IEEE, pages1–8.

[Roman and Stefano(2016)]
authorpersonDumitru Roman and personGatti Stefano. year2016.
Towards a reference architecture for trusted data marketplaces: The credit scoring perspective. In booktitle2016 2nd International Conference on Open and Big Data (OBD). IEEE, pages95–101.

[Rydning et al(2018)]
authorpersonDavid Reinsel-John Gantz-John Rydning, personJohn Reinsel, and personJohn Gantz. year2018.
The digitization of the world from edge to core.
journalFramingham: International Data Corporation  volume16 (year2018), pages1–28.

[Samek and Müller(2019)]
authorpersonWojciech Samek and personKlaus-Robert Müller. year2019.
Towards explainable artificial intelligence.
journalExplainable AI: interpreting, explaining and visualizing deep learning (year2019), pages5–22.

[Shaabany and Anderl(2018)]
authorpersonGhaidaa Shaabany and personReiner Anderl. year2018.
Security by design as an approach to design a secure industry 4.0-capable machine enabling online-trading of technology data. In booktitle2018 International Conference on System Science and Engineering (ICSSE). IEEE, pages1–5.

[Shaabany et al(2016)]
authorpersonGhaidaa Shaabany, personMarco Grimm, and personReiner Anderl. year2016.
Secure information model for data marketplaces enabling global distributed manufacturing.
journalProcedia CIRP  volume50 (year2016), pages360–365.

[Sørlie and Altmann(2019)]
authorpersonJan-Terje Sørlie and personJörn Altmann. year2019.
Sensing as a service revisited: A property rights enforcement and pricing model for IIoT data marketplaces. In booktitleEconomics of Grids, Clouds, Systems, and Services: 16th International Conference, GECON 2019, Leeds, UK, September 17–19, 2019, Proceedings 16. Springer, pages127–139.

authorpersonMarkus Spiekermann. year2019.
Data marketplaces: Trends and monetisation of data goods.
journalIntereconomics volume54, number4 (year2019), pages208–216.

authorpersonMelanie Swan. year2015.
booktitleBlockchain: Blueprint for a new economy.
publisher" O'Reilly Media, Inc.".

authorpersonHubert Tardieu. year2022.
Role of Gaia-X in the European Data Space Ecosystem.
In booktitleDesigning Data Spaces: The Ecosystem Approach To Competitive Advantage. publisherSpringer International Publishing Cham, pages41–59.

[Thomas and Leiponen(2016)]
authorpersonLlewellyn DW Thomas and personAija Leiponen. year2016.
Big data commercialization.
journalIEEE Engineering Management Review volume44, number2 (year2016), pages74–90.

[Upadhyay et al(2021)]
authorpersonArvind Upadhyay, personSumona Mukhuty, personVikas Kumar, and personYigit Kazancoglu. year2021.
Blockchain technology and the circular economy: Implications for sustainability and social responsibility.
journalJournal of cleaner production  volume293 (year2021), pages126130.

[van de Ven et al(2021)]
authorpersonMontijn van de Ven, personAntragama Ewa Abbas, personZenlin Kwee, and personMark de Reuver. year2021.
Creating a taxonomy of business models for data marketplaces. In booktitle34th Bled EConference: Digital Support from Crisis to Progressive Change. University of Maribor Press, pages313–325.

[Varghese et al(2020)]
authorpersonBlesson Varghese, personNan Wang, personDimitrios S Nikolopoulos, and personRajkumar Buyya. year2020.
Feasibility of fog computing.
journalHandbook of Integration of Cloud Computing, Cyber Physical Systems and Internet of Things (year2020), pages127–146.

[Virkar et al(2019)]
authorpersonShefali Virkar, personGabriela Viale Pereira, and personMichela Vignoli. year2019.
Investigating the social, political, economic and cultural implications of data trading. In booktitleElectronic Government: 18th IFIP WG 8.5 International Conference, EGOV 2019, San Benedetto Del Tronto, Italy, September 2–4, 2019, Proceedings 18. Springer, pages215–229.

[Vomfell et al(2015)]
authorpersonLara Vomfell, personFlorian Stahl, personFabian Schomm, and personGottfried Vossen. year2015.
booktitleA classification framework for data marketplaces.
typeTechnical Report. institutionErcis working paper.

[Wilkinson et al(2016)]
authorpersonMark D Wilkinson, personMichel Dumontier, personIJsbrand Jan Aalbersberg, personGabrielle Appleton, personMyles Axton, personArie Baak, personNiklas Blomberg, personJan-Willem Boiten, personLuiz Bonino da Silva Santos, personPhilip E Bourne, et al year2016.
The FAIR Guiding Principles for scientific data management and stewardship.
journalScientific data volume3, number1 (year2016), pages1–9.

[Xu and Chen(2021)]
authorpersonRonghua Xu and personYu Chen. year2021.
Fed-ddm: A federated ledgers based framework for hierarchical decentralized data marketplaces. In booktitle2021 international conference on computer communications and networks (ICCCN). IEEE, pages1–8.

[Zhang et al(2023)]
authorpersonMengxiao Zhang, personFernando Beltrán, and personJiamou Liu. year2023.
A Survey of Data Pricing for Data Marketplaces.
journalIEEE Transactions on Big Data (year2023).

[Zheng et al(2017)]
authorpersonZibin Zheng, personShaoan Xie, personHongning Dai, personXiangping Chen, and personHuaimin Wang. year2017.
An overview of blockchain technology: Architecture, consensus, and future trends. In booktitle2017 IEEE international congress on big data (BigData congress). Ieee, pages557–564.

[Zichichi et al(2020)]
authorpersonMirko Zichichi, personContu Michele, personStefano Ferretti, personRodríguez-Doncel Víctor, et al year2020.
Ensuring personal data anonymity in data marketplaces through sensing-as-a-service and distributed ledger. In booktitleCEUR Workshop Proceedings, Vol. volume2580. Sun SITE Central Europe/RWTH Aachen University, pages1–16.

[Zyskind et al(2015)]
authorpersonGuy Zyskind, personOz Nathan, et al year2015.
Decentralizing privacy: Using blockchain to protect personal data. In booktitle2015 IEEE security and privacy workshops. IEEE, pages180–184.