The Problem

• a database of N objects   (obj₁ , obj₂ , ..., obj_N)
• representations of objects as d-dimensional vectors   (v_obj1 , v_obj2 , ..., v_objN)
  (each vector may represent one or more features of the object)
• a query object q with associated d-dimensional vector (v_q)
• a distance measure   D(v_i , v_j) : [0..1)     (D=0    v_i=v_j)

• a list of the k nearest objects in the database   [a₁ ,   a₂ ,   ...   a_k]
• ordered by distance to query object   D(v_a1 ,v_q)     D(v_a2 ,v_q)     ...     D(v_ak ,v_q)

The Context

• number of dimensions d  =  1 .. 500
• number of objects N  =  10⁴ .. 10¹⁰
• all values in query vector are specified (i.e. no partial-match)
• implementation runs on "standard" hardware/OS
  (e.g. don't assume arrays of parallel disks, huge memory, ...)
• independent of distance measure (?)
• 100% retrieval accuracy (?)

• use minimal resources:   i/o,   cpu-time,   space
• provide fast database updates (for some applications e.g. Magnifi)

The Costs

• the dominant cost   (given current disk technology)
• measured in terms of pages read, not records read

• primarily related to computing distance measure D(v_obj , v_q)
• can be relatively expensive for some QBIC features

• need to store data (feature vectors) within page-size chunks
• access methods typically require additional disk space
  (which can be anywhere from 10% extra to >100% extra)
• intermediate data structures in memory?

Cost Parameters

T_K is related to the use of a DBMS to look up a feature vector via an object identifier/key (the file name of the image).

T_sel is related to the indexed lookup of the nearest curve point via a B-tree during CurveIx querying.

Current Approach

list of results is initially empty

for each image j in the database
{
     dist = D(vj ,vq)
     if (#results < k or dist < maxD)
     {
          insert (j,dist) into results
          sort results by dist
          maxD = largest dist in results
     }
}

Cost   =   T_open  +  N_PT_P  +  NT_D

Note: If q is an image from the database, we can use a pre-computed distance table to make this much faster.

Goals for a Solution

• reduce the number of objects considered (determine candidates)
• ... which, in turn, reduces #vectors read and D computations
• but without excessive overhead in determining candidates

Proposed Approach: CurveIx

The basic idea:

• project d-dimensional vector onto 1-d space-filling curve
• collect set of curve-neighbours (should contain some k-NN)
• repeat above for several curves with different paths through space
• union of neighbour sets from all curves gives candidates
• retrieve and compute distance only for candidates

We want candidate set to contain most/all of k-NN ...

• how many curves do we need?
• how many neighbours do we examine on each curve?

Curve Mapping Functions

• maps d-dimensional vectors onto points on a line
  i.e. [0,1)^d [0,1)
• mapping is one-to-one and defines an order on [0,1)^d
• inverse mapping is continuous

We generate multiple C_is by applying:

• permutations over vector elements
• translations of individual elements

Data Structures for CurveIx

Database Construction

for i in 1..m
{
     p = Ci(vobj)
     insert (i, p, obj) into Index
}
insert (obj, vobj) into Db

Finding k-NN   (Simple Approach)

for i in 1..m
{
     p = Ci(vq)
     lookup (i,p) in Index
     fetch (i,p',j)
     while p' "close to" p on curve i
     {
          collect next (i,p',j) as candidate
     }
}
for each candidate j
{
     lookup j in Db
     fetch (j,vj)
     d = D(vj , vq)
     include j in k-NN if d small enough
}

Cost   =   2T_open  +  mT_sel  +  NfT_P  +  NfT_D

where

• T_sel is the cost of Index lookup using e.g. B-tree
• f is the filtering factor

CurveIx vs. Linear Scan

    Cost   =   T_open  +  N_PT_P  +  NT_D

For CurveIx:

    Cost   =   2T_open  +  mT_sel  +  NfT_P  +  NfT_D

If CurveIx is to be worthwhile, we need:

    (1)   mT_sel  +  NfT_P   <   N_PT_P

    (2)   NfT_D   <   NT_D

(2) simply requires f < 1, which is essential anyway.

... CurveIx vs. Linear Scan

    (1)   (3m+Nf)T_P   <   N_PT_P

Some observations, given N_P = 0.05 N:

• we can't afford to have too many curves   (m)
• CurveIx has to do effective filtering   (f)
• clustering can reduce the NfT_P term

Implementation

• make it stand-alone from QBIC, but use QBIC's distance function
• use the Unix dbm libraries to implement keyed retrieval

build

• reads image idents and color histograms from stdin
• stores each in the Db, a dbm B-tree keyed on ident
• computes m curve-points for each, and stores in Index, a dbm B-tree keyed on curveId and position (C_i(v) value)

query

• reads a single color histogram from stdin
• uses above method to find k best matches
• display list of best matches idents and distances on stdout, along with performance statistics

Example for build Program

% build db < data
Inserted img00000
Inserted img00001
...

where the data file looks like:

...
img00102
 54 0 0 0 0 0 0 5 10 3 1 1 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0
 0 1 8 10 3 2 1 7 3 2 1 1 0 0 0 0
 0 0 0 2 14 34 3 1 2 1 1 0 0 0 0 0
 0 0 0 0 0 0 2 1 0 0 0 3 1 1 2 737
 3 0 5 2 1 0 1 0 0 0 0 0 0 0 0 0
 0 0 0 0 7 0 25 2 1 1 1 0 0 0 9 2
 1 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 3 0 0 0 5 0 0 0 1 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
...

Example for query Program

% time query db 10 1 100 < qry007

QUERY: img00102
0.000000  img00102
0.005571  img00713
0.008826  img00268
0.011413  img05054
0.011811  img00631
0.014259  img04042
0.027598  img00203
0.037471  img00287
0.063639  img00244
0.067583  img00306
# dist calculations: 655
...
   various dbm, i/o statistics
...
2.00user 0.27system ...

C_i Values as Keys

• the Hilbert numbers produced by C_i could be expanded to arbitrary precision in order to distinguish between C_i(p₁ ) and C_i(p₂ )

Problems:

• gives keys that are 96 bytes long
  (producing very large Index files)
• different v_j can be mapped to same point
  (size of candidate sets is artificially inflated)

Solution:

• use a "prefix" index structure (something like a trie)

Query Algorithm

dbm.open(Db)
dbm.open(Index)
compute Ci perms and shifts
for i in 1..Ncurves
{
     p = Ci(vq)
     up = dbm.lookup(Index , (i,p))
     dn = dbm.lookup(Index , (i,p))
     img = dbm.fetch(up)
     insert img in results
     while within Range for up and dn
     {
          dbm.next(up); img = dbm.fetch(up)
	  check insert img in results
	  dbm.prev(dn); img = dbm.fetch(dn)
	  check insert img in results
     }
}
for i in 1..k
     display (dist,imageId) for resultsi

... Query Algorithm

check insert img in results
{
     if already seen img
          return  // no need to check
     
     data = dbm.lookup(Db , img)
     vimg = dbm.fetch(data)
     d = D(vimg , vq)
     include img in k-NN if d small enough
}

The dbm.lookup steps are expensive   (T_sel)

Once a cursor is established, access is via cached buffer.

Performance Analysis

In other words, CurveIx must deliver 0.9 k nearest-neighbours to be considered useful.

Our initial concern has been to answer the questions:

• How many curves are needed to achieve 90% accuracy?
• How many curve-neighbours do we need to examine?
• Can all of this be done reasonably efficiently?

• around 80-100
• around 15-30
• not particularly ... yet

Experiments

• Acc1   average top-10 entries in CurveIx top-10
• Acc2   how frequently CurveIx gives 10 out of 10

• Size   size of Db file + Index file
• Dist   number of distance calculations required
• IO   total amount of I/O performed

• built databases of size 5K, 10K, 15K, 20K   (supersets)
• for each database, ran 25 query "benchmark" set
• for each query, ran for 3,5,10,20,30,40 curve-neighbours
  (but because of curve-mapping problem, only got 20,30,40)
• for each query, ran for 20,40,60,80,100 curves

Sample Comparison

% query db 10 1 100

QUERY: img00102
0.000000  img00102
0.005571  img00713
0.008826  img00268
0.011413  img05054
0.011811  img00631
0.014259  img04042
0.027598  img00203
0.037471  img00287
0.063639  img00244
0.067583  img00306

# dist calcs: 524
1.67user 0.23system ...

% query db 10

QUERY: img00102
0.000000  img00102
0.005571  img00713
0.008826  img00268
0.011413  img05054
0.011811  img00631
0.014259  img04042
0.027598  img00203
0.037471  img00287
0.063639  img00244
0.067583  img00306

# dist calcs: 20000
1.93user 1.12system ...

Experimental Results

Results: Size vs. Accuracy

Results: Costs

Remaining Work

• control of search over curves and neighbours
• better data structure for curve index
• clustering strategies to reduce page reads
• compare to other approaches (e.g. [Pyramid technique] )