have imposed conditions (3.43), 3.44, (3.51), (3.52), and (3.59), with the
hope that a similar strategy will eliminate the divergence in boundary terms
obtained in terms of Ashtekar-Barbero variables. Contrary to expectations,
this strategy did not render the surface terms finite, and in fact, the
charges corresponding to boosts and rotations remain divergent. In section 4,
we have analyzed the reason for this discrepancy and conclude that with the
new boundary conditions, ADM variables and Ashtekar-Barbero variables cannot
be considered canonically equivalent, and this distinction manifests itself in
the boundary terms.

Nonetheless, the significant and noteworthy accomplishment of the present work
is that if we disregard boosts and rotations, the charge corresponding to
translations is not only finite and integrable, but also incorporates
supertranslations. In contrast to [1, 2], where the charge corresponding to
supertranslations vanishes and thus they are pure gauge, in this work, the
supertranslation generators are not identically zero and therefore act non-
trivially in the physical phase space. Thus, we have successfully achieved the
objective outlined in the introduction, which is to associate standard
canonical generators at spatial infinity with supertranslations in terms of
Ashtekar-Barbero variables initially observed at null infinity. The parity
conditions in the theorem play a crucial role in the new boundary conditions,
distinguishing themselves from the previously proposed conditions in [1, 2].
It has been duly noted that the odd parity of $W$ and the even parity of
$\tilde{f}$ define the characteristics of the supertranslations. These
parities, which are incompatible with the parity conditions laid out in [1,
2], do not exist in that approach except when it comes to Poincaré
translations.

This work has potential for extension and further exploration in multiple
directions:

  1. 1.

Our initial motivation for investigating new boundary conditions in the
Ashtekar-Barbero framework is to incorporate techniques from LQG in order to
establish a quantum theory. In future research, our objective is to construct
quantum operators corresponding to the charges of supertranslations using
holonomy and flux operators, and then investigate their quantum behaviors.

  2. 2.

As the charges associated with boosts and rotations are not finite under the
proposed boundary conditions, our future work will focus on identifying
alternative boundary conditions that overcome this limitation. We have
observed that finiteness of the symplectic structure can be achieved through
parity conditions, and therefore we must constrain ourselves to those parity
conditions that yield a finite symplectic structure. One possible approach to
relax these parity conditions is to adopt the framework of holographic
renormalization to remove the divergences appearing in the symplectic
structure, as proposed in [21].

  3. 3.

Once we have successfully accomplished the previous goal, our next aim is to
determine boundary conditions that not only yield supertranslations at spatial
infinity, but also incorporate superrotations [22].

### Acknowledgement

The author expresses gratitude to John Joseph Marchetta for his encouragement
and valuable discussions. The present work is funded by the National Natural
Science Foundation of China (NSFC) under Grants no. 12275022 and no. 11875006.

##  Appendix A Variations of the leading order terms of the canonical
variables

In this appendix, we proceed with the calculation of the variation of
$\bar{F}^{a}_{b}$ and $\bar{G}^{a}_{b}$ under hypersurface deformations, as
used in section 3.3. We begin by examining the variations of the variables
associated with the densitized triad $E^{a}_{i}$. It is important to note that
the variation of $E^{a}_{i}$ under a hypersurface deformations can be obtained
through a combination of equations (3.49), (3.57), and (3.65). By utilizing
the asymptotic expansion of $\delta E^{a}_{i}$, we can readily determine the
variation of $\bar{f}^{a}_{i}$. Specifically, we have that $\delta
E^{r}_{i}=r\sqrt{\bar{\gamma}}\delta\bar{f}^{r}_{i}+O(1)$ and $\delta
E^{A}_{i}=\sqrt{\bar{\gamma}}\delta\bar{f}^{A}_{i}+O(r^{-1})$. It is worth
mentioning that we assume that $\bar{\gamma}^{a}_{i}$ is not subject to
variations under hypersurface deformations, i.e.
$\delta\bar{\gamma}^{a}_{i}=0$. Once we have obtained the expression for
$\delta\bar{f}^{a}_{i}$, we can determine the variation of
$\delta\bar{F}^{a}_{b}$ as
$\delta\bar{F}^{a}_{b}=\delta(\bar{f}^{a}_{i}\bar{\gamma}^{i}_{b})=\bar{\gamma}^{i}_{b}(\delta\bar{f}^{a}_{i})$.
This result follows again from the fact that $\delta\bar{\gamma}_{a}^{i}=0$.

Using the above strategy and after a rather lengthy calculation, we have
obtained all the radial and angular components of $\delta\bar{F}^{a}_{b}$ as
follows.

$\displaystyle\delta\bar{F}^{r}_{r}$
$\displaystyle=\beta\left(\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}\bar{D}_{A}(b\bar{F}^{r}_{B})-\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}\bar{\gamma}_{AC}b\bar{F}^{C}_{B}-b\bar{G}^{A}_{A}+\frac{(\beta^{2}-s)}{\beta}b\bar{k}^{A}_{A}-\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}(\partial_{A}b)\bar{F}^{r}_{B}\right)+2W+\bar{D}_{A}I^{A}+\mathcal{L}_{Y}\bar{F}^{r}_{r}$
$\displaystyle=\beta\left(\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}b\bar{D}_{A}\bar{F}^{r}_{B}-\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}\bar{\gamma}_{AC}b\bar{F}^{C}_{B}-b\bar{G}^{A}_{A}+\frac{(\beta^{2}-s)}{\beta}b\bar{k}^{A}_{A}\right)+2W+\bar{D}_{A}I^{A}+\mathcal{L}_{Y}\bar{F}^{r}_{r}$
(A.1)

