# On Models and Approaches for Human Vital Signs Extraction from Short Range
Radar Signals

Mikolaj Czerkawski, Christos Ilioudis, Carmine Clemente, Craig Michie, Ivan
Andonovic, Christos Tachtatzis  Department of Electronic and Electrical
Engineering, University of Strathclyde, Glasgow G1 1XW, UK

###### Abstract

The paper centres on an assessment of the modelling approaches for the
processing of signals in CW and FMCW radar-based systems for the detection of
vital signs. It is shown that the use of the widely adopted phase extraction
method, which relies on the approximation of the target as a single point
scatterer, has limitations in respect of the simultaneous estimation of both
respiratory and heart rates. A method based on a velocity spectrum is proposed
as an alternative with the ability to treat a wider range of application
scenarios.

###### Index Terms:

Doppler processing, FMCW radar, heart rate monitoring, micro-Doppler,
millimeter wave radar, non-contact monitoring, respiration rate monitoring,
vital signs.

##  I Introduction

The remote detection of vital signs from Doppler derived measurements using
radar has been subject to significant research [1, 2, 3, 4]. The capability to
detect both respiration and heart rate without physical contact represents the
foundation for the development of a number of applications [5, 4, 6, 7],
ranging from monitoring patients with specific conditions, such as sleep
apnea, to patients where constant monitoring of the vital signs is advised due
to risks of the onset of life-threatening conditions.

Early implementations of non-contact vital sign monitoring were based on CW
radar technology. Recently more compact, low-cost Frequency Modulated
Continuous Wave (FMCW) platforms with the capability to map the environment in
range and velocity have become more readily available. Regardless of radar
mode, the approach to the processing of signals has remained relatively
unchanged.

Reported FMCW-based vital sign detection solutions to date, have relied on a
traditional phase extraction approach [8, 9, 10, 11]. The phase of the
reflection vector is extracted, unwrapped and interpreted as changes in range,
proportional to the mechanical motions induced by in this application, organ
contractions. At its core is the assumption that the target may be faithfully
represented as a single point scatterer, demonstrated to be inappropriate when
both of these vital signs are of interest.

The paper investigates the effectiveness of the phase-based approach to
estimate vital signs; the interpretation of the signal is significantly more
challenging if the model does not represent the observed target sufficiently
well. Two approaches to modelling vital signs using a (i) single point
scatterer and (ii) two point scatterers models are assessed, described in
Section II. Section III presents a simulation-based evaluation of the
effectiveness of the extraction of the phase for the two models in the goal of
deriving both respiratory and heart rate simultaneously. Key conclusions are
drawn within Section IV.

##  II Modelling Approaches

Breathing and heart rates may be described as two dynamic components
$R_{b}(t)$ and $R_{h}(t)$, equal to the local changes in distance owing to
each motion. Both motions are normally periodic but with different amplitudes,
harmonic content (affecting the shape of the motion trace) and frequencies.

The simplest approach to modelling vital signs is to assume an offset-radius
$R_{0}$ corresponding to the distance to the centre of the target and to add
to it both of the dynamic components:

$\displaystyle R(t)=R_{0}+R_{b}(t)+R_{h}(t)$ (1)

The inherent assumption is that the animate object can be modelled by a single
point scatterer, proven to be an adequate approximation for scenarios where
both vital signs are present with a preserved ratio of amplitudes
$\frac{A_{b}}{A_{h}}$ in each section of the target surface. However, this is
rarely the case. Lung inflation stretches a wide portion of the torso,
resulting in high amplitude motions ($A_{b}$), whilst the heartbeat motion is
predominately propagated by the cardiovascular system. Consequently, under
these conditions, only the respiratory motion is readily detectable.

The limitation has motivated research to estimate the Radar Cross-Section
(RCS) for each of the human vital signs [12, 13], with the conclusions that
the RCS for respiration is consistently and significantly larger than that for
heartbeat. Furthermore, [14] report that the manifestation of each vital sign
is distributed differently over the body, further evidence that the modelling
of the target as a single scattering point has limitations.

The model for a baseband received signal can be written as:

$\displaystyle s(t)=|X_{0}|e^{j\frac{4\pi}{\lambda}(R_{b}(t)+R_{h}(t))}$ (2)

where $|X_{0}|$ is the effective received spectrum magnitude due to the
superposition of a number of scattering points111At this point, $R_{0}$
contribution to the signal may be omitted in all equations considered in this
analysis since it only results in a constant phase offset due to multiplying
the received signal by $e^{j\frac{4\pi}{\lambda}R_{0}}$. Ultimately, only the
dynamic components of the range trace are of interest. and $\lambda$
represents the carrier wavelength. Equation (2) may lead to a limited
description of what is being observed, especially in cases with a significant
difference in RCS between vital signs.

Therefore, a more appropriate approach is to model the vital signs as two
distinct point scatterers:

$\displaystyle s(t)=|X_{r}|e^{j\frac{4\pi
R_{b}(t)}{\lambda}}+|X_{h}|e^{j\frac{4\pi R_{h}(t)}{\lambda}}$ (3)

where $|X_{r}|$ and $|X_{h}|$ represent the effective magnitudes corresponding
to each vital sign.

Previous research executed phase extraction by applying an inverse tangent
function to the quadrature components followed by the unwrapping of the
obtained vector [8, 9, 10, 11], approximating the target as a single point
scatterer described by (2). The dynamic phase, $\phi_{1p}(t)$ reduces to the
sum of the two vital sign contributions:

$\displaystyle\phi_{1p}(t)=\frac{4\pi}{\lambda}\left[R_{b}(t)+R_{h}(t)\right]$
(4)

The two point model, on the other hand, leads to a substantially different
dynamic phase term, $\phi_{2p}(t)$:

$\displaystyle\phi_{2p}(t)=$
$\displaystyle\textrm{arctan}\left(\frac{|X_{r}|\sin(\frac{4\pi}{\lambda}R_{b}(t))+|X_{h}|\sin(\frac{4\pi}{\lambda}R_{h}(t))}{|X_{r}|\cos(\frac{4\pi}{\lambda}R_{b}(t))+|X_{h}|\cos(\frac{4\pi}{\lambda}R_{h}(t))}\right)$
(5)

It is clear that for a point scatterer model, it is possible to fully recover
all of the dynamic range information. However, for a case where the two vital
signs are not distributed equally over the surface, the phase term is no
longer a linear combination of $R_{b}(t)$ and $R_{h}(t)$.

The respiratory motion is not only of much higher amplitude but is also
present over a wider area than the heartbeat-induced motions, leading to
$|X_{r}|>>|X_{h}|$. In that case, the phase term for the two point scatterers
model approaches the limit of $\frac{4\pi}{\lambda}R_{b}(t)$. At the same
time, the heartbeat component in the signal extracted from the phase becomes
negligible.

Equation (3) describes the dynamic content of $s(t)$ as a sum of complex
exponential components. Fourier Transformation (FT) then becomes a suitable
decomposition method. Using Short-Time FT and converting the Doppler frequency
to velocity, generates a matrix of velocity spectra distributed over time,
referred to as velocity-time maps.

A simulation environment that generates synthetic motion signals corresponding
to each vital sign was established and these signals were subsequently
analysed to assess the performance of the two processing methods under
consideration.

##  III Simulation Results

The simulation was carried out for constant vital sign rates and a V-Band
Radar carrier of 60 GHz, with the settings listed in Table I. The rates of the
vital signs were selected such that none of the harmonics of the respiratory
component interfere with the heart rate spectrum.

TABLE I: Simulated System Settings Respiration Rate, $f_{b}$ | 0.2 Hz
---|---
Heart Rate, $f_{h}$ | 1.1 Hz
H-R Ratio | -10 dB
Sample Rate | 120 sps
Carrier Frequency | 60 GHz
Respiratory Motion Amplitude, $A_{b}$ | 1.0 cm
Heartbeat Motion Amplitude, $A_{h}$ | 0.1 mm

The synthesis of the signal utilises two equations in order to obtain curves
representative of the real vital signs. The applied approximations for the
range displacements have been informed by a significant number of experiments
capturing motions owing to the heartbeat [15], or respiration [16].

$\displaystyle
R_{b}(t)=A_{b}\frac{5-2^{2+\cos(2\pi\int_{-\infty}^{t}f_{b}(t)dt)}}{3}$ (6)
$\displaystyle
R_{h}(t)=A_{h}\sin\left(2\pi\text{mod}(-\int_{-\infty}^{t}f_{h}(t)dt,1)^{10}\right)$
(7)

