Difference between revisions of "Vol-3194/paper49"

From BITPlan ceur-ws Wiki
Jump to navigation Jump to search
(edited by wikiedit)
 
(modified through wikirestore by wf)
Line 1: Line 1:
−
 
+
=Paper=
 
{{Paper
 
{{Paper
−
|wikidataid=Q117344877
+
|id=Vol-3194/paper49
 +
|storemode=property
 +
|title=Investigating Binary Partition Power in Metric Query
 +
|pdfUrl=https://ceur-ws.org/Vol-3194/paper49.pdf
 +
|volume=Vol-3194
 +
|authors=Richard Connor,Alan Dearle,Lucia Vadicamo
 +
|dblpUrl=https://dblp.org/rec/conf/sebd/0001DV22
 
}}
 
}}
 +
==Investigating Binary Partition Power in Metric Query==
 +
<pdf width="1500px">https://ceur-ws.org/Vol-3194/paper49.pdf</pdf>
 +
<pre>
 +
Investigating Binary Partition Power in Metric Query
 +
Richard Connor1 , Alan Dearle1 and Lucia Vadicamo2
 +
1
 +
    School of Computer Science, University of St Andrews, St Andrews, KY16 9SS, Scotland
 +
2
 +
    Institute of Information Science and Technologies, CNR, Pisa, Italy
 +
 +
 +
                                        Abstract
 +
                                        It is generally understood that, as dimensionality increases, the minimum cost of metric query tends
 +
                                        from 𝑂(log 𝑛) to 𝑂(𝑛) in both space and time, where 𝑛 is the size of the data set. With low dimension-
 +
                                        ality, the former is easy to achieve; with very high dimensionality, the latter is inevitable.
 +
                                              We previously described BitPart as a novel mechanism suitable for performing exact metric search in
 +
                                        “high(er)” dimensions. The essential tradeoff of BitPart is that its space cost is linear with respect to the
 +
                                        size of the data, but the actual space required for each object may be small as log2 𝑛 bits, which allows
 +
                                        even very large data sets to be queried using only main memory. Potentially the time cost still scales
 +
                                        with 𝑂(log 𝑛). Together these attributes give exact search which outperforms indexing structures if
 +
                                        dimensionality is within a certain range.
 +
                                              In this article, we reiterate the design of BitPart in this context. The novel contribution is an in-
 +
                                        depth examination of what the notion of “high(er)” means in practical terms. To do this we introduce
 +
                                        the notion of exclusion power, and show its application to some generated data sets across different
 +
                                        dimensions.
 +
 +
                                        Keywords
 +
                                        similarity search, metric indexing, metric search, exclusion power
 +
 +
 +
 +
 +
1. Introduction
 +
Searching a database for objects that are most similar to a query object is a fundamental task in
 +
many database application domains, for example data mining, knowledge discovery, information
 +
extraction, and machine learning [1].
 +
  In [2] we described BitPart as a mechanism suitable for performing exact metric search in
 +
“high(er)” dimensions. While we did not define “high(er)”, the evidence in the paper shows
 +
that it gives its best relative performance for spaces with dimensionality of between 10 and 30.
 +
BitPart’s space cost is linear with respect to the size of the data, but the actual space required
 +
for each object may be small as log2 𝑛 bits, which allows representations of very large data sets
 +
to fit in main memory. Potentially the time cost still scales with 𝑂(log 𝑛) time. Together these
 +
attributes give exact search which outperforms indexing structures as dimensionality increases
 +
within a certain range1 .
 +
 +
 +
SEBD 2022: The 30th Italian Symposium on Advanced Database Systems, June 19-22, 2022, Tirrenia (PI), Italy
 +
" rchc@st-andrews.ac.uk (R. Connor); al@st-andrews.ac.uk (A. Dearle); lucia.vadicamo@isti.cnr.it (L. Vadicamo)
 +
� 0000-0003-4734-8103 (R. Connor); 0000-0002-1157-2421 (A. Dearle); 0000-0001-7182-7038 (L. Vadicamo)
 +
                                      © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
 +
    CEUR
 +
 +
        CEUR Workshop Proceedings (CEUR-WS.org)
 +
    Workshop
 +
    Proceedings
 +
                  http://ceur-ws.org
 +
                  ISSN 1613-0073
 +
 +
 +
 +
 +
                  1
 +
    Note that due to the curse of dimensionality [3] exact metric search rarely outperforms a sequential scan when
 +
dimensionality exceeds 10 [4]. For high-dimensional data, approximate methods are usually employed, e.g [5, 6].
 +
�  The BitPart mechanism uses a set of binary partitions defined over the finite data set, where
 +
each partition is represented by a bitmap. If the total set of bitmaps is perfectly balanced and
 +
perfectly orthogonal, then the probability of a selection of 𝑘 bitmaps being able to exclude an
 +
arbitrary element of the data is 1− 21𝑘 , and the expected number of non-excluded values becomes
 +
very small if 𝑘 ≈ log2 𝑛. While we can come close to achieving this for low-dimensional data,
 +
this becomes increasingly challenging as dimensionality increases.
 +
  In [2] two issues are noted as requiring further investigation. The first is how to select
 +
appropriate pivots in order to find orthogonal exclusion partitions. The second is the interaction
 +
between partition balance and the efficacy of exclusion; this is the subject of this article.
 +
  To do this we introduce the notion of exclusion power, and show its application to some
 +
generated data sets across different dimensions. Exclusion power provides the ability to: fun-
 +
damentally understand the exclusions that are possible in different datasets, to understand
 +
when one approach will outperform another and, to tune the BitPart algorithm to optimally
 +
accommodate data sets of different dimensions.
 +
  The novel contribution of this article is the quantification of exclusion power, which can be
 +
measured for a given binary partition structure with respect to a balancing factor 𝜏 . We observe
 +
that, in low dimensions, partitions are best balanced evenly, approximately splitting the search
 +
space into two equal parts. In higher dimensions however such balanced partitions perform
 +
very badly, and highly skewed partitions have much greater power. We are not aware of any
 +
previous work which attempts to quantify this effect, although it is well known within the
 +
“folklore” of metric search researchers.
 +
 +
 +
2. Formal Context
 +
Formally we are interested in searching a (large) finite set of objects 𝑆 which is a subset of
 +
an infinite set 𝑈 , where (𝑈, 𝑑) is a metric space [1]. The general requirement is to efficiently
 +
find members of 𝑆 which are similar to an arbitrary member of 𝑈 given as a query, where
 +
the distance function 𝑑 gives the only way by which any two objects may be compared. The
 +
simplest type of similarity query is the range search query: for some threshold 𝑡, based on a
 +
query 𝑞 ∈ 𝑈 , the solution set is 𝒬(𝑞, 𝑡) = {𝑠 ∈ 𝑆| 𝑑(𝑞, 𝑠) ≤ 𝑡}.
 +
  The essence of metric search is to spend time pre-processing the finite set 𝑆 (i.e., indexing
 +
it) so that solutions to queries can be efficiently calculated. In all cases distances between
 +
members of 𝑆 and selected reference objects (pivot) are calculated during pre-processing. At
 +
query time the relative distances between the query and the same pivot objects can be used to
 +
make deductions about which data values may, or may not, be candidate solutions to the query.
 +
  Many metric indexes employ binary partitions of the space 𝑈 , i.e., partitions of the form
 +
𝒫 = {𝒫0 , 𝒫1 } where 𝒫0 ∪ 𝒫1 = 𝑈 and 𝒫0 ∩ 𝒫1 = ∅. In the context of metric search, binary
 +
partitions are defined by partition rules that typically rely on computing the distance 𝑑 of the
 +
data objects to a set of pivots. Notable examples include ball and sheet partitioning (see, e.g.,
 +
Figure 1). A ball partition is defined by a pivot 𝑝 ∈ 𝑈 and a covering radius 𝜏 ∈ R+ , so that
 +
 +
                𝒫0 = {𝑢 ∈ 𝑈 | 𝑑(𝑢, 𝑝) > 𝜏 }      𝒫1 = {𝑢 ∈ 𝑈 | 𝑑(𝑢, 𝑝) ≤ 𝜏 }
 +
 +
A sheet partition is defined by two pivots 𝑝1 , 𝑝0 ∈ 𝑈 so that the boundary of the partition
 +
�                                        𝒫0                𝒫1            𝒫0
 +
                                  𝒫1
 +
                                𝑝 𝜏                      𝑝1
 +
                                                                    𝑝0
 +
 +
 +
                        (a) Ball Partitioning          (b) Sheet Partitioning
 +
Figure 1: Examples of a Ball Partitioning defined by a pivot 𝑝 ∈ 𝑈 and a covering radius 𝜏 ∈ R+ , and
 +
a Sheet Partitioning associated to two pivots 𝑝1 , 𝑝0 ∈ 𝑈 .
 +
 +
 +
regions is the hyperplane equidistant from the two reference objects:
 +
 +
        𝒫0 = {𝑢 ∈ 𝑈 | 𝑑(𝑢, 𝑝1 ) > 𝑑(𝑢, 𝑝0 )}        𝒫1 = {𝑢 ∈ 𝑈 | 𝑑(𝑢, 𝑝1 ) ≤ 𝑑(𝑢, 𝑝0 )}
 +
 +
Informally we refer to 𝒫0 as "outside" and 𝒫1 as "inside".
 +
  Under certain circumstances it is possible to deduce that, for a given query, one of the
 +
subsets of the partition cannot (or conversely must) contain solutions to the query. Typically,
 +
the triangle inequality and the distances to the pivots are exploited to determine bounds on
 +
distances between data objects (distance constraints), which are used at query time for excluding
 +
certain regions from the searching process.
 +
  The exclusion of a region of a partition occurs when the query ball does not intersect the
 +
partition boundary. For a ball region, the condition for non-intersection of the query ball and
 +
the boundary is
 +
                                        |𝑑(𝑝, 𝑞) − 𝜏 | > 𝑡                                    (1)
 +
For a sheet region, the non-intersection condition is
 +
 +
                                    |𝑑(𝑝1 , 𝑞) − 𝑑(𝑝0 , 𝑞)| > 2𝑡                                (2)
 +
 +
If the respective non-intersection condition occurs, the implication is that any possible solution
 +
to the query lies on one or other side of the partition boundary, and therefore either 𝒫0 or 𝒫1
 +
may be excluded from the search for solutions.
 +
 +
 +
