# Connecting Compression Spaces with Transformer for Approximate Nearest
Neighbor Search

###### Abstract

We propose a generic feature compression method for Approximate Nearest
Neighbor Search (ANNS) problems, which speeds up existing ANNS methods in a
plug-and-play manner. Specifically, based on transformer, we propose a new
network structure to compress the feature into a low dimensional space, and an
inhomogeneous neighborhood relationship preserving (INRP) loss that aims to
maintain high search accuracy. Specifically, we use multiple compression
projections to cast the feature into many low dimensional spaces, and then use
transformer to globally optimize these projections such that the features are
well compressed following the guidance from our loss function. The loss
function is designed to assign high weights on point pairs that are close in
original feature space, and keep their distances in projected space. Keeping
these distances helps maintain the eventual top-k retrieval accuracy, and down
weighting others creates room for feature compression. In experiments, we run
our compression method on public datasets, and use the compressed features in
graph based, product quantization and scalar quantization based ANNS
solutions. Experimental results show that our compression method can
significantly improve the efficiency of these methods while preserves or even
improves search accuracy, suggesting its broad potential impact on real world
applications.

##  1 Introduction

Approximate nearest neighbor search (ANNS) methods focus on searching for $k$
approximate nearest neighbors from a given database to a given query node $q$.
It is a fundamental technology in information retrieval and is widely used in
applications such as search engines and recommendation systems. The common
goal of ANNS approaches is to minimize the search latency while maintain a low
search accuracy loss on a fixed hardware constraint.

As stated in Subramanya et al. (2019), currently, the two most popular ANNS
methods are graph based approaches and quantization based approaches. Many of
these methods, such as product quantization (PQ) Jegou et al. (2010), HNSW
Malkov & Yashunin (2018) and NSG Fu et al. (2017) are widely used in real-
world applications. Although popular, there are rooms to further improve them.
In PQ, the sub vectors are quantified into codewords using a clustering
objective, which is a poor proxy to search accuracy. In graph based methods,
there are a large number of distance computations in index building time (for
instance, indexing complexity NSG graph is
${O}(kn^{\frac{1+d}{d}}\log{}n^{\frac{1}{d}}+n\log{}n)$ Fu et al. (2017),
where $d$ is data dimension), which in real world applications can last weeks
on billion scale datasets. For PQ related methods, introducing the feature
compression as an intermediate step avoids direct feature quantization from
high dimensional space. Such a two stage quantization strategy usually results
in higher accuracy. For graph based methods, computing distance in low
dimensional space reduces computational cost linearly, which significantly
speeds up indexing.

Existing feature compression methods such as principal components analysis
(PCA) Wold et al. (1987), Variational Auto-Encoders(VAE) Pu et al. (2016)
focus on keeping the information in the input features instead of their
neighborhood relations, but in ANNS applications the neighborhood structure
affects the eventual accuracy more than the locations of the individual data
points themselves. As is shown in experiments, directly applying these methods
lead to significantly reduced search accuracy, which is not suitable for
applications requiring both high speed and high recall.

In this paper, we propose a feature compression method for the approximate
nearest neighbor search problem, which aims to retain the local neighborhood
relations instead of the fidelity of the reconstructed features. Our method is
composed of a compression network which connect compression spaces with
transformer (CCST), and an inhomogeneous neighborhood relationship preserving
(INRP) loss.

Our CCST is a combination of projection units that projects original features
to low dimensions, and transformer units that compose these projections to
generate the output feature. The projection unit is initialized as sparse
random projection (SRP) Li et al. (2006), which is proved by JL
(Johnson–Lindenstrauss) lemma that this projection reserves distances of an
increasing number of data points with decreasing dimension reduction ratios.
We design our network with multiple projections units, so that each can be
used to compress a local neighborhood, and the entire space can be covered in
a piece-wise manner by the ensemble of these units. We then use transformers
to adaptively combine the output of these random projection units, because the
transformer unit has the well known property of globally attending its inputs,
which could lead to better global alignment of these projections. In other
words, multiple compression spaces are connected to one via transformer.
Different from standard transformer based networks, we design an input
dependent, non-trivial output token named compression token, which is itself a
compressed feature derived from the input feature, and is updated by the
transformer layers with skip connections. The compression token is designed to
provide an anchor vector to the multi-head attention units so that
transformers properly mix the output of random projection units to generate
the output compressed feature.

Our training loss is designed for the purpose of preserving local neighborhood
structures. In most ANNS applications, user is mostly interested in the
accuracy of the top few nearest neighbors. So, changes in the distances
between a query and its far away points will not affect the search result, as
long as their distances are still large. Inspired by this property in ANNS
problems, we design the INRP loss, which assigns high losses on point pairs
whose distances are within a threshold. This loss design allows certain
information of the original feature to be discarded while still maintaining
high retrieval accuracy.

Our experiments show that our feature compression model can be seamlessly used
with popular ANNS methods. While saving $1/2$ to $3/4$ indexing time, graphs
built using our compressed features can improve the recall slightly for HNSW
and NSG methods. It also significantly improves recalls of 1@1 and recalls of
1@5 metrics by more than 10.0 percentage points for PQ based methods, and
about 1.0 or 2.0 percentage points for a quantization methods tailored to HNSW
methods Douze et al. (2018).

Our main contributions are summarized as follows.

  1. 1.

We propose a novel feature vector compression model CCST for ANNS problem. In
CCST, traditional projection based compression units and emerging transformer
units are jointly used to compress features for ANNS problems. To our
knowledge, this is the first attempt to apply transformer to this kind of
task.

  2. 2.

We propose an INRP loss that mainly keeps the distances of a point and its
close local neighbors. This maintains top $k$ retrieval accuracy and creates
space for lossy feature compression.

  3. 3.

The experiment results show that our proposed method can be used in most ANNS
methods to improve efficiency. It speeds up indexing speed to 2$\times$ to
4$\times$ for graph based methods and it improves recalls significantly for PQ
related methods.

##  2 Related Work

###  2.1 ANNS methods

Existing ANNS approaches can be divided into four main types: 1) tree-
structure based strategies Silpa-Anan & Hartley (2008), which partitions
indexed datapoints into different subspaces based on specific conditions; 2)
Locality sensitive hashing (LSH) related methods, which map similar items to
the same symbol with a high probability Andoni & Razenshteyn (2015); 3)
product quantization (PQ) related approaches decompose the space into a
Cartesian product of low dimensional subspaces and quantize each subspace
separately Jegou et al. (2010); 4) graph based frameworks search on pre-built
relative neighborhood graphs (RNG) to find the closest data points to query
Malkov & Yashunin (2018). Compared with PQ and graph based methods, tree based
and LSH based methods need ensembles of trees or hash tables to achieve
similar accuracy, which consume considerably more memory and are less
frequently used in large scale ANNS problems.

Product quantization based approach reduces the index memory cost by holding
quantized codes and speeds up distance computation using online or offline
computed distance look up tables. When combined with inverted index to further
reduce the number of distance computations, PQ becomes a strong baseline for
modern ANNS systems. Compared with quantization based approach, which
partitions original feature space to generate shorter features, our method
directly maps the original features into a new space. These two method are
orthogonal. As is shown in experiments, the new space can be further quantized
by PQ, which generates even better speed and accuracy trade-offs than using PQ
method alone.

Graph based algorithms usually construct a navigable graph over database, and
searches along the edges of this built graph to find the closest points to
query. The most recent works in this category are NSG Fu et al. (2017), HNSW
Malkov & Yashunin (2018), Disk-ANN Subramanya et al. (2019) and HM-ANN Ren et
al. (2020). NSG builds a relatively sparse indexing graph to reduce memory
usage and improve search speed. HNSW employs hierarchical graph structure to
reduce query latency. Disk-ANN and HM-ANN focus on reducing memory overhead
via adopting quantization and heterogeneous memory. Besides, Douze et al.
proposed Link and Code (L$\&$C), which takes HNSW as basic ANNS framework and
replaces full precision vectors with refined quantiztion codes Douze et al.
(2018). Compared with brute force, these graph based methods visit 1/1000 or
even less of the indexed points in each search, significantly reduce the
number of needed distance computations. However, most of these methods suffer
from the problem of high indexing time, as constructing a navigable graph over
database has high time complexity. For instance, ${O}(n\log{}n)$ for HNSW and
${O}(kn^{\frac{1+d}{d}}\log{}n^{\frac{1}{d}}+n\log{}n)$ for NSG. In real world
application, building a navigable graph over a billion-scale database with 30+
threads costs several days or even weeks.

###  2.2 Dimension reduction / compression

In early stage, almost all dimension reduction methods are based on
mathematical theory. PCA Wold et al. (1987) and independent components
analysis (ICA) Hyvärinen & Oja (2000) are proposed to transform vectors into
lower dimensional space, where the most information of high dimension vectors
are retained. Random projection Achlioptas (2003)Li et al. (2006) project data
into low dimensional space, while approximately preserving structure
information in original feature space. The efficiency of random projection
methods is guaranteed by Johnson-Lindenstrauss (JL) lemma Johnson &
Lindenstrauss (1984). This lemma states that data points in sufficiently high
dimensional space may be projected into suitable low dimensional space while
approximately preserving the distances between the points in original space.

In 2006, Hinton and Salakhutdiov proposed to compress high dimensional data
via neural network Hinton & Salakhutdinov (2006), and several recent works on
dimension reduction have shifted their methods to neural networks. For
example, VAE maps data to low dimensional space and forces the encoded
features to follow a multivariate Gaussian distribution Pu et al. (2016).

Very recently, Sablayrolles et al. Sablayrolles et al. (2019) proposed an end-
to-end quantization model for similarity search, where a compression network
named catalyst is designed and trained to compress vectors from
${d}_{in}$-dimensional input space to the hypersphere of a
${d}_{out}$-dimensional space, where ${d}_{in}>{d}_{out}$. Our proposed CCST
is close to this work, as it involves an ANNS oriented loss and a learnable
network to compress feature vectors. Compared with catalyst, our training
objective is easier to implement as it does not involve offline exhaustive
search for positive and negative pairs. Also, we design a deep compression
model for the ANNS problem, where Sablayrolles et al. (2019) uses multi-layer
perceptions to demonstrate their entropy maximization idea.

###  2.3 Transformer

Vaswani et al. first proposed transformer model to solve NLP problem in
Vaswani et al. (2017). Inspired by the promising performance of transformer,
several works started to introduce transformer into vision tasks and proposed
a new type of models. Dosovitskiy et.al proposed ViT, in which the input image
is cropped into a sequence of patches to meet the input format requirement of
transformer Dosovitskiy et al. (2020). Later, Touvron et al. proposed to use
knowledge distillation to overcome the difficulties of training ViT models
Touvron et al. (2021). Liu et al proposed a hierarchical transformer, where
representation is computed within shifted windows Liu et al. (2021) to reduce
computation cost. Very recently, Graham et al. mixed CNN and transformer in
their LeVit model, which significantly outperforms previous CNNs and ViT
models with respect to the speed/accuracy tradeoff Graham et al. (2021).

The transformer part of our CCST model is inspired by the works above. We have
made several modifications to better fit transformer with our applications,
which are detailed in section global optimization part.

Figure 1: Overview of the CCST model. The proposed model consists of three
major parts, including compression part, projection part and global
optimization part. The projection part projects input vectors into multiple
subspaces and outputs a sequence of sub vectors. Global optimization part
optimizes the sequence of sub vectors from global perspective and summarizes
all optimized information into compression token. Compression part provides
initial the compression token, and interacts with global optimization part to
generate the final compression result.

##  3 The Proposed Approach

In this section, we present our proposed method in detail. We first introduce
the architecture of the proposed CCST. Then we elaborate on our INRP loss
function.

###  3.1 CCST

As illustrated in Fig. 1, the proposed CCST consists of three major parts,
including projection part, global optimization part and compression part.

The projection part casts the input feature vector $x\in\mathbb{R}^{d_{in}}$
to $n$ different low dimensional spaces. The output of this part is a sequence
of low dimensional vectors
$\left[{p}^{1}(x),{p}^{2}(x),\cdots{p}^{n}(x)\right]$, where
${p}^{i}(x)\in\mathbb{R}^{d_{out}},i=1,\cdots,n$. $d_{in}$ and $d_{out}$
denote feature dimensions before and after compression, respectively.
$p^{i}()$ is a compression projection function. $p^{i}(x)=W^{i}x$, where
$W^{i}\in\mathbb{R}^{d_{in}\times d_{out}}$. The global optimization part
takes $\left[cp(x),{p}^{1}(x),{p}^{2}(x),\cdots{p}^{n}(x)\right]$ as input and
globally optimizes all sub vectors step by step. The global optimization part
then summarizes all optimized sub vectors into a compression token $cp(x)$.
The compression part is responsible for initializing the compression token,
interacting with global optimization part in each step and further processes
the information in compression token to generate the final compression result
$f(x)\in\mathbb{R}^{d_{out}}$.