Each equation can be expressed as a product of an amplitude $A_{b}$, $A_{h}$
and a term that oscillates between -1 and 1, dependent on the corresponding
vital sign rate $f_{b}$ or $f_{h}$. The purpose of (6) and (7) is to emulate
the harmonic content of each vital sign signal, observed in the time domain as
a bell-like shape of the respiration curve (Figure 1), or the impulse property
of the heart rate signal (Figure 2).

Figure 1: Simulated Displacement due to Respiration Figure 2: Simulated
Displacement due to Heart Activity

The single point scatterer model assumes that these two motions contribute to
the reflected signal phase equally, as if both motions were superimposed
across the entire target (Figure 3) and reflected.

Figure 3: Sum of the Simulated Displacements

An analysis of the synthesised signals was carried out to determine their
impact on the Doppler spectrum. The signals are described by (6) and (7) and
were substituted as $d(t)$ to the phase of a complex reflection vector
$s(t)=e^{j\frac{4\pi}{\lambda}d(t)}$.

The analysis of the simulated data was executed at a 0.1 second Doppler-
analysis window applied over a 60 seconds recording. Figure 4 and Figure 5
show the resultant velocity-time maps of both synthesised vital signs. The
velocity translation is carried out using the Doppler equation
$v=-\frac{\lambda}{2}f_{D}$. The simulated respiration signal is relatively
strong and evident is that the shape contained in Figure 4 matches the shape
of the derivative curve (velocity) of the respiratory motion signal. The
heartbeat velocity-time map is harder to interpret because of the low
amplitude generated by motion of the heart. Even though the motion is weak for
the whole derived shape to be clearly visible, a velocity impulse
corresponding to the original signal is nevertheless apparent every 1.1
seconds.

Figure 4: Velocity Time Map of the synthesised Respiration Component Figure 5:
Velocity Time Map of the synthesised Pulse Component

For the simultaneous detection of the vital signs, the two modelling
frameworks along with two processing methods were compared to inform the
selection of the optimum approach for the application under development.

Figure 6 shows the result based on a single point scatterer moving according
to both vital sign motions simultaneously. The motion can be faithfully
reconstructed by extracting the phase of the complex signal and unwrapping.
The top plot shows the unwrapped phase, proportional to the detected velocity.
The alternative is to compute the velocity-time map, as shown in the bottom
graph. It is clear that rates of both vital signs can be extracted from the
map, the respiration as the low-frequency modulation of low velocities whilst
the heart rate as the higher frequency impulse modulation of high velocities.
Both processing techniques can estimate the rates with the phase extraction
technique from a single point scatterer being less computationally expensive
than the velocity-time map analysis.

Figure 6: Processing Output of Single Point Scatterer Signal

The challenge of extracting vital sign rates becomes more difficult when the
target resembles two separate point scatterers. Since the heart rate signal is
not only of lower amplitude but also present over a much smaller area, its
contribution to the net phase of the complex signal may be negligible. As is
evident in Figure 7, the extracted phase derivative is distorted and whilst
the respiratory motion velocity is preserved, the heart rate component is less
apparent.

Figure 7: Processing Output of Two Point Scatterers Signal

Figure 8 and 9 show the spectrum of the unwrapped phase for each of the two
models. For the two point scatterers model, the phase spectrum can only be
used to extract the respiration rate. In the case of a single point scatterer,
the results are clear, comprising a series of respiratory components at every
0.2 Hz, and a series of heart rate harmonics at every 1.1 Hz. By arranging the
strong components into harmonic groups, both vital signs can be reliably
extracted.

Figure 8: Spectrum of the Unwrapped Phase of the Single Point Scatterer Figure
9: Spectrum of the Unwrapped Phase of Two Point Scatterers

The limitation of the phase extraction technique can be contrasted with
results using velocity-time map (bottom graph of Figure 7). Although the
impulse component in the high-velocity band is not as strong as in the case of
the single point scatterer model (since the heart complex reflection component
is 10 dB lower than the respiration vector), it is nevertheless possible to
observe impulses at the period of the heartbeat.

Further, the high bandwidth impulses due to the heartbeat that are most
apparent for high velocities can be used to extract a time-domain spectrum
magnitude vector for a selected velocity. For illustration, 14.7 cm/s was
chosen. Applying an FT to this time signal leads to the result presented in
Figure 10. With this approach, the heartbeat component of the signal is
dominated by respiratory harmonics. One solution is to apply a logarithm to
the vector in the time domain before computing the spectrum, an operation
equivalent to computing the spectrum of the values shown in Figure 7 (bottom)
since all of the spectrograms in the paper are plotted in dB scale. The
logarithm operation is capable of compressing the dynamic range and
emphasising the impulsive components of the signal.

Figure 10: Spectrum of 14.7 cm/s for the Two Point Scatterers Figure 11:
Spectrum of 14.7 cm/s logarithm for the Single Point Scatterer Figure 12:
Spectrum of 14.7 cm/s logarithm for the Two Point Scatterers

Figure 11 and Figure 12 show the spectrum of the logarithm of the selected
velocity. Apart from the low-frequency peaks at the multiples of 0.2 Hz (due
to the respiration), the majority of high peaks are located at multiples of
1.1 Hz, representative of the heart rate.

The analysis confirms that velocity-time maps can be analysed more extensively
to yield vital signs. In scenarios where the phase extraction method limits
the estimation of the heart rate, the more complex Doppler spectrum provides a
better foundation for carrying out the analysis.

##  IV Conclusion

Reported research to date has suggested that the manifestation of the two
human vital signs are distributed on the target’s surface over different areas
and with different effective RCSs. The analysis presented provides evidence
that in the goal of estimating both respiration and heart rates
simultaneously, it is more appropriate to utilise a two point scatterers model
of a living target than the more traditional single point scatterer model. The
former treats more general scenarios and this degree of generality is of value
in the development of solutions addressing typical real-world applications.
The key advantage of the velocity-time map method is that it is capable of
extracting both vital signs regardless of which model represents the factual
environment.

## Acknowledgment

This work was funded by EPSRC under Grant EP/R513349/1.

## References

  * [1] J.. Lin  “Noninvasive microwave measurement of respiration”  In _Proceedings of the IEEE_ 63.10, 1975, pp. 1530–1530  DOI: 10.1109/PROC.1975.9992
  * [2] B. Lohman et al.  “A digital signal processor for Doppler radar sensing of vital signs”  In _IEEE Engineering in Medicine and Biology Magazine_ 21.5, 2002, pp. 161–164  DOI: 10.1109/MEMB.2002.1044188
  * [3] Dennis R. Morgan and Michael G. Zierdt  “Novel signal processing techniques for Doppler radar cardiopulmonary sensing”  In _Signal Processing_ 89.1, 2009, pp. 45–66  DOI: https://doi.org/10.1016/j.sigpro.2008.07.008
  * [4] C. Li, V.. Lubecke, O. Boric-Lubecke and J. Lin  “A Review on Recent Advances in Doppler Radar Sensors for Noncontact Healthcare Monitoring”  In _IEEE Transactions on Microwave Theory and Techniques_ 61.5, 2013, pp. 2046–2060  DOI: 10.1109/TMTT.2013.2256924
  * [5] W. Massagram, V.. Lubecke, A. HØst-Madsen and O. Boric-Lubecke  “Assessment of Heart Rate Variability and Respiratory Sinus Arrhythmia via Doppler Radar”  In _IEEE Transactions on Microwave Theory and Techniques_ 57.10, 2009, pp. 2542–2549  DOI: 10.1109/TMTT.2009.2029716
  * [6] H. Zhao et al.  “A Noncontact Breathing Disorder Recognition System Using 2.4-GHz Digital-IF Doppler Radar”  In _IEEE Journal of Biomedical and Health Informatics_ 23.1, 2019, pp. 208–217  DOI: 10.1109/JBHI.2018.2817258
  * [7] H. Hong et al.  “Noncontact Sleep Stage Estimation Using a CW Doppler Radar”  In _IEEE Journal on Emerging and Selected Topics in Circuits and Systems_ 8.2, 2018, pp. 260–270  DOI: 10.1109/JETCAS.2017.2789278
  * [8] S. Wang et al.  “A novel ultra-wideband 80 GHz FMCW radar system for contactless monitoring of vital signs”  In _2015 37th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC)_ , 2015, pp. 4978–4981  DOI: 10.1109/EMBC.2015.7319509
  * [9] J. Muñoz-Ferreras, Z. Peng, R. Gómez-García and C. Li  “Random body movement mitigation for FMCW-radar-based vital-sign monitoring”  In _2016 IEEE Topical Conference on Biomedical Wireless Technologies, Networks, and Sensing Systems (BioWireleSS)_ , 2016, pp. 22–24  DOI: 10.1109/BIOWIRELESS.2016.7445551
  * [10] J. Muñoz-Ferreras et al.  “FMCW-Radar-Based Vital-Sign Monitoring of Multiple Patients”  In _2019 IEEE MTT-S International Microwave Biomedical Conference (IMBioC)_ 1, 2019, pp. 1–3  DOI: 10.1109/IMBIOC.2019.8777845
  * [11] M. Alizadeh et al.  “Remote Monitoring of Human Vital Signs Using mm-Wave FMCW Radar”  In _IEEE Access_ 7, 2019, pp. 54958–54968  DOI: 10.1109/ACCESS.2019.2912956
  * [12] Ø. Aardal et al.  “Radar cross section of the human heartbeat and respiration”  In _2010 Biomedical Circuits and Systems Conference (BioCAS)_ , 2010, pp. 53–57  DOI: 10.1109/BIOCAS.2010.5709569
  * [13] Ø. Aardal et al.  “Radar cross section of the human heartbeat and respiration in the 500MHz to 3GHz band”  In _2011 IEEE Radio and Wireless Symposium_ , 2011, pp. 422–425  DOI: 10.1109/RWS.2011.5725466
  * [14] K. Kishimoto et al.  “Evaluation of vital sign distribution using array antenna”  In _2017 International Symposium on Antennas and Propagation (ISAP)_ , 2017, pp. 1–2  DOI: 10.1109/ISANP.2017.8228835
  * [15] K. Mohri, T. Jinnouchi and K. Kawano  “Accurate mechanocardiogram sensors using amorphous star-shaped core multivibrator combined with a magnet”  In _IEEE Transactions on Magnetics_ 23.5, 1987, pp. 2212–2214  DOI: 10.1109/TMAG.1987.1065639
  * [16] C.. Merritt, H.. Nagle and E. Grant  “Textile-Based Capacitive Sensors for Respiration Monitoring”  In _IEEE Sensors Journal_ 9.1, 2009, pp. 71–78  DOI: 10.1109/JSEN.2008.2010356


