% =====================================================================
%  CONJURA CONJECTURE STATEMENT
%  A constant-factor guarantee for the best-first (Huffman-style) tree.
%  Requires conjura-conjecture.cls in the same directory.
% =====================================================================
\documentclass{conjura-conjecture}

\runninghead{BEST-FIRST SEARCH TREES}

\newcommand{\bits}{\{0,1\}}
\newcommand{\Qd}{\mathcal{Q}}
\newcommand{\Mon}{\mathcal{M}}
\newcommand{\ORv}{\mathrm{OR}}
\newcommand{\Pcost}{\mathsf{P}}
\newcommand{\SLC}{\mathrm{SLC}}
\newcommand{\Opt}{\mathrm{Opt}}
\newcommand{\BF}{\mathsf{BF}}
\newcommand{\HW}{\mathrm{HW}}
\newcommand{\Exp}{\mathop{\mathbb{E}}}

\begin{document}

\cjkicker{CONJURA \textperiodcentered{} OPEN PROBLEM}
\cjtitle{A Constant-Factor Guarantee for Huffman-Style Search Tree
  Construction}
\cjsubtitle{Greedy pairwise merging against the optimal OR tree}
\cjstatus{Statement: AI-written from Mohammad Etemad, Mohammad Mahmoody
  and David Evans, \emph{Optimizing Trees for Static Searchable
  Encryption}, IACR Cryptology ePrint Archive 2018, not yet checked by a
  human. Nothing is proved about the best-first algorithm's approximation
  ratio for any class of query distributions: the paper's exhaustive
  experiments already refute exact optimality, the approximation-ratio
  question is untouched, and all of the paper's proved bounds concern the
  level-optimal algorithm instead.}
\cjcategory{\emph{Searchable Encryption \& Encrypted Data Structures}.}

\vspace{0.4em}

\begin{informalconjecture}
In a tree-based encrypted index every file sits at a leaf tagged with its
keyword set, every internal node is tagged with the union of the tags
below it, and a query costs one unit for every node it touches on the way
down. Choosing which files to put next to each other therefore decides
the cost of every future search, and the paper reduces the choice to a
clean objective: minimise, over all binary trees on the given leaves, the
sum over internal nodes of the probability that a random query is
satisfied by that node's tag. The paper's best-performing heuristic for
this is the obvious greedy one, borrowed from Huffman coding: repeatedly
take the two current nodes whose merged tag has the smallest such
probability, make them siblings, and replace them by their parent. It
wins every experiment the paper runs, and on eight files it is
essentially indistinguishable from brute-force search over all binary
trees. What is missing is any theoretical guarantee at all: the paper
proves approximation bounds for its other, level-by-level algorithm and
states that analysing the greedy one is left open, while recording its
expectation that all its algorithms are within a constant factor of
optimal. Note that the greedy tree is genuinely not always optimal ---
exhaustive search beats it on some inputs --- so the question really is
about an approximation ratio, and it can just as well be settled by
exhibiting a workload on which greedy is off by an unbounded factor.
\end{informalconjecture}

\section{The setting}\label{sec:setting}

In tree-based searchable symmetric encryption~\cite{Goh03,KP13,BlindSeer}
the encrypted index is a binary tree: files sit at the leaves with a
vector of the keywords they contain, internal nodes carry the bitwise OR
of their children's vectors, and a monotone Boolean query is answered
top-down, descending below exactly those visited nodes whose vector
satisfies it. Every node costs the same to process, so search cost is the
number of visited nodes, and it depends on how the files were grouped.
The paper shows that for any OR tree $T$ over $L$ and any distribution
$\Qd$ over monotone queries,
\[
  \Exp_{q \sample \Qd}\bigl[\,\#\{\text{nodes visited searching }
  q \text{ in } T\}\,\bigr] \;=\; 1 + 2\,\SLC_{\Qd}(T),
\]
so designing the index is the combinatorial problem of minimizing
$\SLC_{\Qd}$ over the $\prod_{i=1}^{n-1}(2i-1)$ trees on $n$ leaves. When
$\Qd$ is uniform over single keywords the objective specializes to
$\frac{1}{m}\sum_{u \in I(T)} \HW(\bar u)$, where $\HW$ is Hamming
weight: minimize the total size of the $n-1$ keyword unions formed while
merging the files into a hierarchy. This is a natural cost measure for
hierarchical clustering with no encryption in it, and it is closely
analogous to the classical problem of building binary search trees tuned
to an access distribution~\cite{Meh75,Nag97}, except that the cost of a
node depends on the union of its subtree rather than on a weight given in
advance.