####  3.1.1 Projection part

Our goal is compressing feature vectors into a low dimensional space, where
the data neighborhood relation in original space is preserved. It seems that
random projections satisfy our requirement and there are already some
classical random projection methods. Unfortunately, according to JL lemma
Johnson & Lindenstrauss (1984), the projection error of using single random
projection function satisfies:

$(1-\epsilon){||{x}_{i}-{x}_{j}||}^{2}_{2}\leq{||p({x}_{i})-p({x}_{j})||}^{2}_{2}\leq(1+\epsilon){||{x}_{i}-{x}_{j}||}^{2}_{2}$
(1)

where $x_{i}$ and $x_{j}$ represent two data points in high dimensional space
and $p(x_{i})$ and $p(x_{j})$ are corresponding projection data points in low
dimensional space. $p()$ is the projection function. $\epsilon$ satisfies
equation $d_{out}>\frac{4\ln(m)}{\epsilon^{2}/2-\epsilon^{3}/3}$, where
$0<\epsilon<1$ and $m$ represents data size. Random projections are
inapplicable in our case. For example, if compressing 960 dimensional vectors
in GIST1M dataset to 480 dimensions, we have $0.63<\epsilon<1$. In GIST1M, the
distance of a query to its nearest neighbor and to its hundredth neighbor are
probably 1.177 and 1.5615, respectively. After projection, with the minimum
$\epsilon$, the distance of a query to its nearest neighbor and to its
hundredth neighbor fall into the scope of [0.7160, 1.5027] and the scope of
[0.9498, 1.9936], respectively. These two scopes have a considerable overlap,
which may disturb neighborhood relationship and lead to a lower search
accuracy. We can draw a consistent conclusion from our experimental results.

Existing random projection methods do not address our problem directly, but
they give us some inspirations. Here, we propose to use $n$ different
projections to boost compression accuracy. Specifically, we initialize the $n$
projection matrices in ${p^{i}(x)=W_{i}x}$ ($i=1,2,\cdots,n$) on input
$x\in\mathbb{R}^{d_{in}}$ to generate a sequence of features
$\left[{p}^{1}(x),{p}^{2}(x),\cdots{p}^{n}(x)\right]$. Following Li et al.
(2006), the elements of in each $W_{i}$ are randomly drawn from:

$\left\\{\begin{array}[]{crr}-\sqrt{\frac{s}{d_{out}}}&\text{with
probability}&1/2s,\\\ 0&\text{with probability}&1-1/s\\\
\sqrt{\frac{s}{d_{out}}}&\text{with probability}&1/2s\\\ \end{array}\right.$
(2)

where $s=\sqrt{d_{i}n}$. Different from traditional random projections,
projection matrices used in here will be further optimized by our INRP loss.

Figure 2: Different modules. (a) Transformer module of ViT Dosovitskiy et al.
(2020). (b) Transformer module proposed in this paper. By adopting lightweight
designs, transformer module in (b) has fewer parameters than that in (a). From
(a) to (b), the number of parameters in attention part decreases from
$4d^{2}h_{n}$ to $2d^{2}h_{n}+2d^{2}e$ and the number of parameters in MLP
part reduces from $8d^{2}$ to $4d^{2}$, where expansion factor $e$ is smaller
than the number of heads $h_{n}$.

####  3.1.2 Global optimization part

The projection part outputs a sequence of low dimensional vectors, which
brings in the core problem of this global optimization part, that is how to
generate the result compressed feature using these features from different sub
spaces.

Here, as the problem that we need to solve is exactly what transformer model
is good at, we tailor a transformer model to overcome the core problem. One
biggest advantage of transformer is it good at capturing and taking use of
relationships between different tokens to get a global optimization result.
When we treat features from different sub spaces as different tokens, our core
problem becomes optimizing a sequence of tokens from the global perspective.
So, based on ViT Dosovitskiy et al. (2020) structure, we propose a new
transformer model for feature compression.

Based on the characteristics of our compression problem, we have made four
major modifications to the original ViT structure, including two structural
modifications and two lightweight designs.

Structural modifications ensure the new proposed transformer structure is
aligned with our problem. These two modifications are:

  1. 1.

Discard position embedding. In transformer models for processing sentences or
images, position embedding and relative position embedding are widely used, as
the order of words and the positions or relative positions of images patches
contain important information. However, in our case, the order of random
projections is fixed. Naturally, position embedding is discarded in our
transformer model. Interestingly, when we add position embedding into our
transformer, the search accuracy drops. We conjecture this is because randomly
initialized position coding disturbs our model.

  2. 2.

Add compression token. In our transformer model, an extra token named
compression token is used. Structurally, this design is similar to the
transformer model in ViT, where an extra token named classification token is
also employed. Compression token and classification token are added for
different purposes and they have different functions. Compression token
provides a base reference for optimizing and summarizing information from
different projection spaces and it also works as a bridge between compression
part and global optimization part. Classification token is used as a
placeholder to perform classification. Different from classification token,
which is a learned constant, our compression token is derived from input
feature vector. Initializing compression token with random numbers is not in
accordance with its role of working as base reference.

Lightweight designs are adopted to reduce the number of learnable parameters.
As shown in Fig. 2, two lightweight designs for MLP part and attention part
are:

  1. 1.

In MLP part, we decrease the expansion ratio (changes among widths of the
adjacent linear mapping layers) from 4 to 2 to reduce the number of parameters
by half, as shown in the bottom half of Fig. 2 (b). In addition, the basic
computing unit in our model is Linear_ABN, which, in data processing order,
consists of a linear mapping layer, activation function and batch
normalization. As pointed out in Chen et al. (2019), placing batch
normalization layer before ReLU leads to the conv layer updated in a
suboptimal way due to the nonnegative responses of activation function. So we
design our unit following the order of
conv$\rightarrow$activation$\rightarrow$bn. This order is also recommended in
Zhuang et al. (2019).

  2. 2.

Attention part has three intermediate variables, which are represented as
Value ($V$), Query ($Q$) and Key ($K$). The output of head $i$ is calculated
as:

$\mathrm{head}_{i}(Q,K,V)=\mathrm{softmax}(\frac{QW_{i}^{Q}\cdot{KW_{i}^{K}}^{T}}{\sqrt{d}})VW_{i}^{V}$
(3)

where $W_{i}^{Q}$, $W_{i}^{K}$ and $W_{i}^{V}$ are three projection matrices.
As in Eqn. 3, V stores main information, $Q$ and $K$ are used to generate
attention weights. In ViT, $Q$, $K$ and $V$ are all the same in each head.
Inspired by Vaswani et al. (2017), we decrease the dimension of $Q$ and $K$
for reducing parameters of $W_{i}^{K}$ and $W_{i}^{V}$.

Structurally, as shown in the middle part of Fig. 1, global optimization part
consists of $s$ stages, each of which has $N_{i}$ transformer encoders. From
stage $1$ to $s-1$, projected vector from compression part is added to
compression token at the end of each stage. Finally, $cp(x)$ is from the
output of last stage is fed back to compression part to generate the final
compression result.

####  3.1.3 Compression part

The compression part is responsible for providing initial compression token,
interacting with global optimization part in each step and generating the
final compression result. Corresponding to three responsibilities three
learnable modules are constructed in this part. As shown in the top part of
Fig. 1, these three modules are a compression module and two linear projection
modules.

The compression module is made up of a sinlge Linear_ABN module. Each linear
projection module has a linear mapping function. Compression module takes
$x\in\mathbb{R}^{d_{in}}$ as input and outputs $cp(x)\in\mathbb{R}^{d_{out}}$.
Linear projection $A$ maps input $x\in\mathbb{R}^{d_{in}}$ to
$d_{out}$-dimensional vector, which is added to compression tokens of global
optimization part. Linear projection $B$ takes compression token from the last
stage of global optimization part as input and output the final compression
result.

###  3.2 INRP loss

Figure 3: The weight curve of INRP loss. $d_{ij}$ is Euclidean distance
between $x_{i}$ and $x_{j}$.

To preserve neighborhood structures, a straightforward way is training the
network to keep distances between all possible point pairs. However, the goal
of ANNS is searching for top $k$ approximate nearest neighbors to a query
point, which generally are points that are close to query point in the
original space. In other words, focusing on keeping distances between close
pairs is more important, as these pairs affect search result the most. In Guo
et al. (2020), Guo et al. presented a similar idea, which is proposed for
quantization instead of compression. Inspired by this, we design our INRP
loss, the formula of which is:

$loss=\frac{1}{m^{2}}\sum_{i=1}^{m}{\sum_{j=1}^{m}}w_{ij}\cdot\lVert\lVert
f(x_{i})-f(x_{j})\rVert_{2}-\lVert x_{i}-x_{j}\rVert_{2}\rVert_{2}$ (4)

where $x_{i}$ and $x_{j}$ are a pair of any two nodes from original space. $m$
denotes data size. $f(x_{i})$ and $f(x_{j})$ are compression results.
${w}_{ij}$ is weight for this pair and it is calculated as:

$w_{ij}=\min(\alpha,\max(\beta,-\ln(\frac{d_{ij}}{boundary})))$ (5)

where $d_{ij}=||x_{i}-x_{j}||_{2}$. $\alpha$ and $\beta$ are two hyper-
parameters, which are set to 2.0 and 0.01 respectively. $boundary$ denotes the
average distance between any two nodes in original space. The curve is shown
in Fig. 3. In implementation, we use all pairs inside a mini-batch to
approximate Eqn.4, which significantly simplifies computation.

Table 1: Experiments of speeding up indexing for graph based methods. C_F represents the feature compression factor. IND and SS denote indexing time and search speed. q/s is query per second. Experiments are performed on a server with two Xeon Gold 5218 CPUs. We build indices with 32 threads and perform search with a single thread. All the speed numbers are averaged from 20 cold runs to rule out random factors. Comp_t is time spent in compressing 1M feature vectors (database) with trained CSSTs. Here, a single RTX2080Ti GPU is used for accelerating compressing process and the GPU memory usage is restricted to about 1GB. C_F | Methods |  |
---|---|---|---
HNSW | NSG | Comp_t | GPU
IND | SS | Recall | IND | SS | Recall | (s) | (G)
(s) | (q/s) | 1@1 | 1@10 | 100@100 | (s) | (q/s) | 1@1 | 1@10 | 100@100 |  |
GIST1M
1 | 733 | 182 | 97.40 | 100.00 | 94.39 | 1118 | 179 | 97.40 | 100.00 | 93.97 | - | -
2 | 454 | 184 | 97.70 | 100.00 | 94.55 | 778 | 180 | 98.00 | 99.90 | 94.16 | 21.43 | 1.19
4 | 245 | 186 | 98.00 | 100.00 | 95.27 | 645 | 182 | 98.30 | 100.00 | 94.85 | 10.00 | 1.17
Deep1M
1 | 300 | 861 | 99.50 | 100.00 | 95.23 | 505 | 820 | 99.7 | 100.00 | 94.53 | - | -
2 | 144 | 870 | 99.50 | 100.00 | 95.46 | 246 | 822 | 99.6 | 100.00 | 94.69 | 5.15 | 1.09
4 | 100 | 874 | 99.80 | 100.00 | 95.60 | 209 | 842 | 99.6 | 100.00 | 94.92 | 4.64 | 1.06
Table 2: Experiments of speeding up indexing for real world database and billion-scale database. Datasets | C_factor | indexing | Recall | Compressing | GPU
---|---|---|---|---|---
time(h) | 1@1 | time (h) | usage(G)
Bigann-1B | 1 | 106 | 92.6 | - | -
2 | 51 | 92.8 | 1.01 | 1.24

##  4 Experiments

###  4.1 Datasets and implementation details

Datasest We carry out experiments on two million-scale benchmark datasets
GIST1M and Deep1M 111Both are downloaded from
https://www.cse.cuhk.edu.hk/systems/hash/gqr/datasets.html . GIST1M consists
of 1 million of 960-dimensional handcrafted feature vectors, which are
extracted from images with GIST descriptors Oliva & Torralba (2001). Deep1M
contains 1 million of 256-dimensional deep feature vectors, which are
extracted by using GoogleNet Krizhevsky et al. (2012).

Training setting Following Muja & Lowe (2014)Gong et al. (2012), we take
database as training set. We train our model for 2400 epochs with the Adamw
optimzier Loshchilov & Hutter (2017), where the initial learning rate and
batch size are set to 1e-4 and 1024 respectively. We use poly learning rate
policy with power of 0.9 to adjust the learning rate for every epoch.

Platforms We implement our CSST using Pytorch222https://pytorch.org/ and
conduct ANNS experiments based on
Faiss333https://github.com/facebookresearch/faiss/releases/tag/v1.7.1 .

###  4.2 Speeding up indexing for graph-based methods

In this section, we focus on using our proposed CSST to speed up indexing of
graph-based methods. Two most popular graph-based methods HNSW Malkov &
Yashunin (2018) and NSG Fu et al. (2017) are employed as baselines. We
construct all HNSW indices with M=48, efConstruction=512, and perform search
with efSearch=100 on GIST1M and efSearch=200 on Deep1M. Following Fu et al.
(2017)Subramanya et al. (2019), we build all NSG indices using R=60, L=70 and
C=500 and initialize K-NN graphs with NN-descent. On GIST1M, we initialize
K-NN graph using GK=400, L=400, iter=12, S=15 and R=100. On Deep1M, we
initialize K-NN graph using GK=200, L=200, iter=10, S=12 and R=100.

We conduct three groups of experiments with different compression ratios. In
all three groups, full-dimensional vectors are used to search nearest
neighbors. Full-dimensional vectors, feature vectors compressed with a factor
of 2 and 4 are respectively used in indexing.

Experiment results listed in Table 1 show that using compressed features
triples indexing speed for HNSW and doubles indexing speed for NSG. Taking
experiments based on HNSW as an example, using compressed features reduce
indexing time from 733 seconds to 454 seconds and 245 seconds for GIST1M
dataset and decreases indexing time from 300 seconds to 144 and 100 seconds
for Deep1M. Experiments based on NSG show similar trends.

Interestingly, using compression feature vectors slightly improves search
accuracy. For instance, on GIST1M, using $4\times$-compressed vectors improves
recall of 1@1 to 98.00% and improves recall of 100@100 to 95.60, 0.5 and 0.37
percentage points higher that that of baseline respectively. We conjecture
this is due to that using compressed feature vectors to build index introduces
some extra links and these links improves search accuracy, just like extra
links selected by select neighbors heuristic improves the accuracy of HNSW
Malkov & Yashunin (2018). Further investigation experiments exceeds the scope
of this paper and will be conducted in our future work.

Note that the speedup is scalable to larger datasets. As shown in Table 2, for
Bigann-1B444https://dl.fbaipublicfiles.com/billion-scale-ann-
benchmarks/bigann/base.1B.u8bin (1 billion 128-d hand drafted features), using
our features reduces indexing time from 106 hours to 51 hours.

Table 3: Fusion experiments. Bytes denotes the size of quantized feacture
vectors. Comp. and Quant. represent compression and quantization methods,
respectively. Following default settings in their source code Douze et al.
(2018), we conduct experiments on L&C Douze et al. (2018), except that the M
of coder is set to 8 (This gets highest accuracy.). For PQ experiments, we
adopt IVFADC (nlist=8) to avoid exhaustive search. GIST1M
---
Bytes | Comp. | ANNS | Speed | Recall
(q/s) | 1@1 | 1@5 | 1@50
60 | - | PQ | 115 | 23.0 | 45.2 | 79.7
60 | CSST | PQ | 117 | 39.5(16.5$\uparrow$) | 72.8(27.6$\uparrow$) | 97.3(17.6$\uparrow$)
60 | - | L&C | 1536 | 31.4 | 48.9 | 54.2
60 | CSST | L&C | 1527 | 30.7(0.7$\downarrow$) | 50.2(1.3$\uparrow$) | 55.1(0.9$\uparrow$)
30 | - | PQ | 246 | 15.2 | 31.0 | 62.4
30 | CSST | PQ | 251 | 20.9(5.7$\uparrow$) | 43.4(12.4$\uparrow$) | 79.7(17.3$\uparrow$)
30 | - | L&C | 2000 | 23.6 | 43.0 | 53.9
30 | CSST | L&C | 1992 | 23.9(0.3$\uparrow$) | 43.9(0.9$\uparrow$) | 54.3(0.4$\uparrow$)
Deep1M
32 | - | PQ | 236 | 32.3 | 67.5 | 95.9
32 | CSST | PQ | 240 | 53.3(21.0$\uparrow$) | 88.5(21.0$\uparrow$) | 100.0(4.1$\uparrow$)
32 | - | L&C | 2000 | 47.9 | 72.3 | 76.4
32 | CSST | L&C | 2020 | 48.7(0.9$\uparrow$) | 74.1(1.8$\uparrow$) | 78.3(1.9$\uparrow$)
16 | - | PQ | 520 | 16.8 | 38.6 | 73.6
16 | Catalyst | PQ | 545 | 19.8(3.0$\uparrow$) | 47.9(9.3$\uparrow$) | 82.5(8.9$\uparrow$)
16 | CSST | PQ | 537 | 32.5(15.7$\uparrow$) | 65.6(27.0$\uparrow$) | 94.4(20.8$\uparrow$)
16 | - | L&C | 2677 | 28.8 | 55.6 | 71.6
16 | CSST | L&C | 2676 | 29.2(0.4$\uparrow$) | 56.9(1.3$\uparrow$) | 73.7(2.1$\uparrow$)

###  4.3 Improving accuracy and speed for PQ related methods

Besides graph-based methods, PQ related methods are also very popular in real
world applications. As quantization and dimension compression are orthogonal
at the method level, we conjecture that our proposed CSST can be applied on PQ
related methods to achieve higher accuracy. In this section, we conduct fusion
experiments to verify this point. Specifically, we fusion our proposed CSST
with the classical PQ Jegou et al. (2010) and most recent proposed L&C Douze
et al. (2018). In addition, as the inspirational method catalyst Sablayrolles
et al. (2019) is close to our method in training networks to compress feature
dimension, we compare our proposed model with catalyst on Deep1M, the dataset
which is used in both this paper and their paper. Experiment results are
listed in Table 3.

Experiment results show that using compressed feature learned by our proposed
CSST improves both search accuracy and speed for PQ related methods. On
Deep1M, in experiments of quantizing feature vectors to 32 bytes, combining
CSST with PQ improves recalls 1@1, 1@5 and 1@50 by 21.0, 21.0 and 4.1
percentage points respectively. Our proposed CSST also brings more improvement
than Catalyst. In experiments of coding input vectors with 16 bytes, using
Catalyst improves recalls 1@1 and 1@5 by 3.0 and 9.3 percentage points and our
proposed CSST improves recalls by 11.7 and 27 percentage points.

Using CSST also improves search accuracy for L&C, but the improvements CSST
brings in here are less than that in PQ. This may result from that 2-level
residual codec already optimized PQ quantized codes once and there is less
room for improvement. Overall, CSST still improves search accuracy for L&C,
while keeping high search speed.

###  4.4 Working together with scalar quantization method

In quantization methods, besides PQ related methods, scalar quantization
methods are also widely used. In this section, we compare and fuse our
proposed CSST with scalar quantization method proposed in Gray et al. (2017).

From experimental results collected in Table 4 we can see: 1) both scalar
quantization and CSST can speed up indexing, but using CSST achieves faster
indexing speed. This is because the distance of two 8-bit quantized codes
still has to be represented by 16-bits, which reduces the data parallelism
when distance of two quantized vectors are computed using AVX2 or AVX512
instructions. For example, computing the distance of two 16 dimensional
float32 vectors (64 bytes) needs two AVX2 instructions calls, but computing
the distance of two 64 dimensional 8-bit quantized vectors (also 64 bytes)
needs to call the instruction 4 times. 2) Jointly using scalar quantization
and CSST reduce indexing time the most. In short, scalar quantization method
and our proposed CSST are complementary.