$\displaystyle\delta\bar{F}^{r}_{D}=$
$\displaystyle\beta\left(\bar{\gamma}_{BD}\frac{\epsilon^{BA}}{\sqrt{\bar{\gamma}}}\left[\bar{D}_{A}(b\bar{F}^{r}_{r})-b\bar{\gamma}_{AC}\bar{F}^{C}_{r}+\bar{F}^{C}_{A}(\bar{D}_{C}b)+(\bar{D}_{A}\tilde{f})\right]+b\;\bar{G}^{A}_{r}\bar{\gamma}_{AD}-\frac{(\beta^{2}-s)}{\beta}b\;\bar{k}^{r}_{D}\right)$
$\displaystyle-\beta\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}\bar{\gamma}_{AD}\left(-b\bar{F}^{r}_{B}+(\partial_{B}b)\bar{F}^{r}_{r}\right)-\partial_{D}W+I_{D}+\mathcal{L}_{Y}\bar{F}^{r}_{D}+\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}\bar{\gamma}_{AD}\bar{\Lambda}^{C}\bar{\gamma}_{BC}$
$\displaystyle=$
$\displaystyle\beta\left(\bar{\gamma}_{AD}\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}\left[b\bar{D}_{B}\bar{F}^{r}_{r}-b(\bar{\gamma}_{BC}\bar{F}^{C}_{r}-\bar{F}^{r}_{B})+\bar{F}^{C}_{B}(\bar{D}_{C}b)+(\bar{D}_{B}\tilde{f})\right]+b\;\bar{G}^{A}_{r}\bar{\gamma}_{AD}-\frac{(\beta^{2}-s)}{\beta}b\;\bar{k}^{r}_{D}\right)$
$\displaystyle-\partial_{D}W+I_{D}+\mathcal{L}_{Y}\bar{F}^{r}_{D}+\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}\bar{\gamma}_{AD}\bar{\Lambda}_{B}$
(A.2)

$\displaystyle\delta\bar{F}^{B}_{r}=$
$\displaystyle\beta\left[\frac{\epsilon^{AC}}{\sqrt{\bar{\gamma}}}\bar{D}_{A}(b\bar{F}^{B}_{C})+\frac{\epsilon^{CB}}{\sqrt{\bar{\gamma}}}\bar{F}^{A}_{C}(\bar{D}_{A}b)+\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}(\bar{D}_{A}\tilde{f})+b\left(\bar{G}^{r}_{A}\bar{\gamma}^{AB}-\frac{(\beta^{2}-s)}{\beta}\bar{k}^{B}_{r}\right)-\frac{\epsilon^{AC}}{\sqrt{\bar{\gamma}}}(\partial_{A}b)\bar{F}^{B}_{C}\right]$
$\displaystyle+\mathcal{L}_{Y}\bar{F}^{B}_{r}-\frac{\epsilon^{BA}}{\sqrt{\bar{\gamma}}}\bar{\gamma}_{AC}\bar{\Lambda}^{C}$
$\displaystyle=$
$\displaystyle\beta\left[\frac{\epsilon^{AC}}{\sqrt{\bar{\gamma}}}b\;\bar{D}_{A}\bar{F}^{B}_{C}+\frac{\epsilon^{CB}}{\sqrt{\bar{\gamma}}}\bar{F}^{A}_{C}(\bar{D}_{A}b)+\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}(\bar{D}_{A}\tilde{f})+b\left(\bar{G}^{r}_{A}\bar{\gamma}^{AB}-\frac{(\beta^{2}-s)}{\beta}\bar{k}^{B}_{r}\right)\right]+\mathcal{L}_{Y}\bar{F}^{B}_{r}-\frac{\epsilon^{BC}}{\sqrt{\bar{\gamma}}}\bar{\Lambda}_{C}$
(A.3)

$\displaystyle\delta\bar{F}^{B}_{D}=$
$\displaystyle\beta\left[\frac{\bar{\gamma}_{CD}}{\sqrt{\bar{\gamma}}}\left(\epsilon^{CA}\bar{D}_{A}(b\bar{F}^{B}_{r})-\epsilon^{CB}\bar{F}^{A}_{r}(\bar{D}_{A}b)-\epsilon^{CA}b\bar{F}^{B}_{A}\right)\right.$
$\displaystyle\hskip
28.45274pt\left.+\sqrt{\bar{\gamma}}b\;(\bar{G}^{C}_{A}\bar{\gamma}^{AB}\bar{\gamma}_{CD}-\delta_{D}^{B}\bar{G}^{b}_{b})+\frac{(\beta^{2}-s)}{\beta}\sqrt{\bar{\gamma}}b\;(\bar{k}^{b}_{b}\delta_{D}^{B}-\bar{k}^{B}_{D})\right]$
$\displaystyle-\beta\frac{\epsilon^{CA}}{\sqrt{\bar{\gamma}}}\bar{\gamma}_{CD}\left(-b\bar{F}^{B}_{A}+(\partial_{A}b)\bar{F}^{B}_{r}\right)+W\delta^{B}_{D}-\bar{D}_{D}I^{B}+\delta^{B}_{D}(\bar{D}_{A}I^{A})+\mathcal{L}_{Y}\bar{F}^{B}_{D}+\frac{\epsilon^{AB}}{\sqrt{\bar{\gamma}}}\bar{\Lambda}^{r}\bar{\gamma}_{BD}$
$\displaystyle=$
$\displaystyle\beta\left[\frac{\bar{\gamma}_{CD}}{\sqrt{\bar{\gamma}}}\left(\epsilon^{CA}b\bar{D}_{A}\bar{F}^{B}_{r}-\epsilon^{CB}\bar{F}^{A}_{r}(\bar{D}_{A}b)\right)+b\;(\bar{G}^{C}_{A}\bar{\gamma}^{AB}\bar{\gamma}_{CD}-\delta_{D}^{B}\bar{G}^{b}_{b})+\frac{(\beta^{2}-s)}{\beta}b\;(\bar{k}^{b}_{b}\delta_{D}^{B}-\bar{k}^{B}_{D})\right]$
$\displaystyle+W\delta^{B}_{D}-\bar{D}_{D}I^{B}+\delta^{B}_{D}(\bar{D}_{A}I^{A})+\mathcal{L}_{Y}\bar{F}^{B}_{D}+\frac{\epsilon^{BC}}{\sqrt{\bar{\gamma}}}\bar{\Lambda}^{r}\bar{\gamma}_{CD}$
(A.4)