The paper's best-first algorithm (Definition~\ref{def:bf}) is the
Huffman-style greedy heuristic for this objective, and it is the one that
performs best: across the paper's Enron experiments it produces the
cheapest trees of the three heuristics, roughly halving the search cost
of a randomly built tree, and on the largest exhaustively checkable
instance ($n=8$, all $135{,}135$ trees enumerated, across $25$ experiment
sets: five randomly selected sets of eight files crossed with five query
distributions) brute force finds a strictly better tree in $13$ of $25$
trials but improves the cost by at most $0.09$. So the greedy tree is not
exactly optimal, which fixes the shape of any positive answer: it must be
an approximation bound, not an optimality proof.

What the paper proves instead concerns only its second algorithm, the
level-optimal algorithm (Algorithm~2), which builds the tree level by
level using Blossom minimum-weight matching; the hybrid algorithm is left
unanalyzed alongside best-first. For that algorithm it gives an
$O(\log n)$ approximation against $\Opt_{\Qd}(L)$ when $\Qd$ is supported
on disjunctive queries, together with a matching $\Omega(\log n)$
instance --- files with disjoint keyword sets, the $i$-th having
$2^{i-1}$ keywords --- on which the best-first tree costs $O(m)$ while
every balanced tree costs $\Omega(m\log n)$. That instance is also the
reason the comparison for best-first has to be against $\Opt_{\Qd}(L)$
over all trees: greedy is the algorithm that is allowed to go unbalanced,
and on that instance it is the one that wins. For the best-first
algorithm itself the paper proves nothing, and its Open questions
paragraph records both the expectation (all three algorithms are probably
within a constant factor of optimal) and the gap (the theoretical
analysis of best-first is left to future work). The level-by-level
argument the paper does have cannot be transplanted: its proof bounds the
zero-weight of the parents of the leaves against that of any balanced
tree layer by layer, which presupposes the layered structure that the
greedy algorithm does not have.

Progress is experimental only. On $n=8$ files, exhaustive enumeration of
all $135{,}135$ binary trees beats the best-first tree in $13$ of $25$
trials, by at most $0.09$ in cost. On the Enron corpus with $n$ up to
$2^{10}$ and dictionary sizes up to $11{,}308$, the best-first tree has
the lowest cost of the two of the paper's algorithms compared there ---
it beats the level-optimal tree in every experiment group of the paper's
Table~1 and roughly halves the cost of a random tree; the hybrid
algorithm is run only for $n > 2^{10}$ and is never compared against
best-first. Those comparisons cover single-keyword queries and two- and
three-keyword conjunctions and disjunctions. In the paper's
$\Omega(\log n)$ separation instance the best-first tree is the cheap
one, costing $O(m)$ against $\Omega(m \log n)$ for any balanced tree.

Why it matters. Best-first is the algorithm that actually wins, in this
paper's own experiments and in the small-$n$ exhaustive comparison, and
it is the one a practitioner would ship for a static encrypted index; it
is also the only one of the three with no guarantee of any kind. A
constant-factor bound would give the deployed heuristic its first
worst-case justification and would say that the cost of an encrypted tree
index is, up to a constant, an intrinsic property of the file collection
and query workload rather than an artefact of how the tree was built. A
counterexample would be equally valuable and arguably more surprising,
since it would exhibit a workload on which a Huffman-style greedy is
asymptotically wrong for a cost function that looks submodular, and it
would tell index builders to look past greedy. Either way the answer is
about a self-contained combinatorial optimization problem ---
approximating the cheapest hierarchical grouping under expected query
satisfaction --- with an interest of its own beyond encrypted search. The
whole statement is bit vectors, bitwise OR, binary trees and one sum of
$n-1$ probabilities; the algorithm is five lines of pseudocode, no
cryptography enters the statement at all, and nothing depends on the
paper's implementation or data.

\section{Notation and parameters}\label{sec:notation}

$[n] = \{1,\dots,n\}$.

The dictionary is a set of $m$ keywords $w_1,\dots,w_m$. A vector
$\bar v \in \bits^m$ records a set of keywords, with $\bar v[j] = 1$
meaning $w_j$ is present; $\ORv(\bar x,\bar y) \in \bits^m$ is the
bitwise OR, i.e.\ $\ORv(\bar x,\bar y)[j] = \bar x[j] \vee \bar y[j]$ for
all $j \in [m]$.

