# The X-ray outburst of PG 1553+113: A precession effect of two jets in the
supermassive black hole binary system

Shifeng Huang  Shandong Key Laboratory of Optical Astronomy and Solar-
Terrestrial Environment,
School of Space Science and Physics,
Institute of Space Sciences, Shandong University,
Weihai, Shandong, 264209, China<EMAIL_ADDRESS><EMAIL_ADDRESS>Hongxing
Yin  Shandong Key Laboratory of Optical Astronomy and Solar-Terrestrial
Environment,
School of Space Science and Physics,
Institute of Space Sciences, Shandong University,
Weihai, Shandong, 264209, China<EMAIL_ADDRESS><EMAIL_ADDRESS>Shaoming Hu
Shandong Key Laboratory of Optical Astronomy and Solar-Terrestrial
Environment,
School of Space Science and Physics,
Institute of Space Sciences, Shandong University,
Weihai, Shandong, 264209, China<EMAIL_ADDRESS><EMAIL_ADDRESS>Xu Chen
Shandong Key Laboratory of Optical Astronomy and Solar-Terrestrial
Environment,
School of Space Science and Physics,
Institute of Space Sciences, Shandong University,
Weihai, Shandong, 264209, China<EMAIL_ADDRESS><EMAIL_ADDRESS>Yunguo
Jiang  Shandong Key Laboratory of Optical Astronomy and Solar-Terrestrial
Environment,
School of Space Science and Physics,
Institute of Space Sciences, Shandong University,
Weihai, Shandong, 264209, China<EMAIL_ADDRESS><EMAIL_ADDRESS>Sofya
Alexeeva  LAMOST fellow  CAS Key Laboratory of Optical Astronomy, National
Astronomical Observatories, Beijing, 100101, China.  Yifan Wang  Shandong Key
Laboratory of Optical Astronomy and Solar-Terrestrial Environment,
School of Space Science and Physics,
Institute of Space Sciences, Shandong University,
Weihai, Shandong, 264209, China<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Blazar PG 1553+113 is thought to be a host of supermassive black hole binary
(SMBHB) system. A 2.2-year quasi-periodicity in the $\gamma$-ray light curve
was detected, possibly result of jet precession. Motivated by the previous
studies based on the $\gamma$-ray data, we analyzed the X-ray light curve and
spectra observed during 2012–2020. The 2.2-year quasi-periodicity might be
consistent with the main-flare recurrence in the X-ray light curve. When a
weak rebrightening in the $\gamma$-ray was observed, a corresponding
relatively strong brightening in the X-ray light curve can be identified. The
“harder-when-brighter” tendency in both X-ray main and weak flares was shown,
as well as a weak “softer-when-brighter” behavior for the quiescent state. We
explore the possibility that the variability in the X-ray band can be
interpreted with two-jet precession scenario. Using the relation between jets
and accretion discs, we derive the primary black hole mass $\simeq 3.47\times
10^{8}M_{\sun}$ and mass of the secondary one $\simeq 1.40\times
10^{8}M_{\sun}$, and their mass ratio $\sim 0.41$.

Supermassive black holes (1663); Blazars (164); X-ray bursts (1814);
Relativistic jets (1390)

††software: astropy (Astropy Collaboration et al., 2013, 2018), emcee
(Foreman-Mackey et al., 2013), matplotlib (Hunter, 2007), scipy (Virtanen et
al., 2020)

##  1 Introduction

The class of active galactic nuclei (AGNs) with their jets pointed at the
observer, is classified as blazars (Urry & Padovani, 1995). At the center of
blazars, supermassive black holes (SMBHs) play the role of engine triggering
the jet. Blazars emit radiation over a wide range of frequencies, from radio
to $\gamma$-rays.

PG 1553+113 is a blazar with redshift $z\simeq 0.5$ (Tavani et al., 2018) and
it most probably hosts a SMBHB (Caproni et al., 2017; Cavaliere et al., 2017;
Sobacchi et al., 2017) resulting in the quasi-periodicity about
$2.2~{}\text{yr}$ in the $\gamma$-ray light curves (Ackermann et al., 2015;
Yan et al., 2018; Sandrinelli et al., 2018; Covino et al., 2020). The
mechanism of the quasi-periodicity in light curves of blazars is still under
debates and the following scenarios were considered: the geometric origin such
as jet precession (Abraham & Carrara, 1998; Abraham & Romero, 1999; Abraham,
2000; Britzen et al., 2018), lighthouse effect (Camenzind & Krockenberger,
1992), beaming effect (Villata et al., 1998) and helical structure of the jet
(Zhou et al., 2018). However, the contribution from the disc should also be
considered, such as the black hole-disc impaction (Lehto & Valtonen, 1996; Dey
et al., 2018), which successfully predicted the 12-year optical quasi-periodic
outburst in OJ 287 (Valtonen et al., 2008, 2016; Laine et al., 2020).
Moreover, the disc instability could be one of the possibilities (Tanaka,
2013) as well.

The quasi-periodicity in the PG 1553+113 light curves is probably related to a
jet precession in the SMBHB system (Caproni et al., 2017; Sobacchi et al.,
2017). However, the $\gamma$-ray light curve shows weaker flares near the main
ones that might indicate the signs of the twin jets in the system (Tavani et
al., 2018; Cavaliere et al., 2019).

Recently, there have been many investigations of the quasi-periodicity for PG
1553+113 mainly based on the $\gamma$-ray light curves. In this work, we focus
not only on the $\gamma$-ray band, but also X-ray. The differences between
X-ray and $\gamma$-ray light curves are due to prominent flares in the X-ray
light curve while weaker counterparts are detected in $\gamma$-ray. In
addition, the interval of each X-ray flare is much shorter than the 2.2 year
quasi-periodicity in the $\gamma$-ray light curve. Motivated by Tavani et al.
(2018), we consider the two-jet structure in this SMBHB system. The motion of
a jet ejected by one of two black holes results in the quasi-periodicity of
the multi-wavelength light curves. While, the jet ejected by another black
hole also contributes to the variation, and the phase of the two jets leads to
a shorter interval of the flares. The model was employed to study the double-
peak structure in the optical outburst of OJ 287 (Villata et al., 1998), and
in this study, we apply this model to the case of PG 1553+113 and the results
show that it is also a possible model.

This paper is organized as follows. In section 2, data reduction is introduced
and the results are shown in section 3. We fit the X-ray light curve with the
model and further discussion is in section 4. Conclusions are presented in
section 5. The following cosmology parameters are used in this work:
$H_{0}=70~{}\text{km}~{}\text{s}^{-1}\text{Mpc}^{-1}$, $\Omega_{M}=0.27$, and
$\Omega_{\Lambda}=0.73$.

##  2 Observation and Data Reduction

###  2.1 Fermi $\gamma$-ray data

The Large Area Telescope (_Fermi_ -LAT), the primary instrument on the Fermi
Gamma-ray Space Telescope (Fermi) mission, is an imaging, wide field-of-view,
high-energy $\gamma$-ray telescope, covering the energy range from below 20
MeV to more than 300 GeV (Atwood et al., 2009). We collected $\gamma$-ray data
of PG 1553+113 from the _Fermi_ -LAT data
website111https://fermi.gsfc.nasa.gov/cgi-bin/ssc/LAT/LATDataQuery.cgi
obtained during 8 years from Jan. 1, 2012 to Jan. 1, 2020.

The data were analyzed with standard unbinned likelihood tutorials using the
Fermi Science Tools Fermitools version 1.0.10. The photons event data were
extracted by gtselect while selecting the source class events centered on the
target from the region of interest (ROI) with the radius of $10^{\circ}$. The
good time intervals were selected with the gtmktime procedure. A counts map of
ROI was created by gtbin and the exposure map was generated by gtltcube and
gtexpmap.

We have adopted the current Galactic diffuse emission model (gll_iem_v07.fits)
and the model for the extragalactic isotropic diffuse emission
iso_P8R3_SOURCE_V2_v1.txt. The source model XML file was created with Python
code make4FGLxml.py, and the diffuse source responses were created by
gtdiffrsp. Finally, the gtlike procedure was run to obtain flux. The threshold
of the test statistics (TS) value is set to be 10 in this work.

###  2.2 Swift XRT and UVOT data

####  2.2.1 X-ray data

The _Swift_ X-Ray Telescope (XRT) is one of the instruments on the Neil
Gehrels _Swift_ observatory with a sensitive broad-band detector for X-ray
from 0.3 to 10 keV (Burrows et al., 2005). The data from January 1, 2012 to
January 1, 2020 were retrieved from the High Energy Astrophysics Science
Archive Research Center (HEASARC) website222https://heasarc.gsfc.nasa.gov/db-
perl/W3Browse/w3browse.pl and we followed standard
threads333https://www.swift.ac.uk/analysis/xrt/index.php to analyse the data
from level I.

All _Swift_ data were reduced with the new released HEASoft 6.26.1. The
xrtpipeline tool was run to reprocess the data. Centering on the target, for
the windowed timing (WT) mode data, a source region file selected by a central
circle with radius of 70 arcsec and a background region file was selected by
an annular with an inner radius of 100 arcsec and outer radius of 150 arcsec.
The pile-up effect was considered for the data collected in photon counting
(PC) mode, and the source region was extracted by an annulus with inner and
outer radius are 10 and 75 arcsec, respectively. The background region for PC
mode was selected with the same method as the case of the WT. The corrected
light curves and spectra were generated by xrtproducts with level II data from
the PC mode and WT mode, respectively.

The source spectra were grouped by grppha with minimum 20 photons per bin for
both PC and WT mode spectra. Besides, in the reduction of X-ray spectra, the
redistribution matrix file swxwt0to2s6_20131212v015.rmf for WT mode and
swxpc0to12s6_20130101v014.rmf for PC mode were used and the ancillary response
files were created by xrtmkarf.

####  2.2.2 UV-optical data

UV/Optical Telescope (UVOT), covering wavelength range 170-600 nm, 7 filters
(v, b, u, uvw1, uvm2, uvw2 and white), with field of view $17^{\prime}\times
17^{\prime}$, is one of instruments on the _Swift_ observatory (Roming et al.,
2005). Following the recommended
threads444https://www.swift.ac.uk/analysis/uvot/index.php, uvotsource in
HEASoft 6.26.1 was run with a source circular region radius of 10 arcsec for
v, b, u bands, but for uvw1, uvw2 and uvm2, we used a source region file with
radius of 20 arcsec. The background region files were extracted in a region
without any source nearing the source with the radius of 50 arcsec. We adopted
the extinction $E(B-V)=0.054$ mag, and the results of Raiteri et al. (2015)
were applied here with 0.173, 0.229, 0.275, 0.394, 0.457, and 0.481 mag
corresponding to the v, b, u, uvw1, uvm2 and uvw2 bands.

###  2.3 XMM-Newton data

_XMM-Newton_ is an X-ray observatory, and its main instrument is the European
Photon Imaging Camera (EPIC), consisting of two MOS detectors and a pn camera
which operate in the 0.2–12.0 keV energy range. Totally, 24 sets of
observations of PG 1553+113 obtained from 2001 to 2020 were employed and
analysed with the software Science Analysis System (SAS version 18.0). We
followed the recommended data analysis threads by XMM-Newton Science Operation
Centre, cifbuild and odfingest procedures for the preparation, and then
xmmextractor for the extractions of the light curves and spectra. The evselect
was run when we extracted the light curves on 0.3–2.0 keV and 2.0–10.0 keV.

###  2.4 Radio data

The 40 m telescope at the Owens Valley Radio Observatory (OVRO), is monitoring
more than 1800 blazars (Richards et al., 2011). We obtain the 15 GHz data
covering from 2012 January to 2020 January from the public data archived
website555http://www.astro.caltech.edu/ovroblazars/index.php?page=home.

##  3 Multi-wavelength light curves

The multi-wavelength light curves during 2012 January – 2020 January of PG
1553+113, ranging from $\gamma$-ray to the radio, are shown in Figure 1. The
light curve of $\gamma$-ray exhibits the quasi-periodic variations which were
reported by Ackermann et al. (2015). Some weak flares can be seen near the
main flares on the $\gamma$-ray light curve. Similar situations can also be
seen in the X-ray and optical/UV bands.

When the main flare in the $\gamma$-ray light curves was observed, the
prominent outbursts in both X-ray and optical/UV bands could be seen, and, in
addition, similar to the case of the $\gamma$-ray, some distinct flares in
X-ray and optical/UV bands were observed when the weak flares in $\gamma$-ray
were recorded.

In the radio light curve, a quasi-periodic variation can also be seen,
however, weak flares are not observed clearly.