3. The BitPart Mechanism
 +
The core of the technique is to define a large set of binary partitions over the original space;
 +
the data is stored as a set of bitmaps according to containment with these regions. At query
 +
time, the query is assessed against this containment information, but without reference to the
 +
original data representation.
 +
  For each region, one of three possible conditions may be determined: (a) the solution set
 +
𝒬(𝑞, 𝑡) must be fully contained in the region, or (b) there is no intersection between the region
 +
and the solution set, or (c) neither of these is the case. In either case (a) or (b), the containment
 +
information stored may be useful with respect to solving the query, and is used as part of the
 +
query computation. In case (c) however the containment information is of no value, and is not
 +
�                                                          Point        Partition bitmaps
 +
                  𝑠6
 +
                                                                    𝒜    ℬ 𝒞 𝒟 ℰ ℱ
 +
        𝑝1          𝑡    𝑝2  𝑠5
 +
              𝑠1 𝑞                                        𝑠1      1    1 0 1 1 0
 +
                                          𝑞𝑡              𝑠2      1    0 0 0 1 1
 +
                      𝑠3
 +
          𝑝3      𝑠2 𝑝                                    𝑠3      0    0 0 0 0 0
 +
                      4
 +
                                                          𝑠4      0    0 0 1 0 1
 +
                                                          𝑠5      0    1 0 1 0 0
 +
                          𝑠3                              𝑠6      1    1 0 1 0 0
 +
        𝒜1 ℬ1 𝒞1 𝒟1 ℰ1 ℱ1                                𝒬(𝑞, 𝑡)  -    1 0 1        -  0
 +
                (a)                    (b)                              (c)
 +
Figure 2: (a) A partitioning of a data space along with a query 𝑞 with threshold 𝑡; (b) the regions
 +
containing the solution set; (c) the data representation according to containment of regions.
 +
 +
 +
 +
 +
accessed as a part of the computation. This approach maximises the effectiveness of memory
 +
used for calculation against the original data representation: the amount of memory required
 +
depends on the cardinality of the original data, but not on the size of its individual objects.
 +
 +
An Example. Figure 2 shows a simple example within the 2D plane, comprising four reference
 +
objects 𝑝1 to 𝑝4 and a set of six regions defined by them. The regions are respectively: 𝒜1 , the
 +
area to the left of the line between 𝑝1 and 𝑝2 ; ℬ1 , the area above the line between 𝑝1 and 𝑝3 ;
 +
and the areas within the variously sized circles drawn around each 𝑝1 to 𝑝4 , labeled 𝒞1 , 𝒟1 , ℰ1
 +
and ℱ1 respectively. Note that each regional boundary defines a binary partition of the total
 +
space of the form 𝒫 = {𝒫1 , 𝒫0 }, where 𝒫0 = 𝑈 ∖ 𝒫1 . Thus in Figure 2, six binary partitions
 +
(𝒜 = {𝒜1 , 𝒜0 }, ℬ = {ℬ1 , ℬ0 }, 𝒞 = {𝒞1 , 𝒞0 }, etc) are considered. For each partition 𝒫 we
 +
generate a bitmap of 𝑛 bits, where 𝑛 is the number of data points, which stores the logical
 +
containment information of each data object 𝑠𝑖 , that is 1 if 𝑠𝑖 ∈ 𝒫1 and 0 if 𝑠𝑖 ∈ / 𝒫1 (Figure 2c).
 +
Thus a bit being set (to 1) corresponds to that object being in the region and a member of 𝑃1 .
 +
  Figure 2a also shows a range query 𝑞 drawn with a threshold 𝑡. It can be seen that all solutions
 +
to this query must lie within the area highlighted in Figure 2b. The circle around the query
 +
intersects with two regional boundaries (𝒜1 and ℰ1 ), and so no information is available with
 +
respect to these; however it is completely contained within two of the defined regions (ℬ1 and
 +
𝒟1 ), and fails to intersect with the final two (𝒞1 and ℱ1 ). Such containment and intersection is
 +
derivable only from the measurement of distances between the query and the reference objects,
 +
the definition of the regions, and the search radius. Here for example the possible solution area
 +
shown is determined using only the four distance calculations 𝑑(𝑞, 𝑝1 ).. 𝑑(𝑞, 𝑝4 ). It can be seen
 +
that the only possible solutions to the query are those which match on all non-intersecting fields;
 +
in this case, the objects 𝑠1 , 𝑠5 and 𝑠6 depicted in Figure 2. This is equivalent to the Conjunctive
 +
Normal Form (CNF) expression ℬ ∧ ¬𝒞 ∧ 𝒟 ∧ ¬ℱ. This expression covers the set of all possible
 +
solutions to the query and hints at how the data can be stored using bit vectors.
 +
�3.1. Data structures
 +
Before describing the query algorithm, we describe the data structures used and how they are
 +
initialised. A set of enumerated pivots 𝑝1 to 𝑝𝑚 is selected from 𝑆. We define a set of binary
 +
partitions within 𝑈 , each of the form 𝒫 = {𝒫0 , 𝒫1 }, defined using the distance function 𝑑.
 +
There may be many more  (︀ )︀ regions than reference objects; for example a set of 𝑚 reference
 +
objects defines at least 𝑚 2 sheet regions, plus 𝑚 ball regions.
 +
  We now define the notion of an exclusion zone (EZ) as a containment map of 𝑆 based on a
 +
given partition; this is the information we will use at query time to perform exclusions and
 +
derive a candidate set of solutions. We impose an ordering on 𝑆, then for each 𝑠𝑖 map whether
 +
it is a member of the region 𝒫1 or otherwise. This logical containment information is best
 +
stored in a bitmap of 𝑛 bits, where 𝑛 = |𝑆|. One such exclusion zone is generated per partition.
 +
 +
3.2. Overview of the Query Algorithm
 +
The query process comprises three distinct phases:
 +
  Phase 1 in which the query is checked against the regional definitions, and the two types of
 +
regions with non-intersecting boundaries are identified. Initially, the distance from the query 𝑞
 +
to each pivot 𝑝𝑖 is measured. For each partition, it can be established if the query ball intersects
 +
with the boundary of the partition. If there is no intersection, any solution to the query must lie
 +
on one or other side of the partition’s boundary, so the exclusion zone is brought into the query
 +
calculation in one of two sets depending on whether the query solutions are fully contained
 +
within 𝒫1 or 𝒫0 . We name these sets of bitmaps 𝐵1 and 𝐵0 , which are carried forwards to the
 +
computation in Phase 2.
 +
  Phase 2 in which the regions identified are used to conduct a series of logical operations,
 +
thus identifying a set of candidate solutions for the query.
 +
  The second phase comprises the manipulation of the bitmaps deriving from the first phase
 +
to identify a set of candidate solutions. This may be efficiently achieved by a series of bitwise
 +
operations over these bitmaps2 . It can be seen now that any solution is guaranteed to be
 +
identifiable from the bitmap deriving from the bitwise calculation:
 +
                                  ⎛      ⎞ ⎛ ⎛            ⎞⎞
 +
                                    ⋀︁                ⋁︁
 +
                                  ⎝      𝑏⎠ ∧ ⎝¬ ⎝        𝑏⎠⎠                                  (3)
 +
                                      𝑏∈𝐵1              𝑏∈𝐵0
 +
 +
  Phase 3 in which the candidate solutions are checked against the original data set to identify
 +
the exact solution to the query. This requires a sequential scan of the single bitmap resulting
 +
from Phase 2 and checking the data corresponding to any remaining set bits using the original
 +
space and distance metric in order to produce an exact solution to the query.
 +
 +
 +
 +
 +
    2
 +
    On modern processors many of these bitwise operations can be performed in single instructions, each of
 +
which may be performed in parallel.
 +
�4. Partition analysis
 +
To unify our treatment of different kinds of binary partitions with their associated distance
 +
constraints, we introduce the concept of a binary partition characterised by a single partition
 +
function 𝑓 : 𝑈 → R and a balancing factor 𝜏 ∈ R with the following properties:
 +
 +
Property 1: 𝒫0 = {𝑠 ∈ 𝑈 |𝑓 (𝑠) > 𝜏 } and 𝒫1 = {𝑠 ∈ 𝑈 |𝑓 (𝑠) ≤ 𝜏 }
 +
 +
Property 2: 𝑑(𝑠, 𝑠′ ) ≥ |𝑓 (𝑠) − 𝑓 (𝑠′ )| for all 𝑠, 𝑠′ ∈ 𝑈 (the distance lower-bound property)
 +
 +
  Note that if 𝑓 (𝑠) = 𝜏 , then 𝑠 is on the partition boundary and by convention we include the
 +
partition boundary in 𝒫1 . The function 𝑓 is used both for determining the regions 𝒫0 , 𝒫1 , and
 +
for deriving the exclusion rules to be used at query time. By exploiting the distance lower-bound
 +
provided by the function 𝑓 , we have that |𝑓 (𝑞) − 𝜏 | > 𝑡 is a sufficient condition to exclude one
 +
of the two partitions from the search. Specifically,
 +
 +
    • if 𝑓 (𝑞) ≤ 𝜏 − 𝑡 then 𝒬(𝑞, 𝑡) ⊂ 𝒫1 and 𝒫0 can be excluded
 +
    • if 𝑓 (𝑞) > 𝜏 + 𝑡 then 𝒬(𝑞, 𝑡) ⊂ 𝒫0 and 𝒫1 can be excluded
 +
 +
Note that different functions 𝑓 may be used to determine the same regions 𝒫0 , 𝒫1 but with
 +
different distance lower-bounds, and thus different exclusion rules. For example, let’s consider
 +
                                                                                        2        2
 +
                                                                                    1 ) −𝑑(𝑠,𝑝0 )
 +