Table 4: Experiments of working together with scalar quantization method. The compression factor is set to 4 and HNSW is used as baseline. Datasets | CSST | Scalar | Indexing | Recall
---|---|---|---|---
Quant. | time (s) | 1@1 | 1@10 | 100 @ 100
GIST1M | N | N | 733 | 97.40 | 100.00 | 94.39
N | Y | 503 | 97.30 | 100.00 | 94.37
Y | N | 245 | 98.00 | 100.00 | 95.27
Y | Y | 121 | 97.00 | 100.00 | 91.42
Deep1M | N | N | 300 | 99.50 | 100.00 | 95.23
N | Y | 148 | 99.70 | 100.00 | 95.19
Y | N | 100 | 99.80 | 100.00 | 95.60
Y | Y | 74 | 99.80 | 100.00 | 95.55
Table 5: Comparison with other dimension reduction methods. The compression factor is set to 4. Brute force denotes exhaustive search. |  | HNSW | Brute force
---|---|---|---
Datasets | Methods | Recall | Recall
|  | 1@1 | 1@5 | 1@10 | 1@1 | 1@5 | 1@10
GIST1M | SRP | 24.9 | 49.4 | 60.7 | 24.8 | 49.7 | 60.9
MLP | 47.9 | 73.8 | 84.2 | 47.9 | 73.8 | 84.1
VAE | 49.2 | 77.0 | 86.0 | 49.3 | 76.8 | 85.8
CSST | 80.1 | 98.4 | 99.8 | 80.9 | 98.3 | 99.7
Deep1M | SRP | 17.3 | 35.6 | 44.4 | 17.3 | 35.6 | 44.4
MLP | 48.3 | 77.6 | 89.1 | 48.4 | 77.6 | 88.9
VAE | 50.0 | 81.9 | 90.2 | 50.0 | 81.9 | 90.2
Catalyst | 57.9 | 89.6 | 92.1 | 57.9 | 89.6 | 92.1
| CSST | 67.3 | 94.9 | 98.9 | 67.3 | 94.9 | 98.9

###  4.5 Comparison with other compression methods

Previous experiments have shown that using compression feature vectors learned
by our proposed CSST speeds up indexing without sacrificing accuracy. Besides
our CSST, there are other compression methods. In this section, we compare the
propsoed models with other methods to evaluate its efficiency.

Here, we employed five comparison methods, including one traditional methods
and four network based learning methods. Table 5 presents comparison results.

Compared with other four compression methods, our proposed CSST achieves the
highest accuracy. For GIST1M, using CSST and HNSW achieves 80.1% recall 1@1,
30.9 percentage points higher that that of VAE. As is analysed in the section
the proposed method, using single sparse random projection harms search
accuracy seriously. Both VAE is classical and powerful compression method, but
it focus on keeping information of the input feature instead of keeping the
neighborhood structure, which is not aligned with the requirement of ANNS.
They are outperformed by our proposed CSST. On Deep1M, the proposed CSST also
achieves better performance, even compared with the most recent proposed
method Catalyst.

##  5 Discussion

In this work, we have proposed a generic feature compression method for ANNS
problem. The proposed method consists of a compression network (CSST) which
combines traditional projection function and transformer model, and an
inhomogeneous neighborhood relationship preserving (INRP) loss which is
aligned with the characteristic of ANNS. The proposed method can be
generalized to most ANNS methods. It speeds up indexing speed to 2$\times$ to
4 $\times$ its original speed without hurting accuracy for graph based
methods, such as NSG and HNSW. It improves recalls by several or even a dozen
percentage points for PQ related methods.

While demonstrated our model’s overall effectiveness and potential usage, we
have not yet verified the importance of individual design choices or the
hypothesis behind our approach. We will leave these to our future work.