Figure 1: Multiwavelength light curves of PG 1553+113 covering $\gamma$-ray,
X-ray, UV, optical and radio bands with epochs from 2012 to 2020. The
$\gamma$-ray light curve is shown with a 20 day binning and the data of X-ray
and optical/UV are rebinned to one data point for each observation.

##  4 Discussion

The quasi-periodic variation in the $\gamma$-ray light curve of PG 1553+113
was explained by the jet precession in the SMBHB (Caproni et al., 2017). One-
jet model is appropriate for main flares, while the existence of the weak
peaks on the light curve, possibly requires a two-jet model to explain this
phenomenon (see e.g., Tavani et al. 2018, Cavaliere et al. 2019).

We attempted to fit the X-ray light curves with the single jet precession, but
unfortunately, the obtained period is much shorter than that in the case of
$\gamma$-ray when the same model was used for fitting. Moreover, similar
behavior of the main and weak flares in the correlation between flux and
spectral index may be the signature of two jets. Based on this possibility, in
order to explore the origin of the X-ray outbursts, we propose the two-jet
model for this case.

###  4.1 The two-jet precession model

In this model, a SMBHB system is considered and each black hole carries its
own jet and the movement of the black holes on the orbit causes the quasi-
periodic variation on the light curves (Villata et al., 1998; Tavani et al.,
2018).

Motivated by the work of Villata et al. (1998), we obtain a function of the
angle between the line of sight and the jet direction

$\displaystyle\cos\theta_{obs,1}$ $\displaystyle=$
$\displaystyle\cos\phi_{1}\cos\alpha_{1}+\sin\phi_{1}\sin\alpha_{1}\cos\omega
t,$ (1) $\displaystyle\cos\theta_{obs,2}$ $\displaystyle=$
$\displaystyle\cos\phi_{2}\cos\alpha_{2}+\sin\phi_{2}\sin\alpha_{2}\cos(\omega
t+\psi),$ (2)

where the subscripts 1 and 2 correspond to the first and the second jet,
respectively, and $\theta_{obs,1}$, $\theta_{obs,2}$ are the angles between
the line of sight and the jet direction, $\phi_{1}$ and $\phi_{2}$ are the
angles between the line of sight and the orbital angular momentum/spin of the
individual black hole (assuming that the spin parallel to the orbital angular
momentum), $\alpha_{1}$ and $\alpha_{2}$ are the angles between the orbital
angular momentum and the jet direction, $\omega$ is the orbital angular
velocity and $\psi$ is the phase position.

The flux of the jet can be expressed as $F(t)=\delta^{3}(t)F_{0}$, where
$F_{0}$ is the flux in the rest frame, and $\delta(t)$ is the Doppler factor
which can be written as $\delta(t)=\frac{1}{\gamma(1-\beta\cos\theta_{obs})}$,
where $\beta$ is the bulk velocity and
$\gamma=\left(1-\beta^{2}\right)^{-\frac{1}{2}}$ is the Lorentz factor. In
addition, before fitting, we transform the flux into luminosity through
$L=4\pi D^{2}F$, where $D$ is the luminosity distance. In our model, the
observed luminosity can be obtained as

$\displaystyle L_{tot}=\delta_{1}^{3}(t)L_{1}+\delta_{2}^{3}(t)L_{2}+L_{b},$
(3)

where $L_{1}$ and $L_{2}$ are the luminosity of jet 1 and jet 2, the subscript
1, 2 of $\delta$ refers to the Doppler factor of the two jets, and $L_{b}$ is
the contribution from other sources such as the disc, corona, etc. For
simplification, the precession of the disc, gravitational redshift, and
intrinsic variety of accretion flow is not considered here, therefore, for
convenience, we assume that $L_{b}$ is not a time-dependent physical quantity
in our model.

###  4.2 Fitting results

In the fitting, we only fixed the orbital angular velocities
($\omega=\frac{2\pi}{P}$) of both black holes. To be consistent with the case
of $\gamma$-ray, the period was frozen as $P=2.2~{}\text{yr}$. Additionally,
$L_{b}$ was frozen as $8.0\times 10^{45}\text{erg}~{}\text{s}^{-1}$ which is
the minimum value in the light curve. Meanwhile, with assumption
$\phi_{1}=\phi_{2}$, other parameters in the model were freed. However,
Villata et al. (1998) assumed the two jets share the same values of the
parameters when they tried to explain the quasi-periodic double peak structure
in the optical light curves of OJ 287. In our work, we do not set the
parameters of the two jets (except for the orbital angular velocities and
$\phi_{1}=\phi_{2}$) to be equal. The Markov Chain Monte Carlo (MCMC) emcee
package (Foreman-Mackey et al., 2013) was used in the fitting and 500 walkers
and 10000 steps were run666The chain was accessed by using the
_EnsembleSampler.get_chain_ in python package _emcee_. Within this method, we
obtained the parameter values as a function of the step numbers in the chain.
When the parameters do not change much, the chain can be considered stable. .
We adopt the uniform prior as $0.0<\phi_{1}<10^{\circ}$,
$0.0<\alpha_{1},\alpha_{2}<10^{\circ}$, $0.0<\psi<2\pi$,
$0.0<\gamma_{1},\gamma_{2}<50.0$, $0.0<L_{1},L_{2}<5.0\times
10^{44}\text{erg}~{}\text{s}^{-1}$. The fitted result is shown in Figure 2.
More details for the fitted parameters in our model are shown in Table 1.

The fitting is unsatisfactory, with a reduced chi-square of 348.41. However,
we did not expect a perfect result based on the X-ray light curve, mainly
because of the simple model and the lack of continuous observations for this
object. Nevertheless, we had tried to free the period parameter in the
fitting, but in the results, the fitted period of 2.8 years is inconsistent
with the case of $\gamma$-ray (Ackermann et al., 2015). Tavani et al. (2018)
showed the consistency between the R-band and X-ray light curves in the long-
term observations. Additionally, Sandrinelli et al. (2018) and Tavani et al.
(2018) reported a similar behavior in the long-term $\gamma$-ray and the
R-band light curve. Therefore, we can assume that the $\gamma$-ray and X-ray
light curves are correlated to some extent. Hence, in fitting, it is
reasonable to fix the periodicity to 2.2 years from continuously monitoring
$\gamma$-ray data (Caproni et al., 2017; Sandrinelli et al., 2018; Cavaliere
et al., 2019).

As mentioned in the last subsection, we only consider the geometric effect in
the system in this work. The profile of the X-ray light curve of PG 1553+113
is fairly complicated, while the fitted model in this work is rather simple
and it can not describe all the data points in the X-ray. We have tried to
improve the model to fit the X-ray light curve and some geometric effects were
considered in the test. Although the statistical fitting result is slightly
improved, the data sampling still plays an important role. The sparse sample
can be fitted well by such complex models may not indicate the true nature of
the system. To further investigate the detail of the variability, more high
cadence observations are needed. The origin of the X-ray is very complex and
there exist some other mechanisms that would modulate the variability. Based
on the assumption that the quasi-periodic variation in the X-ray light curve
is origin from the emission of the jets, we only explore the effect of the two
jets’ precession. However, according to Sobacchi et al. (2017), the Lense-
Thirring precession would modulate the oscillation of angle with the time
scale from days to years and this may affect on the X-ray variability.
Additionally, we did not consider the intrinsic variation of the jets, so our
model can not mirror the activity in the jets. For these reasons, the
predicted light curve may not fit the observed data very well.

Although the data points in the light curve can not be described well by the
two-jet precession scenario, the main and weak flares can be explained well.
In order to predict variability accurately, more aspects need to be taken into
account. However, in this work, we mainly focus on the effect caused by the
precession of two jets in the SMBHB system.

Figure 2: Fitting of the X-ray (0.3 – 10.0 keV) light curve (dots with error
bars) by the two-jet model (solid curves).  Table 1: The best-fit results for
the parameters through two-jet model.

Parameter | Value | Parameter | Value
---|---|---|---
$\phi_{1}$ | 4.35 degree | $t_{0}$ | 2011.40
$\alpha_{1}$ | 1.66 degree | $\alpha_{2}$ | 2.64 degree
$\gamma_{1}$ | 7.67 | $\gamma_{2}$ | 11.96
$L_{1}$ | $0.21\times 10^{44}\text{erg}~{}\text{s}^{-1}$ | $L_{2}$ | $0.12\times 10^{44}\text{erg}~{}\text{s}^{-1}$
$\psi$ | 176.59 degree |  |

Note. — We obtain the fitting results with the two-jet model through emcee.
The subscripts 1 and 2 correspond to the parameter of the jet 1 and jet 2.
$t_{0}$ is the reference time.

###  4.3 The mass estimation of each black hole

The mass of each black hole was not directly estimated in the previous
investigations. We can only constrain the orders of magnitude of the two black
holes masses through the fitting results. Following the relation between the
power of jets and the luminosity of the discs, the mass of each black hole can
be estimated. According to Ghisellini et al. (2014),

$\log P_{rad}=0.98\log L_{disc}+0.639,$ (4)

where $P_{rad}$ is the radiative power of the jet, and $L_{disc}$ is the disc
luminosity. Assuming that X-ray originated from synchrotron emission, the
radiative power of the jet can be written as

$P_{rad}=\frac{32}{5}L_{bol,jet}\frac{\gamma^{4}}{\delta^{6}},$ (5)

where $L_{bol,jet}$ is the bolometric luminosity of the jet which can be
estimated following the method of Runnoe et al. (2012).

Substituting the fitting results from Table 1 into Equations (5) and (4), and
assuming the accretion rate as 0.1 $\dot{M}_{\text{edd}}$ (following Ackermann
et al., 2015), where $\dot{M}_{\text{edd}}$ is the Eddington accretion rate,
we obtain the masses of the black holes launching jet 1 and jet 2 are
$M_{1}\simeq 1.40\times 10^{8}M_{\sun}$ and $M_{2}\simeq 3.47\times
10^{8}M_{\sun}$, respectively. The inferred mass ratio is
$q=\frac{M_{1}}{M_{2}}\simeq 0.41$ that is in agreement with Tavani et al.
(2018). The total mass of the SMBHB system is consistent with the results of
Ackermann et al. (2015) and Cavaliere et al. (2019).

###  4.4 The X-ray properties evolution

The X-ray energy spectra were analyzed with the redshift power-law model
(zpowerlw) through xspec version 12.10.1f. The mean value of the power-law
index is $2.38\pm 0.02$ with the maximum and minimum value of
$2.98^{+0.47}_{-0.42}$ and $1.81^{+0.27}_{-0.24}$ respectively, and the
results can be seen on the middle panel of Figure 3. Centering at the peak
time, we define the 80% of the interval between the two predicted time of
minimum luminosity as the flare epoch. We can also define three states to
describe the X-ray activity: quiescent, weak flares, and main flares, which
corresponding to the different epochs in the results of the two-jet precession
model.

To study the evolution of the X-ray flux of PG 1553+113, we analyzed the
hardness ratio (HR) expressed as

$HR=\frac{CR(2.0\mbox{--}10.0\text{keV})-CR(0.3\mbox{--}2.0\text{keV})}{CR(2.0\mbox{--}10.0\text{keV})+CR(0.3\mbox{--}2.0\text{keV})},$
(6)

where CR(2.0–10.0 keV) and CR(0.3–2.0 keV) are counts rate of the hard and
soft X-ray, respectively. The evolution of HR is shown on the bottom panel of
Figure 3. From 2012.0 to 2020.0, the average value of HR is $-0.689\pm 0.004$
with the maximum and minimum value are $-0.468\pm 0.062$ and $-0.838\pm 0.058$
respectively, which exhibits a very soft level in the stage.

Figure 3: The evolution of X-ray (0.3–10.0 keV) flux, power-law index and
hardness ratio in PG 1553+113 are shown on the top, middle and bottom panels,
respectively. The index was selected by following criterion: reduced chi-
square $<1.2$ and degree of freedoms $>20$. The grey shadows denote the main
flares epochs, and the pink shadows mark the weak flares epochs.

We analyse X-ray data acquired by the _XMM-Newton_ Observatory. The main flare
spectrum was obtained in September 6, 2001 (ID 0094380801), the weak flare was
observed in July 24, 2013 (ID 0727780101), and the spectrum for a quiescent
state with observation ID 0810830201 was obtained in August 27, 2019. The
spectra were analysed with xspec, and final results are presented in Figure 4.
The X-ray energy spectra exhibit different behavior at these epochs. Raiteri
et al. (2015) compared the spectral energy distribution (SEDs) for three
states, and from their results, the quiescent state SEDs showed the
significant different behavior from the flare states in $\gamma$-ray, which
may be the contribution of the jet’s activity.