A similar approach should be employed for $A_{a}^{i}$. Note that the variation
of $A_{a}^{i}$ under hypersurface deformations can be determined by combining
(3.48), (3.56), and (3.64). By using the asymptotic expansion of $\delta
A_{a}^{i}$, the variation of $\bar{g}^{a}_{i}$ can be easily deduced as
follows: $\delta A_{r}^{i}=\frac{1}{r^{2}}\delta\bar{g}_{r}^{i}+O(r^{-3})$ and
$\delta A_{A}^{i}=\frac{1}{r}\delta\bar{g}_{A}^{i}+O(r^{-2})$. Once
$\delta\bar{g}_{a}^{i}$ is obtained, we can find $\delta\bar{G}^{a}_{b}$ using
the equation
$\delta\bar{G}^{a}_{b}=\delta(\bar{g}_{b}^{i}\bar{\gamma}_{i}^{a})=\bar{\gamma}_{i}^{a}(\delta\bar{g}_{b}^{i})$,
since it is known that $\delta\bar{\gamma}^{a}_{i}=0$.

Using the above strategy and after a tedious calculation, we have obtained all
the radial and angular components of $\delta\bar{G}^{a}_{b}$ as follows.

$\displaystyle\delta\bar{G}^{r}_{r}=$
$\displaystyle-\beta\frac{b}{\sqrt{\bar{\gamma}}}\epsilon^{AC}\bar{\gamma}_{BC}\left(\bar{D}_{A}\bar{G}^{B}_{r}+\bar{G}^{B}_{A}\right)+\frac{\beta^{2}-s}{2\sqrt{\bar{\gamma}}}\bar{D}_{A}(b\;\epsilon^{AB}[\bar{\gamma}_{CB}\bar{k}^{C}_{r}+\bar{k}^{r}_{B}])-\beta\frac{\epsilon^{AC}}{\sqrt{\bar{\gamma}}}(\partial_{A}b)\bar{\gamma}_{BC}\bar{G}^{B}_{r}$
$\displaystyle+\mathcal{L}_{Y}\bar{G}^{r}_{r}+\bar{\Lambda}^{r}$ (A.5)

$\displaystyle\delta\bar{G}^{B}_{r}=$
$\displaystyle-\beta\frac{b}{\sqrt{\bar{\gamma}}}\epsilon^{AB}\left(-\bar{D}_{A}\bar{G}^{r}_{r}+\bar{\gamma}_{AC}\bar{G}^{C}_{r}-\bar{G}^{r}_{A}\right)$
$\displaystyle+\frac{\beta^{2}-s}{2\sqrt{\bar{\gamma}}}\left(-2\bar{D}_{A}(b\;\epsilon^{AB}\bar{k}^{r}_{r})-\bar{D}_{A}(b\;\epsilon^{AB}\bar{k}^{C}_{C})-2b\;\epsilon^{BC}\bar{\gamma}_{AC}\bar{k}^{A}_{r}+\bar{D}_{A}(b\;\epsilon^{AC}\bar{k}^{B}_{C}-b\;\epsilon^{BC}\bar{k}^{A}_{C})\right)$
$\displaystyle-\beta\frac{\epsilon^{BA}}{\sqrt{\bar{\gamma}}}\left((\partial_{A}b)\bar{G}^{r}_{r}-b\;\bar{\gamma}_{AC}\bar{G}^{C}_{r}\right)+\mathcal{L}_{Y}\bar{G}^{B}_{r}+\bar{\Lambda}^{B}$
(A.6)

$\displaystyle\delta\bar{G}^{r}_{B}=$
$\displaystyle-\beta\frac{b}{\sqrt{\bar{\gamma}}}\epsilon^{DA}\left(\bar{\gamma}_{BD}\bar{G}^{r}_{A}+\bar{\gamma}_{DC}\bar{D}_{B}\bar{G}^{C}_{A}-\bar{\gamma}_{CD}\bar{D}_{A}\bar{G}^{C}_{B}\right)$
$\displaystyle+\frac{\beta^{2}-s}{2\sqrt{\bar{\gamma}}}\left(\bar{\gamma}_{BC}\bar{D}_{A}(b\;\epsilon^{AC}\bar{k}^{E}_{E})-2b\;\epsilon^{CA}\bar{\gamma}_{AB}\bar{k}^{r}_{C}-\bar{\gamma}_{BD}\bar{D}_{A}(b\;\epsilon^{CD}\bar{k}^{A}_{C}+b\;\epsilon^{CA}\bar{k}^{D}_{C})\right)$
$\displaystyle-\beta\frac{\epsilon^{AD}}{\sqrt{\bar{\gamma}}}(\partial_{A}b)\bar{\gamma}_{CD}\bar{G}^{B}_{C}+\mathcal{L}_{Y}\bar{G}^{r}_{B}-\bar{D}_{B}\bar{\Lambda}^{r}+\bar{\gamma}_{AB}\bar{\Lambda}^{A}$
(A.7)

$\displaystyle\delta\bar{G}^{D}_{B}=$
$\displaystyle\beta\frac{b}{\sqrt{\bar{\gamma}}}\left(\epsilon^{CD}\bar{\gamma}_{BC}\bar{G}^{r}_{r}+\epsilon^{CD}\bar{\gamma}_{AC}\bar{D}_{B}\bar{G}^{A}_{r}+\epsilon^{DA}\bar{D}_{B}\bar{G}^{r}_{A}-\epsilon^{DA}\bar{\gamma}_{BC}\bar{G}^{C}_{A}-\epsilon^{DA}\bar{D}_{A}\bar{G}^{r}_{B}\right)$
$\displaystyle+\frac{\beta^{2}-s}{2\sqrt{\bar{\gamma}}}\left(-2\epsilon^{AD}b\bar{\gamma}_{AB}\bar{k}^{r}_{r}-\epsilon^{AD}b\bar{\gamma}_{AB}\bar{k}^{C}_{C}+\epsilon^{AD}b\bar{\gamma}_{BC}\bar{k}^{C}_{A}+\bar{\gamma}_{BC}\bar{D}_{A}(\epsilon^{CA}b\bar{k}^{D}_{r})-\epsilon^{CA}b\bar{\gamma}_{AB}\bar{k}^{D}_{C}\right.$
$\displaystyle\hskip
51.21504pt\left.-\bar{\gamma}_{BC}\bar{D}_{A}(\epsilon^{CD}b\bar{k}^{A}_{r})+\epsilon^{AE}b\bar{\gamma}_{EC}\bar{k}^{C}_{A}\delta^{D}_{B}-\bar{\gamma}_{BC}\bar{D}_{A}(\epsilon^{AD}b\bar{k}^{C}_{r})+\delta^{D}_{B}\bar{D}_{A}(\epsilon^{EA}b[\bar{k}^{r}_{E}-\bar{\gamma}_{EC}\bar{k}^{C}_{r}])\right)$
$\displaystyle-\beta\frac{\epsilon^{DA}}{\sqrt{\bar{\gamma}}}\left((\partial_{A}b)\bar{G}^{r}_{B}-b\bar{G}^{C}_{B}\bar{\gamma}_{AC}\right)+\mathcal{L}_{Y}\bar{G}^{D}_{B}-\delta^{D}_{B}\bar{\Lambda}^{r}-\bar{D}_{B}\bar{\Lambda}^{D}$
(A.8)