## References

  * Achlioptas (2003) Dimitris Achlioptas.  Database-friendly random projections: Johnson-lindenstrauss with binary coins.  _Journal of computer and System Sciences_ , 66(4):671–687, 2003.
  * Andoni & Razenshteyn (2015) Alexandr Andoni and Ilya Razenshteyn.  Optimal data-dependent hashing for approximate near neighbors.  In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , pp. 793–801, 2015.
  * Chen et al. (2019) Guangyong Chen, Pengfei Chen, Yujun Shi, Chang-Yu Hsieh, Benben Liao, and Shengyu Zhang.  Rethinking the usage of batch normalization and dropout in the training of deep neural networks.  _arXiv preprint arXiv:1905.05928_ , 2019.
  * Dosovitskiy et al. (2020) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Douze et al. (2018) Matthijs Douze, Alexandre Sablayrolles, and Hervé Jégou.  Link and code: Fast indexing with graphs and compact regression codes.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 3646–3654, 2018.
  * Fu et al. (2017) Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai.  Fast approximate nearest neighbor search with the navigating spreading-out graph.  _arXiv preprint arXiv:1707.00143_ , 2017.
  * Gong et al. (2012) Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin.  Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval.  _IEEE transactions on pattern analysis and machine intelligence_ , 35(12):2916–2929, 2012.
  * Graham et al. (2021) Ben Graham, Alaaeldin El-Nouby, Hugo Touvron, Pierre Stock, Armand Joulin, Hervé Jégou, and Matthijs Douze.  Levit: a vision transformer in convnet’s clothing for faster inference.  _arXiv preprint arXiv:2104.01136_ , 2021.
  * Gray et al. (2017) Allison Gray, Chris Gottbrath, R Olson, and S Prasanna.  Deploying deep neural networks with nvidia tensorrt. 2017.  _URL https://developer. nvidia. com/blog/deploying-deep-learning-nvidia-tensorrt_ , 2017.
  * Guo et al. (2020) Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar.  Accelerating large-scale inference with anisotropic vector quantization.  In _International Conference on Machine Learning_ , pp. 3887–3896. PMLR, 2020.
  * Hinton & Salakhutdinov (2006) Geoffrey E Hinton and Ruslan R Salakhutdinov.  Reducing the dimensionality of data with neural networks.  _science_ , 313(5786):504–507, 2006.
  * Hyvärinen & Oja (2000) Aapo Hyvärinen and Erkki Oja.  Independent component analysis: algorithms and applications.  _Neural networks_ , 13(4-5):411–430, 2000.
  * Jegou et al. (2010) Herve Jegou, Matthijs Douze, and Cordelia Schmid.  Product quantization for nearest neighbor search.  _IEEE transactions on pattern analysis and machine intelligence_ , 33(1):117–128, 2010.
  * Johnson & Lindenstrauss (1984) William B Johnson and Joram Lindenstrauss.  Extensions of lipschitz mappings into a hilbert space 26.  _Contemporary mathematics_ , 26, 1984.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  _Advances in neural information processing systems_ , 25:1097–1105, 2012.
  * Li et al. (2006) Ping Li, Trevor J Hastie, and Kenneth W Church.  Very sparse random projections.  In _Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pp. 287–296, 2006.
  * Liu et al. (2021) Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  _arXiv preprint arXiv:2103.14030_ , 2021.
  * Loshchilov & Hutter (2017) Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_ , 2017.
  * Malkov & Yashunin (2018) Yu A Malkov and Dmitry A Yashunin.  Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.  _IEEE transactions on pattern analysis and machine intelligence_ , 42(4):824–836, 2018.
  * Muja & Lowe (2014) Marius Muja and David G Lowe.  Scalable nearest neighbor algorithms for high dimensional data.  _IEEE transactions on pattern analysis and machine intelligence_ , 36(11):2227–2240, 2014.
  * Oliva & Torralba (2001) Aude Oliva and Antonio Torralba.  Modeling the shape of the scene: A holistic representation of the spatial envelope.  _International journal of computer vision_ , 42(3):145–175, 2001.
  * Pu et al. (2016) Yunchen Pu, Zhe Gan, Ricardo Henao, Xin Yuan, Chunyuan Li, Andrew Stevens, and Lawrence Carin.  Variational autoencoder for deep learning of images, labels and captions.  _Advances in neural information processing systems_ , 29:2352–2360, 2016.
  * Ren et al. (2020) Jie Ren, Minjia Zhang, and Dong Li.  Hm-ann: Efficient billion-point nearest neighbor search on heterogeneous memory.  _Advances in Neural Information Processing Systems_ , 2020.
  * Sablayrolles et al. (2019) Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, and Hervé Jégou.  Spreading vectors for similarity search.  In _ICLR_ , 2019.
  * Silpa-Anan & Hartley (2008) Chanop Silpa-Anan and Richard Hartley.  Optimised kd-trees for fast image descriptor matching.  In _2008 IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 1–8. IEEE, 2008.
  * Subramanya et al. (2019) Suhas Jayaram Subramanya, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vardhan Simhadri.  Diskann: Fast accurate billion-point nearest neighbor search on a single node.  In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , pp. 13766–13776, 2019.
  * Touvron et al. (2021) Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In _International Conference on Machine Learning_ , pp. 10347–10357. PMLR, 2021.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in neural information processing systems_ , pp. 5998–6008, 2017.
  * Wold et al. (1987) Svante Wold, Kim Esbensen, and Paul Geladi.  Principal component analysis.  _Chemometrics and intelligent laboratory systems_ , 2(1-3):37–52, 1987.
  * Zhuang et al. (2019) Bohan Zhuang, Chunhua Shen, Mingkui Tan, Lingqiao Liu, and Ian Reid.  Structured binary neural networks for accurate image classification and semantic segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 413–422, 2019.


By convention if a point $x\not\in A$ then the loop $s_{A}$ passes on the
inside of the point $x$ if the points are in a circle or below the point $x$
if the points are in a line. If instead a loop passes on the outside (or
above) of the point $x$ we refer to $x$ as a _double point_ 999In the
handlebody decomposition of the surface, the handle associated to a double
point will intersect the loop in two arcs.. The extra generators have double
points denoted by $\overline{x}$.

Using these generators the non-pairwise relations the cubic relations become

$\displaystyle s_{1\overline{2}3}s_{13}$
$\displaystyle=\left(q^{-1}s_{1}s_{23}+qs_{3}s_{12}+s_{1}s_{2}s_{3}+s_{123}\right)s_{123}+q^{-1}\big{(}s_{2}s_{3}$
$\displaystyle+q^{-1}s_{23}\big{)}s_{23}+q(s_{1}s_{2}+qs_{12})s_{12}+s_{1}^{2}+s_{2}^{2}+s_{3}^{2}-\left(q+q^{-1}\right)^{2},$
$\displaystyle s_{1\overline{2}3}s_{134}$
$\displaystyle=\left(q^{-1}s_{1}s_{23}+qs_{3}s_{12}+s_{1}s_{2}s_{3}+s_{123}\right)s_{1234}+q(s_{1}s_{2}+qs_{12})s_{124}$
$\displaystyle+q^{-1}\left(s_{2}s_{3}+q^{-1}s_{23}\right)s_{234}+s_{1}s_{14}+s_{2}s_{24}+s_{3}s_{34}+\left(q+q^{-1}\right)s_{4},$

and their symmetries, and the quartic relation becomes the two relations

$\displaystyle s_{12}s_{2\overline{34}1}$
$\displaystyle=\left(q^{-1}s_{1}s_{234}+qs_{2}s_{134}+s_{1}s_{2}s_{34}+s_{1234}\right)s_{1234}+q(s_{1}s_{34}+qs_{134})s_{134}$
$\displaystyle+q^{-1}\left(s_{2}s_{34}s_{234}+q^{-1}s_{234}\right)s_{234}+s_{1}^{2}+s_{2}^{2}+s_{34}^{2}-\left(q+q^{-1}\right)^{2},$
$\displaystyle s_{23}s_{3\overline{14}2}$
$\displaystyle=\left(qs_{3}s_{124}+q^{-1}s_{2}s_{134}+s_{2}s_{3}s_{14}+s_{1234}\right)s_{1234}+q(s_{2}s_{14}+qs_{124})s_{124}$
$\displaystyle+q^{-1}\left(s_{3}s_{14}+q^{-1}s_{134}\right)s_{134}+s_{2}^{2}+s_{3}^{2}+s_{14}^{2}-\left(q+q^{-1}\right)^{2}.$

Unfortunately, adding extra generators massively increases the number of
relations, but these extra relations can be generated from the original
relations in a manner which will now be described.

Firstly we have the relations which relate the new generators to the simple
generators which we shall call the _generator generating relations_. For the
generators which consist of two disjoint loops these are trivial:

$s_{12}s_{34}\mapsto s_{12,34}\quad s_{23}s_{14}\mapsto s_{23,14}$

For the generators with a single double point the relations have the form:

$s_{12}s_{23}\mapsto q^{-1}s_{1\overline{2}3}+qs_{13}+s_{1}s_{3}+s_{2}s_{123}$

For the generators with two double points the relations have the form:

$\displaystyle s_{12}s_{2\overline{3}4}$ $\displaystyle\mapsto
q^{-1}s_{1\overline{23}4}+s_{1}s_{4}+qp^{-1}\left(s_{34}s_{13}-p^{-1}s_{14}-s_{1}s_{4}-s_{3}s_{134}\right)$
$\displaystyle+p^{-1}s_{2}\left(s_{34}s_{123}-p^{-1}s_{124}-s_{4}s_{12}-s_{3}s_{1234}\right)$
$\displaystyle s_{12}s_{23,14}$ $\displaystyle\mapsto
qs_{13}s_{14}+q^{-1}s_{1\overline{2}3}s_{14}+s_{2}s_{123}s_{14}+s_{1}s_{3}s_{14}$

where $p=q$ except when finding the coefficients for the symmetric relations
it does not invert. For the full list of relations see the code101010Code
available at https://github.com/jcooke848/Askey-Wilson-Algebras-as-Skein-
Code.git .

Now let $\\{bc\mapsto r_{bc}\\}$ be a relation in 9.3 excluding the commuting
and the commutator relations, and let $\\{ab\mapsto r_{ab}\\}$ be a relation
in the generator generating relations. Hence, we have an equality

$r_{ab}c=abc=ar_{bc}$

and furthermore $r_{ab}c$ contains a new generator multiplied by $c$ on the
right. Rearrange with respect to $mc$ where $m$ is the largest new generator
in $r_{ab}$ and turn this equation into a reduction rule for $mc$.

After generating these new relations for all the original $\\{bc\mapsto
r_{bc}\\}$ relations, iterate by the generating the relations where
$\\{bc\mapsto r_{bc}\\}$ is one of these newly generated relations. This
generates all the new relations including the extra generators apart from the
commuting and commutator relations involving the extra generators. To generate
these consider monomials $ba$ where $b>a$, one of them is a new generator and
$ba$ is not reducible using the generator generating relations or any other
relations we have generated so far. Consider the monomial $\prod b_{i}a_{j}$
where $\prod b_{i}$ generates $b$ and $a_{j}$ generates $a$ as the leading
term using the generator generating relations. We can generate a relation if:

  * •

All the $b_{i}$ terms are larger than all the $a_{j}$ terms by considering
$x=\prod b_{i}a_{j}$

  * •

All the $b_{i}$ terms are smaller than all the $a_{j}$ terms by considering
$x=\prod a_{j}b_{i}$

Take $x$ and apply the generator generating relations to $\prod b_{i}$ and
$\prod a_{j}$ separatly, then order the result using the commutator and
commuting relations and rearrange the result to obtain a relation for $ba$.
This generates a term rewriting system with 241 relations which we shall call
$S_{\mathcal{B}}$ we shall now show is confluent.

######  Proposition 9.14.

All ambiguities in the term rewriting system $S_{\mathcal{B}}$ are resolvable.

###### Proof.

As all reductions in $S_{\mathcal{B}}$ are pairwise, it is sufficient to check
$abc$ where $a,b,c$ are basis elements such that $\\{\;ab\mapsto
r_{ab},\;bc\mapsto r_{bc}\;\\}$ are reductions in $S_{\mathcal{B}}$. As there
are 241 relations, there are a very large number of such ambiguities so we
have used a computer to check theseFootnote 10. ∎

To use the diamond lemma for ring theory we now need to prove that the system
$S_{\mathcal{B}}$ terminates. We shall do this by constructing a partial order
which is compatible with the term rewriting system. This partial order will be
constructed by chaining together three different partial orders. The first
ordering is ordering by _reduced degree_ [Cas17, Section 15]:

######  Definition 9.15.

Give the letters of the finite alphabet $X$ an ordering $x_{1}\leq\dots\leq
x_{N}$. Any word $W$ of length $n$ can be written as $W=x_{i_{1}}\dots
x_{i_{n}}$ where $x_{i_{j}}\in X$. An _inversion_ of $W$ is a pair $k\leq l$
with $x_{i_{k}}\geq x_{i_{l}}$ i.e. a pair with letters in the incorrect
order. The number of inversions of $W$ is denoted $|W|$.

######  Definition 9.16.

Any expression $T$ can be written as a linear combination of words $T=\sum
c_{l}W_{l}$. Define
$\rho_{n}(T):=\sum_{\operatorname{length}(W_{l})=n,c_{l}\neq 0}|W_{l}|$. The
_reduced degree of $T$_ is the largest $n$ such that $\rho_{n}(T)\neq 0$.

######  Definition 9.17.

Under the _reduced degree ordering_ , $T\leq S$ if

  1. (1)

The reduced degree of $T$ is less than the reduced degree of $S$, or

  2. (2)

The reduced degree of $T$ and $S$ are equal, but $\rho_{n}(T)\leq\rho_{n}(S)$
for maximal nonzero $n$.

The second ordering is by total degree.

######  Definition 9.18.

The _total degree_ of $T\in k<X>$ is the maximal degree of its monomials.
Under the _total degree ordering_ $T\leq S$ if the total degree of $T$ is less
than or equal to the total degree of $S$.

######  Definition 9.19.

Let $s$ be one of the extended generators. The _degree_ of $s$ is

$\operatorname{degree}(s)=(\text{number of points inside loop})+2(\text{number
of double points}),$

so for example $s_{1\overline{2}3}$ has degree $4$. The degree of a monomial
is the sum of the degree of its terms.

The final partial order is a partial order based on the notion on how near are
the loops that make up a monomial in the ordered list of loops.

######  Definition 9.20.

Let $\operatorname{group}(s)$ denote the group (1-5) which the loop $s$ is in.
For a monomial $m=\prod_{i\in I}s_{i}$ we define

$\operatorname{nearness}(m)=\sum_{i,j\in
I}|\operatorname{group}(s_{i})-\operatorname{group}(s_{j})|.$

Let $\\{m_{i}\\}$ and $\\{n_{j}\\}$ be the maximal total degree monomials of
expressions $T$ and $S$ respectively. Under the _group distance ordering_
$T\leq S$ if