Figure 4: _XMM-Newton_ X-ray energy spectra for main flare (black), weak flare
(green) and quiescent state (red). Three spectra were fitted by the zpowerlw
model. The power-law indexes for the three states are $2.40\pm 0.01$ (weak
flare), $2.44\pm 0.02$ (main flare) and $2.52\pm 0.01$ (quiescent state),
respectively. The reduced chi-square for the spectral fitting are 1.00 (weak
flare), 0.99 (main flare) and 1.00 (quiescent state), respectively. The errors
are 90% confidence.

###  4.5  Flare spectral indices

The power-law index and hardness ratio stay at a relatively stable level most
of the time. The best linear fit of the correlation between flux and the
power-law index are shown in Figure 5, and the results reveal a slightly
“harder-when-brighter” feature during the main and weak flares while for the
quiescent state, the slightly “softer-when-brighter” tendency can be seen. We
explore the correlation between the index and flux with Spearman test. The
analysis is processed by the python package scipy.stats.spearmanr. During main
flares, the correlation coefficients ($r_{s}$) $<-0.2$ for all cases with
p-value $<0.05$. For the case of weak flares, $r_{s}<-0.1$ and the p-value
$<0.7$ (the result from _XMM-Newton_ shows the p-value of 0.675). The result
of quiescent state reveals $r_{s}<0.2$ with p-value $<0.6$. It should be noted
that in the quiescent state, we obtain only one data point from _XMM-Newton_ ,
hence the correlation test for this instrument can not be applied. More
details for the linear fitting and Spearman test are shown on Table 2.

When we fit all the data together, the slop is very different from the
separated fitting results. We note that this behavior is related to the
distribution of data points. 8 XMM data points for weak flares locate on the
low flux and the power-law index $>2.5$. And for the case of XRT, few points
locate on such interval. Therefore, the XMM data points decrease the slope
when we fit the data from two instruments together.

The similar evolution of the spectral index for both main and weak flares
suggest the same radiation mechanism, which may be related to the jets. The
different behavior of the quiescent states and flares may be the contribution
of the precession of jets. When the jet pointing to the observer, the “harder-
when-brighter” tendency in the flares states can be seen, and in the quiescent
state, with the fraction of the contribution from the disc increase, the
spectra tend to be “softer-when-brighter” (Wang & Jiang, 2020).

Figure 5: The correlation between flux and power-law index for three different
states. The results were obtained by spectral fitting with a single power-law,
and then we selected the results whose reduced Chi-square $\chi_{r}^{2}<1.2$
and the degree of freedoms $>20$ are shown. To compare the discrepancy for
these two telescopes, we fitted the data and presented the results from
_Swift/XRT_ (blue) and _XMM-Newton_ (purple) separately. The red lines are the
best fit of the flux and power-law index for the whole data, and the blue dash
lines are the best fit of the _Swift/XRT_ data, the best fit for XMM data are
shown as the purple dash-dot lines.  Table 2: The correlation between spectral
indices and flux.

Epoch | Instrument | $r_{s}$ | P-Value | Slope | Intercept
---|---|---|---|---|---
Main flares | XRT | -0.296 | 0.003 | $-0.020^{+0.006}_{-0.006}$ | $2.397^{+0.058}_{-0.057}$
Main flares | XMM | -0.846 | 0.001 | $-0.370^{+0.269}_{-0.237}$ | $2.763^{+0.102}_{-0.103}$
Main flares | All | -0.406 | $8.919\times 10^{-6}$ | $-0.187^{+0.081}_{-0.075}$ | $2.563^{+0.063}_{-0.067}$
Weak flares | XRT | -0.308 | 0.033 | $-0.218^{+0.319}_{-0.320}$ | $2.369^{+0.202}_{-0.201}$
Weak flares | XMM | -0.152 | 0.675 | $-0.210^{+0.137}_{-0.131}$ | $2.636^{+0.059}_{-0.060}$
Weak flares | All | -0.415 | 0.001 | $-0.426^{+0.180}_{-0.178}$ | $2.582^{+0.102}_{-0.111}$
Quiescent state | XRT | 0.107 | 0.567 | $0.115^{+0.382}_{-0.380}$ | $2.303^{+0.203}_{-0.204}$
Quiescent state | XMM | - | - | - | -
Quiescent state | All | 0.105 | 0.566 | $0.093^{+0.484}_{-0.466}$ | $2.349^{+0.238}_{-0.252}$

Note. — The Spearman-rank test correlation coefficient, p-value, slope,
intercept, respectively. The slope and intercept are obtained from the linear
fitting. We compare the results of two instruments for each epoch. Then, the
data of _Swift_ and _XMM-Newton_ are combined together in the analysis and the
results are shown on the rows labeled with “All”.

###  4.6 Some possible origins for X-ray light curves variation

In the previous subsections, we argue that the X-ray variation is dominated by
the precession of jets, however, the other potential contributions may be
considered. We discuss the lighthouse effect, general relativity effect, disc
instability, and Lense-Thirring precession below. But the timescale of the
variation from these effects is inconsistent with the 2.2-year quasi-
periodicity, however, we can not exclude out the modulation of these effects
on the long and short timescale variability of PG 1553+113.

####  4.6.1 The lighthouse effect

With the magnetic field of the disc, the plasma bubbles may be injected into
the jet and would be forced to move along it. As the result, the rotation of
these bubbles around the jet would induce the variability of the light curves
(Camenzind & Krockenberger, 1992). In this scenario, the variation of the
light curves is determined by the viewing angle between the line of sight and
the velocity direction of the bubbles and the angle should be time-dependent
and is related to the spin of the black hole. The lighthouse effect can
explain the intraday variability of 3C 273 and BL Lacertae well. However, the
variability timescale of this effect is shorter compared to the quasi-
periodicity of 2.2-year in PG 1553+113.

####  4.6.2 General relativity effect on the jet

When a blob is produced and propagate from disc to jet, its motion would be
affected by the magnetic field, the radiation field, and the gravitational
field which may induce the variation of the light curves (Abramowicz et al.,
1990; Mohan & Mangalam, 2015). According to this scenario, the production of a
blob is located in the vicinity of the black hole, as a result, some general
relativity (GR) effects such as the gravitational redshift, gravitational
lensing and the time delay should be taken into account. The helical orbit of
the blobs cause the quasi-periodic variation of the light curves, and the
results of Mohan & Mangalam (2015) suggest that its time scale ranges from few
days to tens of days.

####  4.6.3 Disc instability

The whole SMBHB system may be surrounded by a huge disc so that the two black
holes are embedded in it, and the periodic leakage of the gas into the cavity
around the SMBHB may occur (Tanaka, 2013). As a result, the fluctuation of
flux which is produced by the periodic accretion can be observed. In this
scenario, the variation time scale is related to the orbital period, however,
the X-ray emission should be very soft and its light curve would decline as a
power-law just similar to the case of tidal disruption events ($L\propto
t^{-5/3}$). According to the fitting results, the emission of PG 1553+113
should be dominated by the jets, and the contribution of the disc is weaker at
least by an order of magnitude. Hence we argue that the effect of the
instability of the disc may be inconspicuous for PG 1553+113.

####  4.6.4 Lense-Thirring precession

The Lense-Thirring precession of the disc would induce the quasi-periodic
oscillations (QPO) in the Kerr space time (Aschenbach, 2004; Johannsen &
Psaltis, 2011). For the case of PG 1553+113, the time scale of QPO due to
Lense-Thirring precession is much longer than the orbital period in SMBHB
system (Sobacchi et al., 2017). As a consequence, the effect from the Lense-
Thirring precession only contributes to the long time scale period of this
system.

##  5 Conclusion

Blazar PG 1553+113 is a SMBHB system candidate showing quasi-periodic
variability across the electromagnetic spectrum. The physical origin of this
variability is still not well-understood. We study the flux and spectral
variability of PG 1553+113 on long-term timescales using _Swift_ and _XMM-
Newton_ X-ray data collected for the period 2012–2020. During this period, the
X-ray light curve of PG 1553+113 exhibits several main and weak flares. The
main X-ray flares and some weak flares are consistent with the corresponding
flares observed on the $\gamma$-ray band. A “harder-when-brighter” behavior is
observed in the X-ray for both main and weak flares, while a “softer-when-
brighter” behavior in quiescent states.

The observed quasi-periodic variation in the $\gamma$-ray light curves could
be explained with one-jet model, however the origin of weak X-ray flares would
remain unclear. In this study, we apply a two-jet model and show that the
contribution from another jet and the accretion disc should be considered to
explain the X-ray variability. Based on our fitting results for the X-ray
light curve and the correlation between the disc and the jet (Ghisellini et
al., 2014), we obtain the mass of the primary black hole is $\simeq 3.47\times
10^{8}M_{\sun}$, the secondary one $\simeq 1.40\times 10^{8}M_{\sun}$, and the
mass ratio $\simeq 0.41$ that is in line with previous studies. Although we
can not obtain the exact values of the parameters, the order of magnitude of
the total mass and the mass ratio are consistent with the previous works. In
order to research the more detail of the variability, more high cadence
observations are needed.

Blazar PG 1553+113 is not the first object with possible double-jet structure
signatures. For example, Qian et al. (2019) proposed a double-jet structure
scenario for 3C 279 and suggested that there may be a SMBHB ejecting two
precessing relativistic jets. At variance with their method, we focused on
X-ray bands. This may be a indirect tool to search such SMBHB systems with two
jets in the future.

In the extreme mass ratio black hole binary systems, the accretion disc may
not form around the secondary black hole within the gravity of the primary
one, such as OJ 287 (Lehto & Valtonen, 1996). However, in mildly mass ratio
SMBHB systems, it is possible that each black hole may have its own disc
(Farris et al., 2014; Bowen et al., 2017; Ryan & MacFadyen, 2017) and two-jet
signature can be detected. Probably, our approach is valid in the case of the
SMBHB systems with a mild mass ratio and we can detect such types of black
hole systems in the future.

In complex environment of blazars, a pure geometric model is one of the tools
to study the X-ray light curves. A simple model should not be expected to
complete the explanation perfectly. Some intrinsic variation in the jets and
discs should be considered in further research.

We are grateful to the anonymous referee for valuable comments that improved
this work. This work is supported by the Natural Science Foundation of China
under grant No. 11873035, the Natural Science Foundation of Shandong province
(No. JQ201702), and the Young Scholars Program of Shandong University (No.
20820162003).Yunguo Jiang is supported by Shandong Provincial Natural Science
Foundation (No. ZR2020MA062) and National Natural Science Foundation of China
(No. U2031102). S. Alexeeva acknowledges support from the National Natural
Science Foundation of China (grant No. 12050410265) and LAMOST FELLOWSHIP
program that is budgeted and administrated by Chinese Academy of Sciences. We
acknowledge Swift for the observation and providing the public data for the
research. OVRO 40-m monitoring program (Richards et al., 2011) which is
supported in part by NASA grants NNX08AW31G, NNX11A043G, and NNX14AQ89G and
NSF grants AST-0808050 and AST-1109911. Based on observations obtained with
XMM-Newton, an ESA science mission with instruments and contributions directly
funded by ESA Member States and NASA.