## References

  * [1] T. Thiemann, “Generalized boundary conditions for general relativity for the asymptotically flat case in terms of Ashtekar’s variables” Class. Quant. Grav. 12 (1995), 181. arXiv:9910008 [gr-qc].
  * [2] M. Campiglia, “Note on the phase space of asymptotically flat gravity in Ashtekar-Barbero variables”, Class. Quant. Grav. 32 (2015), 14. arXiv:1412.5531 [gr-qc].
  * [3] H. Henneaux, C. Troessaert, “BMS Group at Spatial Infinity: the Hamiltonian (ADM) approach”, JHEP 03 (2018), 147. arXiv:1801.03718 [gr-qc].
  * [4] L. Janshen and D. Giulini, “Asymptotic Symmetries of SU(2) Yang-Mills-Higgs Theory in Hamiltonian Formulation”, [arXiv:2310.03797 [hep-th]].
D. Simić, “Note on asymptotic symmetry of massless scalar field at null
infinity”, Phys. Rev. D 108 (2023) no.8, 8 [arXiv:2309.06148 [hep-th]].
O. Fuentealba, “Asymptotic $\mathcal{O}$(r) gauge symmetries and gauge-
invariant Poincaré generators in higher spacetime dimensions”, JHEP 04 (2023),
047 [arXiv:2302.13788 [hep-th]].
O. Fuentealba, M. Henneaux and C. Troessaert, “A note on the asymptotic
symmetries of electromagnetism”, JHEP 03 (2023), 073 [arXiv:2301.05989 [hep-
th]].
É. É. Flanagan and D. A. Nichols, “Conserved charges of the extended Bondi-
Metzner-Sachs algebra”, Phys. Rev. D 95 (2017) no.4, 044002 [arXiv:1510.03386
[hep-th]].
M. Han, Z. Huang and H. Tan, “Symmetry charges on reduced phase space and BMS
algebra”, [arXiv:2309.03293 [gr-qc]].
S. Bakhoda, F. Mahdieh and H. Shojaie, “Asymptotic Conformal Symmetry at
Spatial Infinity”, Phys. Rev. D 100 (2019) no.12, 124051 [arXiv:1910.00520
[gr-qc]].

  * [5] R. M. Wald, “General Relativity”, Chicago Univ. Pr., 1984,
  * [6] H. Bondi, M. G. J. van der Burg and A. W. K. Metzner, “Gravitational waves in general relativity. 7. Waves from axisymmetric isolated systems”, Proc. Roy. Soc. Lond. A 269 (1962), 21-52
  * [7] R. K. Sachs, “Gravitational waves in general relativity. 8. Waves in asymptotically flat space-times”, Proc. Roy. Soc. Lond. A 270 (1962), 103-126
R. Sachs, “Asymptotic symmetries in gravitational theory”, Phys. Rev. 128
(1962), 2851-2864

  * [8] A. Strominger, “Lectures on the Infrared Structure of Gravity and Gauge Theory”, [arXiv:1703.05448 [hep-th]].
A. Ashtekar and M. Streubel, “Symplectic Geometry of Radiative Modes and
Conserved Quantities at Null Infinity”, Proc. Roy. Soc. Lond. A 376 (1981),
585-607
A. Ashtekar, “Asymptotic Quantization of the Gravitational Field”, Phys. Rev.
Lett. 46 (1981), 573-576
A. Strominger, “On BMS Invariance of Gravitational Scattering”, JHEP 07
(2014), 152 [arXiv:1312.2229 [hep-th]].
T. He, V. Lysov, P. Mitra and A. Strominger, “BMS supertranslations and
Weinberg’s soft graviton theorem”, JHEP 05 (2015), 151 [arXiv:1401.7026 [hep-
th]].
F. Cachazo and A. Strominger, “Evidence for a New Soft Graviton Theorem”,
[arXiv:1404.4091 [hep-th]].
M. Campiglia and R. Eyheralde, “Asymptotic $U(1)$ charges at spatial
infinity”, JHEP 11 (2017), 168 [arXiv:1703.07884 [hep-th]].
M. Campiglia and A. Laddha, “Asymptotic symmetries of gravity and soft
theorems for massive particles”, JHEP 12 (2015), 094 [arXiv:1509.01406 [hep-
th]].

  * [9] T. Regge and C. Teitelboim, “Role of Surface Integrals in the Hamiltonian Formulation of General Relativity”, Annals Phys. 88 (1974) 286.
  * [10] D. Christodoulou and S. Klainerman, “The Global nonlinear stability of the Minkowski space”, Princeton University Press, Princeton, 1993
  * [11] A. Ashtekar, “New Hamiltonian formulation of general relativity”, Phys. Rev. D36 (1987), 1587.
  * [12] J. F. Barbero G., “Real Ashtekar variables for Lorentzian signature space times", Phys. Rev. D 51 (1995), 5507-5510 [arXiv:gr-qc/9410014 [gr-qc]].
G. Immirzi, “Real and complex connections for canonical gravity”, Class.
Quant. Grav. 14 (1997), L177-L181 [arXiv:gr-qc/9612030 [gr-qc]].

  * [13] B. S. DeWitt and R. Stora, “Relativity, groups and topology: Proceedings", 40th Summer School of Theoretical Physics - Session 40: Les Houches, France, June 27 - August 4, 1983, vol. 2
  * [14] M. Henneaux and C. Teitelboim, “Quantization of gauge systems”, Princeton, USA: Univ. Pr. (1992)
  * [15] A. Ashtekar and R. Hansen, “A unified treatment of null and spatial infinity in general relativity. I-Universal structure, asymptotic symmetries, and conserved quantities at spatial infinity”, J. Math. Phys. (N.Y.) 19 (1978) 1542.
  * [16] R. Beig and B. G. Schmidt, “Einstein’s equations near spatial infinity”, Commun. Math. Phys. 87 (1982) 65.
  * [17] R. Penrose, “Asymptotic properties of fields and space-times”, Phys. Rev. Lett. 10 (1963) 66.