$\max_{i}(\text{number of distinct loops in }m_{i})<\max_{j}(\text{number of
distinct loops in }m_{j})$

or these maxima are equal and

$\sum_{i}\operatorname{nearness}(m_{i})>\sum_{j}\operatorname{nearness}(n_{j}).$

We now combine these three partial orders to obtain a single partial order of
$\mathcal{R}\langle X\rangle$.

######  Definition 9.21.

Let $m,n\in\mathcal{R}\langle X\rangle$. We define $m\leq n$ if one of the
following conditions is satisfied:

  1. (1)

$m<n$ with respect to the reduced degree ordering

  2. (2)

$m=n$ under the reduced degree ordering and $m<n$ with respect to the total
degree ordering

  3. (3)

$m=n$ under the reduced degree ordering, they have the same total degree and
$m<n$ with respect to the group distance ordering.

######  Lemma 9.22.

The term rewriting system $S_{\mathcal{B}}$ is compatible with the ordering
defined in 9.21.

###### Proof.

This requires that for every rewriting rule $\\{\sigma\mapsto r_{\sigma}\\}$,
$\sigma<m$ for all monomials $m$ in $r_{\sigma}$. This can easily be checked
using the code 10. ∎

We can now apply the diamond lemma for ring theory.

######  Theorem 9.23.

The term-rewriting system $S_{\mathcal{B}}$ is confluent and hence the reduced
monomials form a linear basis for the associated algebra $\mathcal{B}$.

###### Proof.

The ambiguities are resolvable by 9.14 and by 9.22 there is a compatible term
rewriting system so the term rewriting system terminates and hence we can
apply the diamond lemma for ring theory. ∎

If we filter $\mathcal{B}$ by degree, we have a surjective filtered algebra
homomorphism

$\phi:\mathcal{B}\to\operatorname{Sk}_{q}\left(\Sigma_{0,5}\right).$

We now need to prove that $\phi$ is an isomorphism and thus that $\mathcal{B}$
is a presentation for $\operatorname{Sk}_{q}\left(\Sigma_{0,5}\right)$. To do
this we shall compute the Hilbert series of $\mathcal{B}$ and show it is the
same as the Hilbert series for
$\operatorname{Sk}_{q}\left(\Sigma_{0,5}\right)$ which we have already
computed in 8.6.

######  Proposition 9.24.

The Hilbert series of $\mathcal{B}$ is

$\frac{t^{4}-2t^{3}+4t^{2}-2t+1}{(1-t^{2})^{3}(1-t)^{6}}$

###### Proof.

In order to compute the Hilbert series, we first consider what are the
conditions on a monomial $m=\prod_{i\in I}s_{i}$ if it is reduced and
therefore is in the vector space basis. Firstly, note that there is a relation
$yx$ for any $y>x$ so the $s_{i}$ must be ordered. Furthermore, there is a
relation $xy$ between any two loops in the same group; hence,

$m=s_{\textrm{I}}^{\alpha}s_{\textrm{II}}^{\beta}s_{\textrm{III}}^{\gamma}s_{\textrm{IV}}^{\delta}s_{\textrm{V}}^{\epsilon}$

where for example $s_{\textrm{I}}$ is a loop in group 1 and
$\alpha,\beta,\gamma,\delta,\epsilon\in\mathbb{Z}_{\geq 0}$. Also note that as
all the relations are pairwise we only need to concern ourselves with
neighbouring terms in the monomial.

The Hilbert series of
$\\{\;x^{m}\mathrel{|}m\in\mathbb{Z}_{>0},\;\deg(x)=n\;\\}$ is
$\frac{t^{n}}{1-t^{n}}$, so the Hilbert series when there is only a
$s_{\textrm{I}}$ loop is

$1+\frac{4t^{2}}{1-t^{2}}.$

Given a $s_{\textrm{II}}$ loop there are two possible choices for
$s_{\textrm{I}}$; hence the Hilbert series for
$s_{\textrm{I}}^{\alpha}s_{\textrm{II}}^{\beta}$ is

$1+\frac{4t^{2}}{1-t^{2}}+\frac{6t^{4}}{1-t^{4}}\left(1+\frac{2t^{2}}{1-t^{2}}\right)=1+\frac{4t^{2}}{1-t^{2}}+\frac{6t^{4}}{(1-t^{2})^{2}}$

Given a $s_{\textrm{III}}$ loop there are three choices of $s_{\textrm{II}}$
or if there is no $s_{\textrm{II}}$ loop there are three choices for
$s_{\textrm{I}}$; hence the Hilbert series for
$s_{\textrm{I}}^{\alpha}s_{\textrm{II}}^{\beta}s_{\textrm{III}}^{\gamma}$ is

$1+\frac{4t^{2}}{1-t^{2}}+\frac{6t^{4}}{(1-t^{2})^{2}}+\frac{4t^{6}}{1-t^{6}}\left(\frac{3t^{4}}{(1-t^{2})^{2}}+\frac{3t^{2}}{1-t^{2}}+1\right)=\frac{1-t^{8}}{(1-t^{2})^{4}}$

Given a $s_{\textrm{IV}}$ loop there are no choices for $s_{\textrm{III}}$
(the relations are derived from the cubic relation) and two choices for
$s_{\textrm{V}}$. There are four choices for $s_{\textrm{II}}$ and if there is
no $s_{\textrm{II}}$ loop there is a free choice of $s_{\textrm{I}}$; hence
the Hilbert series for
$s_{\textrm{I}}^{\alpha}s_{\textrm{II}}^{\beta}s_{\textrm{III}}^{\gamma}s_{\textrm{IV}}^{\epsilon}s_{\textrm{V}}^{\delta}$
assuming $\delta\neq 0$ is

$\frac{2t^{2}}{1-t^{2}}\left(\frac{2t^{3}}{1-t^{3}}+1\right)\left(\frac{4t^{4}}{(1-t^{2})^{2}}+\frac{4t^{2}}{1-t^{2}}+1\right)$

Finally, we assume there is no $s_{\textrm{IV}}$ loop but fix a
$s_{\textrm{V}}$ loop. There are two choices for $s_{\textrm{III}}$, if there
is no $s_{\textrm{III}}$ loop there are five choices for $s_{\textrm{II}}$ and
if there is only a $s_{\textrm{I}}$ loop then there is a free choice. Hence,
the Hilbert series for
$s_{\textrm{I}}^{\alpha}s_{\textrm{II}}^{\beta}s_{\textrm{III}}^{\gamma}s_{\textrm{V}}^{\epsilon}$
assuming $\epsilon\neq 0$ is

$\frac{4t^{3}}{1-t^{3}}\left(\frac{2t^{6}}{(1-t^{2})^{3}}+\frac{5t^{4}}{(1-t^{2})^{2}}+\frac{4t^{2}}{1-t^{2}}+1\right)=\frac{4t^{3}}{1-t^{3}}\frac{(1-t^{4})}{(1-t^{2})^{4}}.$

Combining these cases gives a Hilbert series for $\mathcal{B}$ of

$\displaystyle\frac{1-t^{8}}{(1-t^{2})^{4}}+\frac{2t^{2}}{1-t^{2}}\left(\frac{2t^{3}}{1-t^{3}}+1\right)\left(\frac{4t^{2}}{(1-t^{2})^{2}}+1\right)+\frac{4t^{3}}{1-t^{3}}\frac{(1-t^{4})}{(1-t^{2})^{4}}$
$\displaystyle=\frac{t^{4}-2t^{3}+4t^{2}-2t+1}{(1-t^{2})^{3}(1-t)^{6}}$

as required. ∎

This means we have an isomorphism

$\phi:\operatorname{Sk}_{q}\left(\Sigma_{0,5}\right)\to\mathcal{B}$

and therefore we have a presentation for
$\operatorname{Sk}_{q}\left(\Sigma_{0,5}\right)$. Finally, we will remove the
extra generators to reduce the presentation to that in 9.3 thus proving this
theorem.

###### Proof of 9.3.

We have that $\mathcal{B}$ is a presentation for
$\operatorname{Sk}_{q}\left(\Sigma_{0,5}\right)$ as the algebras are
isomorphic. Using generator generating relations we can eliminate the non-
simple loop generators of $\mathcal{B}$. The relations in $\mathcal{B}$
between simple loops are the same as in $\mathcal{A}$ and it is
straightforward to check that the new cubic and quartic relations reduce (see
code). The extra relations in $\mathcal{B}$ which were generated from these
relations reduce by how they were defined. Hence, we can reduce the
presentation $\mathcal{B}$ thus concluding the proof. ∎

##  Appendix A Appendix

In this appendix we list explicitly the full list of relations for the
presentation $\operatorname{Sk}_{q}\left(\Sigma_{0,5}\right)$ which is given
in Theorem 9.3.

###  A.1. Commuting

$\displaystyle s_{124}s_{24}$ $\displaystyle=s_{24}s_{124}$ $\displaystyle
s_{124}s_{14}$ $\displaystyle=s_{14}s_{124}$ $\displaystyle s_{134}s_{14}$
$\displaystyle=s_{14}s_{134}$ $\displaystyle s_{134}s_{13}$
$\displaystyle=s_{13}s_{134}$ $\displaystyle s_{124}s_{12}$
$\displaystyle=s_{12}s_{124}$ $\displaystyle s_{234}s_{34}$
$\displaystyle=s_{34}s_{234}$ $\displaystyle s_{234}s_{24}$
$\displaystyle=s_{24}s_{234}$ $\displaystyle s_{134}s_{34}$
$\displaystyle=s_{34}s_{134}$ $\displaystyle s_{234}s_{23}$
$\displaystyle=s_{23}s_{234}$ $\displaystyle s_{123}s_{13}$
$\displaystyle=s_{13}s_{123}$ $\displaystyle s_{123}s_{12}$
$\displaystyle=s_{12}s_{123}$ $\displaystyle s_{123}s_{23}$
$\displaystyle=s_{23}s_{123}$ $\displaystyle s_{14}s_{23}$
$\displaystyle=s_{23}s_{14}$ $\displaystyle s_{34}s_{12}$
$\displaystyle=s_{12}s_{34}$

###  A.2. Commutators

$\displaystyle s_{23}s_{12}$
$\displaystyle=\left(1-q^{2}\right)s_{1}s_{3}+\left(q^{-1}-q^{3}\right)s_{13}+\left(1-q^{2}\right)s_{2}s_{123}+q^{2}s_{12}s_{23}$
$\displaystyle s_{34}s_{23}$
$\displaystyle=\left(1-q^{2}\right)s_{2}s_{4}+\left(q^{-1}-q^{3}\right)s_{24}+\left(1-q^{2}\right)s_{3}s_{234}+q^{2}s_{23}s_{34}$
$\displaystyle s_{14}s_{12}$
$\displaystyle=\left(1-q^{-2}\right)s_{2}s_{4}+\left(q-q^{-3}\right)s_{24}+\left(1-q^{-2}\right)s_{1}s_{124}+q^{-2}s_{12}s_{14}$
$\displaystyle s_{14}s_{34}$
$\displaystyle=\left(1-q^{2}\right)s_{1}s_{3}+\left(q^{-1}-q^{3}\right)s_{13}+\left(1-q^{2}\right)s_{4}s_{134}+q^{2}s_{34}s_{14}$
$\displaystyle s_{13}s_{12}$
$\displaystyle=\left(1-q^{-2}\right)s_{2}s_{3}+\left(q-q^{-3}\right)s_{23}+\left(1-q^{-2}\right)s_{1}s_{123}+q^{-2}s_{12}s_{13}$
$\displaystyle s_{13}s_{23}$
$\displaystyle=\left(1-q^{2}\right)s_{1}s_{2}+\left(q^{-1}-q^{3}\right)s_{12}+\left(1-q^{2}\right)s_{3}s_{123}+q^{2}s_{23}s_{13}$
$\displaystyle s_{13}s_{14}$
$\displaystyle=\left(1-q^{2}\right)s_{3}s_{4}+\left(q^{-1}-q^{3}\right)s_{34}+\left(1-q^{2}\right)s_{1}s_{134}+q^{2}s_{14}s_{13}$
$\displaystyle s_{24}s_{12}$
$\displaystyle=\left(1-q^{2}\right)s_{1}s_{4}+\left(q^{-1}-q^{3}\right)s_{14}+\left(1-q^{2}\right)s_{2}s_{124}+q^{2}s_{12}s_{24}$
$\displaystyle s_{24}s_{23}$
$\displaystyle=\left(1-q^{-2}\right)s_{3}s_{4}+\left(q-q^{-3}\right)s_{34}+\left(1-q^{-2}\right)s_{2}s_{234}+q^{-2}s_{23}s_{24}$
$\displaystyle s_{24}s_{34}$
$\displaystyle=\left(1-q^{2}\right)s_{2}s_{3}+\left(q^{-1}-q^{3}\right)s_{23}+\left(1-q^{2}\right)s_{4}s_{234}+q^{2}s_{34}s_{24}$
$\displaystyle s_{24}s_{14}$
$\displaystyle=\left(1-q^{-2}\right)s_{1}s_{2}+\left(q-q^{-3}\right)s_{12}+\left(1-q^{-2}\right)s_{4}s_{124}+q^{-2}s_{14}s_{24}$
$\displaystyle s_{13}s_{34}$
$\displaystyle=\left(1-q^{-2}\right)s_{1}s_{4}+\left(q-q^{-3}\right)s_{14}+\left(1-q^{-2}\right)s_{3}s_{134}+q^{-2}s_{34}s_{13}$
$\displaystyle s_{123}s_{34}$
$\displaystyle=\left(1-q^{-2}\right)s_{3}s_{1234}+\left(1-q^{-2}\right)s_{4}s_{12}+\left(q-q^{-3}\right)s_{124}+q^{-2}s_{34}s_{123}$
$\displaystyle s_{123}s_{14}$
$\displaystyle=\left(1-q^{2}\right)s_{1}s_{1234}+\left(1-q^{2}\right)s_{4}s_{23}+\left(q^{-1}-q^{3}\right)s_{234}+q^{2}s_{14}s_{123}$
$\displaystyle s_{234}s_{12}$
$\displaystyle=\left(1-q^{2}\right)s_{2}s_{1234}+\left(1-q^{2}\right)s_{1}s_{34}+\left(q^{-1}-q^{3}\right)s_{134}+q^{2}s_{12}s_{234}$
$\displaystyle s_{234}s_{14}$
$\displaystyle=\left(1-q^{-2}\right)s_{4}s_{1234}+\left(1-q^{-2}\right)s_{1}s_{23}+\left(q-q^{-3}\right)s_{123}+q^{-2}s_{14}s_{234}$
$\displaystyle s_{134}s_{23}$
$\displaystyle=\left(1-q^{2}\right)s_{3}s_{1234}+\left(1-q^{2}\right)s_{2}s_{14}+\left(q^{-1}-q^{3}\right)s_{124}+q^{2}s_{23}s_{134}$
$\displaystyle s_{134}s_{12}$
$\displaystyle=\left(1-q^{-2}\right)s_{1}s_{1234}+\left(1-q^{-2}\right)s_{2}s_{34}+\left(q-q^{-3}\right)s_{234}+q^{-2}s_{12}s_{134}$
$\displaystyle s_{124}s_{23}$
$\displaystyle=\left(1-q^{-2}\right)s_{2}s_{1234}+\left(1-q^{-2}\right)s_{3}s_{14}+\left(q-q^{-3}\right)s_{134}+q^{-2}s_{23}s_{124}$
$\displaystyle s_{124}s_{34}$
$\displaystyle=\left(1-q^{2}\right)s_{4}s_{1234}+\left(1-q^{2}\right)s_{3}s_{12}+\left(q^{-1}-q^{3}\right)s_{123}+q^{2}s_{34}s_{124}$