$\Mon_m$ is the set of monotone Boolean formulas over variables
$x_1,\dots,x_m$: formulas built from the variables using $\wedge$ and
$\vee$ only, with no negation. For $q \in \Mon_m$ and
$\bar v \in \bits^m$ we write $q(\bar v) = 1$ if $q$ evaluates to true
under the assignment $x_j := \bar v[j]$ for all $j \in [m]$, and
$q(\bar v) = 0$ otherwise.

$L = \{(f_1,\bar f_1),\dots,(f_n,\bar f_n)\}$ is a set of $n$ file
identifiers $f_i$ with vector labels $\bar f_i \in \bits^m$, where
$\bar f_i[j] = 1$ iff file $f_i$ contains keyword $w_j$. For a tree $T$,
$L(T)$ is its set of leaves, $I(T)$ its set of internal nodes, $\pi(u)$
the parent of a non-root node $u$, and $\Gamma(u)$ the set of children of
an internal node $u$. Each node $u$ of $T$ carries a label
$\bar u \in \bits^m$.

$\Qd$ denotes a distribution over $\Mon_m$, and $q \sample \Qd$ a sample
from it. For a node $u$ with label $\bar u$, its \emph{local cost} is
\[
  \Pcost_{\Qd}(u) \;=\; \Pr_{q \sample \Qd}\bigl[\,q(\bar u) = 1\,\bigr]
  \;\in\; [0,1],
\]
and for an OR tree $T$ over $L$ (Definition~\ref{def:ortree2}),
\[
  \SLC_{\Qd}(T) \;=\; \sum_{u \in I(T)} \Pcost_{\Qd}(u),
\]
\[
  \Opt_{\Qd}(L) \;=\; \min_{T \,:\, L(T) = L} \SLC_{\Qd}(T),
\]
the minimum ranging over all OR trees over $L$, of any shape. Finally
$\BF(L,\Qd)$ is the set of trees the best-first algorithm of
Definition~\ref{def:bf} can output on $L$ and $\Qd$.

The parameters are:
\begin{itemize}
\item $m$, the dictionary size, i.e.\ the number of keywords; labels are
  vectors in $\bits^m$. Unbounded and independent of $n$.
\item $n$, the number of files, hence the number of leaves; any integer
  $n \ge 2$ (best-first needs no power-of-two restriction).
\item $L$, the leaf set: $n$ file identifiers with their keyword
  vectors, arbitrary.
\item $\Qd$, the query distribution, an arbitrary distribution over
  monotone Boolean formulas on $m$ variables.
\item $c$, the approximation constant, absolute: independent of $m$,
  $n$, $L$ and $\Qd$.
\end{itemize}

\begin{definition}[OR tree over $L$]\label{def:ortree2}
Let $L = \{(f_1,\bar f_1),\dots,(f_n,\bar f_n)\}$ with
$\bar f_i \in \bits^m$. An \emph{OR tree over $L$} is a full binary tree
$T$ (every node has either $0$ or $2$ children) with $L(T) = L$, in which
every leaf $f_i$ carries its given label $\bar f_i$ and every internal
node $u \in I(T)$ with $\Gamma(u) = \{x,y\}$ carries the label
$\bar u = \ORv(\bar x, \bar y)$. The labels are therefore determined by
$L$ together with the shape of $T$ and the assignment of files to leaves;
$|I(T)| = n - 1$ always.
\end{definition}

\begin{definition}[the best-first algorithm $\BF$]\label{def:bf}
On input a leaf set $L$ with $|L| = n$ and access to the local cost
function $\Pcost_{\Qd}(\cdot)$, the algorithm sets $W := L$ and, while
$|W| > 1$, does the following. For each unordered pair $x \neq y$ in $W$
let $C(x,y) := \Pcost_{\Qd}(z)$, where $z$ is a new node with label
$\bar z = \ORv(\bar x, \bar y)$. Pick a pair $\{x,y\}$ minimizing
$C(x,y)$, create the node $z$ with label
$\bar z = \ORv(\bar x,\bar y)$, set $\Gamma(z) = \{x,y\}$ and
$\pi(x) = \pi(y) = z$, remove $x$ and $y$ from $W$ and add $z$ to $W$.
When $|W| = 1$ return the tree built, whose root is the single remaining
element of $W$; it is an OR tree over $L$, not necessarily balanced. We
write $\BF(L,\Qd)$ for the set of all trees obtainable this way, over all
choices of minimizing pair at each step.
\end{definition}