T. Mädler and J. Winicour, “Bondi-Sachs Formalism”, Scholarpedia 11 (2016)
33528 [arXiv: 1609.01731 [gr-qc]].

  * [18] T. Thiemann, “Modern Canonical Quantum General Relativity", Cambridge University Press, Cambridge, 2007.
  * [19] C. Rovelli, “Quantum Gravity. Cambridge University Press", Cambridge, 2004.
J. Pullin and R. Gambini, “A first course in Loop Quantum Gravity", Oxford
University Press, New York, 2011.
C. Rovelli and F. Vidotto, “Covariant Loop Quantum Gravity, Cambridge
University Press, Cambridge, 2015.

  * [20] R. Beig and N. oMurchadha, “The Poincare group as the symmetry group of canonical general relativity”, Annals Phys. 174 (1987), 463-498.
  * [21] G. Compere and F. Dehouck, “Relaxing the Parity Conditions of Asymptotically Flat Gravity”, Class. Quant. Grav. 28 (2011), 245016 [erratum: Class. Quant. Grav. 30 (2013), 039501] [arXiv:1106.4045 [hep-th]].
M. Henneaux and C. Teitelboim, “Asymptotically anti-De Sitter Spaces”, Commun.
Math. Phys. 98 (1985), 391-424

  * [22] G. Barnich and C. Troessaert, “Symmetries of asymptotically flat 4 dimensional spacetimes at null infinity revisited”, Phys. Rev. Lett. 105 (2010), 111103 [arXiv:0909.2617 [gr-qc]].
G. Barnich and C. Troessaert, “Aspects of the BMS/CFT correspondence”, JHEP 05
(2010), 062 [arXiv:1001.1541 [hep-th]].
G. Barnich and C. Troessaert, “Supertranslations call for superrotations”, PoS
CNCFG2010 (2010), 010 [arXiv:1102.4632 [gr-qc]].
G. Barnich and C. Troessaert, “BMS charge algebra”, JHEP 12 (2011), 105
[arXiv:1106.0213 [hep-th]].
G. Barnich and C. Troessaert, “Comments on holographic current algebras and
asymptotically flat four dimensional spacetimes at null infinity”, JHEP 11
(2013), 003 [arXiv:1309.0794 [hep-th]].
G. Barnich and C. Troessaert, “Finite BMS transformations”, JHEP 03 (2016),
167 [arXiv:1601.04090 [gr-qc]].


These authors contributed equally to this work.

These authors contributed equally to this work.

These authors contributed equally to this work.

1]Quantori, Cambridge, Massachusetts, United States of America

# Optimizing substructure search: a novel approach for efficient querying in
large chemical databases