###  A.3. Cubic Relations

$\displaystyle s_{34}s_{14}s_{13}$
$\displaystyle=-\left(q+2q^{-1}+q^{-3}\right)+q^{-1}s_{4}^{2}+q^{-1}s_{3}^{2}+q^{-1}s_{1}^{2}$
$\displaystyle+s_{3}s_{4}s_{34}+q^{-2}s_{1}s_{4}s_{14}+s_{1}s_{3}s_{13}+q^{-1}s_{1}s_{3}s_{4}s_{134}+qs_{34}^{2}+s_{1}s_{34}s_{134}$
$\displaystyle+q^{-3}s_{14}^{2}+q^{-2}s_{3}s_{14}s_{134}+qs_{13}^{2}+s_{4}s_{13}s_{134}+q^{-1}s_{134}^{2}$
$\displaystyle s_{12}s_{14}s_{24}$
$\displaystyle=-\left(q^{3}+2q+q^{-1}\right)+qs_{4}^{2}+qs_{2}^{2}+qs_{1}^{2}$
$\displaystyle+s_{1}s_{2}s_{12}+q^{2}s_{1}s_{4}s_{14}+s_{2}s_{4}s_{24}+qs_{1}s_{2}s_{4}s_{124}+q^{-1}s_{12}^{2}+s_{4}s_{12}s_{124}$
$\displaystyle+q^{3}s_{14}^{2}+q^{2}s_{2}s_{14}s_{124}+q^{-1}s_{24}^{2}+s_{1}s_{24}s_{124}+qs_{124}^{2}$
$\displaystyle s_{12}s_{23}s_{13}$
$\displaystyle=-\left(q+2q^{-1}+q^{-3}\right)+q^{-1}s_{3}^{2}+q^{-1}s_{2}^{2}+q^{-1}s_{1}^{2}$
$\displaystyle+s_{1}s_{2}s_{12}+q^{-2}s_{2}s_{3}s_{23}+s_{1}s_{3}s_{13}+q^{-1}s_{1}s_{2}s_{3}s_{123}+qs_{12}^{2}+s_{3}s_{12}s_{123}$
$\displaystyle+q^{-3}s_{23}^{2}+q^{-2}s_{1}s_{23}s_{123}+qs_{13}^{2}+s_{2}s_{13}s_{123}+q^{-1}s_{123}^{2}$
$\displaystyle s_{23}s_{34}s_{24}$
$\displaystyle=-\left(q+2q^{-1}+q^{-3}\right)+q^{-1}s_{4}^{2}+q^{-1}s_{3}^{2}+q^{-1}s_{2}^{2}$
$\displaystyle+s_{2}s_{3}s_{23}+q^{-2}s_{3}s_{4}s_{34}+s_{2}s_{4}s_{24}+q^{-1}s_{2}s_{3}s_{4}s_{234}+qs_{23}^{2}+s_{4}s_{23}s_{234}$
$\displaystyle+q^{-3}s_{34}^{2}+q^{-2}s_{2}s_{34}s_{234}+qs_{24}^{2}+s_{3}s_{24}s_{234}+q^{-1}s_{234}^{2}$

###  A.4. Cubic Relations with Triples

$\displaystyle s_{12}s_{14}s_{234}$
$\displaystyle=\left(q^{2}+1\right)s_{3}+qs_{1}s_{2}s_{4}s_{1234}-q^{2}s_{1}^{2}s_{3}+s_{4}s_{1234}s_{12}+qs_{2}s_{23}$
$\displaystyle+qs_{4}s_{34}+q^{2}s_{2}s_{1234}s_{14}-q^{3}s_{1}s_{13}+s_{1}s_{1234}s_{24}+s_{2}s_{4}s_{234}+qs_{1234}$
$\displaystyle+s_{124}+s_{1}s_{12}s_{23}+q^{-1}s_{12}s_{123}+q^{2}s_{1}s_{34}s_{14}+q^{3}s_{14}s_{134}+q^{-1}s_{24}s_{234}$
$\displaystyle s_{34}s_{14}s_{123}$
$\displaystyle=\left(1+q^{-2}\right)s_{2}+\left(1-q^{2}-q^{-2}\right)s_{2}s_{4}^{2}+q^{-1}s_{1}s_{3}s_{4}s_{1234}+q^{-1}s_{1}s_{12}$
$\displaystyle+q^{-1}s_{3}s_{23}+s_{1}s_{1234}s_{34}+q^{-2}s_{3}s_{1234}s_{14}+s_{4}s_{1234}s_{13}$
$\displaystyle+\left(-q^{3}+q^{-1}-q^{-3}\right)s_{4}s_{24}+s_{1}s_{3}s_{123}+\left(-q^{2}+1\right)s_{3}s_{4}s_{234}+q^{-1}s_{1234}s_{134}$
$\displaystyle+q^{-2}s_{4}s_{12}s_{14}+q^{2}s_{4}s_{23}s_{34}+qs_{34}s_{234}+q^{-3}s_{14}s_{124}+qs_{13}s_{123}$
$\displaystyle s_{23}s_{34}s_{124}$
$\displaystyle=q^{-1}s_{2}s_{3}s_{4}s_{1234}+\left(1+q^{-2}\right)s_{1}+-q^{2}s_{1}s_{3}^{2}+q^{-1}s_{2}s_{12}$
$\displaystyle(q^{2}+1)$
$\displaystyle+s_{4}s_{1234}s_{23}+q^{-2}s_{2}s_{1234}s_{34}+q^{-1}s_{4}s_{14}+\left(-q^{3}-q+q^{-1}\right)s_{3}s_{13}$
$\displaystyle+s_{3}s_{1234}s_{24}+\left(-q^{2}+1\right)s_{2}s_{3}s_{123}+q^{-1}s_{1234}s_{234}+\left(q^{-2}-1\right)s_{3}s_{4}s_{134}$
$\displaystyle+s_{2}s_{4}s_{124}+q^{2}s_{3}s_{12}s_{23}+qs_{23}s_{123}+s_{3}s_{34}s_{14}+q^{-3}s_{34}s_{134}+qs_{24}s_{124}$
$\displaystyle s_{12}s_{23}s_{134}$
$\displaystyle=\left(1+q^{-2}\right)s_{4}-s_{2}^{2}s_{4}+q^{-1}s_{1}s_{2}s_{3}s_{1234}+s_{3}s_{1234}s_{12}$
$\displaystyle+q^{-2}s_{1}s_{1234}s_{23}+q^{-1}s_{3}s_{34}+q^{-1}s_{1}s_{14}+s_{2}s_{1234}s_{13}-qs_{2}s_{24}$
$\displaystyle+q^{-1}s_{1234}s_{123}+\left(q^{-2}-1\right)s_{2}s_{3}s_{234}+s_{1}s_{3}s_{134}+s_{2}s_{12}s_{14}+qs_{12}s_{124}$
$\displaystyle+s_{2}s_{23}s_{34}+q^{-3}s_{23}s_{234}+qs_{13}s_{134}$

###  A.5. Quartic Relation

$\displaystyle s_{12}$ $\displaystyle s_{23}s_{34}s_{14}$
$\displaystyle=s_{1}s_{3}s_{12}s_{23}+s_{2}s_{4}s_{12}s_{14}+s_{2}s_{4}s_{23}s_{34}+s_{1}s_{3}s_{34}s_{14}$
$\displaystyle+\left(qs_{3}s_{12}+qs_{2}s_{13}+q^{-1}s_{1}s_{23}+s_{123}+q^{-1}s_{4}s_{1234}+s_{1}s_{2}s_{3}\right)s_{123}$
$\displaystyle+\left(qs_{4}s_{13}+qs_{3}s_{14}+q^{-1}s_{1}s_{34}+s_{134}+q^{-1}s_{2}s_{1234}+s_{1}s_{3}s_{4}\right)s_{134}$
$\displaystyle+\left(qs_{4}s_{12}+qs_{2}s_{14}+q^{-1}s_{1}s_{24}+s_{124}+q^{-1}s_{3}s_{1234}+s_{1}s_{2}s_{4}\right)s_{124}$
$\displaystyle+q^{-2}\left(q^{-1}s_{4}s_{23}+q^{-1}s_{3}s_{24}+q^{-1}s_{2}s_{34}+q^{-2}s_{234}+q^{-1}s_{1}s_{1234}+(2-q^{2})s_{2}s_{3}s_{4}\right)s_{234}$
$\displaystyle+\left(q^{2}s_{12}+\left(q+q^{-1}\right)s_{1}s_{2}+s_{3}s_{4}s_{1234}\right)s_{12}+\left(q^{-2}s_{23}+q^{-1}s_{2}s_{3}+q^{-2}s_{1}s_{4}s_{1234}\right)s_{23}$
$\displaystyle+\left(q^{2}s_{14}+\left(q+q^{-1}\right)s_{1}s_{4}+s_{2}s_{3}s_{1234}\right)s_{14}+\left(q^{-2}s_{34}+q^{-1}s_{3}s_{4}+q^{-2}s_{1}s_{2}s_{1234}\right)s_{34}$
$\displaystyle+\left(q^{-2}s_{24}+\left(q^{-1}-q\right)s_{2}s_{4}+q^{-2}s_{1}s_{3}s_{1234}\right)s_{24}+\left(q^{2}s_{13}+s_{2}s_{4}s_{1234}\right)s_{13}$
$\displaystyle+q^{-2}s_{1234}^{2}-s_{2}^{2}s_{4}^{2}-s_{1}^{2}s_{3}^{2}+q^{-1}s_{1}s_{2}s_{3}s_{4}s_{1234}+\left(2+q^{-2}\right)\left(s_{1}^{2}+s_{2}^{2}+s_{3}^{2}+s_{4}^{2}\right)$
$\displaystyle-2q^{2}-5-4q^{-2}-q^{-4}$

###  A.6. Loop Triple Relations