the Euclidean space (R𝑛 , ℓ2 ), 𝜏 = 0, 𝑓1 (𝑠) = 𝑑(𝑠,𝑝1 )−𝑑(𝑠,𝑝
 +
                                                        2
 +
                                                              0)
 +
                                                                  and 𝑓2 (𝑠) = 𝑑(𝑠,𝑝2𝑑(𝑝  1 ,𝑝0 )
 +
                                                                                                    for
 +
two fixed pivot 𝑝1 and 𝑝0 . Both the functions 𝑓1 and 𝑓2 produce the same sheet partitioning,
 +
i.e., 𝒫1 = {𝑠 ∈ R𝑛 |𝑑(𝑠, 𝑝1 ) ≤ 𝑑(𝑠, 𝑝0 )} and 𝒫0 = {𝑠 ∈ R𝑛 |𝑑(𝑠, 𝑝1 ) > 𝑑(𝑠, 𝑝0 )}. However, in
 +
[7] we proved that the exclusion rule determined by 𝑓1 (Hyperbolic exclusion) is weaker than
 +
the one determined by 𝑓2 (Hilbert Exclusion), and the latter is valid only on the large class of
 +
Supermetric Spaces [8].
 +
  In the following we show how general ball partitioning and sheet partitioning can be described
 +
within this formalism.
 +
 +
Ball Partitions A ball partition can be characterised by the function 𝑓 (𝑠) = 𝑑(𝑠, 𝑝) and
 +
the constant 𝜏 . In this case 𝒫1 = {𝑠 ∈ 𝑈 |𝑓 (𝑠) = 𝑑(𝑠, 𝑝) ≤ 𝜏 }, and 𝒫0 = {𝑠 ∈ 𝑈 |𝑓 (𝑠) =
 +
𝑑(𝑠, 𝑝) > 𝜏 }, so Property 1 is clear. Properties 2 follows from the triangle inequality:
 +
 +
                𝑑(𝑠, 𝑝) ≤ 𝑑(𝑠, 𝑠′ ) + 𝑑(𝑠′ , 𝑝),  and 𝑑(𝑠′ , 𝑝) ≤ 𝑑(𝑠′ , 𝑠) + 𝑑(𝑠, 𝑝)
 +
 +
which give that 𝑑(𝑠, 𝑠′ ) ≥ |𝑑(𝑠, 𝑝) − 𝑑(𝑠′ , 𝑝)| = |𝑓 (𝑠) − 𝑓 (𝑠′ )| for any 𝑠, 𝑠′ ∈ 𝑈 .
 +
  The balance of the partition is affected by selecting different values for 𝜏 which we refer to
 +
as different balances.
 +
 +
Sheet Partitions Sheet partitions are defined with respect to two reference points 𝑝1 and 𝑝0 .
 +
Usually, a simple binary partition is defined according to whichever of 𝑝1 and 𝑝0 is the nearer
 +
value with respect to the metric 𝑑. However it has been noted [9, 10] that such partitions may
 +
also be subject to a balancing factor 𝛼, so that
 +
 +
  𝒫1    =    {𝑠 ∈ 𝑈 | 𝑑(𝑠, 𝑝1 ) ≤ 𝑑(𝑠, 𝑝0 ) + 𝛼},𝒫0      =    {𝑠 ∈ 𝑈 | 𝑑(𝑠, 𝑝1 ) > 𝑑(𝑠, 𝑝0 ) + 𝛼}
 +
�  In this case, we can use 𝑓 (𝑠) = (𝑑(𝑠, 𝑝1 ) − 𝑑(𝑠, 𝑝0 ))/2 which gives property 1 above for the
 +
constant 𝜏 = 𝛼/2. Moreover from the triangle inequality of the space we have that
 +
 +
                𝑑(𝑠, 𝑝1 ) ≤ 𝑑(𝑠, 𝑠′ ) + 𝑑(𝑠′ , 𝑝1 )    and 𝑑(𝑠′ , 𝑝0 ) ≤ 𝑑(𝑠, 𝑠′ ) + 𝑑(𝑠, 𝑝0 )
 +
                                                                          ′        ′
 +
for any 𝑠, 𝑠′ ∈ 𝑈 , which gives 𝑑(𝑠, 𝑠′ ) ≥ 𝑑(𝑠,𝑝1 )−𝑑(𝑠,𝑝0 )−𝑑(𝑠
 +
                                                              2
 +
                                                                  ,𝑝1 )+𝑑(𝑠 ,𝑝0 )
 +
                                                                                  = 𝑓 (𝑠) − 𝑓 (𝑠′ ). By
 +
symmetry, we also have 𝑑(𝑠, 𝑠′ ) > 𝑓 (𝑠′ ) − 𝑓 (𝑠), therefore 𝑑(𝑠, 𝑠′ ) > |𝑓 (𝑠) − 𝑓 (𝑠′ )|.
 +
  Like ball partitions, the balance of the partition is affected by selecting different values for 𝜏 .
 +
 +
4.1. Exclusion power
 +
The exclusion power of a partition gives a quantification of the effectiveness of that partition
 +
with respect to a given metric search task. It is clear that this is likely to be quite different
 +
depending on the partition type, the selection of reference objects, and the chosen value 𝜏 .
 +
  The meaning of exclusion power is based on the probability, for arbitrarily selected objects
 +
𝑞 and 𝑠, and a distance 𝑡, of being able to demonstrate that 𝑑(𝑞, 𝑠) > 𝑡. As we will show, for
 +
low dimensional spaces the maximum exclusion power of any partition structure is likely to
 +
coincide with a value of 𝜏 which causes the partition to bisect the finite search space 𝑆, i.e.
 +
|𝒫0 | ≈ |𝒫1 |. However as we will see, in higher dimensional spaces this may be a very bad
 +
choice.
 +
  For a range query 𝒬(𝑞, 𝑡) we define the exclusion power of the partition 𝒫 = {𝒫0 , 𝒫1 } as
 +
the probability of excluding one generic element 𝑠 on the basis only of the data partition to
 +
which it belongs:
 +
 +
              𝑃 (𝑠 ∈ 𝒫0 ) · 𝑃 (𝒬(𝑞, 𝑡) ∩ 𝒫0 = ∅) + 𝑃 (𝑠 ∈ 𝒫1 ) · 𝑃 (𝒬(𝑞, 𝑡) ∩ 𝒫1 = ∅)                            (4)
 +
                    = 𝑃 (𝑠 ∈ 𝒫0 ) · 𝑃 (𝒬(𝑞, 𝑡) ⊂ 𝒫1 ) + 𝑃 (𝑠 ∈ 𝒫1 ) · 𝑃 (𝒬(𝑞, 𝑡) ⊂ 𝒫0 )                        (5)
 +
 +
  The exact calculation of the probabilities 𝑃 (𝒬(𝑞, 𝑡) ⊂ 𝒫𝑖 ), for 𝑖 = 0 or 1, is not straightfor-
 +
ward for a general binary partition in a metric space, however, if we know that the partition
 +
can be characterised by a function 𝑓 and a balancing factor 𝜏 , we can estimate a lower-bound
 +
of these probabilities3 and thus obtain an approximation of the exclusion power as
 +
 +
                𝑃 (𝑓 (𝑠) > 𝜏 ) · 𝑃 (𝑓 (𝑞) ≤ 𝜏 − 𝑡) + 𝑃 (𝑓 (𝑠) ≤ 𝜏 ) · 𝑃 (𝑓 (𝑞) > 𝜏 + 𝑡)                        (6)
 +
 +
  Let CDF(𝑥) be the cumulative distribution function of 𝑓 (𝑠) for 𝑠 ∈ 𝑆 then the exclusion
 +
power can be expressed as
 +
 +
                𝑔(𝜏, 𝑡) = (1 − CDF(𝜏 )) · CDF(𝜏 − 𝑡) + CDF(𝜏 ) · (1 − CDF(𝜏 + 𝑡))                              (7)
 +
 +
where 𝜏 is the partition balancing factor and 𝑡 in the query distance threshold
 +
  Estimates of exclusion power can be made with respect to a representative sample of the data
 +
set, and indeed of the query set if that is different4 . A large enough sample will give a good
 +
estimate of the probability of an individual datum falling within each of the subsets.
 +
    3
 +
      In general, 𝑓 (𝑞) ≤ 𝜏 − 𝑡 ⇒ 𝒬(𝑞, 𝑡) ⊂ 𝒫1 , therefore 𝑃 (𝑓 (𝑞) ≤ 𝜏 − 𝑡) ≤ 𝑃 (𝒬(𝑞, 𝑡) ⊂ 𝒫1 ). Similarly, 𝑓 (𝑞) >
 +
𝜏 + 𝑡 ⇒ 𝒬(𝑞, 𝑡) ⊂ 𝒫0 , and thus 𝑃 (𝑓 (𝑞) > 𝜏 + 𝑡) ≤ 𝑃 (𝒬(𝑞, 𝑡) ⊂ 𝒫0 ). The equality holds for some cases, e.g., the
 +
ball partitioning, where it can be proved that 𝑓 (𝑞) ≤ 𝜏 − 𝑡 ⇔ 𝒬(𝑞, 𝑡) ⊂ 𝒫1 and 𝑓 (𝑞) > 𝜏 + 𝑡 ⇔ 𝒬(𝑞, 𝑡) ⊂ 𝒫𝑜 .
 +
    4
 +
      We assume from here on that the distribution of data and query is the same
 +
�5. Power graphs
 +
To understand the effect of different values of 𝜏 an exclusion power graph may be constructed
 +
which is plotted across the range of 𝜏 for a fixed value of 𝑡. This allows the optimum value of 𝜏
 +
to be deduced for a range query with threshold 𝑡.
 +
  We illustrate the construction of power graphs for 5 dimensional data in Section 5.1 and for
 +
20 dimensional data in 5.2.
 +
 +
5.1. Example: single-pivot ball partitioning over 5 dimensional data
 +
 +
                          0.09                                                                          0.2
 +
 +
                          0.08                                                                          0.18
 +
  Normalized Frequency
 +
 +
 +
 +
 +
                                                                                Normalized Frequency
 +
                                                                                                        0.16
 +
                          0.07
 +
                                                                                                        0.14
 +
                          0.06
 +
                                                                                                        0.12
 +
                          0.05
 +
                                                                                                        0.1
 +
                          0.04
 +
                                                                                                        0.08
 +
                          0.03
 +
                                                                                                        0.06
 +
                          0.02
 +
                                                                                                        0.04
 +
 +
                          0.01                                                                          0.02
 +
 +
                            0                                                                            0
 +
                                0.2  0.4  0.6    0.8  1  1.2  1.4  1.6                                0.14  0.16  0.18    0.2  0.22  0.24  0.26  0.28
 +
 +
                                      Distance from ball centre                                                  Distance of a query from its 5NN
 +
 +
                                                  (a)                                                                              (b)
 +
Figure 3: Typical inter-point and query threshold distances from 5-dimensional Euclidean data
 +
 +
 +
  Figure 3 shows histograms of two sets of sampled distances from a randomly generated
 +
five-dimensional Euclidean space. The left-hand side of the figure shows the distribution of
 +
5,000 witness points in terms of distance from a randomly selected pivot point, 𝑝. The right-hand
 +
side shows the distribution of the 5NN (fifth nearest-neighbour) distances for a set of 1,000
 +
queries; this distance representing a query threshold necessary to return a small proportion of
 +
the data, and thus useful values for 𝑡.
 +
  Based on this information, we will pick example values of 𝜏^ = 0.89 and ^𝑡 = 0.19, being the
 +
median values in the distributions of 𝜏 and 𝑡 values, respectively. We can now consider the
 +
exclusion power of these values applied to the partition thus formed, centered around 𝑝.
 +
  The left-hand side of Figure 4 shows the Cumulative Probability Density function (CDF) with
 +
the X-axis values of 𝜏^, 𝜏^ − ^𝑡, and 𝜏^ + ^𝑡 highlighted. Given that 𝜏^ has been selected as the median
 +
distance from 𝑝, the value of the CDF at 𝜏^ is 0.5. Therefore if an exclusion occurs, half of the
 +
data set will be excluded and its exclusion power is: CDF(𝜏^ − ^𝑡) · 0.5 + (1 − CDF(𝜏^ + ^𝑡)) · 0.5.
 +
The more general form of this equation (i.e., Equation 7) hints how the exclusion power can
 +
be displayed for a single partition, as shown on the right-hand side of Figure 4. Here, for a
 +
fixed value of 𝑡 (again 0.19), the power of the partition is calculated over the whole range of
 +
distances that have been measured between the witness points and the point 𝑝. As can be seen,
 +
the maximum power is achieved when the partition is split at the median distance, i.e. 𝜏^ = 0.89
 +
in this example. With this partition, and this value of 𝜏 , the probability of excluding an arbitrary
 +
datum for an arbitrary query is around 0.21.
 +
�                          1                                                                                      0.25
 +
 +
                        0.9
 +
 +
                        0.8                                                                                      0.2
 +
 +
                        0.7
 +
 +
                        0.6                                                                                      0.15
 +
 +
                        0.5
 +
 +
                        0.4                                                                                      0.1
 +
 +
                        0.3
 +
 +
                        0.2                                                                                      0.05
 +
 +
                        0.1
 +
 +
                          0                                                                                        0
 +
                                0      0.2    0.4        0.6        0.8    1      1.2        1.4  1.6              0                          0.2  0.4      0.6      0.8      1    1.2    1.4      1.6        1.8
 +
 +
 +
 +
 +
            (a) CDF of 𝑓 (𝑠) = 𝑑(𝑠, 𝑝) varying 𝑠                                                              (b) Exclusion power graph over 𝜏 (fixing
 +
                                                                                                                  𝑡 = ^𝑡). The exclusion power for 𝜏 = 𝜏^
 +
                                                                                                                  is 0.23.
 +
Figure 4: CDF and Power Graph for 5-dimensional data
 +
 +
 +
5.2. Example: single-pivot ball partitioning over 20 dimensional data
 +
 +
                          0.1                                                                                                                      0.12
 +
 +
                        0.09
 +
                                                                                                                                                    0.1
 +
  Normalized Frequency
 +
 +
 +
 +
 +
                                                                                                                            Normalized Frequency
 +
                        0.08
 +
 +
                        0.07
 +
                                                                                                                                                    0.08
 +
                        0.06
 +
 +
                        0.05                                                                                                                      0.06
 +
 +
                        0.04
 +
                                                                                                                                                    0.04
 +
                        0.03
 +
 +
                        0.02
 +
                                                                                                                                                    0.02
 +
                        0.01
 +
 +
                          0                                                                                                                          0
 +
                                    1  1.2    1.4    1.6        1.8    2  2.2  2.4    2.6                                                            0.9    0.95    1    1.05  1.1  1.15  1.2    1.25    1.3
 +
                                              Distance from ball centre                                                                                          Distance of a query from its 5NN
 +
 +
 +
                                                      (a)                                                                                                                      (b)
 +
Figure 5: Typical inter-point and query threshold distances from 20-dimensional data
 +
 +
 +
  The left-hand side of Figure 5 shows a histogram of 5,000 distances measured with respect to
 +
a randomly selected element 𝑝 of a 20-dimensional uniformly generated Euclidean space. The
 +
right-hand side shows a histogram (for 1,000 queries selected from the same set) of the distances
 +
to the 5th-nearest neighbour with respect to this same set of 5,000 values. Figure 6 shows the
 +
same information in the form of cumulative probability density functions. The left-hand side of
 +
Figure 6 shows the CDF function superimposed with a line corresponding to the medium value
 +
for 𝜏 . The value of t for this data is 1.07.
 +
  Finally, although we have no space here to provide in-depth analysis, Figure 7 shows exclusion
 +
power graphs using sheet partitions over both 5D and 20D spaces. It can be seen that the graph
 +
patterns are quite similar.
 +
�                                                                                  -4
 +
                                                                              10
 +
    1                                                              1.5
 +
 +
    0.9
 +
 +
    0.8
 +
 +
    0.7
 +
                                                                    1
 +
    0.6
 +
 +
    0.5
 +
 +
    0.4
 +
                                                                    0.5
 +
    0.3
 +
 +
    0.2
 +
 +
    0.1
 +
 +
    0                                                              0
 +
          0  0.5  1  1.5  2  2.5  3                                1            1.5  2  2.5  3
 +
 +
 +
 +
 +
(a) CDF of 𝑓 (𝑠) = 𝑑(𝑠, 𝑝) varying 𝑠                          (b) Exclusion power graph over 𝜏 (fix-
 +
                                                                  ing 𝑡 = ^𝑡). The exclusion power
 +
                                                                  for 𝜏 = 𝜏^ is 0
 +
Figure 6: CDF and Power Graph for 20-dimensional data
 +
 +
 +
 +
 +
                        (a) A sheet partition in 5D space    (b) A sheet partition of 20 dimensions
 +
Figure 7: Exclusion Power graphs for sheet partitions in 5 and 20 dimensional Euclidean space
 +
 +
 +
5.3. Use of Exclusion Power analysis
 +
Figures 4 and 6 demonstrate the exclusion power in 5 and 20 Dimensions respectively. In the
 +
5 dimensional case we can observe that setting a 𝜏^ value of 0.89 (close to the mean of the
 +
distribution of measured distances) will work extremely well. With such a value the exclusion
 +
power is maximised. By contrast, choosing the mean in the case of 20D data will work very badly.
 +
As can be seen in Figure 6 such a value is unlikely to result in any successful exclusions. These
 +
diagrams explain behaviour observed by many researchers into metric search that choosing
 +
unbalanced indexing structures often works better for higher dimensional data.
 +
  The establishment of a unified partition interface using 𝑓 and 𝜏 allows similar graphs to be
 +
produced for sheet partitions (e.g., Figure 7). The mechanistic value of these graphs is that the
 +
value or values of 𝜏 corresponding to the maxiumum power can be automatically extracted on
 +
a per-partition basis, and used in an implementation of BitPart. In the case of low dimensional
 +
data a single offset can be used for each ball where as for high(er) dimensional data two offsets
 +
can be used. Furthermore, as described earlier a particular implementation can use as few or as
 +
many exclusion zones that as necessary, as may be predicted by the power value at the optimum
 +
�value.
 +
  In Section 6 these offsets are applied to a BitPart implementation to demonstrate their effect.
 +
 +
 +
6. Experimental Validation using BitPart
 +
 +
 +
 +
 +
                  (a) 5 dimensional space                                (b) 20 dimensional space
 +
Figure 8: Empirical Inverse distances per query for 5D and 20D data for different values of 𝜏 . These
 +
charts plot both ball and sheet partitions, which have different ranges of 𝜏 ; we have therefore nor-
 +
malised these within the offset axis. The Y axis shows the inverse of the number of residual distance
 +
computations, i.e. those not excluded by use of the BitPart mechanism (higher is better).
 +
 +
 +
  In order to validate the above results we ran experiments against a BitPart implementation5
 +
using uniformly generated data in 5 and 20 dimensions with Euclidean distance. Each contained
 +
one million data points, and 1000 queries were executed. In all experiments fixed threshold
 +
distances 𝑡 were used and set to values which correspond to one-millionth of the data volume.
 +
In order to measure exclusion power, the 1000 queries were run 25 times for differing values of
 +
𝜏 for both sheet and ball partitions. The 5D data uses 20 pivot points and(︀ the
 +
                                                                              )︀ 20D data 100.
 +
  In [2] we described how a selection of 𝑚 reference points allows for 𝑚    2 sheet and 𝑚 ball
 +
partitions to be produced. After the above analysis, we used this number for the 5D space, but
 +
in the 20D space we generated twice that number, corresponding to the twin peaks in the power
 +
graphs. Note that this does not require any extra distance calculations at query time, as the
 +
number of reference points is not increased. Furthermore there is not necessarily any increase
 +
in memory usage, as partitions are typically stored in secondary memory and only fetched
 +
when the query ball does not intersect with the partition, which requires only the evaluation of
 +
the 𝑓 function to determine. For each experiment a suitable range is calculated for 𝜏 for both
 +
balls and sheets, ensuring that for all partitions both 𝒫0 and 𝒫1 are non-empty, and the whole
 +
calculation was executed with different values of 𝜏 across this range.
 +
  Results are shown in Figure 8. In order to visualize these results, the number of residual (i.e.
 +
Phase 3) distance calculations per query was measured, this number giving a good proxy for the
 +
value of the exclusion mechanism. The plots show the inverse of these counts. Peaks similar to
 +
those shown in the power graphs in Figures 4 and 6 can be seen in these experimental results.
 +
  5
 +
      The experimental code may be found in https://bitbucket.org/richardconnor/metricbitblaster.git
 +
�7. Conclusions
 +
In this paper, we have reiterated the design of the BitPart indexing and query mechanisms.
 +
The novel contribution of this paper is an exposition of how dimensionality effects the efficacy
 +
of this and other metric search mechanisms. We have demonstrated how the distribution of
 +
distances changes with the dimensionality of the data and how in turn this affects the ability
 +
to perform effective exclusions and thus efficient queries. In particular we have explored the
 +
notion of balance and how that affects exclusion. To do this we have introduced the notion of
 +
exclusion power, and shown its application to some Euclidean data sets in different dimensions.
 +
  This analysis gives fundamental insights into what data can be queried effectively and
 +
what cannot. Furthermore it demonstrates how index and search algorithms can be tuned to
 +
compensate for data sets of arbitrary dimensions.
 +
  We have demonstrated that the phenomena explored in mathematical terms are manifested
 +
in synthetically generated data sets and queries over them using an implementation of BitPart.
 +
We believe that the results in this paper may be applied to other metric search and indexing
 +
mechanisms. Our future plans include investigating these phenomena in real life data sets and
 +
exploring the outstanding issue of partition orthogonality.
 +
 +
 +
References
 +
[1] P. Zezula, G. Amato, V. Dohnal, M. Batko, Similarity search: the metric space approach,
 +
    volume 32, Springer Science & Business Media, 2006.
 +
[2] A. Dearle, R. Connor, Bitpart: Exact metric search in high(er) dimensions, Information
 +
    Systems 95 (2021) 101493.
 +
[3] V. Pestov, Indexability, concentration, and vc theory, Journal of Discrete Algorithms 13
 +
    (2012) 2–18.
 +
[4] R. Weber, H.-J. Schek, S. Blott, A quantitative analysis and performance study for similarity-
 +
    search methods in high-dimensional spaces, in: Proc. of 24th VLDB, volume 98, Morgan
 +
    Kaufmann, 1998, pp. 194–205.
 +
[5] G. Amato, C. Gennaro, P. Savino, MI-File: Using inverted files for scalable approximate
 +
    similarity search, Multimedia Tools and Applications (2014) 1333–1362.
 +
[6] D. Novak, M. Batko, P. Zezula, Metric index: An efficient and scalable solution for precise
 +
    and approximate similarity search, Information Systems 36 (2011) 721–733.
 +
[7] R. Connor, F. A. Cardillo, L. Vadicamo, F. Rabitti, Hilbert exclusion: improved metric
 +
    search through finite isometric embeddings, ACM Transactions on Information Systems
 +
    (TOIS) 35 (2016) 1–27.
 +
[8] R. Connor, L. Vadicamo, F. A. Cardillo, F. Rabitti, Supermetric search, Information Systems
 +
    80 (2019) 108–123.
 +
[9] R. Connor, Reference point hyperplane trees, in: International Conference on Similarity
 +
    Search and Applications, Springer, 2016, pp. 65–78.
 +
[10] J. Lokoč, T. Skopal, On applications of parameterized hyperplane partitioning, in: Proceed-
 +
    ings of the Third International Conference on SImilarity Search and APplications, 2010,
 +
    pp. 131–132.
 +
�
 +
</pre>

Revision as of 17:51, 30 March 2023

Paper

Paper
edit
description  
id  Vol-3194/paper49
wikidataid  →Q117344877
title  Investigating Binary Partition Power in Metric Query
pdfUrl  https://ceur-ws.org/Vol-3194/paper49.pdf
dblpUrl  https://dblp.org/rec/conf/sebd/0001DV22
volume  Vol-3194→Vol-3194
session  →

Investigating Binary Partition Power in Metric Query

load PDF 

Investigating Binary Partition Power in Metric Query
Richard Connor1 , Alan Dearle1 and Lucia Vadicamo2
1
    School of Computer Science, University of St Andrews, St Andrews, KY16 9SS, Scotland
2
    Institute of Information Science and Technologies, CNR, Pisa, Italy


                                         Abstract
                                         It is generally understood that, as dimensionality increases, the minimum cost of metric query tends
                                         from 𝑂(log 𝑛) to 𝑂(𝑛) in both space and time, where 𝑛 is the size of the data set. With low dimension-
                                         ality, the former is easy to achieve; with very high dimensionality, the latter is inevitable.
                                              We previously described BitPart as a novel mechanism suitable for performing exact metric search in
                                         “high(er)” dimensions. The essential tradeoff of BitPart is that its space cost is linear with respect to the
                                         size of the data, but the actual space required for each object may be small as log2 𝑛 bits, which allows
                                         even very large data sets to be queried using only main memory. Potentially the time cost still scales
                                         with 𝑂(log 𝑛). Together these attributes give exact search which outperforms indexing structures if
                                         dimensionality is within a certain range.
                                              In this article, we reiterate the design of BitPart in this context. The novel contribution is an in-
                                         depth examination of what the notion of “high(er)” means in practical terms. To do this we introduce
                                         the notion of exclusion power, and show its application to some generated data sets across different
                                         dimensions.

                                         Keywords
                                         similarity search, metric indexing, metric search, exclusion power




1. Introduction
Searching a database for objects that are most similar to a query object is a fundamental task in
many database application domains, for example data mining, knowledge discovery, information
extraction, and machine learning [1].
   In [2] we described BitPart as a mechanism suitable for performing exact metric search in
“high(er)” dimensions. While we did not define “high(er)”, the evidence in the paper shows
that it gives its best relative performance for spaces with dimensionality of between 10 and 30.
BitPart’s space cost is linear with respect to the size of the data, but the actual space required
for each object may be small as log2 𝑛 bits, which allows representations of very large data sets
to fit in main memory. Potentially the time cost still scales with 𝑂(log 𝑛) time. Together these
attributes give exact search which outperforms indexing structures as dimensionality increases
within a certain range1 .


SEBD 2022: The 30th Italian Symposium on Advanced Database Systems, June 19-22, 2022, Tirrenia (PI), Italy
" rchc@st-andrews.ac.uk (R. Connor); al@st-andrews.ac.uk (A. Dearle); lucia.vadicamo@isti.cnr.it (L. Vadicamo)
� 0000-0003-4734-8103 (R. Connor); 0000-0002-1157-2421 (A. Dearle); 0000-0001-7182-7038 (L. Vadicamo)
                                       © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR

        CEUR Workshop Proceedings (CEUR-WS.org)
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073




                  1
    Note that due to the curse of dimensionality [3] exact metric search rarely outperforms a sequential scan when
dimensionality exceeds 10 [4]. For high-dimensional data, approximate methods are usually employed, e.g [5, 6].
�   The BitPart mechanism uses a set of binary partitions defined over the finite data set, where
each partition is represented by a bitmap. If the total set of bitmaps is perfectly balanced and
perfectly orthogonal, then the probability of a selection of 𝑘 bitmaps being able to exclude an
arbitrary element of the data is 1− 21𝑘 , and the expected number of non-excluded values becomes
very small if 𝑘 ≈ log2 𝑛. While we can come close to achieving this for low-dimensional data,
this becomes increasingly challenging as dimensionality increases.
   In [2] two issues are noted as requiring further investigation. The first is how to select
appropriate pivots in order to find orthogonal exclusion partitions. The second is the interaction
between partition balance and the efficacy of exclusion; this is the subject of this article.
   To do this we introduce the notion of exclusion power, and show its application to some
generated data sets across different dimensions. Exclusion power provides the ability to: fun-
damentally understand the exclusions that are possible in different datasets, to understand
when one approach will outperform another and, to tune the BitPart algorithm to optimally
accommodate data sets of different dimensions.
   The novel contribution of this article is the quantification of exclusion power, which can be
measured for a given binary partition structure with respect to a balancing factor 𝜏 . We observe
that, in low dimensions, partitions are best balanced evenly, approximately splitting the search
space into two equal parts. In higher dimensions however such balanced partitions perform
very badly, and highly skewed partitions have much greater power. We are not aware of any
previous work which attempts to quantify this effect, although it is well known within the
“folklore” of metric search researchers.


2. Formal Context
Formally we are interested in searching a (large) finite set of objects 𝑆 which is a subset of
an infinite set 𝑈 , where (𝑈, 𝑑) is a metric space [1]. The general requirement is to efficiently
find members of 𝑆 which are similar to an arbitrary member of 𝑈 given as a query, where
the distance function 𝑑 gives the only way by which any two objects may be compared. The
simplest type of similarity query is the range search query: for some threshold 𝑡, based on a
query 𝑞 ∈ 𝑈 , the solution set is 𝒬(𝑞, 𝑡) = {𝑠 ∈ 𝑆| 𝑑(𝑞, 𝑠) ≤ 𝑡}.
   The essence of metric search is to spend time pre-processing the finite set 𝑆 (i.e., indexing
it) so that solutions to queries can be efficiently calculated. In all cases distances between
members of 𝑆 and selected reference objects (pivot) are calculated during pre-processing. At
query time the relative distances between the query and the same pivot objects can be used to
make deductions about which data values may, or may not, be candidate solutions to the query.
   Many metric indexes employ binary partitions of the space 𝑈 , i.e., partitions of the form
𝒫 = {𝒫0 , 𝒫1 } where 𝒫0 ∪ 𝒫1 = 𝑈 and 𝒫0 ∩ 𝒫1 = ∅. In the context of metric search, binary
partitions are defined by partition rules that typically rely on computing the distance 𝑑 of the
data objects to a set of pivots. Notable examples include ball and sheet partitioning (see, e.g.,
Figure 1). A ball partition is defined by a pivot 𝑝 ∈ 𝑈 and a covering radius 𝜏 ∈ R+ , so that

                 𝒫0 = {𝑢 ∈ 𝑈 | 𝑑(𝑢, 𝑝) > 𝜏 }       𝒫1 = {𝑢 ∈ 𝑈 | 𝑑(𝑢, 𝑝) ≤ 𝜏 }

A sheet partition is defined by two pivots 𝑝1 , 𝑝0 ∈ 𝑈 so that the boundary of the partition
�                                         𝒫0                𝒫1             𝒫0
                                  𝒫1
                                 𝑝 𝜏                      𝑝1
                                                                     𝑝0


                        (a) Ball Partitioning           (b) Sheet Partitioning
Figure 1: Examples of a Ball Partitioning defined by a pivot 𝑝 ∈ 𝑈 and a covering radius 𝜏 ∈ R+ , and
a Sheet Partitioning associated to two pivots 𝑝1 , 𝑝0 ∈ 𝑈 .


regions is the hyperplane equidistant from the two reference objects:

         𝒫0 = {𝑢 ∈ 𝑈 | 𝑑(𝑢, 𝑝1 ) > 𝑑(𝑢, 𝑝0 )}        𝒫1 = {𝑢 ∈ 𝑈 | 𝑑(𝑢, 𝑝1 ) ≤ 𝑑(𝑢, 𝑝0 )}

Informally we refer to 𝒫0 as "outside" and 𝒫1 as "inside".
   Under certain circumstances it is possible to deduce that, for a given query, one of the
subsets of the partition cannot (or conversely must) contain solutions to the query. Typically,
the triangle inequality and the distances to the pivots are exploited to determine bounds on
distances between data objects (distance constraints), which are used at query time for excluding
certain regions from the searching process.
   The exclusion of a region of a partition occurs when the query ball does not intersect the
partition boundary. For a ball region, the condition for non-intersection of the query ball and
the boundary is
                                        |𝑑(𝑝, 𝑞) − 𝜏 | > 𝑡                                     (1)
For a sheet region, the non-intersection condition is

                                     |𝑑(𝑝1 , 𝑞) − 𝑑(𝑝0 , 𝑞)| > 2𝑡                                 (2)

If the respective non-intersection condition occurs, the implication is that any possible solution
to the query lies on one or other side of the partition boundary, and therefore either 𝒫0 or 𝒫1
may be excluded from the search for solutions.


3. The BitPart Mechanism
The core of the technique is to define a large set of binary partitions over the original space;
the data is stored as a set of bitmaps according to containment with these regions. At query
time, the query is assessed against this containment information, but without reference to the
original data representation.
   For each region, one of three possible conditions may be determined: (a) the solution set
𝒬(𝑞, 𝑡) must be fully contained in the region, or (b) there is no intersection between the region
and the solution set, or (c) neither of these is the case. In either case (a) or (b), the containment
information stored may be useful with respect to solving the query, and is used as part of the
query computation. In case (c) however the containment information is of no value, and is not
�                                                          Point         Partition bitmaps
                  𝑠6
                                                                    𝒜    ℬ 𝒞 𝒟 ℰ ℱ
         𝑝1           𝑡    𝑝2   𝑠5
               𝑠1 𝑞                                        𝑠1       1    1 0 1 1 0
                                           𝑞𝑡              𝑠2       1    0 0 0 1 1
                      𝑠3
          𝑝3      𝑠2 𝑝                                     𝑠3       0    0 0 0 0 0
                      4
                                                           𝑠4       0    0 0 1 0 1
                                                           𝑠5       0    1 0 1 0 0
                          𝑠3                               𝑠6       1    1 0 1 0 0
         𝒜1 ℬ1 𝒞1 𝒟1 ℰ1 ℱ1                                𝒬(𝑞, 𝑡)   -    1 0 1         -  0
                 (a)                    (b)                               (c)
Figure 2: (a) A partitioning of a data space along with a query 𝑞 with threshold 𝑡; (b) the regions
containing the solution set; (c) the data representation according to containment of regions.




accessed as a part of the computation. This approach maximises the effectiveness of memory
used for calculation against the original data representation: the amount of memory required
depends on the cardinality of the original data, but not on the size of its individual objects.

An Example. Figure 2 shows a simple example within the 2D plane, comprising four reference
objects 𝑝1 to 𝑝4 and a set of six regions defined by them. The regions are respectively: 𝒜1 , the
area to the left of the line between 𝑝1 and 𝑝2 ; ℬ1 , the area above the line between 𝑝1 and 𝑝3 ;
and the areas within the variously sized circles drawn around each 𝑝1 to 𝑝4 , labeled 𝒞1 , 𝒟1 , ℰ1
and ℱ1 respectively. Note that each regional boundary defines a binary partition of the total
space of the form 𝒫 = {𝒫1 , 𝒫0 }, where 𝒫0 = 𝑈 ∖ 𝒫1 . Thus in Figure 2, six binary partitions
(𝒜 = {𝒜1 , 𝒜0 }, ℬ = {ℬ1 , ℬ0 }, 𝒞 = {𝒞1 , 𝒞0 }, etc) are considered. For each partition 𝒫 we
generate a bitmap of 𝑛 bits, where 𝑛 is the number of data points, which stores the logical
containment information of each data object 𝑠𝑖 , that is 1 if 𝑠𝑖 ∈ 𝒫1 and 0 if 𝑠𝑖 ∈ / 𝒫1 (Figure 2c).
Thus a bit being set (to 1) corresponds to that object being in the region and a member of 𝑃1 .
   Figure 2a also shows a range query 𝑞 drawn with a threshold 𝑡. It can be seen that all solutions
to this query must lie within the area highlighted in Figure 2b. The circle around the query
intersects with two regional boundaries (𝒜1 and ℰ1 ), and so no information is available with
respect to these; however it is completely contained within two of the defined regions (ℬ1 and
𝒟1 ), and fails to intersect with the final two (𝒞1 and ℱ1 ). Such containment and intersection is
derivable only from the measurement of distances between the query and the reference objects,
the definition of the regions, and the search radius. Here for example the possible solution area
shown is determined using only the four distance calculations 𝑑(𝑞, 𝑝1 ).. 𝑑(𝑞, 𝑝4 ). It can be seen
that the only possible solutions to the query are those which match on all non-intersecting fields;
in this case, the objects 𝑠1 , 𝑠5 and 𝑠6 depicted in Figure 2. This is equivalent to the Conjunctive
Normal Form (CNF) expression ℬ ∧ ¬𝒞 ∧ 𝒟 ∧ ¬ℱ. This expression covers the set of all possible
solutions to the query and hints at how the data can be stored using bit vectors.
�3.1. Data structures
Before describing the query algorithm, we describe the data structures used and how they are
initialised. A set of enumerated pivots 𝑝1 to 𝑝𝑚 is selected from 𝑆. We define a set of binary
partitions within 𝑈 , each of the form 𝒫 = {𝒫0 , 𝒫1 }, defined using the distance function 𝑑.
There may be many more   (︀ )︀ regions than reference objects; for example a set of 𝑚 reference
objects defines at least 𝑚 2 sheet regions, plus 𝑚 ball regions.
   We now define the notion of an exclusion zone (EZ) as a containment map of 𝑆 based on a
given partition; this is the information we will use at query time to perform exclusions and
derive a candidate set of solutions. We impose an ordering on 𝑆, then for each 𝑠𝑖 map whether
it is a member of the region 𝒫1 or otherwise. This logical containment information is best
stored in a bitmap of 𝑛 bits, where 𝑛 = |𝑆|. One such exclusion zone is generated per partition.

3.2. Overview of the Query Algorithm
The query process comprises three distinct phases:
   Phase 1 in which the query is checked against the regional definitions, and the two types of
regions with non-intersecting boundaries are identified. Initially, the distance from the query 𝑞
to each pivot 𝑝𝑖 is measured. For each partition, it can be established if the query ball intersects
with the boundary of the partition. If there is no intersection, any solution to the query must lie
on one or other side of the partition’s boundary, so the exclusion zone is brought into the query
calculation in one of two sets depending on whether the query solutions are fully contained
within 𝒫1 or 𝒫0 . We name these sets of bitmaps 𝐵1 and 𝐵0 , which are carried forwards to the
computation in Phase 2.
   Phase 2 in which the regions identified are used to conduct a series of logical operations,
thus identifying a set of candidate solutions for the query.
   The second phase comprises the manipulation of the bitmaps deriving from the first phase
to identify a set of candidate solutions. This may be efficiently achieved by a series of bitwise
operations over these bitmaps2 . It can be seen now that any solution is guaranteed to be
identifiable from the bitmap deriving from the bitwise calculation:
                                   ⎛       ⎞ ⎛ ⎛             ⎞⎞
                                     ⋀︁                 ⋁︁
                                   ⎝      𝑏⎠ ∧ ⎝¬ ⎝         𝑏⎠⎠                                  (3)
                                       𝑏∈𝐵1               𝑏∈𝐵0

   Phase 3 in which the candidate solutions are checked against the original data set to identify
the exact solution to the query. This requires a sequential scan of the single bitmap resulting
from Phase 2 and checking the data corresponding to any remaining set bits using the original
space and distance metric in order to produce an exact solution to the query.




    2
    On modern processors many of these bitwise operations can be performed in single instructions, each of
which may be performed in parallel.
�4. Partition analysis
To unify our treatment of different kinds of binary partitions with their associated distance
constraints, we introduce the concept of a binary partition characterised by a single partition
function 𝑓 : 𝑈 → R and a balancing factor 𝜏 ∈ R with the following properties:

Property 1: 𝒫0 = {𝑠 ∈ 𝑈 |𝑓 (𝑠) > 𝜏 } and 𝒫1 = {𝑠 ∈ 𝑈 |𝑓 (𝑠) ≤ 𝜏 }

Property 2: 𝑑(𝑠, 𝑠′ ) ≥ |𝑓 (𝑠) − 𝑓 (𝑠′ )| for all 𝑠, 𝑠′ ∈ 𝑈 (the distance lower-bound property)

   Note that if 𝑓 (𝑠) = 𝜏 , then 𝑠 is on the partition boundary and by convention we include the
partition boundary in 𝒫1 . The function 𝑓 is used both for determining the regions 𝒫0 , 𝒫1 , and
for deriving the exclusion rules to be used at query time. By exploiting the distance lower-bound
provided by the function 𝑓 , we have that |𝑓 (𝑞) − 𝜏 | > 𝑡 is a sufficient condition to exclude one
of the two partitions from the search. Specifically,

    • if 𝑓 (𝑞) ≤ 𝜏 − 𝑡 then 𝒬(𝑞, 𝑡) ⊂ 𝒫1 and 𝒫0 can be excluded
    • if 𝑓 (𝑞) > 𝜏 + 𝑡 then 𝒬(𝑞, 𝑡) ⊂ 𝒫0 and 𝒫1 can be excluded

Note that different functions 𝑓 may be used to determine the same regions 𝒫0 , 𝒫1 but with
different distance lower-bounds, and thus different exclusion rules. For example, let’s consider
                                                                                        2         2
                                                                                     1 ) −𝑑(𝑠,𝑝0 )