\section{The conjecture}\label{sec:conjectures}

\begin{conjecture}[best-first is a constant-factor
approximation]\label{conj:main}
There is an absolute constant $c > 0$ such that the following holds for
every dictionary size $m \ge 1$, every $n \ge 2$, every leaf set
$L = \{(f_1,\bar f_1),\dots,(f_n,\bar f_n)\}$ with
$\bar f_i \in \bits^m$, every distribution $\Qd$ over $\Mon_m$, and every
tree $T \in \BF(L,\Qd)$:
\[
  \SLC_{\Qd}(T) \;\le\; c \cdot \Opt_{\Qd}(L).
\]
Equivalently, $\SLC_{\Qd}(T) = O(\Opt_{\Qd}(L))$ with the hidden constant
independent of $m$, $n$, $L$ and $\Qd$. Note that $\Opt_{\Qd}(L)$ is the
minimum over all OR trees over $L$, including unbalanced ones, so no
restriction on the height of $T$ is imposed on either side.
\end{conjecture}

\begin{remark}[the strength of the statement]\label{rem:strength}
This is the maximal reading of the paper, and it may well be false. The
paper leaves open ``a theoretical analysis of the optimality'' of
best-first without stating a target bound; the constant factor comes from
the neighbouring sentence, which says all the paper's algorithms are
``probably within a constant factor of optimal'', and that sentence is
hedged with ``when it comes to real data''. A worst-case constant-factor
claim over all monotone $\Qd$ therefore goes beyond anything the paper
asserts, and a counterexample would settle the problem without
contradicting the paper.
\end{remark}

\begin{remark}[the natural first target]\label{rem:single}
Reviewers who want a version closer to what the paper proves elsewhere
should consider Conjecture~\ref{conj:main} restricted to $\Qd$ uniform
over single keywords, where the objective is
$\frac{1}{m}\sum_{u \in I(T)} \HW(\bar u)$, the total Hamming weight of
the internal labels. That special case is the natural first target and I
would regard it as the real content. The objective is also computable in
closed form for the other family the paper singles out: for $\Qd$ uniform
over $k$-keyword conjunctions, $\Pcost_{\Qd}(u)$ is a fixed polynomial in
$\HW(\bar u)$.
\end{remark}

\begin{remark}[tie-breaking]\label{rem:ties}
The best-first algorithm is defined only up to the choice of minimizing
pair, so its output is a set of trees rather than a single tree, and
Conjecture~\ref{conj:main} quantifies over \emph{every}
$T \in \BF(L,\Qd)$. A bound proved for one canonical tie-breaking rule
would be a partial answer, and worth reporting as such.
\end{remark}

\begin{remark}[what is known about difficulty]\label{rem:difficulty}
Unlike the paper's other open question, this one comes with no
obstruction named by the authors. The only evidence about difficulty is
that greedy is not exactly optimal, and that the paper's layered proof
technique does not apply to an unlayered algorithm --- the latter being a
reading of their proof rather than their statement. Separately, the
general problem of computing $\Opt_{\Qd}(L)$ may be NP-hard, which the
paper never discusses; that would not affect the conjecture, which is
about an approximation ratio, but a solver should be aware of it.
\end{remark}

\section{Bibliography}

\begin{conjurabibliography}{99}

\bibitem[BlindSeer]{BlindSeer}
V. Pappas, F. Krell, B. Vo, V. Kolesnikov, T. Malkin, S. G. Choi,
W. George, A. Keromytis, S. Bellovin.
\emph{Blind Seer: A Scalable Private DBMS}.
35th IEEE Symposium on Security and Privacy, 2014.

\bibitem[Goh03]{Goh03}
E.-J. Goh.
\emph{Secure indexes}.
Technical report, Cryptology ePrint Archive, Report 2003/216, 2003.

\bibitem[KP13]{KP13}
S. Kamara, C. Papamanthou.
\emph{Parallel and dynamic searchable symmetric encryption}.
Financial Cryptography and Data Security, FC, 2013.

\bibitem[Meh75]{Meh75}
K. Mehlhorn.
\emph{Nearly optimal binary search trees}.
Acta Informatica, 5(4):287--295, 1975.

\bibitem[Nag97]{Nag97}
S. V. Nagaraj.
\emph{Optimal binary search trees}.
Theoretical Computer Science, 188(1):1--44, 1997.

\end{conjurabibliography}

\end{document}