$\displaystyle s_{123}s_{134}$
$\displaystyle=-s_{2}s_{4}+s_{1234}s_{13}-\left(q+q^{-1}\right)s_{24}-s_{3}s_{234}-s_{1}s_{124}+s_{12}s_{14}+s_{23}s_{34}$
$\displaystyle s_{134}s_{123}$
$\displaystyle=\left(1-q^{2}-q^{-2}\right)s_{2}s_{4}+s_{1234}s_{13}-\left(q^{3}-q^{-3}\right)s_{24}-q^{2}s_{3}s_{234}-q^{-2}s_{1}s_{124}$
$\displaystyle+q^{-2}s_{12}s_{14}+q^{2}s_{23}s_{34}$ $\displaystyle
s_{234}s_{124}$
$\displaystyle=-q^{2}s_{1}s_{3}-\left(q^{3}+q\right)s_{13}+s_{1234}s_{24}-q^{2}s_{2}s_{123}-s_{4}s_{134}+q^{2}s_{12}s_{23}+s_{34}s_{14}$
$\displaystyle s_{124}s_{234}$
$\displaystyle=-q^{2}s_{1}s_{3}-\left(q^{3}+q\right)s_{13}+s_{1234}s_{24}-s_{2}s_{123}-q^{2}s_{4}s_{134}+s_{12}s_{23}+q^{2}s_{34}s_{14}$

###  A.7. Link Triple Relations

$\displaystyle s_{123}s_{234}$
$\displaystyle=q^{-1}s_{2}s_{3}s_{1234}+s_{1}s_{4}+\left(q^{-1}-q\right)s_{2}s_{4}s_{12}+s_{1234}s_{23}+\left(q+q^{-1}\right)s_{14}$
$\displaystyle+s_{3}s_{134}+q^{-2}s_{2}s_{124}-q^{2}s_{12}s_{24}-qs_{3}s_{12}s_{234}-s_{34}s_{13}-q^{-1}s_{2}s_{34}s_{123}$
$\displaystyle+qs_{12}s_{23}s_{34}$ $\displaystyle s_{234}s_{123}$
$\displaystyle=qs_{2}s_{3}s_{1234}+s_{1}s_{4}+\left(-q^{3}+q\right)s_{2}s_{4}s_{12}+s_{1234}s_{23}+\left(q+q^{-1}\right)s_{14}$
$\displaystyle+q^{2}s_{3}s_{134}+s_{2}s_{124}-q^{4}s_{12}s_{24}-q^{3}s_{3}s_{12}s_{234}-q^{2}s_{34}s_{13}-qs_{2}s_{34}s_{123}$
$\displaystyle+q^{3}s_{12}s_{23}s_{34}$ $\displaystyle s_{124}s_{134}$
$\displaystyle=s_{2}s_{3}+qs_{1}s_{4}s_{1234}+\left(q+q^{-1}\right)s_{23}+s_{1234}s_{14}+q^{2}s_{1}s_{123}$
$\displaystyle+s_{4}s_{234}-q^{2}s_{12}s_{13}-qs_{4}s_{12}s_{134}-s_{34}s_{24}-qs_{1}s_{34}s_{124}$
$\displaystyle+qs_{12}s_{34}s_{14}$ $\displaystyle s_{134}s_{124}$
$\displaystyle=s_{2}s_{3}+q^{-1}s_{1}s_{4}s_{1234}+\left(q+q^{-1}\right)s_{23}+s_{1234}s_{14}+s_{1}s_{123}$
$\displaystyle+q^{-2}s_{4}s_{234}-s_{12}s_{13}-q^{-1}s_{4}s_{12}s_{134}-q^{-2}s_{34}s_{24}-q^{-1}s_{1}s_{34}s_{124}$
$\displaystyle+q^{-1}s_{12}s_{34}s_{14}$ $\displaystyle s_{134}s_{234}$
$\displaystyle=qs_{3}s_{4}s_{1234}+s_{1}s_{2}+\left(q+q^{-1}\right)s_{12}+\left(-q^{3}+q\right)s_{1}s_{3}s_{23}+s_{1234}s_{34}$
$\displaystyle+s_{3}s_{123}+q^{2}s_{4}s_{124}-q^{4}s_{23}s_{13}-q^{3}s_{4}s_{23}s_{134}-q^{2}s_{14}s_{24}-qs_{3}s_{14}s_{234}$
$\displaystyle+q^{3}s_{23}s_{34}s_{14}$ $\displaystyle s_{234}s_{134}$
$\displaystyle=q^{-1}s_{3}s_{4}s_{1234}+s_{1}s_{2}+\left(q+q^{-1}\right)s_{12}+\left(q^{-1}-q\right)s_{1}s_{3}s_{23}+s_{1234}s_{34}$
$\displaystyle+q^{-2}s_{3}s_{123}+s_{4}s_{124}-q^{2}s_{23}s_{13}-qs_{4}s_{23}s_{134}-s_{14}s_{24}-q^{-1}s_{3}s_{14}s_{234}$
$\displaystyle+qs_{23}s_{34}s_{14}$ $\displaystyle s_{124}s_{123}$
$\displaystyle=\left(q^{2}-q^{-2}+q^{-4}\right)s_{3}s_{4}+\left(1-q^{-1}+q^{-3}\right)s_{1}s_{2}s_{1234}+s_{1234}s_{12}$
$\displaystyle+\left(q-q^{-1}\right)s_{2}s_{4}s_{23}+\left(q^{3}+q-q^{-1}+q^{-5}\right)s_{34}+\left(q^{-3}-q^{-1}\right)s_{1}s_{3}s_{14}$
$\displaystyle+\left(q^{2}-q^{-2}+q^{-4}\right)s_{2}s_{234}+\left(q^{2}-1+q^{-4}\right)s_{1}s_{134}-q^{-4}s_{23}s_{24}$
$\displaystyle-q^{-3}s_{1}s_{23}s_{124}-q^{2}s_{14}s_{13}-qs_{2}s_{14}s_{123}+q^{-1}s_{12}s_{23}s_{14}$
$\displaystyle s_{123}s_{124}$
$\displaystyle=\left(q^{4}-q^{2}+q^{-2}\right)s_{3}s_{4}+\left(q^{3}-q+q^{-1}\right)s_{1}s_{2}s_{1234}+s_{1234}s_{12}$
$\displaystyle+\left(q^{3}-q\right)s_{2}s_{4}s_{23}+\left(q^{5}-q+q^{-1}+q^{-3}\right)s_{34}+\left(q^{-1}-q\right)s_{1}s_{3}s_{14}$
$\displaystyle+\left(q^{4}-1+q^{-2}\right)s_{2}s_{234}+\left(q^{4}-q^{2}+q^{-2}\right)s_{1}s_{134}-q^{-2}s_{23}s_{24}$
$\displaystyle-q^{-1}s_{1}s_{23}s_{124}-q^{4}s_{14}s_{13}-q^{3}s_{2}s_{14}s_{123}+qs_{12}s_{23}s_{14}$

###  A.8. Crossing Relations

$\displaystyle s_{13}s_{24}$
$\displaystyle=\left(q+q^{-1}\right)s_{1234}+s_{1}s_{2}s_{3}s_{4}+q^{-1}s_{3}s_{4}s_{12}+qs_{1}s_{4}s_{23}+q^{-1}s_{1}s_{2}s_{34}$
$\displaystyle+qs_{2}s_{3}s_{14}+s_{4}s_{123}+s_{1}s_{234}+s_{2}s_{134}+s_{3}s_{124}+q^{-2}s_{12}s_{34}+q^{2}s_{23}s_{14}$
$\displaystyle s_{24}s_{13}$
$\displaystyle=\left(q+q^{-1}\right)s_{1234}+s_{1}s_{2}s_{3}s_{4}+qs_{3}s_{4}s_{12}+q^{-1}s_{1}s_{4}s_{23}+qs_{1}s_{2}s_{34}$
$\displaystyle+q^{-1}s_{2}s_{3}s_{14}+s_{4}s_{123}+s_{1}s_{234}+s_{2}s_{134}+s_{3}s_{124}+q^{2}s_{12}s_{34}+q^{-2}s_{23}s_{14}$

###  A.9. Double and Triple Crossing Relations

$\displaystyle s_{123}s_{24}$
$\displaystyle=-s_{2}s_{1234}-qs_{1}s_{3}s_{4}-s_{1}s_{34}-s_{3}s_{14}-q^{2}s_{4}s_{13}-qs_{2}s_{4}s_{123}$
$\displaystyle-\left(q+q^{-1}\right)s_{134}+qs_{4}s_{12}s_{23}+s_{12}s_{234}+s_{23}s_{124}$
$\displaystyle s_{234}s_{13}$
$\displaystyle=-s_{3}s_{1234}-qs_{1}s_{2}s_{4}-s_{4}s_{12}-s_{2}s_{14}-q^{2}s_{1}s_{24}-qs_{1}s_{3}s_{234}$
$\displaystyle-\left(q+q^{-1}\right)s_{124}+qs_{1}s_{23}s_{34}+s_{23}s_{134}+s_{34}s_{123}$
$\displaystyle s_{13}s_{124}$
$\displaystyle=-q^{-1}s_{2}s_{3}s_{4}+\left(1-q^{2}-q^{-2}\right)s_{1}s_{1234}-q^{2}s_{4}s_{23}-q^{-2}s_{2}s_{34}-q^{-2}s_{3}s_{24}$
$\displaystyle-\left(q^{3}-q^{-3}\right)s_{234}-q^{-1}s_{1}s_{3}s_{124}+q^{-1}s_{3}s_{12}s_{14}+q^{-2}s_{12}s_{134}+q^{2}s_{14}s_{123}$
$\displaystyle s_{24}s_{134}$
$\displaystyle=\left(1-q^{2}-q^{-2}\right)s_{4}s_{1234}-qs_{1}s_{2}s_{3}-q^{2}s_{3}s_{12}-q^{-2}s_{1}s_{23}-q^{2}s_{2}s_{13}$
$\displaystyle-\left(q^{3}-q^{-3}\right)s_{123}-qs_{2}s_{4}s_{134}+qs_{2}s_{34}s_{14}+q^{2}s_{34}s_{124}+q^{-2}s_{14}s_{234}$
$\displaystyle s_{24}s_{123}$
$\displaystyle=\left(1-q^{2}-q^{-2}\right)s_{2}s_{1234}-qs_{1}s_{3}s_{4}-q^{2}s_{1}s_{34}-q^{-2}s_{3}s_{14}-q^{2}s_{4}s_{13}$
$\displaystyle-
qs_{2}s_{4}s_{123}-\left(q^{3}-q^{-3}\right)s_{134}+qs_{4}s_{12}s_{23}+q^{2}s_{12}s_{234}+q^{-2}s_{23}s_{124}$
$\displaystyle s_{13}s_{234}$
$\displaystyle=\left(1-q^{2}-q^{-2}\right)s_{3}s_{1234}-qs_{1}s_{2}s_{4}-q^{-2}s_{4}s_{12}-q^{2}s_{2}s_{14}-q^{2}s_{1}s_{24}$
$\displaystyle-
qs_{1}s_{3}s_{234}-\left(q^{3}-q^{-3}\right)s_{124}+qs_{1}s_{23}s_{34}+q^{2}s_{23}s_{134}+q^{-2}s_{34}s_{123}$
$\displaystyle s_{134}s_{24}$
$\displaystyle=-s_{4}s_{1234}-qs_{1}s_{2}s_{3}-s_{3}s_{12}-s_{1}s_{23}-q^{2}s_{2}s_{13}-\left(q+q^{-1}\right)s_{123}$
$\displaystyle-
qs_{2}s_{4}s_{134}+qs_{2}s_{34}s_{14}+s_{34}s_{124}+s_{14}s_{234}$
$\displaystyle s_{124}s_{13}$
$\displaystyle=-q^{-1}s_{2}s_{3}s_{4}-s_{1}s_{1234}-s_{4}s_{23}-s_{2}s_{34}-q^{-2}s_{3}s_{24}-\left(q+q^{-1}\right)s_{234}$
$\displaystyle-q^{-1}s_{1}s_{3}s_{124}+q^{-1}s_{3}s_{12}s_{14}+s_{12}s_{134}+s_{14}s_{123}$