## References

  * Abraham & Carrara (1998) Abraham, Z. & Carrara, E. A. 1998, ApJ, 496, 172
  * Abraham & Romero (1999) Abraham, Z. & Romero, G. E. 1999, A&A, 344, 61
  * Abraham (2000) Abraham, Z., 2000, A&A, 355, 915
  * Abramowicz et al. (1990) Abramowicz, M. A., Ellis, G. F. R., & Lanza, A. 1990, ApJ, 361, 470
  * Ackermann et al. (2015) Ackermann, M., Ajello, M., Albert, A., et al. 2015, ApJ, 813, L41
  * Aschenbach (2004) Aschenbach, B. 2004, A&A, 425, 1075
  * Astropy Collaboration et al. (2013) Astropy Collaboration, Robitaille, T. P., Tollerud, E. J., et al. 2013, A&A, 558, A33
  * Astropy Collaboration et al. (2018) Astropy Collaboration, Price-Whelan, A. M., Sipőcz, B. M., et al. 2018, AJ, 156, 123
  * Atwood et al. (2009) Atwood, W. B., Abdo, A. A., Ackermann, M., et al. 2009, ApJ, 697, 1071
  * Bowen et al. (2017) Bowen, D. B., Campanelli, M., Krolik, J. H., et al. 2017, ApJ, 838, 42
  * Britzen et al. (2018) Britzen, S., Fendit, C., Witzel, G., et al. 2018, MNRAS, 478, 3199
  * Burrows et al. (2005) Burrows, D. N., Hill, J. E., Nousek, J. A., et al. 2005, Space Sci. Rev., 120, 165
  * Camenzind & Krockenberger (1992) Camenzind, M., & Krockenberger, M. 1992, A&A, 255, 59
  * Caproni et al. (2017) Caproni, A., Abraham, Z., Motter, J. C., et al. 2017, ApJ, 851, L39
  * Cavaliere et al. (2017) Cavaliere, A., Tavani, M., & Vittorini, V. 2017, ApJ, 836, 220
  * Cavaliere et al. (2019) Cavaliere, A., Tavani, M., Munar-Adrover, P., et al. 2019, ApJ, 875, L22
  * Covino et al. (2020) Covino, S., Landoni, M., Sandrinelli, A., et al. 2020, ApJ, 895, 122
  * Dey et al. (2018) Dey, L., Valtonen, M. J., Gopakumar, A., et al. 2018, ApJ, 866, 11
  * Farris et al. (2014) Farris, B. D., Duffell, P., MacFadyen, A. I., et al. 2014, ApJ, 783, 134
  * Foreman-Mackey et al. (2013) Foreman-Mackey, D., Hogg, D. W., Lang, D., et al. 2013, PASP, 125, 306
  * Ghisellini et al. (2014) Ghisellini, G., Tavecchio, F., Maraschi, L., et al. 2014, Nature, 515, 376
  * Hunter (2007) Hunter, J. D. 2007, Computing in Science and Engineering, 9, 90
  * Johannsen & Psaltis (2011) Johannsen, T., & Psaltis, D. 2011, ApJ, 726, 11
  * Katz (1997) Katz, J. I., 1997, ApJ, 478, 527
  * Laine et al. (2020) Laine, S., Dey, L., Valtonen, M., et al. 2020, ApJ, 894, L1
  * Lehto & Valtonen (1996) Lehto, H. J., & Valtnoen, M. J., 1996, ApJ, 460, 207
  * Mohan & Mangalam (2015) Mohan, P., & Mangalam, A. 2015, ApJ, 805, 91
  * Qian et al. (2019) Qian, S. J., Britzen, S., Krichbaum, T. P., et al. 2019, A&A, 621, A11.
  * Raiteri et al. (2015) Raiteri, C. M., Stamerra, A., Villata, M., et al. 2015, MNRAS, 454, 353
  * Richards et al. (2011) Richards, J. L., Max-Moerbeck, W., Pavlidou, V., et al. 2011, ApJS, 194, 29
  * Roming et al. (2005) Roming, P. W. A., Kennedy, T. E., Mason, K. O., et al. 2005, Space Sci. Rev., 120, 95
  * Runnoe et al. (2012) Runnoe, J. C., Brotherton, M. S., & Shang, Z. 2012, MNRAS, 422, 478
  * Ryan & MacFadyen (2017) Ryan, G. & MacFadyen, A. 2017, ApJ, 835, 199
  * Sandrinelli et al. (2018) Sandrinelli, A., Covino, S., Treves, A., et al. 2018, A&A, 615, A118
  * Sobacchi et al. (2017) Sobacchi, E., Sormani, M. C., & Stamerra, A. 2017, MNRAS, 465, 161
  * Tanaka (2013) Tanaka, T. L. 2013, MNRAS, 434, 2275
  * Tavani et al. (2018) Tavani, M., Cavaliere, A., Munar-Adrover, P., et al. 2018, ApJ, 854, 11
  * Urry & Padovani (1995) Urry, C. M., & Padovani, P. 1995, PASP, 107, 803
  * Valtonen et al. (2008) Valtonen, M. J., Lehto, H. J., Nilsson, K., et al. 2008, Nature, 452, 851
  * Valtonen et al. (2016) Valtonen, M. J., Zola, S., Ciprini, S., et al. 2016, ApJ, 819, L37
  * Villata et al. (1998) Villata, M., Raiteri, C. M., Sillanpaa, A., et al. 1998, MNRAS, 293, L13
  * Virtanen et al. (2020) Virtanen, P., Gommers, R., Oliphant, T. E., et al. 2020, Nature Methods, 17, 261.
  * Wang & Jiang (2020) Wang, Y.-F. & Jiang, Y.-G. 2020, ApJ, 902, 41.
  * Yan et al. (2018) Yan, D., Zhou, J., Zhang, P., et al. 2018, ApJ, 867, 53
  * Zhou et al. (2018) Zhou, J., Wang, Z., Chen, L., et al. 2018, Nature Communications, 9, 4599


which is positive. If $g(B/H)\geq 2$, then we get $\sharp H\leq g(B)-1$ by
$T\geq 2$, and it follows that $r_{i}\leq\sharp H\leq g(B)-1$ for any
$i=1,\cdots s$.

Assume that $g(B/H)=1$. Then we get $s>0$ by $T>0$. By $r_{i}\geq 2$ for any
$i=1,\cdots s$, we get $1-1/r_{i}\geq 1/2.$ Therefore we obtain
$r_{i}\leq\sharp H\leq 4(g(B)-1)$ for any $i=1,\cdots s$ by $T\geq 1/2$.

Assume that $g(B/H)=0$. When $s\geq 5$, we get $r_{i}\leq\sharp H\leq
4(g(B)-1)$ for any $i=1,\cdots s$ by $T\geq 1/2$. When $s=4$, one of $r_{i}$
is not less than $3$. So we get $r_{i}\leq\sharp H\leq 12(g(B)-1)$ for any
$i=1,\cdots s$ by $T\geq 1/6$. When $s=3$, we may assume $r_{1}\geq r_{2}\geq
r_{3}$. By the definition of $T$, we get

$\displaystyle r_{1}\leq\sharp
H=\frac{2g(B)-2}{1-\frac{1}{r_{1}}-\frac{1}{r_{2}}-\frac{1}{r_{3}}},$

so we obtain

$\displaystyle r_{1}-1-\frac{r_{1}}{r_{2}}-\frac{r_{1}}{r_{3}}\leq 2g(B)-2.$

If $r_{3}=2$, then $r_{2}\geq 3$, so we get

$\displaystyle r_{1}-1-\frac{r_{1}}{3}-\frac{r_{1}}{2}\leq 2g(B)-2.$

Hence we get $r_{1}\leq 6(2g(B)-1)$. If $r_{2}\geq r_{3}\geq 3$, we get
$r_{1}\leq 3(2g(B)-1)$. Therefore we obtain $r_{p}\leq 6(2g(B)-1)$ for any
$p\in B$.

(ii) The case of $g(B)=1$.

We do not have to consider a translation, since it has no fixed points. Then
it is well known that the order of the automorphism groups of $B$ which fixes
a point is at most $6$. So the order of the stabilizer of $H$ is at most $6$,
and we get $r_{p}\leq 6$.

(iii) The case of $g(B)=0$

If $H$ is neither a cyclic group nor a dihedral group, the order of the
stabilizer of $H$ is at most $5$. So we may assume $H$ is either a cyclic
group or a dihedral group. It is well known that a rational pencil with at
most two singular fibers is iso-trivial. If the number of singular fibers of
$f$ is at least three, then there exist a point $p\in B$ such that
$\mu_{n}\geq n\sharp\mathaccent 869{K}/K_{f}^{2}(\Gamma_{p})$ and $r_{p}\leq
2$. Hence we may assume $r_{p}\leq 2$. ∎

######  Theorem 6.2.

Let $f:S\to B$ be a non-locally trivial primitive cyclic covering fibration of
type $(g,1,n)$ with
$g\geq\mathrm{max}\\{\frac{30n^{2}-47n+25}{n+1},\frac{7}{2}n(n-1)+1\\}$. Put

$\displaystyle\mu_{n}^{\prime}:=\frac{6n^{2}\delta}{(n-1)(5n-4)}.$

Assume furthermore that the branch locus $R$ has singular points on at least
three $($resp. one$)$ fibers when $g(B)=0$ $($resp. $g(B)\geq 1$$)$.  Let $G$
be a finite subgroup of $\mathrm{Aut}(f)$. Then it holds

$\sharp G\leq\begin{cases}6(2g(B)-1)\mu_{n}^{\prime}K_{f}^{2}&(g(B)\geq 1),\\\
5\mu_{n}^{\prime}K_{f}^{2}&(g(B)=0).\end{cases}$

######  Corollary 6.3.

Let $f:S\to B$ be a non-locally trivial bielliptic fibration with $g\geq 17$.
Assume furthermore that the branch locus $R$ has singular points on at least
three $($resp. one$)$ fibers when $g(B)=0$ $($resp. $g(B)\geq 1$$)$.  Let $G$
be a finite subgroup of $\mathrm{Aut}(f)$. Then it holds

$\sharp G\leq\begin{cases}24\delta(2g(B)-1)K_{f}^{2}&(g(B)\geq 1),\\\ 20\delta
K_{f}^{2}&(g(B)=0).\end{cases}$

######  Corollary 6.4.

Let $f:S\to B$ be a non-locally trivial primitive cyclic covering fibration of
type $(g,1,n)$ with
$g\geq\mathrm{max}\\{\frac{30n^{2}-47n+25}{n+1},\frac{7}{2}n(n-1)+1\\}$. Put
$\mathrm{Aut}(S/B):=\\{(\kappa_{S},\mathrm{id}_{B})\in\mathrm{Aut}(f)\\}$.
Assume that the branch locus $R$ has a singular point. Then it holds

$\sharp\mathrm{Aut}(S/B)\leq\frac{6n^{2}\delta}{(n-1)(5n-4)}K_{f}^{2}.$

##  7\. Example

We construct bielliptic fibrations $f:S\to B$ with a large automorphism group.
Let $(E,O)$ be an elliptic curve with the identity element $O\in E$. The
symbol $P\oplus Q$ denotes the sum of $P$, $Q\in E$ as the group law.
Furthermore, we define

$\displaystyle[k]P:=\underbrace{P\oplus\cdots\oplus P}_{k-summands}.$

Let $e$ be a positive even number and $P$ a point of $E$ of order $e$. We
define the automorphisms of $E$ as follows:

$\displaystyle\tau_{P}:E\to E\;$ $\displaystyle;\;Q\mapsto P\oplus Q$
$\displaystyle\iota:E\to E\;$ $\displaystyle;\;Q\mapsto\ominus Q$

where $\ominus Q$ denotes the inverse element of $Q$. Let $Q_{1},Q_{2}\in E$
be distinct points such that $[2]Q_{1}=[2]Q_{2}=P$. We note that the order of
$Q_{1}$ and $Q_{2}$ is $2e$. We define divisors

$\displaystyle\mathfrak{d}_{i}$
$\displaystyle:=Q_{i}+[3]Q_{i}+\cdots+[2e-1]Q_{i}\;(i=1,2),$ $\displaystyle
R_{E}$ $\displaystyle:=\mathfrak{d}_{1}+\mathfrak{d}_{2}.$

We recall that $P\oplus Q=R$ if and only if $P+Q\sim R+O$, where the symbol
$\sim$ means the linearly equivalence. Since $e$ is even, we have
$\mathfrak{d}_{1}\sim\mathfrak{d}_{2}\sim eO$. Hence we consider a double
covering

$\displaystyle\pi:F:=\mathrm{Spec}_{E}\left(\mathcal{O}_{E}\bigoplus\mathcal{O}_{E}(-\mathfrak{d}_{1})\right)\to
E$

branched along $R_{E}\in|2\mathfrak{d}_{1}|$. Let $K_{E}$ be the automorphism
group on $E$ generated by $\tau_{P}$ and $\iota$, then $K_{E}$ has order $2e$.
Since $\mathfrak{d}_{1}$ and $R_{E}$ are $K_{E}$-stable, there exists
$\mathaccent 869{\kappa}\in\mathrm{Aut}(F)$ for any $\kappa\in K_{E}$ such
that the diagram

$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathaccent
869{\kappa}}$$\scriptstyle{\pi}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pi}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\kappa}$$\textstyle{E}$

commutes.

Put $W:=\mathbb{P}^{1}\times E$ and let $\varphi:W\to\mathbb{P}^{1}$ be the
projection. An action of $\kappa\in K_{E}$ induces the following action on
$W$:

$\kappa:W\to W\;:\;(x,y)\mapsto(x,\kappa(y))$

Thus, we can regard $K_{E}$ as a subgroup of $\mathrm{Aut}(W/\mathbb{P}^{1})$.
Let $R_{h}$ and $\mathfrak{d}_{h}$ be the pullback of $R_{E}$ and
$\mathfrak{d}_{1}$ by the natural projection $W\to E$.

We recall that the icosahedral group $I_{60}$ acts $\mathbb{P}^{1}$. We denote
by $p_{1},\cdots,p_{12}$ the $I_{60}$-orbit on $\mathbb{P}^{1}$ with length
$12$. Let $\Gamma_{i}$ be the fiber of $\varphi$ over $p_{i}$. We define the
action on $W$ for $h\in I_{60}$ as follows.