where $q$ is an integer and $a_1, \dots, a_q$ are elements of $\field$ and the morphism $f_i$ is a non zero composition of $u_{k}^{R}$ morphisms. In other words, there exists a sequence $k^f_1, \dots k^f_{p_f}$ such that $f_i = u_{k^f_{p_f}}\circ\dots\circ u_{k^f_{1}}$. Suppose $F(\sum_{i=1}^q a_i\cdot f_i) = 0$ in $\mathcal{Y}_{m,n}$. We can also assume $f_1\not = 0$ and $\alpha_1 \not = 0$. The previous Lemma ensures that zero relations, i.e when $q=1$ correspond exactly to those described in Lemma <ref>. To conclude when $q>1$ we want to argue that sequences $k^f_1, \dots k^f_{p_f}$ contain the same elements, independently of $i$.

By Lemmas <ref>, <ref> and <ref> there exists a list $C$ of transformations to go from $\alpha$ to $\beta$. We argue that it is the only possible list. Suppose $L$ is a list of transformations giving a non zero morphism from $\alpha$ to $\beta$. Order both $C$ and $L$ using the order relation $\prec$ with starting point $k_{min}$ the minimum of the starting points for $C$ and $L$. If there exists $s$ an element of $L$ which is not in $C$ pick $s$ minimal for $\prec$. Then using the transformations listed by $L$, $s-1 \in \beta$ but through $C$, $s-1\not\in \beta$ which is a contradiction. Hence all the elements of $L$ appear in $C$. Symmetrically, all the elements of $C$ appear in $L$.

Denote $f^{\star}$ the composition of the maps associated to the list in increasing order of their combinatorial datum. Note that Lemma  <ref> and its proof apply to the category $C$ as well since the proof only relied on the relations $\rho_{k, l}$ and $z_{k}$. Hence there exist elements $a, b\in \field$ such that $f_1 - a\cdot f^{\star}=0$ in $\mathcal{C}$ and $-\frac{1}{a_1}\sum_{i=2}a_i\cdot f_i - b\cdot f^{\star}$ in $\mathcal{C}$. Because $F(\sum_{i=1}^q a_i\cdot f_i) = 0$ in $\mathcal{Y}_{m,n}$, $a= -b$ and $\sum_{i=1}^q a_i\cdot f_i = 0$ in $C$.

For a configuration $R$ as well as an integer $0 \leq l \in R$ and $0 > k\in R$, define
\[\kappa(R, l) = \sum_{\substack{r \in R\\ l \geq r\geq 0}} r \text{ and } \nu(R, k) = \sum_{k \geq r\in R} r.\]
We establish a number of identities concerning $\kappa$ and $\nu$ combined with a transformation $\sigma_l^-$. Let $l_1$ and $l_2$ be allowed in $R_+$. Without loss of generality we can assume that $l_1 < l_2$. Then $\kappa(\sigma^-_{l_1}(R), l_2) = \kappa(R, l_2) - 1$ while $\kappa(\sigma^-_{l_2}(R), l_1) = \kappa(R, l_1)$. Hence $\kappa$ is a combinatorial statistic that detects the event $l_1\leq l_2$. Similarly, if $k_1$ and  $k_2$ are allowed in $R_-$ and $k_1 < k_2$ then $\nu(\sigma^-_{k_1}(R), k_2) = \nu(R, k_2) - 1$ while $\nu(\sigma^-_{k_2}(R), k_1) = \nu(R, k_1)$. Hence $\nu$ detects the event $k_1 < k_2$. Combining the two statistics we get $\kappa(\sigma^-_k(R), l) = \kappa(R, l)$ and $\nu(\sigma^-_l(R), k) = \nu(R, k)$.
Alternatively we can define these quantities on partitions. We will only use the quantity $\kappa$ which we express as follows: let $\alpha$ be a partition, $i$ be allowed in $S_{\alpha}$ and set

\begin{equation}\label{eq:shift}
\kappa(\alpha, i) = \sum_{k = 1}^i \lambda_k.
\end{equation}

Because it will be used several times, we write $\kappa_{\alpha} = \kappa_R = \kappa(\alpha, i) = \kappa(R, R_{max})$.

To conclude this subsection, we give three presentations of the category $\mathcal{Y}_{m,n}$. The first one is a direct corollary of Proposition <ref> with the relations of Lemma <ref>. According to equation (<ref>), with that presentation some squares of elementary morphisms commute and some anticommute. Using Notations <ref> we give two more presentations, one where all the squares commute and one where they all anticommute.

The morphisms in $\mathcal{Y}_{m,n}$ are generated by

* the maps $u_k^R$ for all $R\in C_{m,n}$ and for all $k\in R$ allowed, with relations generated by $\rho_{k,l}^R = u_l^{\sigma_k^-(R)}\circ u_{k}^R - \varepsilon u^{\sigma^-_l(R)}_k \circ u_l^R $ where $k, l\in R$ such that $k - 1, l - 1 \not\in R$ and $\varepsilon = -1$ if $k$ and $l$ are positive and $1$ otherwise, along with $z_{k}^R = u_{k}^{\sigma^-_{k-1}(R)}\circ u_{k}^R$ where $k\in R$, but $k-1, k-2 \not\in R$;

* the maps $v_{k}^R = (-1)^{\kappa(R, k)}\cdot u_k^R$ for all $R\in C_{m,n}$ and for all $k\in R$ allowed, with relations generated by $(\rho'_{k,l})^{R} = v_l^{\sigma_k^-(R)}\circ v_{k}^R - v^{\sigma^-_l(R)}_k \circ v_l^R $ where $k, l\in R$ such that $k - 1, l - 1 \not\in R$ along with $(z'_{k})^R = v_{k-1}^{\sigma^-_k(R)}\circ v_{k}^R$ where $k\in R$, but $k-1, k-2 \not\in R$;

* the morphisms $w_{k}^R = \varepsilon(R,k)(-1)$ for all $R\in C_{m,n}$ with $\varepsilon(R, k) = (-1)^{\nu(R, k) +\kappa_R}$ if $k < 0$ and $\varepsilon(R, k) = 1$ otherwise, for all $k\in R$ allowed, with relations generated by $(\rho_{k,l}'')^R = w_l^{\sigma_k^-(R)}\circ w_{k}^R + w^{\sigma^-_l(R)}_k \circ w_l^R $ where $k, l\in R$ such that $k - 1, l - 1 \not\in R$ along with $(z_k'')^R = w_{k-1}^{\sigma^-_k(R)}\circ  w_{k}^R$ where $k\in R$, but $k-1, k-2 \not\in R$.