## References

  * [AGS96] Anton Yu. Alekseev, Harald Grosse and Volker Schomerus  “Combinatorial quantization of the Hamiltonian Chern-Simons theory. II”  In _Comm. Math. Phys._ 174.3, 1996, pp. 561–604  URL: http://projecteuclid.org/euclid.cmp/1104275486
  * [Ale94] Anton Yu. Alekseev  “Integrability in the Hamiltonian Chern-Simons theory”  In _Algebra i Analiz_ 6.2, 1994, pp. 53–66
  * [Bas05] Pascal Baseilhac  “Deformed Dolan-Grady relations in quantum integrable models”  In _Nuclear Phys. B_ 709.3, 2005, pp. 491–521  DOI: 10.1016/j.nuclphysb.2004.12.016
  * [BB13] Pascal Baseilhac and Samuel Belliard  “The half-infinite XXZ chain in Onsager’s approach”  In _Nuclear Phys. B_ 873.3, 2013, pp. 550–584  DOI: 10.1016/j.nuclphysb.2013.05.003
  * [BCP19] Pascal Baseilhac, Nicolas Crampé and Rodrigo A. Pimenta  “Higher rank classical analogs of the Askey-Wilson algebra from the $sl_{N}$ Onsager algebra”  In _J. Math. Phys._ 60.8, 2019, pp. 081703, 13  DOI: 10.1063/1.5111292
  * [Ber78] George M. Bergman  “The diamond lemma for ring theory”  In _Adv. in Math._ 29.2, 1978, pp. 178–218  DOI: 10.1016/0001-8708(78)90010-5
  * [BFKB99] Doug Bullock, Charles Frohman and Joanna Kania-Bartoszyńska  “Understanding the Kauffman bracket skein module”  In _J. Knot Theory Ramifications_ 8.3, 1999, pp. 265–277  DOI: 10.1142/S0218216599000183
  * [BJ17] Adrien Brochier and David Jordan  “Fourier transform for quantum $D$-modules via the punctured torus mapping class group”  In _Quantum Topol._ 8.2, 2017, pp. 361–379  DOI: 10.4171/QT/92
  * [BK05] Pascal Baseilhac and Kozo Koizumi  “A deformed analogue of Onsager’s symmetry in the $XXZ$ open spin chain”  In _J. Stat. Mech. Theory Exp._ , 2005, pp. P10005, 15  DOI: 10.1088/1742-5468/2005/10/p10005
  * [BP00] Doug Bullock and Józef H. Przytycki  “Multiplicative structure of Kauffman bracket skein module quantizations”  In _Proc. Amer. Math. Soc._ 128.3, 2000, pp. 923–931  DOI: 10.1090/S0002-9939-99-05043-1
  * [BS18] Yuri Berest and Peter Samuelson  “Affine cubic surfaces and character varieties of knots”  In _J. Algebra_ 500, 2018, pp. 644–690  DOI: 10.1016/j.jalgebra.2017.11.015
  * [Bul97] Doug Bullock  “Rings of $\mathrm{SL}_{2}({\mathbf{C}})$-characters and the Kauffman bracket skein module”  In _Comment. Math. Helv._ 72.4, 1997, pp. 521–542  DOI: 10.1007/s000140050032
  * [Bul99] Doug Bullock  “A finite set of generators for the Kauffman bracket skein algebra”  In _Math. Z._ 231.1, 1999, pp. 91–101  DOI: 10.1007/PL00004727
  * [Cas17] Bill Casselman  “Essays on representations of real groups: introduction to Lie algebras” https://personal.math.ubc.ca/cass/research/pdf/Lalg.pdf, 2017
  * [CL20] Francesco Costantino and Thang T. Q. Lê  “Stated skein algebras of surfaces”, 2020  arXiv:1907.11400 [math.GT]
  * [Coo19] Juliet Cooke  “Excision of Skein Categories and Factorisation Homology”, 2019  arXiv:1910.02630 [math.QA]
  * [Coo19a] Juliet Cooke  “Factorisation Homology and Skein Categories of Surfaces”, 2019
  * [Coo20] Juliet Cooke  “Kauffman skein algebras and quantum Teichmüller spaces via factorization homology”  In _J. Knot Theory Ramifications_ 29.14, 2020, pp. 2050089, 54  DOI: 10.1142/S0218216520500893
  * [Cra+20] Nicolas Crampé, Julien Gaboriaud, Luc Vinet and Meri Zaimi  “Revisiting the Askey-Wilson algebra with the universal $R$-matrix of $U_{q}(\mathfrak{sl}_{2})$”  In _J. Phys. A_ 53.5, 2020, pp. 05LT01, 10  DOI: 10.1088/1751-8121/ab604e
  * [Cra+21] Nicolas Crampé et al.  “The Askey-Wilson algebra and its avatars”  In _J. Phys. A_ 54.6, 2021, pp. Paper No. 063001, 32  DOI: 10.1088/1751-8121/abd783
  * [Cra+21a] Nicolas Crampe, Julien Gaboriaud, Loïc Poulain d’Andecy and Luc Vinet  “Racah algebras, the centralizer $Z_{n}(\mathfrak{sl}_{2})$ and its Hilbert-Poincaré series”, 2021  arXiv:2105.01086 [math.RT]
  * [DBDCV20] Hendrik De Bie, Hadewijch De Clercq and Wouter Vijver  “The Higher Rank $q$-Deformed Bannai-Ito and Askey-Wilson Algebra”  In _Comm. Math. Phys._ 374.1, 2020, pp. 277–316  DOI: 10.1007/s00220-019-03562-w
  * [De ̵19] Hadewijch De Clercq  “Higher rank relations for the Askey-Wilson and $q$-Bannai-Ito algebra”  In _SIGMA Symmetry Integrability Geom. Methods Appl._ 15, 2019, pp. Paper No. 099, 32  DOI: 10.3842/SIGMA.2019.099
  * [DM03] J. Donin and A. Mudrov  “Reflection equation, twist, and equivariant quantization”  In _Israel J. Math._ 136, 2003, pp. 11–28  DOI: 10.1007/BF02807191
  * [Fai20] Matthieu Faitg  “Holonomy and (stated) skein algebras in combinatorial quantization”  In _arXiv e-prints_ , 2020, pp. arXiv:2003.08992  arXiv:2003.08992 [math.QA]
  * [FSW03] Gaetano Fiore, Harold Steinacker and Julius Wess  “Unbraiding the braided tensor product”  In _J. Math. Phys._ 44.3, 2003, pp. 1297–1321  DOI: 10.1063/1.1522818
  * [GJS19] Sam Gunningham, David Jordan and Pavel Safronov  “The finiteness conjecture for skein modules”, 2019  arXiv:1908.05233 [math.QA]
  * [Haï21] Benjamin Haïoun  “Relating stated skein algebras and internal skein algebras”, 2021  arXiv:2104.13848 [math.QA]
  * [Hik19] Kazuhiro Hikami  “DAHA and skein algebra of surfaces: double-torus knots”  In _Lett. Math. Phys._ 109.10, 2019, pp. 2305–2358  DOI: 10.1007/s11005-019-01189-5
  * [Hua17] Hau-Wen Huang  “An embedding of the universal Askey-Wilson algebra into $U_{q}(\mathfrak{sl}_{2})\otimes U_{q}(\mathfrak{sl}_{2})\otimes U_{q}(\mathfrak{sl}_{2})$”  In _Nuclear Phys. B_ 922, 2017, pp. 401–434  DOI: 10.1016/j.nuclphysb.2017.07.007
  * [Jan96] Jens Carsten Jantzen  “Lectures on quantum groups” 6, Graduate Studies in Mathematics  American Mathematical Society, Providence, RI, 1996, pp. viii+266  DOI: 10.1090/gsm/006
  * [JF21] Theo Johnson-Freyd  “Heisenberg-picture quantum field theory”  In _Representation theory, mathematical physics, and integrable systems_ 340, Progr. Math.  Birkhäuser/Springer, Cham, [2021] ©2021, pp. 371–409
  * [JL92] Anthony Joseph and Gail Letzter  “Local finiteness of the adjoint action for quantized enveloping algebras”  In _J. Algebra_ 153.2, 1992, pp. 289–318  DOI: 10.1016/0021-8693(92)90157-H
  * [JT21] Alexander Kirillov Jr and Ying Hong Tham  “Factorization Homology and 4D TQFT”, 2021  arXiv:2002.08571 [math.QA]
  * [KL94] Louis H. Kauffman and Sóstenes L. Lins  “Temperley-Lieb recoupling theory and invariants of $3$-manifolds” 134, Annals of Mathematics Studies  Princeton University Press, Princeton, NJ, 1994, pp. x+296  DOI: 10.1515/9781400882533
  * [Koo07] Tom H. Koornwinder  “The relationship between Zhedanov’s algebra ${\rm AW}(3)$ and the double affine Hecke algebra in the rank one case”  In _SIGMA Symmetry Integrability Geom. Methods Appl._ 3, 2007, pp. Paper 063, 15  DOI: 10.3842/SIGMA.2007.063
  * [KS97] Anatoli Klimyk and Konrad Schmüdgen  “Quantum groups and their representations”, Texts and Monographs in Physics  Springer-Verlag, Berlin, 1997, pp. xx+552  DOI: 10.1007/978-3-642-60896-4
  * [Kul96] Petr P. Kulish  “Yang-Baxter equation and reflection equations in integrable models”  In _Low-dimensional models in statistical physics and quantum field theory (Schladming, 1995)_ 469, Lecture Notes in Phys.  Springer, Berlin, 1996, pp. 125–144  DOI: 10.1007/BFb0102555
  * [Lê18] Thang T. Q. Lê  “Triangular decomposition of skein algebras”  In _Quantum Topol._ 9.3, 2018, pp. 591–632  DOI: 10.4171/QT/115
  * [Lic93] W. B. R. Lickorish  “Skeins and handlebodies”  In _Pacific J. Math._ 159.2, 1993, pp. 337–349  URL: http://projecteuclid.org/euclid.pjm/1102634266
  * [Lus10] G. Lusztig  “Introduction to Quantum Groups”, Modern Birkhäuser Classics  Birkhäuser Boston, 2010  URL: https://books.google.co.uk/books?id=HKPjCUiOUQ0C
  * [Maj91] Shahn Majid  “Braided groups and algebraic quantum field theories”  In _Letters in Mathematical Physics_ 22.3, 1991, pp. 167–175  DOI: 10.1007/BF00403542
  * [Maj95] Shahn Majid  “Foundations of quantum group theory”  Cambridge University Press, Cambridge, 1995, pp. x+607  DOI: 10.1017/CBO9780511613104
  * [MV94] Gregor Masbaum and Pierre Vogel  “$3$-valent graphs and the Kauffman bracket”  In _Pacific J. Math._ 164.2, 1994, pp. 361–381  URL: http://projecteuclid.org/euclid.pjm/1102622100
  * [NS04] Masatoshi Noumi and Jasper V. Stokman  “Askey-Wilson polynomials: an affine Hecke algebra approach”  In _Laredo Lectures on Orthogonal Polynomials and Special Functions_ , Adv. Theory Spec. Funct. Orthogonal Polynomials  Nova Sci. Publ., Hauppauge, NY, 2004, pp. 111–144
  * [PS00] Józef H. Przytycki and Adam S. Sikora  “On skein algebras and $\mathrm{SL}_{2}({\mathbf{C}})$-character varieties”  In _Topology_ 39.1, 2000, pp. 115–148  DOI: 10.1016/S0040-9383(98)00062-7
  * [PW17] Sarah Post and Anthony Walter  “A higher rank extension of the Askey-Wilson Algebra”, 2017  arXiv:1705.01860 [math.QA]
  * [RTF89] N. Yu. Reshetikhin, L. A. Takhtadzhyan and L. D. Faddeev  “Quantization of Lie groups and Lie algebras”  In _Algebra i Analiz_ 1.1, 1989, pp. 178–206
  * [Ter01] Paul Terwilliger  “Two relations that generalize the $q$-Serre relations and the Dolan-Grady relations”  In _Physics and combinatorics 1999 (Nagoya)_ World Sci. Publ., River Edge, NJ, 2001, pp. 377–398  DOI: 10.1142/9789812810199“˙0013
  * [Ter11] Paul Terwilliger  “The Universal Askey-Wilson Algebra”  In _SIGMA Symmetry Integrability Geom. Methods Appl._ 7, 2011, pp. Paper 069, 24
  * [Ter13] Paul Terwilliger  “The universal Askey-Wilson algebra and DAHA of type $(C^{\vee}_{1},C_{1})$”  In _SIGMA Symmetry Integrability Geom. Methods Appl._ 9, 2013, pp. Paper 047, 40  DOI: 10.3842/SIGMA.2013.047
  * [TV04] Paul Terwilliger and Raimundas Vidunas  “Leonard pairs and the Askey-Wilson relations”  In _J. Algebra Appl._ 3.4, 2004, pp. 411–426  DOI: 10.1142/S0219498804000940
  * [USW04] Masaru Uchiyama, Tomohiro Sasamoto and Miki Wadati  “Asymmetric simple exclusion process with open boundaries and Askey-Wilson polynomials”  In _J. Phys. A_ 37.18, 2004, pp. 4985–5002  DOI: 10.1088/0305-4470/37/18/006
  * [VY20] Christian Voigt and Robert Yuncken  “Complex semisimple quantum groups and representation theory” 2264, Lecture Notes in Mathematics  Springer, Cham, [2020] ©2020, pp. x+374  DOI: 10.1007/978-3-030-52463-0
  * [Wal06] Kevin Walker  “TQFTs [early incomplete draft]”, http://canyon23.net/math/tc.pdf, 2006
  * [Zhe91] Alexei S. Zhedanov  ““Hidden symmetry” of Askey-Wilson polynomials”  In _Teoret. Mat. Fiz._ 89.2, 1991, pp. 190–204  DOI: 10.1007/BF01015906