$h:W\to W\;;\;(x,y)\mapsto(h(x),y)$

Hence we define an automorphism group

$\mathaccent 869{G}:=I_{60}\times K_{E}\cong
I_{60}K_{E}\subset\mathrm{Aut}(\varphi).$

The order of $\mathaccent 869{G}$ is $120e$. We define divisors

$\mathfrak{d}:=\mathfrak{d}_{h}+\sum_{i=1}^{6}\Gamma_{i},\quad
R:=R_{h}+\sum_{i=1}^{12}\Gamma_{i}.$

Since $R_{E}$ and $2\mathfrak{d}_{1}$ are linearly equivalent, we have
$R\in|2\mathfrak{d}|$. Hence we can take a double covering

$\displaystyle\theta:S_{0}:=\mathrm{Spec}_{W}\left(\mathcal{O}_{W}\bigoplus\mathcal{O}_{W}(-\mathfrak{d})\right)\to
W$

branched along $R\in|2\mathfrak{d}|$. Let $S$ be the minimal resolution of
$S_{0}$. Then the induced fibration $f:S\to\mathbb{P}^{1}$ is a bielliptic
fibration with $g=l+1$. By the assumption of $\mathaccent 869{G}$, we have
$\kappa^{\ast}\mathfrak{d}\sim\mathfrak{d}$ and $\kappa^{\ast}R=R$. Thus, any
action $\kappa$ induces an action $\mathaccent 869{\kappa}\in\mathrm{Aut}(f)$.
Hence we can construct a subgroup $G$ of $\mathrm{Aut}(f)$ generated by
$\mathaccent 869{\kappa}$’s and the covering transformation. Then $G$ is a
finite subgroup with $\sharp G\geq 240e$.

On the other hand, we have

$K_{f}^{2}(\Gamma_{i})=2e.$

since $R$ has $e$ ordinary double points on each $\Gamma_{i}$. Thus, we have
$K_{f}^{2}=24e$ and it holds that $\sharp G\geq 10K_{f}^{2}$.

## References

  * [1] H. Akaike, Bounds for the order of automorphism groups of cyclic covering fibrations of a ruled surface, arxiv:2011.03000v3[math.AG].
  * [2] T. Arakawa, Bounds for the order of automorphism groups of hyperelliptic fibrations, Tôhoku. Math. J. 50 (1998), 317–323.
  * [3] M. A. Barja, On the slope of bielliptic fibrations, Proc. Amer. Math. Soc. 129 (2001), 1899–1906.
  * [4] Z. Chen, Best bounds of automorphism groups of hyperelliptic fibrations, Tôhoku. Math. J. 50 (1998), 469–489.
  * [5] M. Enokizono, Slopes of fibered surfaces with a finite cyclic automorphism, Michigan Math. J. 66 (2017), 125–154.
  * [6] M. Enokizono, Upper bounds on the slope of certain fibered surfaces, J. Math. Soc. Japan. Advance Publication (2022), 1–51, https://doi.org/10.2969/jmsj/86278627
  * [7] K. Kodaira, On compact analytic surfaces I, Ann. of Math. 71 (1960), 111–152; II, ibid. 77 (1963), 563–626; III, ibid. 78 (1963), 1–40.
  * [8] K. Konno, A lower bound of the slope of trigonal fibrations, Intern. J. Math. 7 (1996), 19–27.
  * [9] R. Miranda and U. Persson, Torsion groups of elliptic surfaces, Compositio Math 72 (1989), 249–267.
  * [10] G. Xiao, Bound of automorphism of surfaces of general type, I, Ann. of Math. 139 (1994), 51–77.
  * [11] G. Xiao, Bound of automorphism of surfaces of general type, II, J.Algebraic Geom. 4 (1995), 701–793.

Hiroto Akaike

Department of Mathematics, Graduate School of Science, Osaka University,

1-1 Machikaneyama, Toyonaka, Osaka 560-0043, Japan

e-mail<EMAIL_ADDRESS>


# Pb-Hash: Partitioned b-bit Hashing

Ping Li, Weijie Zhao

LinkedIn Ads
700 Bellevue Way NE, Bellevue, WA 98004, USA
<EMAIL_ADDRESS>
###### Abstract

Many hashing algorithms including minwise hashing (MinHash), one permutation
hashing (OPH), and consistent weighted sampling (CWS) generate integers of $B$
bits. With $k$ hashes for each data vector, the storage would be $B\times k$
bits; and when used for large-scale learning, the model size would be
$2^{B}\times k$, which can be expensive. A standard strategy is to use only
the lowest $b$ bits out of the $B$ bits and somewhat increase $k$, the number
of hashes. In this study, we propose to re-use the hashes by partitioning the
$B$ bits into $m$ chunks, e.g., $b\times m=B$. Correspondingly, the model size
becomes $m\times 2^{b}\times k$, which can be substantially smaller than the
original $2^{B}\times k$.

There are multiple reasons why the proposed “partitioned b-bit hashing” (Pb-
Hash) can be desirable: (1) Generating hashes can be expensive for industrial-
scale systems especially for many user-facing applications. Thus, engineers
may hope to make use of each hash as much as possible, instead of generating
more hashes (i.e., by increasing the $k$). (2) To protect user privacy, the
hashes might be artificially “polluted” and the differential privacy (DP)
budget is proportional to $k$. (3) After hashing, the original data are not
necessarily stored and hence it might not be even possible to generate more
hashes. (4) One special scenario is that we can also apply Pb-Hash to the
original categorical (ID) features, not just limited to hashed data.

Our theoretical analysis reveals that by partitioning the hash values into $m$
chunks, the accuracy would drop. In other words, using $m$ chunks of $B/m$
bits would not be as accurate as directly using $B$ bits. This is due to the
correlation from re-using the same hash. On the other hand, our analysis also
shows that the accuracy would not drop much for (e.g.,) $m=2\sim 4$. In some
regions, Pb-Hash still works well even for $m$ much larger than 4. We expect
Pb-Hash would be a good addition to the family of hashing methods/applications
and benefit industrial practitioners.

We verify the effectiveness of Pb-Hash in machine learning tasks, for linear
SVM models as well as deep learning models. Since the hashed data are
essentially categorical (ID) features, we follow the standard practice of
using embedding tables for each hash. With Pb-Hash, we need to design an
effective strategy to combine $m$ embeddings. Our study provides an empirical
evaluation on four pooling schemes: concatenation, max pooling, mean pooling,
and product pooling. There is no definite answer which pooling would be always
better and we leave that for future study.

##  1 Introduction

In this paper, we focus on effectively re-using hashes and developing the
theory to explain some of the interesting empirical observations. Typically,
for each data vector, applying some hashing method $k$ times generates $k$
integers of $B$ bits, where $B$ can be (very) large. For example, with the
celebrated minwise hashing (Broder, 1997; Broder et al., 1997, 1998; Li and
Church, 2005; Li and König, 2010), we generate a permutation of length $D$,
where $D$ is the data dimension, and apply the same permutation to all data
vectors (which are assumed to be binary). For each data vector, the location
of the first non-zero entry after the permutation is the hashed value. Then we
repeat the permutation process $k$ times to generate $k$ hash values for each
data vector. For vector $u$, we denote its $k$ hashes as $h_{j}(u)$,
$j=1,2,...,k$. For vector $v$, we similarly have $h_{j}(v)$. It is known that
the collision probability is $Pr(h_{j}(u)=h_{j}(v))=J$, where for minwise
hashing $J$ is the Jaccard similarity between two binary vectors $u$ and $v$,
i.e., $J=\frac{\sum_{i=1}^{D}1\\{u_{i}\neq 0\text{ and }v_{i}\neq
0\\}}{\sum_{i=1}^{D}1\\{u_{i}\neq 0\text{ or }v_{i}\neq 0\\}}$.

When we use (e.g.,) minwise hashes for building machine learning models, we
need to treat the hash values as categorical features and expand them as one-
hot representations. For example, if $D=4$, then the minwise hash values are
between 0 and 3. Supposed $k=3$ hashes are {3, 1, 2}, we will encode them as a
$2^{2}\times 3=12$-dimensional binary vector: $[1,0,0,0,\ 0,0,1,0,\ 0,1,0,0]$
as the feature vector fed to the model. Let $D=2^{B}$. This scheme can easily
generate extremely high-dimensional data vectors and excessively large model
sizes. A common strategy is to only use the lowest $b$ bits for each hash
value, a method called “b-bit minwise hashing” (Li and König, 2010). It can be
a drastic reduction from $2^{B}$ is $2^{b}$, for example, $B=32$ and $b=10$.
Typically, we will have to increase $k$ the number of hashes to compensate the
loss of accuracy due to the use of only $b$ bits.

###  1.1 Collision Probability of $b$-bit Hashing and the Basic Assumption

Denote $h_{j}^{(b)}(u)$ and $h_{j}^{(b)}(v)$ as the lowest $b$ bits of
$h_{j}(u)$ and $h_{j}(v)$, respectively. Theorem 1 describes the collision
probability of minwise hashing $Pr\left(h_{j}^{(b)}(u)=h_{j}^{(b)}(v)\right)$
by assuming $D=2^{B}$ is large.

######  Theorem 1.

(Li and König, 2010) $Pr\left(h_{j}(u)=h_{j}(v)\right)=J$ is the collision
probability of minwise hashing. Assume $D$ is large. Denote
$f_{1}=\sum_{i=1}^{D}1\\{u_{i}\neq 0\\}$, $f_{2}=\sum_{i=1}^{D}1\\{v_{i}\neq
0\\}$. Then

$\displaystyle
P_{b}=Pr\left(h_{j}^{(b)}(u)=h_{j}^{(b)}(v)\right)=C_{1,b}+(1-C_{2,b})J$ (1)

where

$\displaystyle
C_{1,b}=A_{1,b}\frac{r_{2}}{r_{1}+r_{2}}+A_{2,b}\frac{r_{1}}{r_{1}+r_{2}},\hskip
14.45377ptC_{2,b}=A_{1,b}\frac{r_{1}}{r_{1}+r_{2}}+A_{2,b}\frac{r_{2}}{r_{1}+r_{2}},$
$\displaystyle
A_{1,b}=\frac{r_{1}[1-r_{1}]^{2^{b}-1}}{1-[1-r_{1}]^{2^{b}}},\hskip
14.45377ptA_{2,b}=\frac{r_{2}[1-r_{2}]^{2^{b}-1}}{1-[1-r_{2}]^{2^{b}}},\hskip
14.45377ptr_{1}=\frac{f_{1}}{D},\hskip 14.45377ptr_{2}=\frac{f_{2}}{D}$