the Euclidean space (R𝑛 , ℓ2 ), 𝜏 = 0, 𝑓1 (𝑠) = 𝑑(𝑠,𝑝1 )−𝑑(𝑠,𝑝
                                                        2
                                                               0)
                                                                  and 𝑓2 (𝑠) = 𝑑(𝑠,𝑝2𝑑(𝑝  1 ,𝑝0 )
                                                                                                    for
two fixed pivot 𝑝1 and 𝑝0 . Both the functions 𝑓1 and 𝑓2 produce the same sheet partitioning,
i.e., 𝒫1 = {𝑠 ∈ R𝑛 |𝑑(𝑠, 𝑝1 ) ≤ 𝑑(𝑠, 𝑝0 )} and 𝒫0 = {𝑠 ∈ R𝑛 |𝑑(𝑠, 𝑝1 ) > 𝑑(𝑠, 𝑝0 )}. However, in
[7] we proved that the exclusion rule determined by 𝑓1 (Hyperbolic exclusion) is weaker than
the one determined by 𝑓2 (Hilbert Exclusion), and the latter is valid only on the large class of
Supermetric Spaces [8].
   In the following we show how general ball partitioning and sheet partitioning can be described
within this formalism.

Ball Partitions A ball partition can be characterised by the function 𝑓 (𝑠) = 𝑑(𝑠, 𝑝) and
the constant 𝜏 . In this case 𝒫1 = {𝑠 ∈ 𝑈 |𝑓 (𝑠) = 𝑑(𝑠, 𝑝) ≤ 𝜏 }, and 𝒫0 = {𝑠 ∈ 𝑈 |𝑓 (𝑠) =
𝑑(𝑠, 𝑝) > 𝜏 }, so Property 1 is clear. Properties 2 follows from the triangle inequality:

                𝑑(𝑠, 𝑝) ≤ 𝑑(𝑠, 𝑠′ ) + 𝑑(𝑠′ , 𝑝),   and 𝑑(𝑠′ , 𝑝) ≤ 𝑑(𝑠′ , 𝑠) + 𝑑(𝑠, 𝑝)

which give that 𝑑(𝑠, 𝑠′ ) ≥ |𝑑(𝑠, 𝑝) − 𝑑(𝑠′ , 𝑝)| = |𝑓 (𝑠) − 𝑓 (𝑠′ )| for any 𝑠, 𝑠′ ∈ 𝑈 .
   The balance of the partition is affected by selecting different values for 𝜏 which we refer to
as different balances.

Sheet Partitions Sheet partitions are defined with respect to two reference points 𝑝1 and 𝑝0 .
Usually, a simple binary partition is defined according to whichever of 𝑝1 and 𝑝0 is the nearer
value with respect to the metric 𝑑. However it has been noted [9, 10] that such partitions may
also be subject to a balancing factor 𝛼, so that

  𝒫1     =    {𝑠 ∈ 𝑈 | 𝑑(𝑠, 𝑝1 ) ≤ 𝑑(𝑠, 𝑝0 ) + 𝛼},𝒫0      =     {𝑠 ∈ 𝑈 | 𝑑(𝑠, 𝑝1 ) > 𝑑(𝑠, 𝑝0 ) + 𝛼}
�  In this case, we can use 𝑓 (𝑠) = (𝑑(𝑠, 𝑝1 ) − 𝑑(𝑠, 𝑝0 ))/2 which gives property 1 above for the
constant 𝜏 = 𝛼/2. Moreover from the triangle inequality of the space we have that

                𝑑(𝑠, 𝑝1 ) ≤ 𝑑(𝑠, 𝑠′ ) + 𝑑(𝑠′ , 𝑝1 )     and 𝑑(𝑠′ , 𝑝0 ) ≤ 𝑑(𝑠, 𝑠′ ) + 𝑑(𝑠, 𝑝0 )
                                                                           ′         ′
for any 𝑠, 𝑠′ ∈ 𝑈 , which gives 𝑑(𝑠, 𝑠′ ) ≥ 𝑑(𝑠,𝑝1 )−𝑑(𝑠,𝑝0 )−𝑑(𝑠
                                                              2
                                                                  ,𝑝1 )+𝑑(𝑠 ,𝑝0 )
                                                                                  = 𝑓 (𝑠) − 𝑓 (𝑠′ ). By
symmetry, we also have 𝑑(𝑠, 𝑠′ ) > 𝑓 (𝑠′ ) − 𝑓 (𝑠), therefore 𝑑(𝑠, 𝑠′ ) > |𝑓 (𝑠) − 𝑓 (𝑠′ )|.
  Like ball partitions, the balance of the partition is affected by selecting different values for 𝜏 .

4.1. Exclusion power
The exclusion power of a partition gives a quantification of the effectiveness of that partition
with respect to a given metric search task. It is clear that this is likely to be quite different
depending on the partition type, the selection of reference objects, and the chosen value 𝜏 .
   The meaning of exclusion power is based on the probability, for arbitrarily selected objects
𝑞 and 𝑠, and a distance 𝑡, of being able to demonstrate that 𝑑(𝑞, 𝑠) > 𝑡. As we will show, for
low dimensional spaces the maximum exclusion power of any partition structure is likely to
coincide with a value of 𝜏 which causes the partition to bisect the finite search space 𝑆, i.e.
|𝒫0 | ≈ |𝒫1 |. However as we will see, in higher dimensional spaces this may be a very bad
choice.
   For a range query 𝒬(𝑞, 𝑡) we define the exclusion power of the partition 𝒫 = {𝒫0 , 𝒫1 } as
the probability of excluding one generic element 𝑠 on the basis only of the data partition to
which it belongs:

              𝑃 (𝑠 ∈ 𝒫0 ) · 𝑃 (𝒬(𝑞, 𝑡) ∩ 𝒫0 = ∅) + 𝑃 (𝑠 ∈ 𝒫1 ) · 𝑃 (𝒬(𝑞, 𝑡) ∩ 𝒫1 = ∅)                            (4)
                     = 𝑃 (𝑠 ∈ 𝒫0 ) · 𝑃 (𝒬(𝑞, 𝑡) ⊂ 𝒫1 ) + 𝑃 (𝑠 ∈ 𝒫1 ) · 𝑃 (𝒬(𝑞, 𝑡) ⊂ 𝒫0 )                         (5)

   The exact calculation of the probabilities 𝑃 (𝒬(𝑞, 𝑡) ⊂ 𝒫𝑖 ), for 𝑖 = 0 or 1, is not straightfor-
ward for a general binary partition in a metric space, however, if we know that the partition
can be characterised by a function 𝑓 and a balancing factor 𝜏 , we can estimate a lower-bound
of these probabilities3 and thus obtain an approximation of the exclusion power as

                 𝑃 (𝑓 (𝑠) > 𝜏 ) · 𝑃 (𝑓 (𝑞) ≤ 𝜏 − 𝑡) + 𝑃 (𝑓 (𝑠) ≤ 𝜏 ) · 𝑃 (𝑓 (𝑞) > 𝜏 + 𝑡)                         (6)

  Let CDF(𝑥) be the cumulative distribution function of 𝑓 (𝑠) for 𝑠 ∈ 𝑆 then the exclusion
power can be expressed as

                 𝑔(𝜏, 𝑡) = (1 − CDF(𝜏 )) · CDF(𝜏 − 𝑡) + CDF(𝜏 ) · (1 − CDF(𝜏 + 𝑡))                               (7)

where 𝜏 is the partition balancing factor and 𝑡 in the query distance threshold
   Estimates of exclusion power can be made with respect to a representative sample of the data
set, and indeed of the query set if that is different4 . A large enough sample will give a good
estimate of the probability of an individual datum falling within each of the subsets.
     3
       In general, 𝑓 (𝑞) ≤ 𝜏 − 𝑡 ⇒ 𝒬(𝑞, 𝑡) ⊂ 𝒫1 , therefore 𝑃 (𝑓 (𝑞) ≤ 𝜏 − 𝑡) ≤ 𝑃 (𝒬(𝑞, 𝑡) ⊂ 𝒫1 ). Similarly, 𝑓 (𝑞) >
𝜏 + 𝑡 ⇒ 𝒬(𝑞, 𝑡) ⊂ 𝒫0 , and thus 𝑃 (𝑓 (𝑞) > 𝜏 + 𝑡) ≤ 𝑃 (𝒬(𝑞, 𝑡) ⊂ 𝒫0 ). The equality holds for some cases, e.g., the
ball partitioning, where it can be proved that 𝑓 (𝑞) ≤ 𝜏 − 𝑡 ⇔ 𝒬(𝑞, 𝑡) ⊂ 𝒫1 and 𝑓 (𝑞) > 𝜏 + 𝑡 ⇔ 𝒬(𝑞, 𝑡) ⊂ 𝒫𝑜 .
     4
       We assume from here on that the distribution of data and query is the same
�5. Power graphs
To understand the effect of different values of 𝜏 an exclusion power graph may be constructed
which is plotted across the range of 𝜏 for a fixed value of 𝑡. This allows the optimum value of 𝜏
to be deduced for a range query with threshold 𝑡.
   We illustrate the construction of power graphs for 5 dimensional data in Section 5.1 and for
20 dimensional data in 5.2.

5.1. Example: single-pivot ball partitioning over 5 dimensional data

                          0.09                                                                           0.2

                          0.08                                                                          0.18
   Normalized Frequency




                                                                                 Normalized Frequency
                                                                                                        0.16
                          0.07
                                                                                                        0.14
                          0.06
                                                                                                        0.12
                          0.05
                                                                                                         0.1
                          0.04
                                                                                                        0.08
                          0.03
                                                                                                        0.06
                          0.02
                                                                                                        0.04

                          0.01                                                                          0.02

                            0                                                                             0
                                 0.2   0.4   0.6     0.8   1   1.2   1.4   1.6                                 0.14   0.16   0.18     0.2   0.22   0.24   0.26   0.28

                                       Distance from ball centre                                                  Distance of a query from its 5NN

                                                   (a)                                                                              (b)
Figure 3: Typical inter-point and query threshold distances from 5-dimensional Euclidean data


   Figure 3 shows histograms of two sets of sampled distances from a randomly generated
five-dimensional Euclidean space. The left-hand side of the figure shows the distribution of
5,000 witness points in terms of distance from a randomly selected pivot point, 𝑝. The right-hand
side shows the distribution of the 5NN (fifth nearest-neighbour) distances for a set of 1,000
queries; this distance representing a query threshold necessary to return a small proportion of
the data, and thus useful values for 𝑡.
   Based on this information, we will pick example values of 𝜏^ = 0.89 and ^𝑡 = 0.19, being the
median values in the distributions of 𝜏 and 𝑡 values, respectively. We can now consider the
exclusion power of these values applied to the partition thus formed, centered around 𝑝.
   The left-hand side of Figure 4 shows the Cumulative Probability Density function (CDF) with
the X-axis values of 𝜏^, 𝜏^ − ^𝑡, and 𝜏^ + ^𝑡 highlighted. Given that 𝜏^ has been selected as the median
distance from 𝑝, the value of the CDF at 𝜏^ is 0.5. Therefore if an exclusion occurs, half of the
data set will be excluded and its exclusion power is: CDF(𝜏^ − ^𝑡) · 0.5 + (1 − CDF(𝜏^ + ^𝑡)) · 0.5.
The more general form of this equation (i.e., Equation 7) hints how the exclusion power can
be displayed for a single partition, as shown on the right-hand side of Figure 4. Here, for a
fixed value of 𝑡 (again 0.19), the power of the partition is calculated over the whole range of
distances that have been measured between the witness points and the point 𝑝. As can be seen,
the maximum power is achieved when the partition is split at the median distance, i.e. 𝜏^ = 0.89
in this example. With this partition, and this value of 𝜏 , the probability of excluding an arbitrary
datum for an arbitrary query is around 0.21.
�                           1                                                                                      0.25

                         0.9

                         0.8                                                                                       0.2

                         0.7

                         0.6                                                                                      0.15

                         0.5

                         0.4                                                                                       0.1

                         0.3

                         0.2                                                                                      0.05

                         0.1

                           0                                                                                        0
                                0       0.2     0.4         0.6         0.8    1      1.2         1.4   1.6              0                           0.2   0.4      0.6       0.8      1     1.2     1.4      1.6         1.8




            (a) CDF of 𝑓 (𝑠) = 𝑑(𝑠, 𝑝) varying 𝑠                                                              (b) Exclusion power graph over 𝜏 (fixing
                                                                                                                  𝑡 = ^𝑡). The exclusion power for 𝜏 = 𝜏^
                                                                                                                  is 0.23.
Figure 4: CDF and Power Graph for 5-dimensional data


5.2. Example: single-pivot ball partitioning over 20 dimensional data

                          0.1                                                                                                                       0.12

                         0.09
                                                                                                                                                     0.1
  Normalized Frequency




                                                                                                                             Normalized Frequency
                         0.08

                         0.07
                                                                                                                                                    0.08
                         0.06

                         0.05                                                                                                                       0.06

                         0.04
                                                                                                                                                    0.04
                         0.03

                         0.02
                                                                                                                                                    0.02
                         0.01

                           0                                                                                                                          0
                                    1   1.2    1.4    1.6         1.8     2   2.2   2.4     2.6                                                            0.9    0.95    1     1.05   1.1   1.15   1.2    1.25     1.3
                                              Distance from ball centre                                                                                          Distance of a query from its 5NN


                                                      (a)                                                                                                                      (b)
Figure 5: Typical inter-point and query threshold distances from 20-dimensional data


   The left-hand side of Figure 5 shows a histogram of 5,000 distances measured with respect to
a randomly selected element 𝑝 of a 20-dimensional uniformly generated Euclidean space. The
right-hand side shows a histogram (for 1,000 queries selected from the same set) of the distances
to the 5th-nearest neighbour with respect to this same set of 5,000 values. Figure 6 shows the
same information in the form of cumulative probability density functions. The left-hand side of
Figure 6 shows the CDF function superimposed with a line corresponding to the medium value
for 𝜏 . The value of t for this data is 1.07.
   Finally, although we have no space here to provide in-depth analysis, Figure 7 shows exclusion
power graphs using sheet partitions over both 5D and 20D spaces. It can be seen that the graph
patterns are quite similar.
�                                                                                   -4
                                                                              10
     1                                                              1.5

    0.9

    0.8

    0.7
                                                                     1
    0.6

    0.5

    0.4
                                                                    0.5
    0.3

    0.2

    0.1

     0                                                               0
          0   0.5   1   1.5   2   2.5   3                                 1             1.5   2   2.5   3




 (a) CDF of 𝑓 (𝑠) = 𝑑(𝑠, 𝑝) varying 𝑠                          (b) Exclusion power graph over 𝜏 (fix-
                                                                   ing 𝑡 = ^𝑡). The exclusion power
                                                                   for 𝜏 = 𝜏^ is 0
Figure 6: CDF and Power Graph for 20-dimensional data




                         (a) A sheet partition in 5D space     (b) A sheet partition of 20 dimensions
Figure 7: Exclusion Power graphs for sheet partitions in 5 and 20 dimensional Euclidean space


5.3. Use of Exclusion Power analysis
Figures 4 and 6 demonstrate the exclusion power in 5 and 20 Dimensions respectively. In the
5 dimensional case we can observe that setting a 𝜏^ value of 0.89 (close to the mean of the
distribution of measured distances) will work extremely well. With such a value the exclusion
power is maximised. By contrast, choosing the mean in the case of 20D data will work very badly.
As can be seen in Figure 6 such a value is unlikely to result in any successful exclusions. These
diagrams explain behaviour observed by many researchers into metric search that choosing
unbalanced indexing structures often works better for higher dimensional data.
   The establishment of a unified partition interface using 𝑓 and 𝜏 allows similar graphs to be
produced for sheet partitions (e.g., Figure 7). The mechanistic value of these graphs is that the
value or values of 𝜏 corresponding to the maxiumum power can be automatically extracted on
a per-partition basis, and used in an implementation of BitPart. In the case of low dimensional
data a single offset can be used for each ball where as for high(er) dimensional data two offsets
can be used. Furthermore, as described earlier a particular implementation can use as few or as
many exclusion zones that as necessary, as may be predicted by the power value at the optimum
�value.
  In Section 6 these offsets are applied to a BitPart implementation to demonstrate their effect.


6. Experimental Validation using BitPart




                   (a) 5 dimensional space                                 (b) 20 dimensional space
Figure 8: Empirical Inverse distances per query for 5D and 20D data for different values of 𝜏 . These
charts plot both ball and sheet partitions, which have different ranges of 𝜏 ; we have therefore nor-
malised these within the offset axis. The Y axis shows the inverse of the number of residual distance
computations, i.e. those not excluded by use of the BitPart mechanism (higher is better).


   In order to validate the above results we ran experiments against a BitPart implementation5
using uniformly generated data in 5 and 20 dimensions with Euclidean distance. Each contained
one million data points, and 1000 queries were executed. In all experiments fixed threshold
distances 𝑡 were used and set to values which correspond to one-millionth of the data volume.
In order to measure exclusion power, the 1000 queries were run 25 times for differing values of
𝜏 for both sheet and ball partitions. The 5D data uses 20 pivot points and(︀ the
                                                                               )︀ 20D data 100.
   In [2] we described how a selection of 𝑚 reference points allows for 𝑚    2 sheet and 𝑚 ball
partitions to be produced. After the above analysis, we used this number for the 5D space, but
in the 20D space we generated twice that number, corresponding to the twin peaks in the power
graphs. Note that this does not require any extra distance calculations at query time, as the
number of reference points is not increased. Furthermore there is not necessarily any increase
in memory usage, as partitions are typically stored in secondary memory and only fetched
when the query ball does not intersect with the partition, which requires only the evaluation of
the 𝑓 function to determine. For each experiment a suitable range is calculated for 𝜏 for both
balls and sheets, ensuring that for all partitions both 𝒫0 and 𝒫1 are non-empty, and the whole
calculation was executed with different values of 𝜏 across this range.
   Results are shown in Figure 8. In order to visualize these results, the number of residual (i.e.
Phase 3) distance calculations per query was measured, this number giving a good proxy for the
value of the exclusion mechanism. The plots show the inverse of these counts. Peaks similar to
those shown in the power graphs in Figures 4 and 6 can be seen in these experimental results.
   5
       The experimental code may be found in https://bitbucket.org/richardconnor/metricbitblaster.git
�7. Conclusions
In this paper, we have reiterated the design of the BitPart indexing and query mechanisms.
The novel contribution of this paper is an exposition of how dimensionality effects the efficacy
of this and other metric search mechanisms. We have demonstrated how the distribution of
distances changes with the dimensionality of the data and how in turn this affects the ability
to perform effective exclusions and thus efficient queries. In particular we have explored the
notion of balance and how that affects exclusion. To do this we have introduced the notion of
exclusion power, and shown its application to some Euclidean data sets in different dimensions.
   This analysis gives fundamental insights into what data can be queried effectively and
what cannot. Furthermore it demonstrates how index and search algorithms can be tuned to
compensate for data sets of arbitrary dimensions.
   We have demonstrated that the phenomena explored in mathematical terms are manifested
in synthetically generated data sets and queries over them using an implementation of BitPart.
We believe that the results in this paper may be applied to other metric search and indexing
mechanisms. Our future plans include investigating these phenomena in real life data sets and
exploring the outstanding issue of partition orthogonality.


References
 [1] P. Zezula, G. Amato, V. Dohnal, M. Batko, Similarity search: the metric space approach,
     volume 32, Springer Science & Business Media, 2006.
 [2] A. Dearle, R. Connor, Bitpart: Exact metric search in high(er) dimensions, Information
     Systems 95 (2021) 101493.
 [3] V. Pestov, Indexability, concentration, and vc theory, Journal of Discrete Algorithms 13
     (2012) 2–18.
 [4] R. Weber, H.-J. Schek, S. Blott, A quantitative analysis and performance study for similarity-
     search methods in high-dimensional spaces, in: Proc. of 24th VLDB, volume 98, Morgan
     Kaufmann, 1998, pp. 194–205.
 [5] G. Amato, C. Gennaro, P. Savino, MI-File: Using inverted files for scalable approximate
     similarity search, Multimedia Tools and Applications (2014) 1333–1362.
 [6] D. Novak, M. Batko, P. Zezula, Metric index: An efficient and scalable solution for precise
     and approximate similarity search, Information Systems 36 (2011) 721–733.
 [7] R. Connor, F. A. Cardillo, L. Vadicamo, F. Rabitti, Hilbert exclusion: improved metric
     search through finite isometric embeddings, ACM Transactions on Information Systems
     (TOIS) 35 (2016) 1–27.
 [8] R. Connor, L. Vadicamo, F. A. Cardillo, F. Rabitti, Supermetric search, Information Systems
     80 (2019) 108–123.
 [9] R. Connor, Reference point hyperplane trees, in: International Conference on Similarity
     Search and Applications, Springer, 2016, pp. 65–78.
[10] J. Lokoč, T. Skopal, On applications of parameterized hyperplane partitioning, in: Proceed-
     ings of the Third International Conference on SImilarity Search and APplications, 2010,
     pp. 131–132.
�
Retrieved from "http://ceur-ws.bitplan.com/index.php?title=Vol-3194/paper49&oldid=1591"