On the expected cost of partial match queries in random Quad-K-d trees

La Matematica (2024) 3:385–416 https://doi.org/10.1007/s44007-024-00090-5 ORIGINAL RESEARCH ARTICLE On the Expected Cost of Partial Match Queries in Random Quad-K-d Trees Amalia Duch1 ·Conrado Martínez1 Received: 7 February 2023 / Revised: 5 December 2023 / Accepted: 8 January 2024 / Published online: 4 March 2024 © The Author(s) 2024 Abstract Quad-K-d trees introduced by Bereckzy et al. (In: Proceedings of the 11th Latin merican Theoretical Informatics Conference (LATIN). Lecture Notes in Computer Science, vol. 8392, pp. 743–754, 2014) are a generalization of several well-known hierarchical multidimensional data structures. They provide a unified framework for the analysis of associative queries, and they are specially suitable to investigate the trade-offs between the cost of different operations and the memory needs (each node x of a quad-K-d tree has arity 2m(x)for some m(x),1≤m(x)≤K). Indeed, we consider here partial match—one of the fundamental associative queries for several families of quad-K-d trees including, among others, relaxed K-d trees and quadtrees. In particular, we prove that the expected cost ˆ Pnof a random partial match query that has sout of Kspecified coordinates in a random quad-K-d tree of size nis ˆ Pn∼β·nα, where αand βare constants given in terms of Kand sas well as additional parameters that characterize the specific family of quad-K-d trees under consideration. Additionally, we derive a precise asymptotic estimate for the main order term of the expected cost Pn,qof a fixed partial match with query qin a random quad-K-d tree of size n.The techniques used to derive the mentioned costs are those already applied successfully to derive analogous results in quadtrees and relaxed K-d trees; our results show that the previous results are just particular cases and prove the validity of the conjecture made in Duch et al. (In: Proceedings of the 12th Latin American Theoretical Informatics Conference (LATIN). Lecture Notes in Computer Science, vol. 9644, pp. 376–389, 2016) for a wider variety of multidimensional data structures. Amalia Duch and Conrado Martínez have contributed equally to this work BConrado Martínez [email protected] Amalia Duch [email protected] 1Department of Computer Science, Universitat Politècnica de Catalunya, Jordi Girona 1-3, 08034 Barcelona, Spain 123 386 La Matematica (2024) 3:385–416 Keywords Quadtrees ·K-d trees ·Partial match queries ·Associative queries · Multidimensional search ·Analysis of algorithms 1 Introduction Considered as fundamental associative queries, partial match queries have been widely studied in the literature (see for instance [1,2]). Given a collection (or file) Fof ndata points, in which each data point has a key x=(x0,...,xK−1)which is an ordered K-tuple of values (known as attributes or coordinates), an associative query in F retrieves the data points satisfying certain given conditions involving several of their (key) coordinates. Without loss of generality, we shall identify data points as their keys. In partial match (PM, hereinafter) queries, the goal is to retrieve from Fall the data points with attributes matching the specified attributes of the query argument. For instance, for K=3, a partial match query might be given by q=(∗,0.3,0.2), and the goal is then to retrieve all data points xin Fsuch that x=(x0,x1,x2)has x1=0.3 and x2=0.2 (and x0can be anything, this is indicated by q0=∗). Indeed, the analysis of PM queries (either random or fixed) has been carried out in a wide variety of hierarchical multidimensional data structures, see [3–9] and references therein. From the point of view of their analysis, it would be of great interest to unify all these results in a comprehensive way. The general framework of quad-K-d trees (introduced in [10]) is an attempt in that direction. A quad-K-d tree is a multidimensional tree in which each node contains a data point xand discriminates with respect to some number m,1≤m≤K, of coordinates (and thus it has 2msubtrees). The number m (the type of the node) and the subset of mdiscriminating coordinates are potentially distinct for each node. When all the Kcoordinates are used to discriminate at every node of the tree (m(x)=Kfor all x), the tree is a quadtree [11]; in contrast, when exactly one of the Kcoordinates is used to discriminate at every node (m(x)=1for all x), the tree is a K-d tree [12]. In this work, we follow the approach of Chern and Hwang [5] to prove (extending the preliminary results in [6]) that the expected cost ˆ Pnof a random PM query in a random quad-K-d tree of size nis ˆ Pn=β·nα+lower order terms (l.o.t.), with αand βgiven in Theorem 1. Our preliminary results in [6] only characterized the exponent αin the expected cost (nα)of random PMs and relied upon Roura’s continuous master theorem [13]. We also give here (following the steps in [7,14]) a precise asymptotic estimate for the main order term of the expected cost Pn,q=ν·f(q)·nα+l.o.t. of a fixed partial match with query qin a random quad-K-d tree of size n, where αis the same as for random PM queries—our result applies under the reasonable but technically hard to establish assumption that the limit of Pn,q/nαwhen n→∞exists. This is formalized in Theorem 2where we give the explicit form of the constant νand of f(q). Our results apply to any family of quad-K-d trees whose nodes have their type m and the subset of mdiscriminating coordinates randomly and independently generated 123 La Matematica (2024) 3:385–416 387 for each node. This includes, indeed, random relaxed K-d trees and quadtrees (with the “degenerate” random types m=1 and m=K, respectively). The paper—that is based upon the extended abstract appeared in [15]—is organized as follows. In Sect. 2, we give some preliminaries of quad-K-d trees (Sect. 2.1) and partial matches (Sect. 2.2). We then derive, in Sect.3, the expected cost of random and fixed PM queries in a random quad-K-d tree (Sects. 3.1 and 3.2, respectively). We finish in Sect.4with conclusions and a brief discussion around further work in this research topic. 2 Preliminaries 2.1 Quad-K-d Trees Quad-K-d trees generalize K-dimensional trees [12] and quadtrees [11]. In K-d trees each node xhas a discriminating coordinate i,0≤i<K:allkeysyin the left subtree of xhave their i-th coordinate yismaller than xi. Likewise, all keys zin the right subtree of xhave their i-th coordinate zilarger than xi. We will write x,ifor a node of a K-d tree holding the data point xand discriminating w.r.t. coordinate i. Each node x,iof a K-d tree is thus associated with a region (called the bounding box) of the domain from which the keys are drawn, and divides that region into two, depending on how the i-th coordinate of the points in the region compares to xi.The choice of which coordinate discriminates at each node leads to several variants of K-d trees. For quadtrees, each node xinduces a partition of its associated region into 2K quadrants, and it will have thus 2Ksubtrees, one for each quadrant. If we label subtrees with a bit string wof length K,thei-th bit of windicates if all keys yin the subtree have yi<xi(when wi=0) or yi>xi(when wi=1). For example, for K=2, the root xof a quadtree divides the space into four quadrants; the subtree T00 contains the data points zsuch that z0<x0and z1<x1(southwest quadrant), T01 contains the data points zsuch that z0<x0and z1>x1(northwest), etc. Quad-K-d trees, being a generalization of both K-dimensional trees and quadtrees, store for each node a subset of mdiscriminating coordinates, with mranging from 1 to K, potentially different for each node. We say that such a node is of type m.All nodes in a K-d tree are of type 1, all nodes in a K-dimensional quadtree are of type K, and a general quad-K-d tree may contain a mixture of nodes of different types. The subset of discriminating coordinates of a node is represented by its characteristic function or coordinate split vector δ:ifδi=0 then the corresponding node does not discriminate with respect to the i-th coordinate, otherwise δi=1 and the node will discriminate with respect to that coordinate. Thus, a node of type mhas 2msubtrees and partitions its associated region of the domain of the keys into 2msubregions, each subregion associated to a subtree. Figure 1shows an example of a 3-dimensional quad-K-d tree. Inside each node appears its label and in the table therein is the 3-dimensional key associated to the node together with its split vector. Next to every edge appears the label (the string w)ofthe subtree where it points to. When wi=0, it means that iis a discriminating coordinate 123 388 La Matematica (2024) 3:385–416 1 2 3 4 5 6 7 8 #0# #1# #0# #1# 00# 01# 10# 11# 000 001 010 010 100 101 110 111 Node Coordinates Split vector 1 (0.35,0.5,0.17) 010 2 (0.31, 0.45, 0.47) 010 3 (0.29, 0.6, 0.9) 110 4 (0.3, 0.3, 0.3) 001 5 (0.4, 0.47, 0.3) 110 6 (0.2, 0.7, 0.5) 111 7 (0.38, 0.8, 0.89) 011 8 (0.25, 0.68, 0.4) 100 Fig. 1 An example of a 3-dimensional quad-K-d tree, omitting some empty subtrees (δi=1) and all keys yin the subtree have yi<xi.Ifwi=1 then iis a discriminating coordinate (δi=1) but now all keys yin the subtree have yi>xi. When iis not a discriminating coordinate (δi=0), we indicate so in the subtree/subregion label wby setting wi=#. More formally, a K-dimensional record (or key) is a K-tuple of values x= (x0,...,xK−1), where each xiis drawn from a totally ordered domain Di. The domain D=D0×···×DK−1is known as the search space, and without loss of generality, it is usually assumed to be D=[0,1]K. Then, the formal definition of quad-K-d trees is as follows. Definition 1 (Bereckzy et al. [16]) A quad-K-d search tree Tof size n≥0 stores a set of nK-dimensional records, each holding a key x=(x0,...,xK−1)and a coordinate split bit vector δ=(δ0,...,δK−1)∈{0,1}K. The quad-K-d tree Tis such that •either it is empty if n=0, or •its root rstores a record with key x, a coordinate split vector δthat contains exactly mones (we say that δis of order mand that the root node is of type m), with 1 ≤m≤K, and pointers to its 2msubtrees that store the n−1 remaining records as follows: each subtree, let us call it Tw, is itself a quad-K-d tree and its label w=w0w1...wK−1∈{0,1,#}Kis such that for all j,0≤j<K, δj=0⇒ wj=#, and for any key y∈Tw, –ifδj=1 and wj=0, then yj<xj –ifδj=1 and wj=1, then yj>xj. It is worth noting that with this definition, as is the case of binary search trees and other search trees, we do not consider cases in which two or more keys have some identical coordinates in the same dimension; however, the definition above can be adapted (and hence the algorithms supported by the data structure) to cover these cases. However, because of our assumptions in the analysis, we can safely disregard 123 La Matematica (2024) 3:385–416 389 this situation—as is usually done in the literature—since the probability that two records share a coordinate value is 0. As we have already mentioned, both K-d trees and quadtrees are special cases of quad-K-d trees. In fact, for any quad-K-d tree Tof size n, if the split vector δ associated with every node of Tcontains all the Kcoordinates (δj=1 for all j) then Tis a quadtree, and if it contains exactly one for every node then Tis a relaxed K-d tree [17]. We use here the term relaxed K -d trees to stress that the discriminating coordinate of each node is arbitrary, in contrast with standard K-d trees [12], squarish K-d trees [18], and other families of K-d trees where the discriminating coordinate of each node is determined by some fixed rule. Thus, relaxed K-d trees are the most general family of K-d trees, of which all other families are particular instances. We can have a similar situation with quad-K-d trees: we can define families of quad- K-d trees in which some fixed rule prescribes the types of the nodes, as well as the discriminating coordinate of every node. We will use the term relaxed quad-K-d trees to emphasize that we consider the most general family of quad-K-d trees, as implied by Definition 1; however, all over this work, unless otherwise stated, we will refer to relaxed quad-K-d trees as simply quad-K-d trees. A node holding key xand split vector δin a quad-K-d tree is of type m if and only if δis of order m,1≤m≤K. Every node of type mhas 2mchildren. A m-regular (or m-ary) quad-K-d tree is a quad-K-d tree that has all its internal nodes of type m. Indeed, quadtrees of dimension Kare K-regular quad-K-d trees and all variants of K-d trees are 1-regular quad-K-d trees. The probabilistic analysis of PM queries in quad-K-d trees works under the assumption that the trees under consideration are random. Definition 2 A random relaxed quad-K-d tree of size nis a quad-K-d tree built by n random insertions (see below) into an initially empty tree, and it additionally satisfies the following two conditions: 1. The types of its nnodes are given by ni.i.d. random variables in the set {1,...,K}. We denote as τmthe probability that an arbitrary node is of type m. 2. For a node of type m, any subset of mcoordinates out of Kis equally likely to be the set of discriminating coordinates (that is, those for which δj=1). Thus, the probability that the discriminating coordinates of a node of type mare 0 ≤i0< i1<···<im−1<Kis 1/K m, for any subset {i0,...,im−1}⊆{0,...,K−1}. There are several equivalent ways to characterize random insertions. The one we consider here is that every coordinate of the data point to be inserted is independently drawn from some continuous distribution in [0,1]. The previous definition of random quad-K-d trees is equivalent to the conventional random models found in the literature for the particular cases of random quadtrees and random relaxed K-d trees. Several instances of random quad-K-d trees have been proposed in previous works [6,10], including, among others, the following families of search trees: •Random quadtrees: these are K-regular random quad-K-d trees; here τK=1, and τm=0ifm= K. •Random relaxed K-d trees: these are 1-regular random quad-K-d trees. We have τ1=1, and τm=0ifm= 1. 123 390 La Matematica (2024) 3:385–416 •Random Split [16] quad-K-d trees. We will use the name Pseudo-binomial Split to refer to this family hereinafter. Given some real value p,0<p<1, if m>1, we have τm=K mpmqK−m,q=1−p, and τ1=qK+KpqK−1. •Uniform Split quad-K-d trees. We have here τm=1/K, for any m. •Binomial Split quad-K-d trees. Given some real value p,0<p<1, we have τm=K−1 m−1pm−1qK−m,q=1−p. •Geometric Split quad-K-d trees. Given some real value p,0<p<1, we have, for m<K τm=qpm−1,q=1−p, and τK=1−1≤m≤K−1τm=pK−1. •m-regular relaxed quad-K-d trees. All types are given by the “degenerate” random variable X∼m; that is, τm=1 and τ=0 for all = m. In the case of Pseudo-binomial Split (a.k.a. Random Split), Binomial Split, and Geometric Split quad-K-d trees, we have a “dial” to control the transition from random relaxed K-d trees to quadtrees. When p=0, all these families coincide with random relaxed K-d trees, while they become quadtrees when p=1. In the case of m-regular relaxed quad-K-d trees, we also have the transition from relaxed K-d trees (m=1) to quadtrees (m=K). The expected amount of memory used in a quad-K-d tree is obviously related to the arity of the different nodes. If dis the average arity of a quad-K-d tree of nnodes, we expect to need dn +1 pointers (including the pointer to the root of the tree), of which approximately (d−1)nwill be null. Indeed, the average arity dof a random relaxed quad-K-d tree is given by d= 1≤m≤K τm2m. Table 1gives the average arity for the families of random relaxed quad-K-d trees mentioned in this paper. In the case of Geometric Split, it is interesting to observe that there are three regimes, according to p<1/2, p=1/2orp>1/2. If p<1/2 then the average degree is constant (d≈2q 1−2p), irrespective of K, it grows linearly with Kwhen p=1/2( d=K+1), and it grows exponentially with Kwhen p>1/2 (d≈1 2p−1(2p)K). 123 La Matematica (2024) 3:385–416 391 Table 1 Average arity and type for some families of random relaxed quad-K-d trees Family Average arity dAverage type m Quadtrees 2KK Relaxed K-d trees 2 1 m-regular relaxed 2mm Uniform Split 2 K(2K−1)K+1 2 Pseudo-binomial Split (1+p)K+(1−p)KKp+qK Binomial Split 2(1+p)K−1Kp+q Geometric Split (2p)K+2p−2 2p−1if p= 1/21−pK 1−p K+1ifp=1/2 Some families depend on a parameter p,0≤p≤1, q:= 1−p Table 1also gives the average type of a node m= 1≤m≤K mτm, which is a relevant parameter in the analysis of the expected cost of building a random quad-K-d tree, as well as in the analysis of the expected cost of exact successful searches. Both costs (construction and exact search) are related to the internal path length (IPL) of the quad-K-d tree; it can be easily shown that the expected IPL Inof a random quad-K-d tree of size nis [10] In=2 mnln n+l.o.t.. 2.2 Partial Match A PM query is a pair q,u, where q=(q0,...,qK−1)is a K-dimensional key and u=(u0,...,uK−1)is the pattern of the query; when ui=S, it indicates that the i-th attribute of the query is specified and when ui=∗, it indicates that the i-th attribute is unspecified. Alternatively, we can define a PM query as K-tuple q=(q0,...,qK−1) where each qiis a value in the i-th domain Dior qi=∗to indicate that it is unspecified; we will use most often this second form to represent PM queries. The PM query q,uis random if q=(q0,...,qK−1)is independently drawn from the same continuous distribution as the data points, otherwise we say that the PM is fixed. The goal of the PM search is to report all data points x=(x0,...,xK−1)in the tree such that xi=qiwhenever qi=∗. The number of specified coordinates will be denoted by s; the interesting cases are when 0 <s<K. Therefore, to perform a PM search with query q, a quad-K-d tree with root of type mis recursively explored as follows. First, we check whether the root with associated xmatches qor not, to report 123 392 La Matematica (2024) 3:385–416 it in the former case. Since the node discriminates by mcoordinates, let us consider that iof them corresponds to specified coordinates in the query (0 ≤i≤min{s,m})). Then, we make recursive calls in all the 2m−isubtrees Twof the root such that wj=# or qj=∗,orwj=0 and qj≤xj,orwj=1 and qj>xj(we say that the pair x,wmatches the query q). Equivalently, we must recursively follow the PM query in the subtree Twif the (K−s)-dimensional region (embedded in the K-dimensional space) defined by the query qintersects the K-dimensional region associated to Tw (the bounding box of its root node). For example, imagine that K=5 and we have the PM query q=(0.1,0.82,∗, 0.76,∗). Moreover, suppose that the root node is of type m=3 with coordinate split vector δ=(1,0,1,1,0)and that it contains the key x=(0.54,0.46,0.39,0.03,0.62). The 8 subtrees of the root node are labeled as (0,#,0,0,#), (0,#,0,1,#),...,(1,#, 1,1,#). Coordinates 0 and 3 are specified in qand discriminating in the quad-K-d tree’s root. Coordinate 1 is specified in q, but not discriminating; coordinate 2 is discriminating but not specified in q; coordinate 4 is neither specified nor discriminating. So, from the point of view of the PM algorithm, there are only m=3 coordinates to care for (those discriminating) of which the query only specifies i=2. Since 0.1<0.54 and 0.76 >0.03, we will have to explore the two subtrees with w0=0 and w3=1, namely, (0,#,0,1,#)and (0,#,1,1,#)since the third coordinate is not specified albeit discriminating; hence the PM query must recursively follow into both subtrees (the one with w2=0 and the one with w2=1). A version of the PM search algorithm that counts the number of visited nodes is shown in Algorithm 1. Algorithm 1 PM search Returns the number of visited nodes in Twith query q function Partial_Match (tree T, query q) if T=then return 0 else res ←1 m←T.type type of the root; 1 ≤m≤K x←T.key δ←T.split w←0m0m=0·····0 while w = 1mdo for i←0to K−1do if δi=1then ˆwi←wi else ˆwi←# end if end for if x,ˆ wmatches q then res ←res +Partial_Match(Tˆ w,q) end if w←next(w)next bit string of length m 123 La Matematica (2024) 3:385–416 393 end while return res end if end function end 3 Analysis The cost of the PM search is measured—as usual in the literature—as the number of nodes visited by the algorithm in the corresponding tree. According to this way of measuring the cost, it is relevant toward our analysis to observe that, except for eventual matches, only the relative order of the coordinates of the stored keys matters. Indeed, let us call the rank vector of a query qthe vector r(q)=(r0,...,rK−1) such that ri=∗,ifqi=∗, and riis the number of records xin the collection Fsuch that xi≤qi(0 ≤ri≤n), if qi=∗. Then, for any two given queries qand qwith equal rank vectors r(q)=r(q), the PM procedure described above will visit exactly the same set of nodes of the tree. In our analysis, we will use rank vectors instead of the queries themselves (as done in [6,14]) and consider the cost Pn,rof a random PM query with given rank vector rin a random quad-K-d tree of size n. We will use Pn,q for the cost of a PM query with a query qin a random quad-K-d tree of size n, where each qi∈(0,1)or qi=∗. From our discussion above, Pn,q=Pn,r(q). Moreover, because of the symmetries in the model of random quad-K-d trees, we can safely assume that the queries are of the form q=(q0,...,qs−1,∗,...,∗)with qi∈(0,1) for all i,0≤i<s, we will abuse the notation and simply write q=(q0,...,qs−1) and r=(r0,...,rs−1), omitting the non-specified coordinates. 3.1 Analysis of Random Partial Match Let ˆ Pndenote the expected cost of a random PM query in a random relaxed quad-K-d tree of size n. In a random PM query, we fix a pattern uin advance and the query is the pair q,uwhere qis a random K-dimensional point independently drawn from the same distribution as the data points of the quad-K-d tree. On the other hand, because of the symmetries of the problem, if all coordinates of all data points (and of the random partial match queries) are identically and independently drawn from the same continuous distribution Din [0,1]then we can safely assume that the specified coordinates in a random query are the first scoordinates, and we can say that a random PM query is a K-tuple q=(q0,...,qs−1,∗,...,∗)with each qii.i.d. drawn from the distribution D. Here we are going to proceed—as is usual in the literature—obtaining the expected cost P nof an “idealized” PM search procedure that works as if every time that we recursively invoke it on a subtree, a new random query was generated (but inside the region of the space associated to the subtree under consideration). The random variable for the cost of this idealized PM search is obviously different from the one that gives the cost of a PM search with a random query; but their respective expected 123 400 La Matematica (2024) 3:385–416 0 5 10 15 20 25 0 0.02 0.04 0.06 0.08 0.1 0.12 s em K=25,m∈{1,5,...,25} 1 5 10 15 22 25 Fig. 3 Behavior of the excess =α−1+s/Kfor m-regular quad-K-d trees with different values of s, and mtaking values in {1,...,K}. Notice that m=1 corresponds to random relaxed K-d trees, while m=K=25 corresponds to quadtrees as we increase the number of specified coordinates—indeed, if we had s=Kthen the expected cost of such a “partial match” is (log n), our formulas give the limiting value α→0 when s→K, if we look at sand Kas if they were continuous variables. Comparing the behavior of the different families of quad-K-d trees, it seems that the m-regular quad-K-d trees outperform all the others, while the geometric split family seems to have the worst performance as shown in Fig.4. In order to produce these plots, we solve for the parameter pthat will give the desired fixed average type m in each family, for example, if we want m=2 when K=20 for the binomial split family,wemustusep=1/19 (the solution of Kp+1−p=m). The difference in performance between the binomial split and the pseudo-binomial split families is almost indiscernible—it is not discernible in the plot of Fig.4, at least. The variation can be better appreciated in Fig. 5where the difference of the specific values of αis plotted for the geometric split family vs. the binomial split family (α(GS,BS)=αGS −αBS) together with the binomial split family vs. the m-regular family (α(BS,REG)=αBS −αREG), always keeping fixed sand Kand varying the desired average type (that is, setting m=mfor regular trees, and in the other cases, we use the parameter pthat renders the desired average type). In summary, Figs.4and 5show graphically how the value of the exponent αevolves once we have fixed the parameters of the query, and we change the average type of our quad-K-d trees—roughly speaking as we increase the average memory space to store the data structure and as a consequence decrease the time for insertions and exact searches— the average memory space is directly correlated, and the average insertion/exact search cost inversely proportional to m(see Sect. 2.1). For the special case K=2, it is possible to calculate the exact values of αand β. In this case, we must have that s=1. For m-regular quad-K-d trees there are only 123 La Matematica (2024) 3:385–416 401 2 4 6 8 10 12 14 16 18 20 0.96 0.96 0.96 0.97 ¯m α s=1,K =20 GS BS PBS REG 2468101214161820 0.3 0.32 0.34 0.36 ¯m α s=15,K =20 GS BS PBS REG Fig. 4 Behavior of αfor several families of quad-K-d trees with different values of the average type m,and fixed sand K 2 4 6 8 101214161820 0 0.5 1 1.5 ·10−3 ¯m Δα(X,Y )×10−3 s=1,K =20 Δα(GS, BS) Δα(BS,REG) 2 4 6 8 10 12 14 16 18 20 0 0.5 1 1.5 ·10−2 ¯m Δα(X,Y )×10−2 s=15,K =20 Δα(GS, BS) Δα(BS,REG) Fig. 5 Difference α(X,Y)=αX−αYon the values of αfor geometric split, binomial split, and m-regular families of quad-K-d trees with different values of the average type m,andfixedsand K 00.20.40.60.81 0.56 0.58 0.6 0.62 p α K=2,s=1 REG, m =1 PBS GS/BS REG, m =2 00.20.40.60.81 1.6 1.7 1.8 1.9 p β K=2,s=1 REG, m =1 PBS GS/BS REG, m =2 Fig. 6 Behavior of α(left) and β(right) for several families of quad-K-d trees when s=1andK=2 123 402 La Matematica (2024) 3:385–416 Table 3 Equation of αfor some families of random relaxed quad-K-d trees when K=2ands=1(αis the unique real solution in the interval (0,1)of the corresponding equation) Family Equation of α Relaxed K-d trees (m=1) 1 α+1+1 α+2=1 Quadtrees (m=2) 4 (α+1)(α+2)=1 Binomial & Geometric Split (1−p)1 α+1+1 α+2+4p (α+1)(α+2)=1 Pseudo-binomial Split (1−p2)1 α+1+1 α+2+4p2 (α+1)(α+2)=1 Table 4 Polynomial (z)(middle column) and its roots (right column) in some families of random relaxed quad-K-d trees when K=2ands=1 Family (z)Roots of (z) Relaxed K-d trees (m=1) (z+1)z−2z−1=01 2+√5 2,1 2−√5 2 Quadtrees (m=2) (z+1)z−4=0−1 2+√17 2,−1 2−√17 2 Binomial & Geometric Split (z+1)z−4p−p+1 2+4p2+8p+5 2 −2(1−p)(z+1 2)=0−p+1 2−4p2+8p+5 2 Pseudo-binomial Split (z+1)z−4p2−p2+1 2+4p4+8p2+5 2 −2(1−p2)(z+1 2)−4p2−p2+1 2−4p4+8p2+5 2 two values of m, namely, m=1 and m=2, that is, relaxed K-d trees and quadtrees, respectively. For the other families, the value of pgoverns the proportion of nodes that discriminate with respect to both coordinates. Thus, when p=0, we have relaxed K-d trees, whereas when p=1, we have ordinary quadtrees. We can appreciate the phenomenon in Fig.6, where the values of αand βare plotted for the different families of quad-K-d trees as pgoes from 0 to 1. In Tables 3and 4, we show, for the special case K=2, the equation that has to be solved in order to obtain α, as well as the polynomial (z)together with its roots, for the different families of random relaxed quad-K-d trees. Notice that the value of τmcoincides for both binomial and geometric split families of quad-K-d trees, when K=2, and their αs and βs coincide too. 3.2 Analysis of Fixed Partial Match In this subsection, we consider the expected cost of a PM search with rank vector r,or equivalently with a query q, if every coordinate of each data point is independent and uniformly distributed in (0,1),see[6] for a discussion about the two “models” and how results for one translate into results for the other. We shall start stating the main theorem of this section, also one of the major contributions of this extended abstract, and devote the rest of the subsection to its proof. 123 La Matematica (2024) 3:385–416 403 Theorem 2 Let r=(r0,r1,...,rK−1)be a rank vector, where ri∈[0..n]∪{∗}, 0≤i<K , and such that exactly s of the ranks is specified, that is, we have ri=∗, for s ranks, 0<s<K . Let zi=limn→∞ ri/nifr i=∗and suppose zi∈(0,1)for all i such that ri=∗,0≤i<K. Then, for any variant of random relaxed quad-K -d trees, the expected cost Pn,rof a fixed PM query with rank vector rin a random quad-K -d tree of size n is Pn,r=νs,K⎛ ⎝ ri=∗ zi(1−zi)⎞ ⎠ α/2 nα+l.o.t., where νs,K=βs,K s(α +2) 2s(α/2+1), and αand βs,Kare the same as in Theorem 1, provided that lim n→∞ Pn,r nα, exists.1 Proof Let Pn,rbe the cost (number of visited nodes) of a partial match search in a random quad-K-d tree of size nwhere the query has fixed rank vector r. Our goal is to find the main order asymptotics of Pn,r=EPn,r; more specifically, our goal is to show that for r=(r0,...,rs−1,∗,...,∗), if limn→∞ ri/n=zi, with zi∈(0,1) for all i,0≤i<sand lim n→∞ Pn,r nα, exists, with αthe exponent of nin the expected cost of a random partial match search (see previous subsection), then lim n→∞ Pn,r nα=f(z0,...,zs−1), and f(z0,...,zs−1)=νs,K⎛ ⎝ ri=∗ zi(1−zi)⎞ ⎠ α/2 , thus yielding the statement of the theorem. 1Besides empirical evidence, the existence of such limit has been formally established for particular instances of quad-K-d trees namely 2-d quadtrees [3], relaxed K-d trees [7], and standard 2-d trees [25]. 123 404 La Matematica (2024) 3:385–416 The first step in our analysis is to set up a recurrence for Pn,r. As in our analysis of random PMs, we condition first on the type mof the root node, so we can write Pn,r= K  m=1 τmP(m) n,r, where P(m) n,r=EPn,r|root of type m. Given that the root node discriminates with respect to mcoordinates, we consider all possible K msplit vectors and then condition to with respect to the number iof discriminating coordinates for which the query is specified: P(m) n,r=1 K m m  i=0 δ∈i,s,K Pn,r(δ), with Pn,r(δ)=EPn,r|root’s split vector is δand i,Kis the set of K- dimensional split vectors such that the prefix of length scontains exactly i1’s, that is i,s,K={δ∈(0+1)K||δ0...δ s−1|1=i}. But any of the K−s m−isplit vectors that discriminate with respect to the same specified coordinates (by our assumptions, split vectors that discriminate for the same icoordinates indexed between 0 and s−1) will be dealt with in exactly the same way when the partial match algorithm is visiting the root node of the tree, because the identity of the non-specified discriminating coordinates is irrelevant at that point. Hence, P(m) n,r=1 K m m  i=0K−s m−i δ∈i,s,s Pn,r(δ·1m−i0K−s−m+i) =1 K m m  i=0K−s m−i w∈i,s Pn,r(w), that is, we can take as representatives of the equivalence classes the split vectors that have i1’s and s−i0’s in their initial prefix s, shuffled in all possible s iways, and then m−i1’s followed by 0K−s−m+i0’s, or equivalently, consider already the contribution of each subtree index wof length sin which ibits are 0 or 1: i,s={w∈(+1+#)s| |w|0,1=i}, each Pn,r(δ·1m−i0K−s−m+i)is the sum of 2icontributions Pn,r(w). Now, let us recall that for fixed partial matches in K-dimensional quadtrees with queries with sspecified coordinates, the expected cost Qn,rof the partial match can be expressed, taking into account the symmetries of the problem, as Qn,r=1+2K−s ns w∈(0+1)s j∈[0..n−1]s Qn,r(j,w), 123 La Matematica (2024) 3:385–416 405 with Qn,r(j,w)denoting the contribution to the expected cost of the fixed partial match when (recursively) visiting, if needed, the subtree with index specified by w and when the first scoordinates of rank vector of the key at the root is j. Here, we are also assuming that r=(r0,...,rs−1,∗,...,∗). Then Qn,r(j,w)= n≥0 r π(n,n;r,r;j,w)Qn,r, where the (complicated) form of the probabilities π(n,n;r,r;j,w)can be obtained from our previous work [14], it is the probability that a fixed partial match in a random quadtree of size nwith query rank vector rcontinues recursively in the subtree of index wof size nand the query rank vector in the recursive call is r, conditioned to the key at the root having a rank vector such that the first scoordinates are given by j. The important point here is that the fixed partial match in a quad-K-d tree with root of type msuch that iof the discriminants are specified in the query will behave at the first level of recursion exactly as in an m-dimensional quadtree with a query in which exactly icoordinates are specified. Notice that we can have i=0, then we have to enter recursively into all 2msubtrees, or i=m, then we have to recursively continue in one subtree; in general, we have to continue recursively into 2m−isubtrees. However, the identity of the chosen discriminating coordinates matters here, as now we are dealing with a fixed partial match—in contrast to random PM where only the distinction between specified or non-specified coordinates is relevant, and so they could be handled equally. This is an important aspect that introduces a new degree of difficulty in the analysis of fixed PM in quad-K-d trees. The other difficulty lies in deducing how the rank vector rchanges when the PM recursively continues in a subtree Tw, that is, what is the probability that the rank vector is rin the recursive call in Twgiven that the rank vector was r. In a quadtree, all coordinates are discriminating and affect rin the same way, only depending on the bit vector wand the key xat the root. In order to write down the recurrence for Pn,r(more specifically Pn,r(w)), we can condition on jas we did for quadtrees: Pn,r(w)=1+2m−i ni j∈[0..n−1]i Pn,r(j;w), and Pn,r(j;w)= n≥0 r π(n,n;rw,r;j,w)Pn,r, where wis composed of the ibits of wthat are discriminating; likewise, rwis an m-dimensional rank vector with the icomponents of rthat are discriminated and specified, followed by m−iunspecified coordinates. The K-dimensional rank vector r is related to r(an m-dimensional rank vector) as follows: we haver k=r kwhenever kis a discriminating coordinate (i.e., δk=1) and r k=rkif kis not a discriminating but specified coordinate. 123 406 La Matematica (2024) 3:385–416 When we pass to the limit on both sides of the recurrence, and under the assumption that f(z0,...,zs−1)=lim n→∞ Pn,r nα, exists, with zi=limn→∞ ri/nand 0 <zi<1, the probabilities π(n,n;r,r;j,w) become highly concentrated around the expected values of r, and thus it becomes considerably simplified. Summations transform into integrals, and the recurrence leads to an integral equation for f(z0,...,zs−1). Let us begin first with the (identical) contribution of all 2m−isubtrees with a particular choice ˆ k=(ˆ k0,...,ˆ km−i)of non-specified discriminating coordinates (hence, we have s≤ˆ kj<K): 1 0···1 0f(z0,...,zs−1)·(uα ˆ k0+(1−uˆ k0)α)··· ·(uα ˆ km−i+(1−uˆ km−i)α)duˆ k0···duˆ km−i=2 α+1m−i f(z0,...,zs−1). Putting everything together yields f(z0,...,zs−1)= K  m=1 τm i≥0K−s m−i K m2 α+1m−i · w∈(0+1+#)s |w|0,1=i Iw0(z0)···Iws−1(zs−1) fρw0(z0,u0),...,ρ ws−1(zs−1,us−1) ·θw0(u0)···θws−1(us−1)α dus−1···du0,(6) where ρ1(zi,ui)=zi ui,ρ0(zi,ui)=1−zi 1−ui,ρ#(zi,ui)=zi,θ1(u)=u,θ0(u)=1−u, θ#(u)=1, I1(z)=[z,1],I0(z)=[0,z]and I#(z)=[0,1]. Recall that only i≤mcoordinates will be specified and discriminating at the root of the quad-K-d tree; the remaining coordinates are either unspecified or nondiscriminating and the PM does the same at the first level of the recursion as far as these coordinates are concerned; we have thus to sum over all possible choices involving the sspecified coordinates: the root does not discriminate for that coordinate (wj=#), the root discriminates for that coordinate and the rank specified in the PM is less (or equal to) than the rank of the key of the root node (wj=0) and when the root discriminates for that coordinate and the rank specified in the PM is greater than the rank of the key of the root node (wj=1). The ranges of the integrals, and the arguments of f and the multiplicative factor (θw0(u0)···θws−1(us−1))αin the integrand are arrived at following the same steps as in the analysis of fixed partial match in quadtrees. In order to find a solution for the integral equation above, we will use that f(z0,...,zs−1)—if it exists—satisfies the following conditions: 123 La Matematica (2024) 3:385–416 407 1. f(z0,...,zs−1)is symmetric on all variables, that is, for any iand j, f(z0,...,zi,...,zj,...,zs−1)=f(z0,...,zj,...,zi,...,zs−1); and, 2. averaging Pn,rover all possible rshould give us ˆ Pn, hence 1 01 0···1 0 f(z0,...,zs−1)dz0···dzs−1=βs,K, where βs,Kis the constant factor of the main order term of ˆ Pn(see Theorem 1). We will begin by assuming that the integral Eq. (6) admits a solution on separate variables, that is, f(z0,z1,...,zs−1)=φ0(z0)·φ1(z1)···φs−1(zs−1). And because of the symmetries that fsatisfies, namely Condition #1 above, we must have φ= φ0=···=φs−1. Then φ(z0)...φ(zs−1)= K  m=1 τm m  i=0K−s m−i K m2 α+1m−i · w∈(0+1+#)s |w|0,1=i Iw0(z0)···Iws−1(zs−1) φ(ρw0(z0,u0))...φ(ρ ws−1(zs−1,us−1)) ·θw0(u0)···θws−1(us−1)α dus−1···du0 = K  m=1 τm m  i=0K−s m−i K m2 α+1m−i w∈(0+1+#)s |w|0,1=i  s−1  k=0Iwk[zk] φ(ρwk(zk,y))(θwk(zk,y))αdy. Since we are assuming that f(z0,...,zs−1)=φ(z0)···φ(zs−1), the summation on won the right-hand side can be written  w∈(0+1+#)s |w|0,1=iIw0(z0)···Iws−1(zs−1) fρw0(z0,u0), . . . , ρws−1(zs−1,us−1) ·θw0(u0)···θws−1(us−1)α dus−1···du0 = w∈(0+1+#)s |w|0,1=is  k=0Iwk(zk) φ(ρwk(zk,uk)) θwk(uk)αduk 123 408 La Matematica (2024) 3:385–416 = k=(k0,...,ki−1)⊂{0,...,s−1}i−1  =0zk 0 φ(zk/u)uαdu +1 zk φ((1−zk)/(1−u)) (1−u)αdu· 0≤j<s:j/∈k1 0 φ(zj)du. Making the change of variables in the integrals (y:= zi/uior y:= (1−zi)/(1−ui), as needed), we arrive at φ(z0)·φ(z1)···φ(zs−1)= K  m=1 τm m  i=0K−s m−i K m2 α+1m−i  k=(k0,...,ki−1)⊂{0,...,s−1} i−1  =0zα kzk 0 φ(u)du uα+2 +(1−zk)α1 zk φ(u)du (1−u)α+2· 0≤j<s:j/∈k φ(zj).(7) Inspired by the analysis of fixed PM queries in particular instances of quad-K-d trees (e.g., [3,7,25,26]), let φ(z)=ν(z(1−z))ϕ−1, with ϕ=α/2+1, for an arbitrary constant ν, and the exponent αin the expected cost of random PM queries for the particular family under consideration. If we define L[φ(z)]=zα1 z φ(y)dy yα+2,and R[φ(z)]=(1−z)αz 0 φ(y)dy (1−y)α+2, then it is easy to show (see [7] for more details) that φ(z)=ϕ·(L[φ(z)]+R[φ(z)]). Let k={k0,k1,...,ki−1}⊂{0,...,s−1}and ˆ k={ ˆ k0,ˆ k1,...,ˆ ks−1−i}= {0,...,s−1}\k, then, for any k,wehave φ(zˆ k0)···φ(zˆ ks−1−i)· i−1  =0L[φ(zk)]+R[φ(zk)] =φ(zˆ k0)···φ(zˆ ks−1−i)·1 ϕi ·φ(zk0)···φ(zki−1) =φ(z0)···φ(zs−1)·1 ϕi . 123 La Matematica (2024) 3:385–416 409 Therefore, the summation in (7) reads  k:k⊂{0,...,s−1} φ(zˆ k0)···φ(zˆ ks−1−i)· i−1  =0L[φ(zk)]+R[φ(zk)] =s i1 ϕi φ(z0)···φ(zs−1). Thus, we can express the right-hand side of (6)as K  m=1 τm m  i=0K−s m−i K m2 α+1m−i  k:k⊂{0,...,s−1} ˆ k={0,...,s−1}\k φ(zˆ k0)···φ(zˆ ks−1−i) i−1  =0L[φ(zk)]+R[φ(zk)] = K  m=1 τm m  i=0K−s m−i K m2 α+1m−is i1 ϕi φ(z0)···φ(zs−1) =φ(z0)···φ(zs−1)·K  m=1 τm m  i=0K−s m−is i K m 2m (α +1)m−i(α +2)i =φ(z0)···φ(zs−1)=f(z0,...,zs−1), where we have used the fact that the summation enclosed in curly braces of the second- to-last line is, by definition, equal to 1 (see (1)). To conclude, we need to find the value of μ. Using Condition #2, the integral of f in the hypercube [0,1]smust be equal to βs,K. That is, we must have 1 0 ν(z(1−z))α/2dzs =βs,K, hence the value of νs,Kgiven in Theorem 2must be βs,K1 1 0(z(1−z))α/2dzs =βs,K s(α +2) 2s(α/2+1).  4 Conclusions and Further Work We have derived in this paper the expected performance of partial match queries in random relaxed quad-K-d trees, for random as well as for fixed queries. Our results show 123 416 La Matematica (2024) 3:385–416 14. Duch, A., Lau, G., Martínez, C.: Fixed partial match queries in quadtrees. In: Fill, J.A., Ward, M.D. (eds.) Proceedings of the 29th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA). Leibniz International Proceedings in Informatics (LIPIcs), vol. 110, pp. 20–12018. Schloß Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl (2018) 15. Duch, A., Martínez, C.: Partial match queries in quad-k-d trees. In: Ward, M.D. (ed.) Proceedings of the 33rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA). Leibniz International Proceedings in Informatics (LIPIcs), vol. 225, pp. 8–1816. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl (2022). https://doi.org/10. 4230/LIPIcs.AofA.2022.8.https://drops.dagstuhl.de/opus/volltexte/2022/16094 16. Bereczky, N., Duch, A., Németh, K., Roura, S.: Quad-k-d trees. In: Proceedings of the 11th Latin American Theoretical Informatics Conference (LATIN). Lecture Notes in Computer Science, vol. 8392, pp. 743–754. Springer, Heidelberg (2014) 17. Duch, A., Estivill-Castro, V., Martínez, C.: Randomized K-dimensional binary search trees. In: Chwa, K.Y., Ibarra, O.H. (eds.) Proceedings of the 9th International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 1533, pp. 199–208. Springer, Heidelberg (1998) 18. Devroye, L., Jabbour, J., Zamora-Cura, C.: Squarish k-d trees. SIAM J. Comput. 30, 1678–1700 (2000) 19. Boyadzhiev, K.N.: Notes on the Binomial Transform. World Scientific, Singapore (2018) 20. Sloane, N.J.A., Plouffe, S.: The Encyclopedia of Integer Sequences. Academic Press, Cambridge (1995) 21. Knuth, D.E.: The Art of Computer Programming: Sorting and Searching, vol. 3, 2nd edn Addison- Wesley, Reading (1998) 22. Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science, 2nd edn. Addison-Wesley, Reading (1994) 23. Flajolet, P., Sedgewick, R.: Mellin transforms and asymptotics: finite differences and rice’s integrals. Theor. Comput. Sci. 144(1&2), 101–124 (1995) 24. Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009) 25. Curien, N., Joseph, A.: Partial match queries in two-dimensional quadtrees: a probabilistic approach. Adv. Appl. Prob. 43(1), 178–194 (2011) 26. Duch, A., Jiménez, R.M., Martínez, C.: Selection by rank in k-dimensional binary search trees. Random Struct. Algorithms 45(1), 14–37 (2014) 27. Duch, A., Martínez, C.: On the average performance of orthogonal range search in multidimensional data structures. J. Algorithms 44(1), 226–245 (2002) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123