The result in Theorem 1 was obtained via conducting careful and tedious
summations of the individual probability terms. Interestingly, if
$r_{1},r_{2}\rightarrow 0$, then $A_{1,b}=A_{2,b}=\lim_{r\rightarrow
0}\frac{r[1-r]^{2^{b}-1}}{1-[1-r2^{b}]}=\frac{1}{2^{b}}$,
$C_{1,b}=C_{2,b}=\frac{1}{2^{b}}$ and
$P_{b}=\frac{1}{2^{b}}+\left(1-\frac{1}{2^{b}}\right)J=J+\left(1-J\right)\frac{1}{2^{b}}$.
This (much) simplified probability has an intuitive interpretation using
(approximate) conditional probabilities: $h_{j}(u)=h_{j}(v)$ with probability
$J$. If $h_{j}(u)\neq h_{j}(v)$ (which occurs with probability $(1-J)$, there
is still a roughly $\frac{1}{2^{b}}$ probability to have
$h_{j}^{(b)}(u)=h_{j}^{(b)}(v)$, because the space is of size $2^{b}$. In
fact, one can also resort to the commonly used “re-hash” idea to explicitly
map $h_{j}(u)$ uniformly into $[0,1,2,...,2^{b}-1]$.

Therefore, in this paper, we make the following basic assumption:

Basic Assumption: Apply the hash function $h$ to two data vectors $u$ and $v$
to obtain $h(u)$ and $h(v)$, respectively, where $h(.)\in[0,1,2,...,2^{B}-1]$.
The collision probability is $Pr\left(h(u)=h(v)\right)=J$. $h^{(b)}(u)$ and
$h^{(b)}(v)$ denote the values by taking $b$ bits of $h(u)$ and $h(v)$,
respectively, with

$\displaystyle
P_{b}=Pr\left(h^{(b)}(u)=h^{(b)}(v)\right)=c_{b}+(1-c_{b})J,\hskip
14.45377ptc_{b}=\frac{1}{2^{b}}$ (2)

We call it an “assumption” because, when the original space is large, the “re-
hash” trick typically can only be done approximately, for example, through
universal hashing (Carter and Wegman, 1977). There is also an obvious
“descrepancy” that, in (2), we actually need $b\rightarrow\infty$ in order to
have $Pr\left(h^{(b)}(u)=h^{(b)}(v)\right)=J$. But here for simplicity we just
assume that, when $b=B$, we have $Pr\left(h^{(B)}(u)=h^{(B)}(v)\right)=J$.
Because $B$ is typically large, we do not worry much about the discrepancy.
Otherwise the analysis would be too complicated, just like Theorem 1.

The basic assumption (2) allows us to derive a simple unbiased estimator of
the basic similarity $J$:

$\displaystyle\hat{J}_{b}=\frac{\hat{P}_{b}-c_{b}}{1-c_{b}},\hskip
14.45377ptVar\left(\hat{J}_{b}\right)=\frac{Var(\hat{P}_{b})}{(1-c_{b})^{2}}=\frac{P_{b}(1-P_{b})}{(1-c_{b})^{2}}.$
(3)

where the variance $Var\left(\hat{J}_{b}\right)$ assumes only one sample,
because the sample size $k$ will usually be canceled out in the comparison.
When $b=B$, the variance of $\hat{J}$ would be simply $J(1-J)$, i.e., the
variance of the Bernoulli trial. We can compute the ratio of the variances to
assess the loss of accuracy due to taking only $b$ bits:

$\displaystyle
R_{b}=\frac{Var(\hat{J}_{b})}{Var(\hat{J})}=\frac{P_{b}(1-P_{b})}{(1-c_{b})^{2}}\frac{1}{J(1-J)}=1+\frac{c_{b}}{1-c_{b}}\frac{1}{J}=1+\frac{1}{(2^{b}-1)J}$
(4)

Here $R_{b}$ (where $R_{b}\rightarrow\infty$ as $J\rightarrow 0$) can be
viewed as the multiplier needed for increasing the sample size by using only
$b$ bits. In real-world applications, typically only a tiny fraction of data
vector pairs have relatively large similarity ($J$) values. For the majority
of the pairs, the $J$ values are very small. For example, when $J=0.1$ and
$b=1$, we have $R_{b}=11$. In other words, if we keep only 1 bit per hash and
increase the number of hashes by a factor of 11, then the variance would
remain the same.

###  1.2 Motivations for Re-using Hashes and Pb-Hash: Partitioned b-bit
Hashing

Instead of using fewer bits and generating more hashes, in this paper, we
study the strategy of re-using the hashes. The idea is simple. For a $B$-bit
hash value, we break the bits into $m$ chunks: $b_{1}$, $b_{2}$, $...$,
$b_{m}$ with $\sum_{i=1}^{m}b_{i}=B$. It is often convenient to simply let
$b_{1}=b_{2}=...=b_{m}=b$ and $m\times b=B$. The dimensionality is
(substantially) reduced from $2^{B}$ to $m\times 2^{b}$. In many scenarios,
this strategy can be desirable. In industrial large-scale systems, the cost
for generating hashes can often be considerable especially for serving (for
example, in many user-facing applications). Thus, it is always desired if we
can generate fewer hashes for better efficiency. From the perspective of
privacy protection, it is also crucial to reduce $k$ the number of hashes,
because typically the needed privacy budget “$\epsilon$” (in the
$(\epsilon,\delta)$-DP language (Dwork et al., 2006)) is proportional to $k$.
There is another strong motivation in that we may not be able to generate more
hashes in some situations. For example, in some applications, the original
data are not necessarily stored after hashing.

Interestingly, we can also directly apply the Pb-Hash idea to the original
categorical (ID) features. In large-scale recommender systems (Fan et al.,
2019; Zhao et al., 2019; Shi et al., 2020), the use of ID features is
dominating. For companies which do not have infrastructure to handle ID
features of billion or even just million categories, they can apply Ph-Hash to
reduce the model dimensions.

Figure 1: An visual illustration for the embedding table lookup and Pb-Hash
lookup.

Figure 1 is an illustration of the idea of Pb-Hash with training for large ID
data. Basically, we can first apply a random permutation on the IDs, then
break the bits into $m$ chunks so that one can substantially reduce the
embedding size, for example, from the original size of $2^{B}$ to $m\times
2^{b}$ with $B=m\times b$. The number of parameters will be substantially
reduced. We will need a strategy to merge these $m$ embedding tables. The
obvious choices are concatenation, mean, max, and product. Note that for this
application, our Pb-Hash includes the so-called “QR-hash” (Shi et al., 2020)
as a special case (which uses $m=2$).

##  2 Theoretical Analysis of Pb-Hash

Recall the Basic Assumption:
$P_{b}=Pr\left(h^{(b)}(u)=h^{(b)}(v)\right)=c_{b}+(1-c_{b})J$,
$c_{b}=\frac{1}{2^{b}}$. With Pb-Hash, the basic idea is to break the total
$B$ bits into $m$ chunks. Let $\sum_{i=1}^{m}b_{i}=B$, and later we can assume
$b_{1}=b_{2}=...=b_{m}$ to simplify the expressions. Then, we have the
following expectations:

$\displaystyle E\left(\hat{P}_{b_{i}}\right)=c_{b_{i}}+(1-c_{b_{i}})J$ (5)
$\displaystyle
E\left(\sum_{i=1}^{m}\hat{P}_{b_{i}}\right)=\sum_{i=1}^{m}c_{b_{i}}+J\sum_{i=1}^{m}(1-c_{b_{i}}).$
(6)

which allows us to write down an unbiased estimator of $J$:

$\displaystyle\hat{J}_{m}=\frac{\sum_{i=1}^{m}\hat{P}_{b_{i}}}{\sum_{i=1}^{m}(1-c_{b_{i}})}-\frac{\sum_{i=1}^{m}c_{b_{i}}}{\sum_{i=1}^{m}(1-c_{b_{i}})}.$
(7)

######  Theorem 2.

$\displaystyle E\left(\hat{J}_{m}\right)=J,$ (8) $\displaystyle
Var\left(\hat{J}_{m}\right)=\frac{\sum_{i=1}^{m}P_{b_{i}}(1-P_{b_{i}})+\sum_{i\neq
i^{\prime}}\left(P_{b_{i}+b_{i^{\prime}}}-P_{b_{i}}P_{b_{i^{\prime}}}\right)}{\left(\sum_{i=1}^{m}(1-c_{b_{i}})\right)^{2}}.$
(9) where $\displaystyle c_{b_{i}}=\frac{1}{2^{b_{i}}},\hskip
7.22743ptP_{b_{i}}=c_{b_{i}}+(1-c_{b_{i}})J,\hskip
7.22743ptP_{b_{i}+b_{i^{\prime}}}=c_{b_{i}+b_{i^{\prime}}}+(1-c_{b_{i}+b_{i^{\prime}}})J$
(10)

Proof of Theorem 2. Firstly, it is easy to show that

$\displaystyle E\left(\hat{J}_{m}\right)=J,\hskip
14.45377ptVar\left(\hat{J}_{m}\right)=Var\left(\sum_{i=1}^{m}\hat{P}_{b_{i}}\right)/\left(\sum_{i=1}^{m}(1-c_{b_{i}})\right)^{2}.$

Then we expand the variance of the sum:

$\displaystyle Var\left(\sum_{i=1}^{m}\hat{P}_{b_{i}}\right)=$
$\displaystyle\sum_{i=1}^{m}Var\left(\hat{P}_{b_{i}}\right)+\sum_{i\neq
i^{\prime}}Cov\left(\hat{P}_{b_{i}},\hat{P}_{b_{i^{\prime}}}\right)$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{m}P_{b_{i}}(1-P_{b_{i}})+\sum_{i\neq
i^{\prime}}\left(P_{b_{i}+b_{i^{\prime}}}-P_{b_{i}}P_{b_{i^{\prime}}}\right).$

Here we have used the Basic Assumption. $\Box$

The key in the analysis of Pb-Hash is the covariance term
$Cov\left(\hat{P}_{b_{i}},\hat{P}_{b_{i^{\prime}}}\right)$, which in the
independence case would be just zero. With Pb-Hash, however, the covariance is
always non-negative. This is the reason why the accuracy of using $m$ chunks
of $b$-bits from the same hash value would not be as good as using $m$
independent $b$-bits (i.e., $m$ independent hashes).

######  Lemma 3.

$\displaystyle P_{b_{1}+b_{2}}-P_{b_{1}}P_{b_{2}}\geq 0$ (11)

is a concave function in $J\in[0,1]$. Its maximum is
$\frac{1}{4}\left(1-\frac{1}{2^{b_{1}}}\right)\left(1-\frac{1}{2^{b_{2}}}\right)$,
attained at $J=1/2$.

Proof of Lemma 3

$\displaystyle f(J)=P_{b_{1}+b_{2}}-P_{b_{1}}P_{b_{2}}=$ $\displaystyle
J+(1-J)\frac{1}{2^{b_{1}+b_{2}}}-\left(J+(1-J)\frac{1}{2^{b_{1}}}\right)\left(J+(1-J)\frac{1}{2^{b_{2}}}\right)$
$\displaystyle
f^{\prime\prime}(J)=-\left(1-\frac{1}{2^{b_{1}}}\right)\left(1-\frac{1}{2^{b_{2}}}\right)\leq
0$

This means that $f(J)$ is a concave function in $J\in[0,1]$. Also, we have

$\displaystyle
f(0)=\frac{1}{2^{b_{1}+b_{2}}}-\frac{1}{2^{b_{1}}}\frac{1}{2^{b_{2}}}=0,\hskip
14.45377ptf(1)=1-1=0$

Therefore, we must have $f(J)\geq 0$. Furthermore, by setting
$f^{\prime}(J)=0$, we can see that the maximum value of $f(J)$ is attained at
$J=1/2$. $\hfill\qed$

Figure 2 verifies the results in Lemma 3, with $P_{2b}-P_{b}^{2}$ (left panel)
and $P_{2b}-P_{1}P_{2b-1}$ (right panel). It is interesting that in both
cases, the maximums are attained at $J=1/2$, as predicted.

Figure 2: Plots to verify Lemma 3 that $P_{b_{1}+b_{2}}-P_{b_{1}}P_{b_{2}}\geq
0$. Left panel: $P_{2b}-P_{b}^{2}$. Right panel: $P_{2b}-P_{1}P_{2b-1}$. It is
interesting that in both cases, the maximums are attained at $J=1/2$.

To simplify the expression and better visualize the results, we consider
$b_{1}=b_{2}=...=b_{m}=b$ and $b\times m=B$. Then we have

$\displaystyle\hat{J}_{m}=\frac{\sum_{i=1}^{m}\hat{P}_{b_{i}}}{m(1-c_{b})}-\frac{c_{b}}{1-c_{b}},$
(12)

and

$\displaystyle
Var\left(\hat{J}_{m}\right)=\frac{P_{b}(1-P_{b})+(m-1)\left(P_{2b}-P_{b}^{2}\right)}{m(1-c_{b})^{2}}=\frac{1}{m}\frac{P_{b}(1-P_{b})}{(1-c_{b})^{2}}+\frac{m-1}{m}\frac{P_{2b}-P_{b}^{2}}{(1-c_{b})^{2}}.$
(13)

We can again compare the variance of $Var\left(\hat{J}_{m}\right)$ with,
$J(1-J$), which is the variance of $\hat{J}$ using all the bits:

$\displaystyle
R_{m,b}=\frac{Var\left(\hat{J}_{m}\right)}{J(1-J)}=\frac{P_{b}(1-P_{b})+(m-1)\left(P_{2b}-P_{b}^{2}\right)}{m(1-c_{b})^{2}J(1-J)},\hskip
7.22743ptm\times b=B.$ (14)

When $R_{m,b}$ is close to 1, it means that Pb-Hash does not lose accuracy as
much. Recall that, if we have hashed values for building learning models, the
model size is $2^{B}\times k$, where $k$ is the number of hashes. By Pb-Hash,
we can (substantially) reduce the model size to be $m\times 2^{b}\times k$. In
practice, the ID features can have very high cardinality, for example, a
million (i.e., $B=20$) or billion (i.e., $B=30$). Figure 3 implies that, as
long as $B$ is not too small, we do not expect a significant loss of accuracy
if $m=2\sim 4$.

Figure 3: Plots for $B\in\\{30,24,18,12\\}$ to illustrate the variance ratio
$R_{m,b}$ in (14).

##  3 Applications and Experiments

Recall that in our Basic Assumption, we have not specified which particular
hashing method is used. For the applications and experiments, we focus on
minwise hashing (MinHash) for binary (0/1) data, and consistent weighted
sampling (CWS) for general non-negative data.

###  3.1 Minwise Hashing (MinHash) on Binary (0/1) Data

The binary Jaccard similarity, also known as the “resemblance”, is a
similarity metric widely used in machine learning and web applications. It is
defined for two binary (0/1) data vectors, denoted as $u$ and $v$, where each
vector belongs to the set $\\{0,1\\}^{D}$. The Jaccard similarity is
calculated as:

$J(u,v)=\frac{\sum_{i=1}^{D}1\\{u_{i}=v_{i}=1\\}}{\sum_{i=1}^{D}1\\{u_{i}+v_{i}\geq
1\\}}.$ (15)

In this context, the vectors $u$ and $v$ can be interpreted as sets of items,
represented by the positions of non-zero entries. However, computing pairwise
Jaccard similarity becomes computationally expensive as the data size
increases in industrial applications with massive datasets. To address this
challenge and enable large-scale search and learning, the “minwise hashing”
(MinHash) algorithm is introduced (Broder, 1997; Broder et al., 1997, 1998; Li
and Church, 2005; Li and König, 2010) as a standard hashing technique for
approximating the Jaccard similarity in massive binary datasets. MinHash has
found applications in various domains, including near neighbor search,
duplicate detection, malware detection, clustering, large-scale learning,
social networks, and computer vision (Charikar, 2002; Fetterly et al., 2003;
Das et al., 2007; Buehrer and Chellapilla, 2008; Bendersky and Croft, 2009;
Chierichetti et al., 2009; Pandey et al., 2009; Lee et al., 2010; Deng et al.,
2012; Chum and Matas, 2012; He et al., 2013; Tamersoy et al., 2014;
Shrivastava and Li, 2014; Zhu et al., 2017; Nargesian et al., 2018; Wang et
al., 2019; Lemiesz, 2021; Feng and Deng, 2021; Jia et al., 2021).

MinHash produces integer outputs. For efficient storage and utilization of the
hash values in large-scale applications, Li and König (2010) proposed a
variant called “$b$-bit MinHash”. This method only retains the lowest $b$ bits
of the hashed integers, providing a memory-efficient and convenient approach
for similarity search and machine learning tasks. Over the years, $b$-bit
MinHash has become the standard implementation of MinHash (Li et al., 2011,
2015; Shah and Meinshausen, 2017; Yu and Weber, 2022). Additionally, we should
mention “circulant MinHash” (C-MinHash) (Li and Li, 2022). C-MinHash employs a
single circular permutation, which enhances hashing efficiency and perhaps
surprisingly improves estimation accuracy. Figure 4 depicts the use case of
Pb-Hash on minwise hashing, for verifying the theoretical results in Theorem
2.

Figure 4: We use the “Words” dataset (Li and Church, 2005). The vector,
denoted by “UNITED”, stores whether each of $D=2^{16}$ documents contains the
word “UNITED”. We use minwise hashing to estimate the Jaccard similarity
between the word-pair, e.g., “UNITED–STATES”, with $k=1$ to $1000$ hashes. For
each hash, we apply Pb-Hash with $m\in\\{1,2,4,8,16\\}$. We simulate each case
$10^{4}$ times in order to reliably estimate the biases and variances. The
left upper panel plots the biases for each $m$ and $k$. The biases are very
small (and the bias2, which will be on the scale as the variance, will be much
smaller.). For “UNITED–STATES”, the variance curves all overlap in the right
upper panel. Thus, we zoom in the plot and present the much magnified portion
in the right bottom panel. We can see that, even at such as fine scale, the
theoretical variances match the empirical simulations very well. In the left
bottom panel, we provide the variance curves on another word-pair “LOW–PAY”.
Again, the empirical and theoretical curves match quite well. These
experiments verify the accuracy of Theorem 2, even though it was based on the
“Basic Assumption”.

###  3.2 Consistent Weighted Sampling (CWS) and Linear SVM

MinHash and OPH are techniques designed to process binary data, representing
unweighted sets. In the literature, to tackle the real-valued data (weighted
sets), the weighted Jaccard similarity is defined as follows:

$\displaystyle
J(u,v)=\frac{\sum_{i=1}^{D}\min\\{u_{i},v_{i}\\}}{\sum_{i=1}^{D}\max\\{u_{i},v_{i}\\}},$

where $u,v\in\mathbb{R}_{+}^{D}$ are two non-negative data vectors. In
contrast to binary data, weighted data often carries more detailed
information. Consequently, the weighted Jaccard similarity measure has
garnered significant attention and has been extensively studied and applied
across various domains, such as theory, databases, machine learning, and
information retrieval (Kleinberg and Tardos, 1999; Charikar, 2002; Fetterly et
al., 2003; Gollapudi and Sharma, 2009; Bollegala et al., 2011; Delgado et al.,
2014; Schubert et al., 2014; Wang et al., 2014; Fu et al., 2015; Pewny et al.,
2015; Manzoor et al., 2016; Raff and Nicholas, 2017; Tymoshenko and Moschitti,
2018; Bag et al., 2019; Pouget-Abadie et al., 2019; Yang et al., 2019; Zhu et
al., 2019; Fuchs et al., 2020; Lei et al., 2020; Li et al., 2022; Zheng et
al., 2023). This extended similarity metric enables the analysis and
comparison of weighted sets, facilitating a deeper understanding of the
underlying data. ChatGPT The weighted Jaccard similarity has emerged as a
potential non-linear kernel, especially in the realm of large-scale
classification and regression tasks (Li, 2017). It has been demonstrated to
surpass the widely used RBF (Radial Basis Function) kernel in terms of
performance across numerous tasks and datasets. The weighted Jaccard
similarity’s ability to capture intricate relationships within the datasets it
is applied to makes it a promising choice for achieving superior results in
various machine learning applications.

In line with this, several large-scale hashing algorithms have been developed
to efficiently estimate or approximate the weighted Jaccard similarity. A
series of studies (Kleinberg and Tardos, 1999; Charikar, 2002; Shrivastava,
2016; Ertl, 2018; Li and Li, 2021) have proposed and refined hashing
algorithms based on the rejection sampling technique, which proves to be
efficient for dense data vectors. Furthermore, researchers such as Gollapudi
and Panigrahy (2006); Manasse et al. (2010); Ioffe (2010) have introduced
consistent weighted sampling (CWS), offering a complexity of $O(Kf)$ similar
to that of MinHash. CWS operates effectively on relatively sparse data. To
improve upon these methods, Li et al. (2021) presented Extremal Sampling (ES)
based on the extremal stochastic process. Moreover, Li et al. (2019) extended
the concept of “binning + densification” from OPH to CWS and proposed Bin-wise
Consistent Weighted Sampling (BCWS) with a complexity of $O(f)$. BCWS provides
a significant speedup of approximately $K$-fold compared to standard CWS.
These advancements in large-scale hashing algorithms facilitate efficient
computations and estimations of the weighted Jaccard similarity for diverse
datasets. We report the results of Pb-Hash on CWS in Figure 5 and Figure 6.

Figure 5: For the “WebspamN1” dataset (a character 1-gram dataset), we apply
CWS and keep $B=8$ bits for each hash value. We choose $b\in\\{1,2,4,8\\}$ to
run the linear SVM classifier. The left panel shows that when $b=1$ and $b=2$,
we observe a substantial loss of accuracy. In the right panel, we zoom in to
show the Pb-Hash results (i.e., dashed curves). We can see that $m=2$ and
$m=4$ barely lose any accuracy ($m=2$ is slightly better than $m=4$).

Figure 6: For the “Dailysports” dataset, we apply CWS and keep $B=12$ bits for
each hash value. We choose $b\in\\{1,2,3,4,6,12\\}$ to run the linear SVM
classifier. The left panel shows that when $b=1$ and $b=2$, we observe a
substantial loss of accuracy. In the right panel, we zoom in to show the Pb-
Hash results (i.e., dashed curves). We can see with $m=2\sim 4$ the loss of
accuracy is small.

###  3.3 CWS and Neural Nets

Next we conduct experiments with using CWS hashes for training neural nets. We
first break the hash bits into $m$ chunks (for $m=1,2,4,8$). For each chunk,
we connect it with an embedding of size 16. We can simply concatenate all $m$
embeddings, but to reduce the number of parameters and speed up training, we
experiment 3 other pooling options: product (“Prod”), mean (”Mean”), and
maximum (“Max”). Figure 7 presents the experimental results.

Figure 7: For the “Webspam” (3-gram) dataset, we apply CWS and keep $B=16$
bits for each hash value. For every hash, we apply Pb-Hash with
$m\in\\{1,2,4,8\\}$. We connect every (sub)-hash to an embedding of size $16$.
Next we aggregate $m$ embeddings via four different pooling strategies:
concatenate, mean, product, and max. Then we connect the pooled embeddings
with one hidden layer of size 256.

##  4 Conclusion

The idea of Pb-Hash, i.e., breaking the bits of one hash value into $m$
chunks, is a very natural one after the work on $b$-bit minwise hashing (Li
and König, 2010). At that time, Pb-Hash did not seem to have obvious
advantages compared to $b$-bit hashing, because re-generating independent
hashes would be always more accurate than re-using the hashes. In recent
years, because of the privacy constraint (Li and Li, 2023), we have started to
realize the importance of re-using the hashes. Furthermore, with hashing
algorithms used in deep neural nets, the hashed value (i.e., new ID features)
is typically connected to an embedding layer and hence there is a strong
motivation to break the hash bits into chunks to reduce the embedding size.
Also, it is natural to apply Pb-Hash to the original ID features (not the new
features obtained via hashing).

## References

  * Bag et al. [2019] Sujoy Bag, Sri Krishna Kumar, and Manoj Kumar Tiwari.  An efficient recommendation generation using relevant Jaccard similarity.  _Information Sciences_ , 483:53–64, 2019.
  * Bendersky and Croft [2009] Michael Bendersky and W. Bruce Croft.  Finding text reuse on the web.  In _Proceedings of the Second International Conference on Web Search and Web Data Mining (WSDM)_ , pages 262–271, Barcelona, Spain, 2009.
  * Bollegala et al. [2011] Danushka Bollegala, Yutaka Matsuo, and Mitsuru Ishizuka.  A web search engine-based approach to measure semantic similarity between words.  _IEEE Trans. Knowl. Data Eng._ , 23(7):977–990, 2011.
  * Broder [1997] Andrei Z Broder.  On the resemblance and containment of documents.  In _Proceedings of the Compression and Complexity of Sequences (SEQUENCES)_ , pages 21–29, Salerno, Italy, 1997.
  * Broder et al. [1997] Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, and Geoffrey Zweig.  Syntactic clustering of the web.  _Comput. Networks_ , 29(8-13):1157–1166, 1997\.
  * Broder et al. [1998] Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher.  Min-wise independent permutations.  In _Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC)_ , pages 327–336, Dallas, TX, 1998.
  * Buehrer and Chellapilla [2008] Gregory Buehrer and Kumar Chellapilla.  A scalable pattern mining approach to web graph compression with communities.  In _Proceedings of the International Conference on Web Search and Web Data Mining (WSDM)_ , pages 95–106, Stanford, CA, 2008.
  * Carter and Wegman [1977] Larry Carter and Mark N. Wegman.  Universal classes of hash functions (extended abstract).  In _Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC)_ , pages 106–112, Boulder, CO, 1977.
  * Charikar [2002] Moses S Charikar.  Similarity estimation techniques from rounding algorithms.  In _Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing (STOC)_ , pages 380–388, Montreal, Canada, 2002.
  * Chierichetti et al. [2009] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Panconesi, and Prabhakar Raghavan.  On compressing social networks.  In _Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 219–228, Paris, France, 2009.
  * Chum and Matas [2012] Ondrej Chum and Jiri Matas.  Fast computation of min-hash signatures for image collections.  In _Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 3077–3084, Providence, RI, 2012.
  * Das et al. [2007] Abhinandan Das, Mayur Datar, Ashutosh Garg, and Shyamsundar Rajaram.  Google news personalization: scalable online collaborative filtering.  In _Proceedings of the 16th International Conference on World Wide Web (WWW)_ , pages 271–280, Banff, Alberta, Canada, 2007.
  * Delgado et al. [2014] Agustín D. Delgado, Raquel Martínez-Unanue, Víctor Fresno-Fernández, and Soto Montalvo.  A data driven approach for person name disambiguation in web search results.  In _Proceedings of the 25th International Conference on Computational Linguistics (COLING)_ , pages 301–310, Dublin, Ireland, 2014.
  * Deng et al. [2012] Fan Deng, Stefan Siersdorfer, and Sergej Zerr.  Efficient jaccard-based diversity analysis of large document collections.  In _Proceedings of the 21st ACM International Conference on Information and Knowledge Management (CIKM)_ , pages 1402–1411, Maui, HI, 2012\.
  * Dwork et al. [2006] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith.  Calibrating noise to sensitivity in private data analysis.  In _Proceedings of the Third Theory of Cryptography Conference (TCC)_ , pages 265–284, New York, NY, 2006.
  * Ertl [2018] Otmar Ertl.  BagMinHash - minwise hashing algorithm for weighted sets.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD)_, pages 1368–1377, London, UK, 2018.
  * Fan et al. [2019] Miao Fan, Jiacheng Guo, Shuai Zhu, Shuo Miao, Mingming Sun, and Ping Li.  MOBIUS: towards the next generation of query-ad matching in baidu’s sponsored search.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD)_, pages 2509–2517, Anchorage, AK, 2019.
  * Feng and Deng [2021] Weiqi Feng and Dong Deng.  Allign: Aligning all-pair near-duplicate passages in long texts.  In _Proceedings of the International Conference on Management of Data (SIGMOD)_ , pages 541–553, Virtual Event, China, 2021.
  * Fetterly et al. [2003] Dennis Fetterly, Mark Manasse, Marc Najork, and Janet L. Wiener.  A large-scale study of the evolution of web pages.  In _Proceedings of the Twelfth International World Wide Web Conference (WWW)_ , pages 669–678, Budapest, Hungary, 2003.
  * Fu et al. [2015] Min Fu, Dan Feng, Yu Hua, Xubin He, Zuoning Chen, Wen Xia, Yucheng Zhang, and Yujuan Tan.  Design tradeoffs for data deduplication performance in backup workloads.  In _Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST)_ , pages 331–344, Santa Clara, CA, 2015.
  * Fuchs et al. [2020] Gilad Fuchs, Yoni Acriche, Idan Hasson, and Pavel Petrov.  Intent-driven similarity in e-commerce listings.  In _Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM)_ , pages 2437–2444, Virtual Event, Ireland, 2020.
  * Gollapudi and Panigrahy [2006] Sreenivas Gollapudi and Rina Panigrahy.  Exploiting asymmetry in hierarchical topic extraction.  In _Proceedings of the 2006 ACM CIKM International Conference on Information and Knowledge Management (CIKM)_ , pages 475–482, Arlington, VA, 2006.
  * Gollapudi and Sharma [2009] Sreenivas Gollapudi and Aneesh Sharma.  An axiomatic approach for result diversification.  In _Proceedings of the 18th International Conference on World Wide Web (WWW)_ , pages 381–390, Madrid, Spain, 2009.
  * He et al. [2013] Kaiming He, Fang Wen, and Jian Sun.  K-means hashing: An affinity-preserving quantization method for learning binary compact codes.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2938–2945, 2013.
  * Ioffe [2010] Sergey Ioffe.  Improved consistent sampling, weighted minhash and L1 sketching.  In _Proceedings of the 10th IEEE International Conference on Data Mining (ICDM)_ , pages 246–255, Sydney, Australia, 2010.
  * Jia et al. [2021] Peng Jia, Pinghui Wang, Junzhou Zhao, Shuo Zhang, Yiyan Qi, Min Hu, Chao Deng, and Xiaohong Guan.  Bidirectionally densifying LSH sketches with empty bins.  In _Proceedings of the International Conference on Management of Data (SIGMOD)_ , pages 830–842, Virtual Event, China, 2021.
  * Kleinberg and Tardos [1999] Jon Kleinberg and Eva Tardos.  Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields.  In _Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 14–23, New York, NY, 1999.
  * Lee et al. [2010] David C. Lee, Qifa Ke, and Michael Isard.  Partition min-hash for partial duplicate image discovery.  In _Proceedings of the 11th European Conference on Computer Vision (ECCV), Part I_ , pages 648–662, Heraklion, Crete, Greece, 2010.
  * Lei et al. [2020] Yifan Lei, Qiang Huang, Mohan S. Kankanhalli, and Anthony K. H. Tung.  Locality-sensitive hashing scheme based on longest circular co-substring.  In _Proceedings of the 2020 International Conference on Management of Data (SIGMOD)_ , pages 2589–2599, Online conference [Portland, OR, USA], 2020.
  * Lemiesz [2021] Jakub Lemiesz.  On the algebra of data sketches.  _Proc. VLDB Endow._ , 14(9):1655–1667, 2021\.
  * Li et al. [2015] Jin Li, Sudipta Sengupta, Ran Kalach, Ronakkumar N Desai, Paul Adrian Oltean, and James Robert Benton.  Using index partitioning and reconciliation for data deduplication, August 18 2015.  US Patent 9,110,936.
  * Li [2017] Ping Li.  Linearized GMM kernels and normalized random Fourier features.  In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 315–324, Halifax, Canada, 2017.
  * Li and Church [2005] Ping Li and Kenneth Ward Church.  Using sketches to estimate associations.  In _Proceedings of the Human Language Technology Conference and the Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP)_ , pages 708–715, Vancouver, Canada, https://github.com/pltrees/Smallest-K-Sketch, 2005.
  * Li and König [2010] Ping Li and Arnd Christian König.  b-bit minwise hashing.  In _Proceedings of the 19th International Conference on World Wide Web (WWW)_ , pages 671–680, Raleigh, NC, 2010.
  * Li et al. [2011] Ping Li, Anshumali Shrivastava, Joshua L. Moore, and Arnd Christian König.  Hashing algorithms for large-scale learning.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 2672–2680, Granada, Spain, 2011.
  * Li et al. [2019] Ping Li, Xiaoyun Li, and Cun-Hui Zhang.  Re-randomized densification for one permutation hashing and bin-wise consistent weighted sampling.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 15900–15910, Vancouver, Canada, 2019.
  * Li et al. [2021] Ping Li, Xiaoyun Li, Gennady Samorodnitsky, and Weijie Zhao.  Consistent sampling through extremal process.  In _Proceedings of the Web Conference (WWW)_ , pages 1317–1327, Virtual Event / Ljubljana, Slovenia, April 19-23, 2021, 2021.
  * Li et al. [2022] Ping Li, Xiaoyun Li, and Gennady.  P-MinHash algorithm for continuous probability measures: Theory and application to machine learning.  In _Proceedings of the 31st ACM International Conference on Information and Knowledge Management (CIKM)_ , Atlanta, GA, 2022.
  * Li and Li [2021] Xiaoyun Li and Ping Li.  Rejection sampling for weighted jaccard similarity revisited.  In _Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI)_ , Virtual Event, 2021.
  * Li and Li [2022] Xiaoyun Li and Ping Li.  C-MinHash: Improving minwise hashing with circulant permutation.  In _Proceedings of the International Conference on Machine Learning (ICML)_ , pages 12857–12887, Baltimore, MD, 2022.
  * Li and Li [2023] Xiaoyun Li and Ping Li.  Differentially private one permutation hashing and bin-wise consistent weighted sampling.  _arXiv preprint_ , 2023.
  * Manasse et al. [2010] Mark Manasse, Frank McSherry, and Kunal Talwar.  Consistent weighted sampling.  Technical Report MSR-TR-2010-73, Microsoft Research, 2010.
  * Manzoor et al. [2016] Emaad A. Manzoor, Sadegh M. Milajerdi, and Leman Akoglu.  Fast memory-efficient anomaly detection in streaming heterogeneous graphs.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 1035–1044, San Francisco, CA, 2016.
  * Nargesian et al. [2018] Fatemeh Nargesian, Erkang Zhu, Ken Q. Pu, and Renée J. Miller.  Table union search on open data.  _Proc. VLDB Endow._ , 11(7):813–825, 2018.
  * Pandey et al. [2009] Sandeep Pandey, Andrei Broder, Flavio Chierichetti, Vanja Josifovski, Ravi Kumar, and Sergei Vassilvitskii.  Nearest-neighbor caching for content-match applications.  In _Proceedings of the 18th International Conference on World Wide Web (WWW)_ , pages 441–450, Madrid, Spain, 2009.
  * Pewny et al. [2015] Jannik Pewny, Behrad Garmany, Robert Gawlik, Christian Rossow, and Thorsten Holz.  Cross-architecture bug search in binary executables.  In _Proceedings of the 2015 IEEE Symposium on Security and Privacy (SP)_ , pages 709–724, San Jose, CA, 2015.
  * Pouget-Abadie et al. [2019] Jean Pouget-Abadie, Kevin Aydin, Warren Schudy, Kay Brodersen, and Vahab S. Mirrokni.  Variance reduction in bipartite experiments through correlation clustering.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 13288–13298, Vancouver, Canada, 2019.
  * Raff and Nicholas [2017] Edward Raff and Charles K. Nicholas.  An alternative to NCD for large sequences, lempel-ziv jaccard distance.  In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 1007–1015, Halifax, Canada, 2017.
  * Schubert et al. [2014] Erich Schubert, Michael Weiler, and Hans-Peter Kriegel.  SigniTrend: scalable detection of emerging topics in textual streams by hashed significance thresholds.  In _Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 871–880, New York, NY, 2014.
  * Shah and Meinshausen [2017] Rajen Dinesh Shah and Nicolai Meinshausen.  On b-bit min-wise hashing for large-scale regression and classification with sparse data.  _J. Mach. Learn. Res._ , 18:178:1–178:42, 2017.
  * Shi et al. [2020] Hao-Jun Michael Shi, Dheevatsa Mudigere, Maxim Naumov, and Jiyan Yang.  Compositional embeddings using complementary partitions for memory-efficient recommendation systems.  In _Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 165–175, Virtual Event, CA, 2020.
  * Shrivastava [2016] Anshumali Shrivastava.  Simple and efficient weighted minwise hashing.  In _Neural Information Processing Systems (NIPS)_ , pages 1498–1506, Barcelona, Spain, 2016.
  * Shrivastava and Li [2014] Anshumali Shrivastava and Ping Li.  In defense of minhash over simhash.  In _Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (AISTATS)_ , pages 886–894, Reykjavik, Iceland, 2014.
  * Tamersoy et al. [2014] Acar Tamersoy, Kevin A. Roundy, and Duen Horng Chau.  Guilt by association: large scale malware detection by mining file-relation graphs.  In _Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 1524–1533, New York, NY, 2014.
  * Tymoshenko and Moschitti [2018] Kateryna Tymoshenko and Alessandro Moschitti.  Cross-pair text representations for answer sentence selection.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2162–2173, Brussels, Belgium, 2018\.
  * Wang et al. [2014] Jiang Wang, Yang Song, Thomas Leung, Chuck Rosenberg, Jingbin Wang, James Philbin, Bo Chen, and Ying Wu.  Learning fine-grained image similarity with deep ranking.  In _Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 1386–1393, Columbus, OH, 2014.
  * Wang et al. [2019] Pinghui Wang, Yiyan Qi, Yuanming Zhang, Qiaozhu Zhai, Chenxu Wang, John C. S. Lui, and Xiaohong Guan.  A memory-efficient sketch method for estimating high similarities in streaming sets.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD)_, pages 25–33, Anchorage, AK, 2019.
  * Yang et al. [2019] Dingqi Yang, Paolo Rosso, Bin Li, and Philippe Cudré-Mauroux.  NodeSketch: Highly-efficient graph embeddings via recursive sketching.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD)_, pages 1162–1172, Anchorage, AK, 2019.
  * Yu and Weber [2022] Yun William Yu and Griffin M. Weber.  Hyperminhash: Minhash in loglog space.  _IEEE Trans. Knowl. Data Eng._ , 34(1):328–339, 2022.
  * Zhao et al. [2019] Weijie Zhao, Jingyuan Zhang, Deping Xie, Yulei Qian, Ronglai Jia, and Ping Li.  AIBox: CTR prediction model training on a single node.  In _Proceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM)_ , pages 319–328, Beijing, China, 2019\.
  * Zheng et al. [2023] Xinyi Zheng, Weijie Zhao, Xiaoyun Li, and Ping Li.  Building k-anonymous user cohorts with consecutive consistent weighted sampling (ccws).  In _Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR)_ , Taipei, 2023.
  * Zhu et al. [2017] Erkang Zhu, Ken Q. Pu, Fatemeh Nargesian, and Renée J. Miller.  Interactive navigation of open data linkages.  _Proc. VLDB Endow._ , 10(12):1837–1840, 2017\.
  * Zhu et al. [2019] Erkang Zhu, Dong Deng, Fatemeh Nargesian, and Renée J. Miller.  JOSIE: overlap set similarity search for finding joinable tables in data lakes.  In _Proceedings of the 2019 International Conference on Management of Data (SIGMOD)_ , pages 847–864, Amsterdam, The Netherlands, 2019\.