Vsevolod Vaskin<EMAIL_ADDRESS>Dmitri Jakovlev
<EMAIL_ADDRESS>Fedor Bakharev<EMAIL_ADDRESS>[

###### Abstract

Substructure search in chemical compound databases is a fundamental task in
cheminformatics with critical implications for fields such as drug discovery,
materials science, and toxicology. However, the increasing size and complexity
of chemical databases have rendered traditional search algorithms ineffective,
exacerbating the need for scalable solutions. We introduce a novel approach to
enhance the efficiency of substructure search, moving beyond the traditional
full-enumeration methods. Our strategy employs a unique index structure: a
tree that segments the molecular data set into clusters based on the presence
or absence of certain features. This innovative indexing mechanism is inspired
by the binary Ball-Tree concept and demonstrates superior performance over
exhaustive search methods, leading to significant acceleration in the initial
filtering process. Comparative analysis with the existing Bingo algorithm
reveals the efficiency and versatility of our approach. Although the current
implementation does not affect the verification stage, it has the potential to
reduce false positive rates. Our method offers a promising avenue for future
research, meeting the growing demand for fast and accurate substructure search
in increasingly large chemical databases.

###### keywords:

substructure search, subgraph isomorphism, fingerprints, molecular databases,
chemical pattern search, cheminformatics

###### pacs:

[

MSC Classification]92E10

##  1 Introduction

Substructure search in chemical compound databases is a vital task in
cheminformatics, underpinning broad applications in drug discovery, materials
science, and toxicology. The objective is to identify all molecules in a
database that contain a given query substructure, which typically corresponds
to a specific chemical motif or functional group. This search has been a
cornerstone in understanding the influence of specific substructures on the
biological activity, physicochemical properties, and reactivity of a compound,
a concept recognized for decades [1].

Historical advancements in computer-assisted substructure search were marked
by the adoption of graph-based methods to detect particular substructures in
chemical compounds. A significant milestone was the introduction of the
Simplified Molecular Input Line Entry System (SMILES) notation by Weininger in
the 1980s [12]. This innovation offered a straightforward linear portrayal of
molecular configurations in string format.

The search for a structure fundamentally relies on the solution of the
subgraph isomorphism problem, a problem known to be NP-complete [11]. Due to
its high computational complexity, numerous algorithms and heuristics have
been devised to accelerate the search process. Among these, the Filter-and-
Verification paradigm has been a prevalent approach, involving an initial
filtering step to quickly eliminate unsuitable candidate graphs, and a more
computationally intensive verification step to confirm the presence of the
query substructure in the remaining candidates [4, 10]. Over time, graph-based
subgraph isomorphism algorithms, such as the Ullmann algorithm [11] and the
VF2 algorithm [4], have emerged as more efficient and scalable solutions for
substructure search in large chemical databases.

In addition to these, frequent subgraph mining algorithms like gSpan [13],
FFSM [6], and Gaston [7] have proven valuable in identifying frequently
occurring substructures in large sets of chemical compounds. These approaches
are particularly beneficial for applications such as structure-activity
relationship (SAR) analysis and molecular classification.

Efficient filtering techniques often involve the use of binary and
quantitative features, or fingerprints, to represent molecular structures.
These fingerprints facilitate the rapid elimination of graphs that do not
contain the specific features required by the query subgraph, thereby speeding
up the substructure search process [2, 5].

However, as the number of known molecules and the size of chemical databases
have grown significantly, traditional approaches, which often require a full
or nearly full enumeration of candidates, have become increasingly challenging
to implement efficiently. This development underscores the need for more
scalable solutions. The complexity is not just computational but also involves
handling increasingly large data sets that cannot be efficiently processed
using traditional methods.

Our work introduces a unique approach to mitigating these challenges. While in
certain cases the algorithm may resort to exhaustive enumeration, in most
scenarios it employs a more sophisticated strategy, transcending the
conventional full enumeration paradigm. Instead, we introduce a unique index
structure: a tree that segments the molecular dataset into clusters based on
the presence orc absence of features. Inspired by the binary Ball-Tree concept
[8, 3], this structure demonstrates superior performance over exhaustive
search on average, leading to a significant acceleration in the filtering
process.

We provide a comparative analysis of our method based on Bingo [9] with the
original Bingo algorithm, highlighting key differences.

Although Bingo uses advanced filtering effectively, it relies on exhaustive
search in a chemical space that continually expands. On the contrary, our
approach departs from exhaustive search and places an existing molecular
fingerprint into a tree structure, rather than a conventional relational
database. While our current version does not impact the verification stage, it
speeds up the filtering stage. By introducing this innovative structure, we
aim to cater to the growing scale of chemical databases and the escalating
demand for efficient and scalable search solutions. Our approach offers
potential for future research and application in the quest for more efficient
and accurate substructure search techniques.

##  2 Algorithm description

Figure 1: The scheme of the algorithm

###  2.1 Notation and main idea

The objective of our research is to facilitate the identification of specific
substructures within molecules from a database $\mathcal{M}$. For this, we
utilize the concept of a “fingerprint”, a binary string of constant length
${\sf fl}$, corresponding to each molecule. To perform this mapping, we define
a function ${\sf fp}:\mathcal{M}\to\mathcal{F}$ that takes a molecule from the
set $\mathcal{M}$ and produces its corresponding fingerprint in the set
$\mathcal{F}$.

To make the substructure search process more efficient, we propose organizing
these fingerprints in a binary search tree, denoted $\mathcal{T}$. The tree is
binary and complete, having a specific depth $d$.

In this tree, the root, left and right subtrees of a node $\tt{v}$ are
represented as $\mathcal{T}.\tt{root}$, $\tt{v.left}$, and $\tt{v.right}$,
respectively. Each node also has a set of all leaves in its subtree, denoted
as $\tt{v.leaves}$. Each leaf $\ell$ in the tree $\mathcal{T}$ holds a set
$\ell.\tt{set}$ of fingerprints. A unique concept of our approach is the
centroid, ${\tt v.centroid}$, recorded at each node $v$. The centroid is
defined as a fingerprint $F$ for which $F[i]=1$ if and only if there exists
another fingerprint $F^{\prime}$ in the subtree of $\tt{v}$ such that
$F^{\prime}[i]=1$. This is represented as

${\tt v.centroid}=\bigvee\limits_{\ell\in{\tt
v.leaves}}\bigvee\limits_{F\in\ell.{\tt set}}F.$

This concept of the centroid is inspired by BallTree literature.

Our search process is designed to locate all fingerprints $F^{\prime}$ in the
set $\mathcal{F}$ where $F$ is a submask of $F^{\prime}$. This search is based
on the relation $F_{1}\leq F_{2}$ for the fingerprints $F_{1},F_{2}$ that
holds if and only if for every $i\in{1,2,\ldots,{\sf fl}},\ F_{1}[i]\leq
F_{2}[i]$.

The search starts from the root and recursively descends into both subtrees.
We stop the recursive descent if we reach a node ${\tt v}$ where
$F\not\leq{\tt v.centroid}$. Conversely, if we reach a leaf $\ell$ and
$F\leq\ell.{\tt centroid}$, we add to $\mathcal{F}_{M}$ the set
$\\{F^{\prime}\in\ell.{\tt set}\mid{\sf fp}(M)\leq F^{\prime}\\}$.

Following the generation of $\mathcal{F}_{M}$, the next phase involves
examining each

$M^{\prime}\in\bigcup\limits_{F^{\prime}\in\mathcal{F}_{M}}{\sf
fp}^{-1}(F^{\prime}).$

The objective is to determine whether each $M^{\prime}$ is a substructure of
$M$. This determination is made by employing external algorithms to verify the
predicate $\verb|SubStructure|(M^{\prime},M)$, which is true if and only if
$M^{\prime}$ is a substructure of $M$.

Further details on the BallTree and the utilization of the tree in the
substructure search process will be provided in the subsequent sections.

The pseudocode for the fingerprint search function in the tree is described in
Algorithm 1. The pseudocode for the function that searches for superstructures
of a given molecule is described in Algorithm 2.

Algorithm 1 Searching for all matching fingerprints in a subtree

1:${\tt v}$ is a tree vertex, $F$ is a fingerprint

2:$\\{F^{\prime}\in\bigcup\limits_{\ell\in{\tt v.leaves}}\ell.{\tt set}\mid
F\leq F^{\prime}\\}$

3:procedure FindInSubtree(${\tt v},F$)

4: if $F\not\leq{\tt v.centroid}$ then

5: return $\varnothing$

6: else if ${\tt v}\text{ is leaf}$ then

7: return $\\{F^{\prime}\in{\tt v.set}\mid F\leq F^{\prime}\\}$

8: else

9: ${\tt left}\leftarrow$ FindInSubtree(${\tt v.left},F$)

10: ${\tt right}\leftarrow$ FindInSubtree(${\tt v.right},F$)

11: return Concatenate(${\tt left},{\tt right}$)

12: end if

13:end procedure

Algorithm 2 Searching for all superstructures of a given molecule

1:$M$ is a molecule

2:$\\{M^{\prime}\in\mathcal{M}\mid{\tt SubStructure}(M,M^{\prime})\\}$

3:procedure FindMetaStructures($M$)

4: $F\leftarrow{\sf fp}(M)$

5: $F_{M}\leftarrow$ FindInSubtree($\mathcal{T}.{\tt root},F$)

6: return $\\{M^{\prime}\in\bigcup\limits_{F^{\prime}\in\mathcal{F}_{M}}{\sf
fp}^{-1}(F^{\prime})\mid\textsc{\tt SubStructure}(M,M^{\prime})\\}$

7:end procedure

###  2.2 Building the tree

Algorithm 3 Building the tree

1:$\mathcal{F}$ is the set of all fingerprints, $d$ is the depth of the tree

2:$\mathcal{T}$ is the BallTree for the superstructure fingerprint search

3:procedure BuildTree($\mathcal{F},d$)

4: ${\tt v}\leftarrow$ new node

5: if $d=1$ then

6: ${\tt v.set}\leftarrow\mathcal{F}$

7: ${\tt v.centroid}\leftarrow\bigvee\limits_{F\in\mathcal{F}}F$

8: return ${\tt v}$

9: else

10: $\mathcal{F}_{l},\mathcal{F}_{r}\leftarrow$
SplitFingerprints($\mathcal{F}$)

11: ${\tt v.left}\leftarrow$ BuildTree($\mathcal{F}_{l},d-1$)

12: ${\tt v.right}\leftarrow$ BuildTree($\mathcal{F}_{r},d-1$)

13: ${\tt v.centroid}\leftarrow{\tt v.left.centroid}\lor{\tt
v.right.centroid}$

14: return ${\tt v}$

15: end if

16:end procedure

To start, let us create a trivial tree with a single node, denoted as
$\mathcal{T}.{\tt root}$. Assign $\mathcal{T}.{\tt root.set}=\mathcal{F}$.
Next, we will inductively split the leaves of the tree into two parts, thereby
adding new nodes to the tree.

More formally, for each leaf node $\ell$ of the tree, we will divide
$\ell.{\tt set}$ using a specific function called SplitFingerprints:
$\mathcal{F}_{l},\mathcal{F}_{r}\leftarrow{\tt SplitFingerprints}(\ell.{\tt
set})$ ($\mathcal{F}_{l}\sqcup\mathcal{F}_{r}=\ell.{\tt set}$). Next, we will
recursively build trees for $\ell.{\tt left},\ell.{\tt right}$ using the sets
$\mathcal{F}_{l},\mathcal{F}_{r}$.

We will continue to split the leaves in this manner until $\mathcal{T}$
becomes a full binary tree with depth $d$. The pseudocode for the algorithm
described above can be found in 3.

Algorithm 4 Algorithm for splitting fingerprints in parts during tree
construction

1:set $\mathcal{F}$ of fingerprints to be split

2:the split $\mathcal{F}_{l},\mathcal{F}_{r}$ of the set $\mathcal{F}$

3:procedure SplitFingerprints($\mathcal{F}$)

4:
$j\leftarrow\operatorname*{arg\,min}\limits_{i}\\{\left||\mathcal{F}|-2k\right|\mid
k=\\#\\{F\in\mathcal{F}\mid F_{i}=1\\}\\}$

5: $\mathcal{F}_{l}\leftarrow\\{F\in\mathcal{F}\mid F[j]=0\\}$

6: $\mathcal{F}_{r}\leftarrow\\{F\in\mathcal{F}\mid F[j]=1\\}$

7: if $|\mathcal{F}_{l}|>\lfloor\frac{n}{2}\rfloor$ then

8: $\mathcal{F}_{r}\leftarrow\mathcal{F}_{r}\ \cup$
TakeLastElements($\mathcal{F}_{l},|\mathcal{F}_{l}|-\lfloor\frac{n}{2}\rfloor$)

9: $\mathcal{F}_{l}\leftarrow$
DropLastElements($\mathcal{F}_{l},|\mathcal{F}_{l}|-\lfloor\frac{n}{2}\rfloor$)

10: else if $|\mathcal{F}_{r}|>\lceil\frac{n}{2}\rceil$ then

11: $\mathcal{F}_{l}\leftarrow\mathcal{F}_{l}\ \cup$
TakeLastElements($\mathcal{F}_{r},|\mathcal{F}_{r}|-\lceil\frac{n}{2}\rceil$)

12: $\mathcal{F}_{r}\leftarrow$
DropLastElements($\mathcal{F}_{r},|\mathcal{F}_{r}|-\lceil\frac{n}{2}\rceil$)

13: end if

14: return $\mathcal{F}_{l},\ \mathcal{F}_{r}$

15:end procedure

We want to perform the splits in such a way that, on average, the search often
prunes branches during the traversal. That is, the if statement in line 4 of
the algorithm 1 should be executed frequently. Let us discuss the function
SplitFingerprints in more detail.

Initially, one might consider selecting a specific bit $j$ and assigning all
fingerprints $F$ such that $F[j]=0$ to the left subtree, and those with
$F[j]=1$ to the right subtree. In this case, when searching for
superstructures of the fingerprint $F^{\prime}$, if $F^{\prime}[j]=1$, the
entire left subtree would be cropped. However, in practice, this approach
leads to significant differences between the left and right parts after a few
splits, making it difficult to create a deep and balanced tree. Unfortunately,
a shallow or unbalanced tree does not offer substantial improvements over a
full search, as it barely eliminates any search branches.

Therefore, we suggest the following method: we will still select the bit as
mentioned above, but we will divide the fingerprints in a way that ensures the
sizes of the resulting partitions match. For instance, if the optimal division
of $n$ fingerprints yields parts with sizes $n_{0},n_{1}(n_{0}<n_{1}\ \land\
n_{0}+n_{1}=n)$, then all values with zero will be assigned to the left
partition, while the values with one will be distributed to achieve final left
and right partition sizes of
$\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil$ respectively. If
$n_{0}>n_{1}$, we will proceed symmetrically. The algorithm for the
SplitFingerprints function can be found in the pseudocode 4.

##  3 Benchmarks

In this study, we have performed a comprehensive benchmarking to assess the
performance of our algorithm, which is an extension of the Bingo
fingerprinting system, compared to the established index, namely Bingo [9].
Notably, throughout the benchmarking, search results were constrained to the
first 10,000 answers to maintain consistency and manageable data size. Our
benchmarking process was performed under the following conditions:

  * •

OS: Ubuntu 22.04

  * •

Processor: Intel Xeon E5-2686 v4 (Broadwell)

  * •

Clock speed: 2.7 GHz

  * •

RAM: 120 GB

The query dataset used for the benchmarking was retrieved from
https://hg.sr.ht/~dalke/sqc/browse?rev=tip, which contains 3488 relevant
queries for the substructure search. Ten queries were excluded due to various
issues, resulting in a final set of 3478 compounds.

% |  | Qtr Algorithm,
---
single-threaded,
in-memory
| Bingo NoSQL,
---
single-threaded
10% | 0.0273381 | 0.526846
20% | 0.053802 | 0.554869
30% | 0.100528 | 0.610074
40% | 0.208735 | 0.700541
50% | 0.553334 | 0.841574
60% | 0.938981 | 1.06477
70% | 1.09632 | 1.48609
80% | 1.36175 | 2.61958
90% | 2.61875 | 6.42211
95% | 7.83572 | 13.3279
$\leq$ 60 s: | 98.56% | 98.39%
Table 1:  Performance Comparison of Single-Threaded In-Memory Execution
Between Qtr Algorithm and Bingo NoSQL.

For a single-threaded in-memory execution, our algorithm demonstrates
competitive performance. The Table 1 and Fig. 2 summarizes these benchmark
timings, providing a clear comparison between our Qtr algorithm and the Bingo
algorithm. This detailed analysis offers valuable information about the
performance and potential scalability of our algorithm.

Figure 2: Log-Log Plot of Percentage of Unfinished Queries vs Time for Qtr
Algorithm and Bingo NoSQL

##  4 Further Development

Fingerprints currently form the basis of our algorithm, but they do have
certain limitations which do not make them the ideal fit for our tree-based
approach.

Firstly, the condensed nature of the fingerprint is aimed at ensuring
efficient computation, which often leads to grouping together several
characteristics. For instance, a single attribute in a fingerprint often
encapsulates multiple individual elements because these isolated items, while
lacking substantial filtering power across the entire dataset, might be
relevant for specific subsets. However, the fingerprint structure does not
account for such instances. On the contrary, our approach could accommodate
more complex functions, even if they operate slower than traditional filtering
methods, for example, using a fingerprint variant that does not amalgamate
different elements.

Secondly, fingerprints are designed to provide a universal filter throughout
the dataset. This results in a significantly reduced set of attributes
applicable to the entire database. For example, Bingo utilizes 2584
attributes, which intuitively seem insufficient to capture all the
peculiarities of a 113M-sized molecule dataset. Even a substantially enlarged
fingerprint variant would not be able to cover all exceptional cases. In
contrast, our approach, by dealing with subsets, can extract a unique
characteristic for a tree node relevant to the set in the given subtree, thus
allowing for much more effective coverage of the existing data nuances.

As a result, a potential enhancement of our algorithm might involve the use of
a specific attribute in each tree node. Depending on its presence or absence,
the search continues in both subtrees or only in the right subtree. This
attribute would be chosen in advance to approximately bisect the set in the
subtree. A leaf would contain several characteristics that would be examined
when filtering elements from the leaf.

Using the method described above, we could potentially improve the false-
positive rate, as the selected attributes would be relevant to the examined
subsets. Moreover, these attributes could be utilized during verification,
possibly resulting in substantial improvements in the verification stage
speed, thanks to the relevance of these attributes to the molecule subsets.

##  5 Conclusion

The current version of our approach can serve as an extension of a
fingerprint, enhancing filtering speed by avoiding exhaustive enumeration.
Moreover, the tree’s ability to cluster molecules enables a more detailed
examination of cluster-specific attributes, an aspect that existing algorithms
struggle with, as they aim to find optimal ways to generalize across the
entire dataset. Therefore, our approach could potentially be used in the
future to improve both the false-positive rate and the verification speed.

## References

  *   * Barnard [1993] Barnard JM (1993) Substructure searching methods: Old and new. Journal of Chemical Information and Computer Sciences 33(4):532–538. 10.1021/ci00014a001
  * Bonchi et al [2011] Bonchi F, Perego R, Silvestri F, et al (2011) Recommendations for the long tail by term-query graph. In: Proceedings of the 20th international conference companion on World wide web. ACM, pp 15–16, 10.1145/1963192.1963201
  * Clarkson [2006] Clarkson KL (2006) Nearest-neighbor searching and metric space dimensions. In: Shakhnarovich G, Darrell T, Indyk P (eds) Nearest-Neighbor Methods in Learning and Vision. The MIT Press, p 15–60, 10.7551/mitpress/4908.003.0005
  * Cordella et al [2004] Cordella L, Foggia P, Sansone C, et al (2004) A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 26(10):1367–1372. 10.1109/TPAMI.2004.75
  * Klein et al [2011] Klein K, Kriege N, Mutzel P (2011) CT-index: Fingerprint-based graph indexing combining cycles and trees. In: 2011 IEEE 27th International Conference on Data Engineering. IEEE, pp 1115–1126, 10.1109/ICDE.2011.5767909
  * Kuramochi and Karypis [2001] Kuramochi M, Karypis G (2001) Frequent subgraph discovery. In: Proceedings 2001 IEEE International Conference on Data Mining. IEEE Comput. Soc, pp 313–320, 10.1109/ICDM.2001.989534
  * Nijssen and Kok [2004] Nijssen S, Kok JN (2004) A quickstart in frequent structure mining can make a difference. In: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 647–652, 10.1145/1014052.1014134
  * Omohundro [1989] Omohundro S (1989) Five Balltree Construction Algorithms. Technical report (International Computer Science Institute), International Computer Science Institute
  * Pavlov et al [2010] Pavlov D, Rybalkin M, Karulin B (2010) Bingo from SciTouch LLC: chemistry cartridge for oracle database. Journal of Cheminformatics 2:F1. 10.1186/1758-2946-2-S1-F1
  * Shasha et al [2002] Shasha D, Wang JTL, Giugno R (2002) Algorithmics and applications of tree and graph searching. In: Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM, pp 39–52, 10.1145/543613.543620
  * Ullmann [1976] Ullmann JR (1976) An algorithm for subgraph isomorphism. Journal of the ACM 23(1):31–42. 10.1145/321921.321925
  * Weininger [1988] Weininger D (1988) SMILES, a chemical language and information system. 1. introduction to methodology and encoding rules. Journal of Chemical Information and Computer Sciences 28(1):31–36. 10.1021/ci00057a005
  * Xifeng Yan and Jiawei Han [2002] Xifeng Yan, Jiawei Han (2002) gSpan: graph-based substructure pattern mining. In: 2002 IEEE International Conference on Data Mining, 2002. Proceedings. IEEE Comput. Soc, pp 721–724, 10.1109/ICDM.2002.1184038