Level-Optimal Search Trees Beyond Disjunctive Queries

–

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

Tree-based encrypted search stores each file at a leaf tagged with its keyword set and tags every internal node with the union of the sets below it; a query descends only below nodes whose tag is consistent with it, so the cost of a search is the number of nodes touched. The source paper builds the tree bottom-up, one level at a time, pairing the current nodes by a minimum-weight perfect matching. The result is balanced, which is what encrypted search wants, since an unbalanced tree leaks its own shape. The authors prove that when every query is a disjunction of keywords this balanced tree is never worse than a logarithmic factor times the cheapest tree of any shape, and that the logarithmic loss is unavoidable. They conjecture the guarantee survives for a wider class of query distributions — without saying which, so naming the class is part of the problem.

View PDF · Download LaTeX source

Notation is as in c/0015: \(\mathcal{M}_m\) is the monotone formulas over \(x_1,\dots,x_m\); a leaf set \(L\) carries keyword indicators \(\bar f_i \in \{0,1\}^m\); an OR tree labels each internal node with the bitwise OR beneath it; \(P_{\mathcal{Q}}(u) = \Pr_{q \leftarrow \mathcal{Q}}[q(\bar u) = 1]\); \(\mathrm{SLC}_{\mathcal{Q}}(T) = \sum_{u \in I(T)} P_{\mathcal{Q}}(u)\); and \(\mathrm{Opt}_{\mathcal{Q}}(L)\) is the minimum of \(\mathrm{SLC}_{\mathcal{Q}}\) over all OR trees over \(L\), including unbalanced ones.

The level-optimal algorithm builds the tree bottom-up: at each level it pairs the current nodes by a perfect matching of minimum total weight, the weight of \(\{u,v\}\) being \(P_{\mathcal{Q}}(u \vee v)\), and replaces each matched pair by a parent. It requires \(n = 2^k\) and yields a balanced tree. The minimum-weight matching need not be unique, so write \(\mathrm{LO}(L,\mathcal{Q})\) for the set of trees obtainable.

Conjecture. There are a class \(\mathcal{C}\) of query distributions, strictly containing every distribution supported on disjunctive queries, and an absolute constant \(c > 0\), such that for every \(m \ge 1\), every \(k \ge 1\) with \(n = 2^k\), every leaf set \(L\), every \(\mathcal{Q} \in \mathcal{C}\) over \(\mathcal{M}_m\), and every \(T \in \mathrm{LO}(L,\mathcal{Q})\), \[\mathrm{SLC}_{\mathcal{Q}}(T) \;\le\; c \cdot \log n \cdot \mathrm{Opt}_{\mathcal{Q}}(L).\]

The existential over \(\mathcal{C}\) is the point. The paper writes only that it conjectures “a more general theorem (than our Theorem B.1) holds for a broader class of query distributions” and names no class; for every \(\mathcal{Q}\) supported on disjunctions \(\bigvee_{j \in S} x_j\) the displayed bound is already a theorem of the paper, so the content of the conjecture is exactly that \(\mathcal{C}\) can be taken strictly larger.

Maximal formalization. The same statement with \(\mathcal{C}\) the class of all distributions over \(\mathcal{M}_m\). This is not the paper’s statement. It is the largest class available in the paper’s own framework — the class over which the algorithms are defined and where the experiments live — and is recorded here as the maximal reading of the authors’ sentence, not as a claim about what they assert.

Open beyond disjunctions.

The proved case. For every \(\mathcal{Q}\) supported on disjunctive queries, the bound holds with a logarithmic factor, and the paper exhibits a family — files with pairwise disjoint keyword sets — showing the \(\log n\) is necessary. So the disjunctive cell is closed in both directions.

Why that proof says nothing about any larger class. It never looks at the algorithm. If \(q\) is a disjunction, then \(q(\bar u) = 1\) forces some file beneath \(u\) to satisfy \(q\), because \(\bar u\) is the OR of the labels below. Consistency therefore implies a witness below, and every balanced tree is within a logarithmic factor for free. The guarantee is a property of the shape, not of the matchings.

Where it fails. With conjunctions the implication breaks: a node can be consistent with an AND of two keywords while no single file beneath it contains both, since the OR label can collect the two keywords from two different files. The paper exhibits an arrangement in which such a query sweeps the entire tree and returns nothing. So for conjunctions no shape-only argument can work, and any proof must use something about the matchings the algorithm actually picks. Nothing of that kind is known for any class.

The only other proved case is a different comparison. For \(\mathcal{Q}\) uniform over single keywords the paper gives a constant-factor bound against the optimal balanced tree, not against \(\mathrm{Opt}_{\mathcal{Q}}(L)\), and it needs \(n\) even together with a density hypothesis. It is not an instance of the conjecture.

The conjecture is unusual in that its statement is partly the thing to be found. A solver is not handed a class and asked to prove a bound over it; they are asked to identify any class strictly larger than the disjunctions for which the bound survives, and the paper’s own experiments — covering AND and OR of two and three keywords — suggest where to look without licensing any particular choice.

Two natural targets sit at opposite ends. The maximal reading, all monotone distributions, is the largest class the framework supports and would be the strongest possible answer. At the other end, any concrete class properly containing the disjunctions — disjunctions of pairs, or bounded-width formulas — would settle the conjecture as stated. A negative result is equally valuable: a distribution class in which every level-optimal tree is \(\omega(\log n)\) from optimal would show the disjunctive theorem is essentially maximal and that the conjecture’s premise is wrong.

Note also that \(\mathrm{LO}(L,\mathcal{Q})\) is a set rather than a single tree, because minimum-weight matchings need not be unique. The conjecture as stated asks for the bound on every member; a result for one canonical choice of matching would be a partial answer, and the paper’s own definition fixes a single returned tree rather than quantifying.