The presentation with relations as per item <ref> follows directly from the previous discussion. The morphisms $\{v_k^{R}\}_{k,r}$ and $\{w_k^{R}\}_{k,r}$ still form generating sets for the morphisms differing from their $u_{k}^R$ counterpart by a unit. Moreover, the zero relations $z^R_k, (z'_k)^R$ and $(z_k'')^R$ are also proportional for each $R$ and $k$. We will now show that the same is true for the square relations as per the following computations. Without loss of generality we can assume that $k\leq l$. We first consider te relations from item <ref>. We write the terms of the relations as follows

\begin{align*}
v_l^{\sigma^-_k(R)}\circ v_k^R &= (-1)^{\kappa(R, k) + \kappa(\sigma^-_k(R),l)}\cdot u_l^{\sigma_k^-(R)}\circ u_{k}^R,\\
v_k^{\sigma^-_l(R)}\circ v_l^R &= (-1)^{\kappa(R, l) + \kappa(\sigma^-_l(R),k)}\cdot u^{\sigma^-_l(R)}_k \circ u_l^R.
\end{align*}

If $k$ is negative, then

\[\kappa(R, k) + \kappa(\sigma^-_k(R),l) = \kappa(R, l) + \kappa(\sigma^-_l(R),k).\]

Hence we have

\[(\rho'_{k,l})^R = v_l^{\sigma^-_k(R)}\circ v_k^R - v_k^{\sigma^-_l(R)}\circ v_l^R = (-1)^{\kappa(R, k) + \kappa(\sigma^-_k(R),l)} \cdot\rho_{k,l}^R.\]
Otherwise, from the computation in Notation <ref> we have
$\kappa(R, k) = \kappa(\sigma_l^-(R), k)$ and
$\kappa(R, l) = \kappa(\sigma_k^-(R), l) + 1$
which implies

\begin{align*}
&= v_l^{\sigma^-_k(R)}\circ v_k^R - v_k^{\sigma^-_l(R)}\circ v_l^R \\
&= (-1)^{\kappa(R, k) + \kappa(\sigma^-_k(R),l)} \cdot(u_l^{\sigma_k^-(R)}\circ u_{k}^R + u^{\sigma^-_l(R)}_k\circ u_l^R)\\	&= (-1)^{\kappa(R, k) + \kappa(\sigma^-_k(R),l)}\cdot\rho_{k,l}^R.
\end{align*}

For the square relations of item <ref> we distinguish three cases. When $k \geq 0$ and $l \geq 0$ we have $\varepsilon(\sigma_l^-(R), k)=\varepsilon(R, l) = \varepsilon(\sigma_k^-(R), l)=\varepsilon(R, k) = 1$ so $(\rho''_{k,l})^R = \rho_{k,l}^R$. Next, when $k<0 \leq l$ we still have $\varepsilon(R, l) = 1 = \varepsilon (\sigma_k^-(R), l)$. However, by Notation <ref> we have,

\[\varepsilon(\sigma_l^-(R), k) = (-1)^{\nu(\sigma_l^-(R), k) + \kappa_{\sigma_l^-(R)}} = (-1)^{\nu(R, k) + \kappa_{R} -1 } = -\varepsilon(R, k),\]

so it holds that

\begin{align*}(\rho''_{k,l})^R &= w_l^{\sigma_k^-(R)}\circ w_{k}^R + w^{\sigma^-_l(R)}_k \circ w_l^R\\
&=\varepsilon(R, k) \cdot u_l^{\sigma_k^-(R)}\circ w_{k}^R + \varepsilon(\sigma_l^-(R), k) \cdot u^{\sigma^-_l(R)}_k \circ u_l^R\\
&=\varepsilon(R,k) \cdot \rho_{k,l}^R.\end{align*}

Finally, when $k<l<0$ we compute

\[\varepsilon(\sigma_l^-(R), k) = (-1)^{\nu(\sigma_l^-(R), k) + \kappa_{\sigma_l^-(R)}} = (-1)^{\nu(R, k) + \kappa_{R}} =\varepsilon(R, k)\]

\[\varepsilon(R, l) = (-1)^{\nu(R, l) + \kappa_{R}} = (-1)^{\nu(\sigma_k^-(R), l)+ 1 + \kappa_{\sigma_k^-(R)}} = - \varepsilon(\sigma_k^-(R), l)\]

which yields, after similar computations

\[(\rho''_{k,l})^R = -\varepsilon(R,k)\varepsilon(R,l) \cdot \rho_{k,l}^R\]

and completes the proof.

§.§ Tilting object

We now consider the subcategory of $\mathcal{Y_{m,n}}$ spanned by the plain partitions, i.e. the partitions that satisfy $\mu_{r+1} = 0$ which simply corresponds to the elements of $J_{m,n}$.
The subcategory $\Thicc(\{\PRes_{\alpha} | \alpha\in J_{m,n}\})$ is the category of perfect complexes of $J_{m,n}$.

In the proof of the main result of section <ref> we constructed by induction each projective module as the end of a sequence of cones starting in  $\mathcal{Y}_{m,n}$. The argument  only relied on the fact that each projective had a quotient belonging to the family $(\PRes_{\alpha})_{\alpha}$. Restricting the family to the modules associated with plain partitions, i.e those with the bar pushed all the way to the right, proves the claim about $\Thicc(T)$.

Using notation <ref> we set

\begin{equation}\label{eq:tiltings}
T: = \bigoplus_{\alpha\in J_{m,n}} \PRes_{\alpha}[\kappa_{\alpha}].
\end{equation}

The goal of the rest of this section is to prove that this complex is a tilting complex, meaning it has no self extensions, and to compute the algebra $\End{T}^{op}$. We can hope to do so because we know the extensions only appear in one degree for each couple of summands of $T$. Shifting each summand of $T$ by $\kappa_{\alpha}$ amounts to concentrate all the morphisms in degree zero. Note that it is not possible for any subgraph of figure (<ref>).

The object $T$ has no self extensions.

First note that the quantity $\kappa_{\alpha}$ only depends on the non zero values of a partition i.e the one indexed by $S_{\alpha}$. Hence if there is a morphism in degree zero $\PRes_{\alpha}\to \PRes_{\beta}$ then $\kappa_{\alpha} = \kappa_{\beta}$. This follows from Item <ref> of Lemma <ref>, the fact that we only look at plain partitions and the fact that the quantity $\kappa_{\alpha}$ does not depend on the multiplicity of zero. Moreover, if $J$ is allowed, $|J| = p$ then $\kappa_{q_J(\alpha)} = \kappa_{\alpha} + p$. We put these two remarks together. If there exists a non zero morphism

\begin{equation}
\PRes_{\alpha}[\kappa_{\alpha}] \to \PRes_{\beta}[\kappa_{\beta}][p]
\end{equation}

by Proposition <ref>, there exists a unique subset $J$ of $S_{\alpha}$ $q_J(\alpha) \in [f(\beta), \beta]$ and $|J| = -\kappa_{\alpha} + \kappa_{\beta} + p$. Because $J$ is allowed for $\alpha$, $\kappa_{\alpha} = \kappa_{q_J(\alpha)} - |J|$. Because there is a non zero morphism of modules from $\PRes_{q_{J}(\alpha)}$ to $\PRes_{\beta}$, we have $\kappa_{\beta} = \kappa_{q_J(\alpha)}$. Thus, $|J| = \kappa_{\beta} - \kappa_{\alpha}$, $p=0$ and $T$ has no self extensions.

Proposition <ref> together with lemma <ref> show that the objet $T$ is tilting. We now describe its algebra of endomorphisms and to do so we recall the construction of higher Auslander algebras of type $A$ following convention from <cit.>. Note that we compose arrows using a different convention but everything else is written as close to that source as possible. Let $d$ and $s$ be integers. The higher Auslander algebra of type $A_s^d$ is constructed as a quotient of a quiver algebra by relations. The underlying set of the quiver is the set of increasing sequences of length $d+1$ with values in $\{1, \dots, d+s\}$. Let $x = (x_0,\dots, x_d)$ be an element of $Q_0$. For $k\in x$, we define a partial transformation $\sigma_k^+$ on $Q_0$ by

\[\sigma_k^+(x) = (x_0<\dots x_{i} < k + 1 < x_{i+2} < \dots x_d)\]

whenever the resulting sequence is increasing i.e $x_{i+2} \not = k + 1$. Similarly we write $\sigma^-_k$ for the partial  map that replaces $k$ by $k-1$ in the sequence whenever possible. Let $Q_1$ the set of arrows of the quiver consist of elements $\alpha_k^x$ with source $x$ and target $\sigma_k^+(x)$ whenever the target is well defined. In the path algebra of the resulting quiver $\IncAlg_{(Q)}$ we consider the ideal generated by the following elements

\begin{equation*}
\rho^x_{k,l} =  \begin{cases}
\alpha_k^{\sigma_l^+(x)}\alpha_l^x - \alpha_l^{\sigma_k^+(x)}\alpha_k^x & \text{ if } k, l\in x \text{ and } k + 1, l+1 \not \in x,\\
\alpha_k^{\sigma_{k+1}^+(x)}\alpha_{k+1}^x&\text{ if } l= k+1 \in x \text{ and } l + 1\not\in x.\\
\end{cases}
\end{equation*}

Then we set $(\IncAlg(Q)/ I)^{op}$ to be the higher Auslander algebra $A_s^d$. With these relations and the usual grading by length of paths it is clear that $A_s^d$ is quadratic. Its quadratic dual is

\[A^{!} = (\IncAlg(Q)^{op}/(I^{\bot}))^{op}\]

where $\IncAlg(Q)^{op}\cong \IncAlg(Q^{op})$ and $I^{\bot}$ is the orthogonal complement of $I$ in the dual of $\IncAlg(Q)_{2}$, the vector space with basis the paths of length two in the quiver $Q$<cit.>. It remains to compute the orthogonal of $I$ in $\IncAlg(Q)^{op}$ to get a presentation of the quadratic dual as a quiver with relations.

The orthogonal component $I^{\bot}$ of $I$, is generated as an ideal by

\begin{equation*}
\begin{cases}
(\alpha_k^x)^{op}(\alpha_l^{\sigma_k^+(x)})^{op} + (\alpha_l^x)^{op}(\alpha_k^{\sigma_l^+(x)})^{op}\\
\end{cases}
\end{equation*}

where $k, l\in x$ while $k+1, l+1\not\in x$.

It is clear that these elements are in $I^{\bot}$. We know that
$$\dim I + \dim I^{\bot} = \dim \IncAlg(Q)_2.$$
We argue that the set above is precisely $I^{\bot}$ for reasons of cardinality. To do so, notice that the composition of two arrows in the quiver modifies either one or two elements of the sequence. The case where it modifies one element corresponds to the first relations in the equation above. When two elements are modified there are two cases. Either the order matters or it does not. If it does then we are in the case of the zero relations of $A_s^d$. If it doesn't, than the 2-path appears in the commutation relation of $A_s^d$ but also in the anticommutation relation we exhibited for $(A_s^d)^{!}$ just now. Hence there is a partition of a basis of $\IncAlg(Q)_2$ into the paths in $I$ and $I^{\bot}$.

Note that in the quadratic dual, squares commute with a sign i.e $ab + cd = 0$. What remains to prove for Theorem <ref> is that the signs of the squares can be modulated meaning that we can construct ismorphisms between the quiver algebra modulo relations with $ab + cd = 0$ and then one with $ab - cd = 0$ for some square relations in the ideal $I$. This is not true for general quotients of paths algebras but it holds for certain configurations of squares in $J_{m,n}$  and $A_s^d$. Note that $A_s^d$ and $(A_s^d)^{op}$ are isomorphic.

The restriction of the presentation of $\mathcal{Y}_{m,n}$ given in <ref> item <ref> to the indecomposable components of the object $T$ correspond exactly to the presentation of $A_{m+1}^{n-1}$ after replacing the configurations by their complements in $\mathcal{Z}$ and shifting them by $+m$. See Figure (<ref>) to see how taking the complement of the configuration gives a relation that matches one in $A_{m+1}^{n-1}$.

(.5, 0.6)node[](circle1) circle (2pt);
(-0.1, 0.5) rectangle node[](rect1) (0.1,0.7);
(-0.6, 0.5) rectangle (-0.4,0.7);
[->](circle1) – (rect1);
[->](0,0.75) edge [bend left = 50] (.5,.7);

(0.4, 0.1) rectangle (0.6, 0.3);
(0, 0.2) node[](circle2) circle (2pt);
(-0.6, 0.1) rectanglenode[](rect2) (-0.4,0.3);
[->](circle2) – (rect2);
[->](-0.5,0.35) edge [bend left = 50] (0,.3);

(0.4, -0.3) rectangle (0.6, -0.1);
(-0.1, -0.3) rectangle (0.1,-0.1);
(-0.5, -0.2) circle (2pt);

illustrating the duality of the relations

The algebra $J_{m, n}$ is derived equivalent to $(A_{n+1}^{m-1})^{!}$.

The generators and relations of the algebra $\End(T)^{op}$ given in <ref> item <ref> after restricting to the tilting object are exactly the relations of the quadratic dual of $A_{n+1}^{m-1}$ described in Proposition <ref> after shifting the values of the configurations by $+m$.

As a direct corollary of the proof we have the following nice result which is probably well known but for which i have not found a suitable reference in the literature.
There is an isomorphism of algebras between $A_s^d$ and the quadratic dual of $A_{d+2}^{s-2}$.

=0mu plus 3mu

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

Princeton University Press, Princeton, NJ

seriesPrinceton Math. Ser.
titleHomological algebra

Cambridge: Cambridge Univ. Press

journaltitleCamb. Stud. Adv. Math.
titleAn introduction to homological algebra.
pagesxiv + 450

Course at École Normale Supérieure, Paris

howpublishedNotes taken by J. Bellaïche, J.-F. Dat, I. Marin, G. Racinet and H. Randriambololona
titleTriangulated categories and geometry

journaltitlePac. J. Math.
titleKoszul equivalences and dualities.

journaltitleAdv. Math.
titleAuslander correspondence.

titleUniversal derived equivalences of posets of cluster tilting objects
Representation Theory (math.RT),Combinatorics (math.CO),FOS: Mathematics,FOS: Mathematics,16G20; 06A11; 18E30

Zürich: European Mathematical Society (EMS)

booktitleTrends in representation theory of algebras and related topics. Proceedings of the 12th international conference on representations of algebras and workshop (ICRA XII), Toruń, Poland, August 15–24, 2007.
titleAuslander-Reiten theory revisited.

journaltitleAdv. Math.
titleA combinatorial rule for (co)minuscule Schubert calculus

John Wiley & Sons, Chichester; London Mathematical Society, London

issn0024-6093; 1469-2120/e
journaltitleBull. Lond. Math. Soc.
title\(n\)-representation-finite algebras and twisted fractionally Calabi-Yau algebras

Cham: Springer

seriesAlgebr. Appl.
titleRepresentation theory. A homological algebra point of view.

journaltitleColloq. Math.
titleThe periodicity conjecture for blocks of group algebras.

journaltitleAdv. Math.
noteId/No 106762
titleSimplicial strucures in higher Auslander-Reiten theory

Springer Netherlands, Dordrecht

issn1386-923X; 1572-9079/e
journaltitleAlgebr. Represent. Theory
titleThe Coxeter transformation on cominuscule posets

Cambridge University Press

journaltitleForum of Mathematics, Sigma
titleThe symplectic geometry of higher Auslander algebras: Symmetric products of disks

journaltitleJ. Pure Appl. Algebra
noteId/No 106583
titleClassification of higher wide subcategories for higher Auslander algebras of type \(A\)

journaltitleAdv. Math.
noteId/No 107885
titleThe bounded derived categories of the Tamari lattices are fractionally Calabi-Yau

journaltitleAdv. Math.
noteId/No 108233
titleDistributive lattices and Auslander regular algebras

titlePosets and Fractional Calabi-Yau Categories

titleSymplectic higher Auslander correspondence for type A

journaltitleAlgebras and Representation Theory
titleSerre Functors and Graded Categories
family=Stacks project authors,

titleThe Stacks project

titlePeriodic trivial extension algebras and fractionally Calabi-Yau algebras
family=Wikipedia contributors,

howpublished<https://en.wikipedia.org/w/index.php?title=Bubble_sort   oldid=1215273569>
note[Online; accessed 25-March-2024]
titleBubble sort — Wikipedia, The Free Encyclopedia

Tal Gottesman

Université Paris Cité and Sorbonne Université, CNRS, IMJ-PRG, F-75013 Paris, France.

Email address:


11institutetext: Bernhard Haslhofer, Rainer Simon 22institutetext: Austrian
Institute of Technology, 22email<EMAIL_ADDRESS>33institutetext: Antoine Isaac 44institutetext: Europeana, 44email:
<EMAIL_ADDRESS>
# Knowledge Graphs in the Libraries and Digital Humanities Domain

Bernhard Haslhofer and Antoine Isaac and Rainer Simon

##  1 Definition

Knowledge graphs represent concepts (e.g., people, places, events) and their
semantic relationships. As a data structure, they underpin a digital
information system, support users in resource discovery and retrieval, and are
useful for navigation and visualization purposes. Within the libaries and
humanities domain, knowledge graphs are typically rooted in _knowledge
organization systems_ , which have a century-old tradition and have undergone
their digital transformation with the advent of the Web and Linked Data. Being
exposed to the Web, metadata and concept definitions are now forming an
interconnected and decentralized global knowledge network that can be curated
and enriched by community-driven editorial processes. In the future, knowledge
graphs could be vehicles for formalizing and connecting findings and insights
derived from the analysis of possibly large-scale corpora in the libraries and
digital humanities domain.

##  2 Overview

The term “knowledge graph” was popularized in 2012 (Singhal 2012) with the
announcement of the “Google Knowledge Graph”, which gathers and formalizes
information from several sources in order to enhance search results. Knowledge
graphs can be generic and cover a broad range of domains, or they can be
tailored to a specific domain or application context. They typically integrate
data from multiple, heterogeneous sources and provide both a human-
interpretable representation as well as a formalized machine-readable basis
for information retrieval tasks, such as (latent) semantic indexing,
classification or query recommendation. Well-known examples for openly
available, generic knowledge graphs are DBpedia (Auer et al 2007), Freebase
(Bollacker et al 2008), or Wikidata (Vrandečić and Krötzsch 2014).

Within the libraries and digital humanities domain, the concept of a knowledge
graph is deeply rooted in knowledge organization systems, which is an umbrella
term for vocabularies such as a classification schemes, thesaurus, or
glossary.

Knowledge organization systems have a centuries-old tradition in the library
domain, where they have been used in metadata descriptions to organize
resources and facilitate their discovery and retrieval. With the advent of
Linked Data (Bizer et al 2009), knowledge organization systems — and metadata
descriptions making use them — have undergone a digital transformation and
entered the realm of the World Wide Web. By linking them with semantically
related Web resources within and outside the library domain, they are now
forming an interconnected and decentralized global knowledge graph.

The development of knowledge graphs also has a long-standing tradition in the
Humanities. For a long time, scholarly efforts have been concerned with the
curation of authoritative data on e.g. places or people within a specific
domain, resulting in taxonomies, gazetteers, and prosopgraphies. In terms of
their digital transformation, these knowledge graphs have been following a
similar pattern as knowledge organization schemes in libraries: they are
increasingly being published according to Linked Data principles, and
connected to other knowledge graphs on the Web, using shared semantic
concepts.

Members of both domains soon realized that knowledge graphs can be curated and
enriched by community-driven editorial processes, similar to those of
Wikipedia. As a result, processes emerged that either allow users to directly
edit a knowledge graph or provide mechanisms such as semantic tagging to
support enriching corpora with concepts from knowledge graphs.

Cross-domain knowledge graphs, as they are emerging in the libraries and
digital humanities domain, open a whole new spectrum of research
opportunities. They can, for instance, inform the design of quantitative
analytics tasks being applied on possibly large-scale document corpora. Taking
into account the numerous digitization efforts in the library and humanities
domain, knowledge graphs can be vehicles for connecting and exchanging
findings as well as factual knowledge gained by applying those task on copora.
This can also stimulate the development of novel, mixed methods research
methodologies.

##  3 Knowledge Organization Systems in Libraries

Libraries have long identified the value of maintaining (meta)data about their
holdings. Over centuries the classical form of the book-based catalog has
evolved into card-based catalogs and then electronic catalogs organized around
the _record_ unit, representing data about one of the library’s holdings (a
monograph, a journal issue, etc). Library science developed resources and
methods to rationalize the way these data were produced and exploited. The
first of them were designed for classification and subject indexing, such as
the Dewey Decimal Classification (DDC), the Universal Decimal Classification
(UDC) or the Library of Congress Subject Headings (LCSH). Classification
schemes, subject heading lists, thesauri and other taxonomies were engineered
to guide the description of the subjects of library assets (or their type).
Name authority files and gazetteers played a similar role as organized
listings of names for persons, organizations and places. All these are
composed of elements (classes, concepts, names, etc.) that are provided with
lexical information (variants, synonyms) or semantic information (especially,
hierarchical or associative links), which qualifies them as knowledge
organization systems. They also constitute vast bodies of knowledge, with
dozens of thousands of concepts (LCSH contained 342,107 authority records in
April 2017) that are richly described (UDC classes exist in over 40
languages).

In parallel, the structure of records was also the subject of much
rationalization efforts, with description rules being agreed at the level of
thematic or geographic communities. As libraries became (early) adopters of
electronic information systems, these gave rise to formats geared for exchange
of bibliographic metadata, such as MARC, which defines lists of codes for the
fields in records (title, author, subject, etc).

The need for structure and control within library systems came at the same
time as a need to share and collaborate. Rather than each developing their own
knowledge organization systems, libraries sought to share and re-use existing
ones: classifications like UDC, thesauri like AGROVOC, subject heading lists
like LCSH or RAMEAU are used in entire networks of libraries. They can be seen
as collaboratively built systems, as all the organizations that use them can
contribute updates, even as one of them plays a leading role for maintenance
and quality control. A similar form of sharing happens at the level of the
datasets describing assets: _union cataloguing_ systems have been put in place
so that consortia of libraries can refer to an existing description of a book,
possibly after adding to it, rather than creating a new – probably poorer –
one from scratch. This pooling of data gives even more importance to the
knowledge organization systems backing these datasets, and raised the
motivation for enhancing their coverage and quality over time.

Of course, full standardization is not attainable, and overlapping
vocabularies have been built, e.g., specific to a (sub-)domain or a (group of)
country(ies). This became a problem when libraries needed a higher level of
interoperability for their data. In some cases it has been addressed: the
Virtual International Authority File (VIAF) has managed to consolidate links
between the reference lists of persons and organization from dozens of (mostly
national) libraries into a multilingual dataset (43 million clusters of links
in 2014). MACS (Multilingual ACcess to Subjects) was another notable project,
in which the national libraries of Switzerland, France and Germany have teamed
with the British Library to create thousands of links across the subject
heading lists LCSH, RAMEAU and SWD.

Considering the long standing knowledge organization tradition in libraries,
one can conclude that libraries have established systems resembling the
characteristics of today’s knowledge graphs. And indeed the Mundaneum, an
early 20th century attempt to build a universal repository of facts, heavily
inspired by library science, has been sometimes acknowledged as a precursor of
the Semantic Web notion. Yet, as the W3C Incubator Group on Library Linked
Data (W3C 2011) has put it, more than twenty years after the invention of the
Web, the library and Semantic Web communities had similar metadata concepts,
but still different terminology; traditional library standards were designed
only for the library community; library data was not well integrated with Web
resources; and still expressed primarily in presentation-oriented, natural-
language text.

##  4 Library Linked Data

The adoption of the Linked Data principles is a major step in the transition
from library-centric knowledge organization systems to domain-spanning, openly
available, and easily accessible knowledge graphs. These principles postulate
a conceptual representation of library objects and concepts as first-class Web
resources and then propose (i) the assignment of unique Web identifiers (URI)
to these resources, (ii) the provision of machine-readable metadata describing
these resources, and (iii) linkage of resources with semantically related
resources in other datasets or knowledge organization systems. Those
principles are being adopted in the publication of metadata element sets and
value vocabularies, as detailed in the reports of the W3C Library Linked Data
Incubator Group. This provided the basis for a number of data aggregation,
linkage and exposure efforts producing a large variety of library linked
datasets.

### Metadata Element Sets

A metadata element set provides elements (e.g., title, date, subject) to be
used to describe a resource (e.g., a book), like the the aforementioned MARC.
Within the scope of Linked Data, metadata element sets are typically defined
using RDF Schema (Brickley and R.V.Guha 2014) or the OWL Web Ontology Language
(Hitzler et al 2012). Besides supporting the definition of elements
(properties), those schema or ontology definition languages also provide
primitives for describing groups of related resources (classes) and the
relationships between these resources. Important metadata element sets within
the Library Linked Data field are the Dublin Core Metadata Element Set (DCMI
2012), the Bibliographic Framework Initiative (BIBFRAME) vocabulary or the
Resource Description and Access (RDA) element set. Interestingly, Dublin Core
was developed at the time when the notions of the Semantic Web were
articulated, with several key people involved in both initiatives, which
positioned it as one of the most used vocabularies in Library Linked Data and
beyond.

### Value Vocabularies

A value vocabulary defines concepts that are used in the value space of
bibliographic metadata records – cataloging rules in libraries often require
terms of certain vocabularies to be used with certain metadata elements. Value
vocabularies include knowledge organization systems such as introduced above,
and their semantic expressiveness ranges from flat term definition lists
(glossaries), over hierarchical structures such as classification schemes and
taxonomies, to more connected vocabularies like thesauri.

Within the context of Linked Data, concepts defined as part of value
vocabularies should be first-class resources identified by dereferenceable
HTTP URIs. Concepts can be linked to other concepts within the same value
vocabulary as well as to other concepts, possibly defined by another domain.
The Simple Knowledge Organization System (SKOS) (Baker et al 2013) has become
the de facto standard for expressing the basic structure and content of
controlled value vocabularies.

A number of value vocabularies established in the library field were made
available as Linked Data: LCSH (Summers et al 2008), the multilingual AGROVOC
thesaurus (Caracciolo et al 2013), VIAF, several national authority files
(e.g., German GND), the Getty vocabularies (Getty 2017) as well as parts of
the Dewey Decimal Classification (OCLC 2017).

The terms ’ontology’ and ’vocabulary’ are often used to refer both to metadata
element sets and value vocabularies. Their role in the making of Linked Data
differ quite significantly however. Descriptions typically reuse elements from
standard metadata element sets in combination with elements from value
vocabularies. Figure 1 shows an example bibliographic metadata description
with metadata fields taken from a metadata element set and a value vocabulary
concept.

Figure 1: Library Linked Data Example and Notions.

### Library Linked Datasets

Within the last decade, a number of instutions have published collections of
metadata records as linked data on the Web. Such records typically describe
books, but other types of cultural objects can be described too.

The Hungarian and Swedish National (Malmsten 2008) libraries, who opened and
exposed their OPAC catalog and corresponding authority files around the year
2008, were among the earlier adopters of the Linked Data principles. The
British National Bibliography (BNB) (Deliot 2014) is a prominent Linked
Library example which also links to external sources such as VIAF or LCSH.
This was followed by many other data publication initatives on an
institutional or service level, including the Amsterdam Museum (De Boer et al
2012b), the CrossRef service, the Linked Open Library Data project, or Linked
Art, which is a community working together to create a shared Linked Data
model to describe art.

In parallel to instution- and service-level linked data publication
initatives, major metadata aggregation hubs across libraries and other
institutions, such as Europeana (Haslhofer and Isaac 2011) and the Digital
Public Library of America (DPLA) (DPLA 2017) started to expose collected
cross-domain metadata records as Linked Open Data on a larger scale (as of
2017 Europeana and DPLA provide access to over 51 and 18 million objects,
respectively) and to link them with other sources such as Wikidata. An
important milestone achieved by these efforts was the wider adoption of public
domain and (standard) open licenses (like the ones of Creative Commons) for
the metadata. This has not only been a major business shift for libraries, but
also fulfilled two important preconditions for building large-scale, cross-
domain knowledge graphs: the ability to mix and match library data with data
from other sources, and the possibility to edit and enhance knowledge graphs
under control of a larger community.

##  5 Community-driven Knowledge Graph Enrichment

In the early days of linked data, most knowledge graphs were published out of
existing institutional repositories or extracted from public knowledge sources
(e.g., Wikipedia) in a rather static, ’push’ fashion. The community soon
realized however that knowledge graphs can be curated by community-driven
editoral processes similar to those of Wikipedia.

A strong form of community-driven knowledge graph enrichment was provided by
Freebase (Bollacker et al 2008), which allowed users to enhance existing and
add new facts to their knowledge graph. However, Freebase was acquired by
Google and shut down its public API in 2016. An even stronger form is
implemented by Wikidata (Vrandečić and Krötzsch 2014), in which the user
community controls not only the data and schema but also the entire editorial
process. Wikidata is also important as a case of interlinking vocabularies,
tackling one of the issues in traditional library data. The Wikidata
community-developed alignment tool Mix’n’Match, for instance, allows users to
upload a vocabulary to Wikidata and create an alignment for it, which has
helped to position Wikidata as a huge hub for Library Linked Data and beyond.
Near-systematic references are now available between Wikidata entities and
resources from vocabularies like VIAF and GND.

Within the Digital Libraries and Digital Humanities domains, community-driven
knowledge graph enrichment mostly focused on involving users in linking
resources from existing corpora with concepts in knowledge graphs. One
possible enrichment technique is _semantic tagging_ , which supports users in
associating digital items or fragments thereof with concepts expressed in
existing knowledge graphs. That technique has been used for semantic tagging
of historical maps (Haslhofer et al 2013), images, and texts (Simon et al
2015).

##  6 Knowledge Graphs in the Digital Humanities

The development and curation of domain-specific knowledge structures has
traditionally been an important element of humanities scholarship. In many
cases, these structures emerge as an implicit research output, e.g., when
studying the interrelation between actors and events in a specific historical
setting. In other cases, the development of a knowledge organization system as
such — or components of it — is the main objective of the research endeavor.
This is the case, for example, for the development of domain taxonomies,
gazetteers or prosopgraphies (dictionaries of people or groups of people).
Initiatives such as the Tabula Imperii Romani (TIR-FOR 2016), the Tabula
Imperii Byzantini (TIB 2017), the Prosopography of the Byzantine World (PBW
2011), the Great Britain Historical GIS (GBHGIS 2012), or the Treasury of
Lives (ToL 2017) have been concerned exclusively — sometimes over a
significant timespan, and long before the digital transformation — with the
curation of authoritative data on places or people within their domain. Other
efforts have focused on the translation of existing analog authority
information to digital; some of them, such as the Pleiades Gazetteer of the
Ancient World (Pleiades Contributors 2017) specifically as Linked Data.

The motivation behind the development of classification schemes and authority
information in the humanities is much the same as in the library domain: a
need for structure, control, and a common vocabulary to facilitate
collaboration. Arguably, however, scholarly humanities research differs
insofar as there is a much higher degree of specificity to particular —
sometimes even niche — domains. The heterogeneous nature of research outputs;
the interpretative quality of humanities research; and the fact that work is
often organized around the efforts of a single individual or small group,
funded through time-limited grants, makes a “global knowledge graph of the
humanities” seem an unachievable goal. Yet the need to publish data under open
licenses, and build connections between datasets based on shared value
vocabularies and metadata element sets is increasingly perceived in the
community as key for enabling re-use; for the transparency of scholarly
methods; and, ultimately, sustainability of results. This trend is reflected
in the rise of Linked Data at as a theme at Digital Humanities events,
conferences, and curricula, as much as in the emergence of community
initiatives dedicated to establishing common interlinking standards and
practices.

By and large, such initiatives advocate the idea of cross-domain linkage by
means of shared name authority files, along with recommendations on metadata
element use. Crucial to this effort are, on the one hand, generic knowledge
graphs - DBpedia and Wikidata in particular. On the other hand, linked data
sets from libraries or museums, such as VIAF, the Getty Thesaurus of
Geographic Names, or the Getty Art & Architecture Thesaurus have been gaining
traction as an interconnecting “spine” through which community-specific
datasets can build outbound links to contribute to a global graph.

As these networking efforts are enabling the aggregation of increasingly large
corpora of cultural heritage content, the use of computational methods to
study larger cultural phenomena is becoming more feasible (cf. Schich et al
(2014); Cook et al (2012)). New tools are transforming traditional
scholarship, enabling scholars to identify and and answer new research
questions (cf. (Siemens and Schreibman 2008; Bodenhamer and Corrigan Trevor M.
Harris 2010; Bodard and Romanello 2016)). Michel et al (2010) popularized the
term Culturomics as “the application of high-throughput data collection and
analysis to the study of human culture”. In this context, knowledge
organization systems represent the crucial connecting medium within an ecology
of independent initiatives, that is gradually increasing mutual connectivity
by creating and using Linked Open Data (Isaksen et al 2014).

##  7 Future Directions of Research

Large-scale knowledge graphs, as they have been emerging in the libraries and
digital humanities domain, and the publication of seminal papers (e.g., Michel
et al (2010)) demonstrate how the application of quantitive analysis to large-
scale corpora opens up a spectrum of possible new research questions that, up
until now, were hard to answer with existing methods and primary sources. Data
was manually curated and often bound to an institution or the scope of an
individual researcher’s project. Most studies in the humanities and related
disciplines have focused on rather small corpora, while the constitution and
maintenance of institutional knowledge organization systems and related
datasets in libraries required years of work for a highly skilled and trained
workforce.

Exploiting the opportunities of quantiative analysis methods poses a number of
methodological, technical, and organizational challenges: first, novel serial
analysis methods and tools are needed that support scholars in in viewing,
annotating, and systematically analyzing relevant parts of possibly large
digitized corpora. Scholars could express relevance by selecting corresponding
concept definitions in knowledge graphs. Second, scalable text-mining and
machine-learning techniques are needed to systematically and efficiently
analyze and compare the characteristics, contents, and relationships of
concepts expressed in knowledge graphs within and across corpora. Third,
algorithms are needed that support scholars in detecting, contextualizing, and
analyzing various forms of expressions and associated narrative techniques in
copora spanning a long time period, in which the syntax and semantics may have
been subject to costant change. Under this premise, future research could
focus on:

  * •

the development of tools and scalable techniques for aligning large scale,
possible multi-media corpora with concepts expressed in knowledge graphs.

  * •

the investigation of text mining algorithms that can learn from scholar’s
annotations and support them in investigating semantic relationships extracted
from large copora.

  * •

the investigation of novel reconcilation mechanisms that ensure that
institutional and community-curated knowledge graphs produced in different
context are truly interoperable and do not lead to “competing” data offers.

  * •

the design of appropriate provenance tracking, crowd- or nichesourcing De Boer
et al (2012a) approaches, and validation mechanisms that ensure trust in data
quality when data are curated by humans with different levels of expertise
and/or result from automatic processes.

The possible research directions describe above show that there is a clear
need for collaborative research among researchers from humanities, computer
science as well as library information science. This will also result in novel
mixed qualitative and quantiative methods for the analysis of large-scale
digitized corpora relevant to the humanities and related disciplines.

## References

  * Auer et al (2007) Auer S, Bizer C, Kobilarov G, Lehmann J, Cyganiak R, Ives Z (2007) Dbpedia: A nucleus for a web of open data. The semantic web pp 722–735
  * Baker et al (2013) Baker T, Bechhofer S, Isaac A, Miles A, Schreiber G, Summers E (2013) Key choices in the design of simple knowledge organization system (skos). Web Semantics: Science, Services and Agents on the World Wide Web 20(Supplement C):35 – 49
  * Bizer et al (2009) Bizer C, Heath T, Berners-Lee T (2009) Linked data-the story so far. Semantic services, interoperability and web applications: emerging concepts pp 205–227
  * Bodard and Romanello (2016) Bodard G, Romanello M (2016) Digital Classics Outside the Echo-Chamber. Ubiquity Press, London, URL http://www.oapen.org/record/608306
  * Bodenhamer and Corrigan Trevor M. Harris (2010) Bodenhamer D, Corrigan Trevor M Harris J (2010) The Spatial Humanities: GIS and the Future of Humanities Scholarship
  * Bollacker et al (2008) Bollacker K, Evans C, Paritosh P, Sturge T, Taylor J (2008) Freebase: a collaboratively created graph database for structuring human knowledge. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data, AcM, pp 1247–1250
  * Brickley and R.V.Guha (2014) Brickley D, RVGuha (2014) Rdf schema 1.1. W3C Recommendation, URL https://www.w3.org/TR/rdf-schema/, accessed: 2017-12-07
  * Caracciolo et al (2013) Caracciolo C, Stellato A, Morshed A, Johannsen G, Rajbhandari S, Jaques Y, Keizer J (2013) The agrovoc linked dataset. Semantic Web 4(3):341–348
  * Cook et al (2012) Cook J, Das Sarma A, Fabrikant A, Tomkins A (2012) Your two weeks of fame and your grandmother’s. In: Proceedings of the 21st International Conference on World Wide Web, ACM, New York, NY, USA, WWW ’12, pp 919–928, URL http://doi.acm.org/10.1145/2187836.2187959
  * DCMI (2012) DCMI (2012) Dublin core metadata element set. Online, URL http://dublincore.org/documents/dces/, accessed: 2017-12-07
  * De Boer et al (2012a) De Boer V, Hildebrand M, Aroyo L, De Leenheer P, Dijkshoorn C, Tesfa B, Schreiber G (2012a) Nichesourcing: Harnessing the power of crowds of experts. In: ten Teije A, Völker J, Handschuh S, Stuckenschmidt H, d’Acquin M, Nikolov A, Aussenac-Gilles N, Hernandez N (eds) Knowledge Engineering and Knowledge Management, Springer Berlin Heidelberg, Berlin, Heidelberg, pp 16–20
  * De Boer et al (2012b) De Boer V, Wielemaker J, Van Gent J, Hildebrand M, Isaac A, Van Ossenbruggen J, Schreiber G (2012b) Supporting linked data production for cultural heritage institutes: the amsterdam museum case study. The Semantic Web: Research and Applications pp 733–747
  * Deliot (2014) Deliot C (2014) Publishing the british national bibliography as linked open data. Catalogue & Index 174:13–18
  * DPLA (2017) DPLA (2017) Digital public library of america (dpla). Website, URL https://dp.la/, accessed: 2012-12-12
  * GBHGIS (2012) GBHGIS (2012) Great britain historical geographical information system (gbhgis). URL http://www.port.ac.uk/research/gbhgis/, accessed: 2017-12-12
  * Getty (2017) Getty TGRI (2017) Getty vocabularies as linked open data. Online, URL http://www.getty.edu/research/tools/vocabularies/lod/index.html, accessed: 2017-12-07
  * Haslhofer and Isaac (2011) Haslhofer B, Isaac A (2011) data. europeana. eu: The europeana linked open data pilot. In: International Conference on Dublin Core and Metadata Applications, pp 94–104
  * Haslhofer et al (2013) Haslhofer B, Robitza W, Guimbretiere F, Lagoze C (2013) Semantic tagging on historical maps. In: Proceedings of the 5th Annual ACM Web Science Conference, ACM, pp 148–157
  * Hitzler et al (2012) Hitzler P, Krötsch M, Parsia B, Schneider PFP, Rudolph S (2012) Owl 2 web ontology language primer (second edition). W3C Recommendation, URL https://www.w3.org/TR/owl2-primer/, accessed: 2017-12-07
  * Isaksen et al (2014) Isaksen L, Simon R, Barker ET, de Soto Cañamares P (2014) Pelagios and the emerging graph of ancient world data. In: Proceedings of the 2014 ACM Conference on Web Science, ACM, New York, NY, USA, WebSci ’14, pp 197–201, URL http://doi.acm.org/10.1145/2615569.2615693
  * Malmsten (2008) Malmsten M (2008) Making a library catalogue part of the semantic web. In: International Conference on Dublin Core and Metadata Applications-Metadata for Semantic and Social Applications 22-26 September 2008, Berlin (DC-2008), Humboldt-Universität zu Berlin
  * Michel et al (2010) Michel JB, Shen YK, Aiden AP, Veres A, Gray MK, Team TGB, Pickett JP, Holberg D, Clancy D, Norvig P, Orwant J, Pinker S, Nowak MA, Aiden EL (2010) Quantitative analysis of culture using millions of digitized books. Science URL http://www.sciencemag.org/content/331/6014/176.full
  * OCLC (2017) OCLC (2017) Oclc linked data. Online, URL https://www.oclc.org/developer/develop/linked-data.en.html, accessed: 2012-12-07
  * PBW (2011) PBW (2011) Prosopography of the byzantine world. Online, URL http://blog.pbw.cch.kcl.ac.uk/, accessed: 2017-12-12
  * Pleiades Contributors (2017) Pleiades Contributors (2017) The pleiades gazetteer of the ancient world. URL http://pleiades.stoa.org/, 2017-12-12
  * Schich et al (2014) Schich M, Song C, Ahn YY, Mirsky A, Martino M, Barabasi AL, Helbing D (2014) A network framework of cultural history 345(6196):558 – 562, DOI 10.1126/science.1240064, received for publication 6 May 2013, Accepted for publication 13 June 2014.
  * Siemens and Schreibman (2008) Siemens R, Schreibman S (2008) A Companion to Digital Literary Studies: Blackwell Companions to Literature and Culture. Wiley Publishing
  * Simon et al (2015) Simon R, Barker E, Isaksen L, de Soto Cañamares P (2015) Linking early geospatial documents, one place at a time: annotation of geographic documents with recogito. e-Perimetron 10(2):49–59, URL http://oro.open.ac.uk/43613/
  * Singhal (2012) Singhal A (2012) Introducing the knowledge graph: Things, not strings. URL https://goo.gl/U168iz, accessed: 2017-11-21
  * Summers et al (2008) Summers E, Isaac A, Redding C, Krech D (2008) Lcsh, skos and linked data. In: International Conference on Dublin Core and Metadata Applications-Metadata for Semantic and Social Applications 22-26 September 2008, Berlin (DC-2008), Humboldt-Universität zu Berlin
  * TIB (2017) TIB (2017) Digital tabula imperii byzantini. Online, URL http://tib.oeaw.ac.at/, accessed: 2017-12-12
  * TIR-FOR (2016) TIR-FOR (2016) Tabula imperii romani — forma orbis romani. URL http://tir-for.iec.cat/, accessed: 2017-12-12
  * ToL (2017) ToL (2017) The treasury of lives - a biographical encyclopedia of tibet, inner asia, and the himalaya. Online, URL http://treasuryoflives.org/, accessed: 2017-12-12
  * Vrandečić and Krötzsch (2014) Vrandečić D, Krötzsch M (2014) Wikidata: a free collaborative knowledgebase. Communications of the ACM 57(10):78–85
  * W3C (2011) W3C (2011) Library linked data incubator group final report. Online, URL https://www.w3.org/2005/Incubator/lld/, accessed: 2017-12-13