Making QBIC Faster

Overview

1. QBIC and Content-based Image Retrieval
2. High-dimensional k Nearest Neighbours Problem
3. Database Indexing Schemes and HDkNN Retrieval
4. The Curveix Approach ... Preliminary Results
5. Conclusions and Future Work

The QBIC System

The aim was to build a system for images that provide analogy to text retrieval operation ``Find documents like this one''.

The focus was on developing measures of image similarity that:

• corresponded somewhat to human perception of "similarity"
• were not too expensive to compute

... The QBIC System

Content-based Image Retrieval

System returns a ranked list of "matching" images from DB.

The Problem

• returns images that closely match the user's intent
• does this quickly, even for very large image collections

One efficiency measure already implemented: an N N table of pre-computed distances to speed up retrieval within database.

High-dimensional Nearest Neighbours Search

Given:

• a set of data points in a d-dimensional space
• a specific query point q in that space

A solution to this problem would be useful in several areas:

• information retrieval, multimedia databases, machine learning, ...

The Problem (Re-stated)

• 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)

... where time is the most important efficiency factor

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
  (important 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

Name	Meaning	Typically
N	number of objects in the database	103 .. 1010
d	number of dimensions in object features	1 .. 256
P	number of bytes per disk page	512 .. 8K
V	number of bytes for d-dimensional vector	4d
O	average number of bytes per stored object (key+vector)	12+4d .. 256+4d
NO	average number of stored objects per page P/O	1 .. 512
NP	number of disk pages to hold stored objects N/NO	50 .. 1010
Topen	time to open a database file	10ms
TP	time to read a page from disk into memory	10ms
TD	time to compute distance between two objects (using vectors)	100us (?)
TK	average time to find the page address for a given object	10ms (?)

The T_K measure is related to the use of a DBMS (e.g. dbm or DB2) to look up object vectors via the object identifier/key (the file name of the image).

Analysing Costs

That is, accessing n object vectors (chosen at random) is going to result in n page reads.

This gives an upper-bound on the actual cost.
The real cost will typically be less due to clustering and caching.

On the other hand, we also assume that if the access to the vectors is via a sequential scan, then each page in the database file will be read exactly once.

Measuring Costs

Unix (AIX) is not helpful in measuring I/O costs
(the rusage structure doesn't seem to count block input/output)

We use a combination of

• our own I/O monitoring   (to count read, write ops)
• profiling   (fine-grained analysis of cpu-time costs)
• wall-clock time   (the "bottom line" for users)

Current Approach

results = [];   maxD = infinity

for each obj in the database
{
	dist = D(vobj,vq)
	if (#results < k or dist < maxD)
	{
		insert (obj,dist) into results
		// results is sorted with length <= k
		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.

Specific Goals for a Solution

• reduce the number of objects considered (find candidates)
• ... which, in turn, reduces i / o and D computations
• but without excessive overhead in determining candidates

Some Potential Solutions

• use auxiliary (spatial) data structure to identify candidates
• space-partitioning methods: Grid file, k-d-b-tree, quadtree
• data-partitioning methods: R-tree, X-tree, SS-tree, TV-tree, ...

• use approximating data structure to identify candidates
• signature files: VA-files
• projections: space-filling curves

... Some Potential Solutions

• reduce I/O by reducing size of vectors   (compression)
• reduce I/O by placing "similar" records together   (clustering)
• reduce I/O by remembering previous pages   (caching)
• reduce cpu by making D computation faster   (ColorHist)

Tree-based Methods

Non-leaf nodes correspond to a union of subregions in children

Partitioned space containing data points:

... Tree-based Methods

Above has no overlap among subregions; some partitioning schemes permit overlap.

Above uses hyper-rectangles for partitioning; other shapes (e.g. spheres, convex polyhedra) have been used.

Detailed summary/comparison of tree methods can be found in [White & Jain] , [Kurniawati et al.]

Insertion with Trees

Insertion procedure:

   traverse tree to find leaf node n
   	    whose region contains vobj
   
   if (enough space in n)
   {
      insert vobj into corresponding page
   }
   else
   {
      need to perform local rearrangement in tree
         by splitting points between n and n's parent
         and n's siblings according to split heuristic
   }

Split heuristics include:

• minimise total volume of bounding regions
• minimise variance in volume of regions
• minimise overlap among regions
• .....

Query with Trees

Method involves:

• a search over the tree
• a "nearest neighbour (NN) region"
  (related to maxD in the original search method).

Consider the following space and two query points q1 and q2.

... Query with Trees

Variations on search methods in literature:

• overall search order   e.g. depth-first vs. breadth-first
• order to check nodes   e.g. distance from query point to node centroid
• pruning criteria   e.g. minimum distance exceeds maxD

Why Trees Don't Work (for d > 10)

• (degeneration)   the complexity of searching via a partitioning scheme tends to O(N) for sufficiently large d
• (complexity)   for every partitioning scheme, there exists some d such that all blocks are accessed if dimensionality exceeds d
• (performance)   most data- and space-partitioning schemes perform worse than sequential scan by the time d=10

Signature-based Methods   (VA-Files)

Use a file of signatures in parallel with main data file, one signature for each vector.

Signatures have properties:

• (much) more compact than vectors
• provide approximation to information in vectors

VA-File Signatures

where hi_m gives the top-order m bits

This essentially:

• partitions each dimension into 2^m regions
• maps vector into "identifier" of region that contains it

For non-equi-width regions, use mapping array to determine partition boundaries.

Insertion with VA-Files

Insertion is extremely simple.

sig = signature(vobj)
append vobj to data file
append sig to signature file

Storage overhead determined by m   (e.g. 3/32).

Query with VA-Files

results = [];  maxD = infinity;

for each sig in signature file
{
	vnear = closest point to vq in region[sig]
	dist = D(vnear,vq)
	if (#results < k  or  dist < maxD)
	{
		dist = D(vobj,vq)
		if (#results < k  or  dist < maxD)
		{
			insert (obj,dist) into results
			maxD = largest dist in results
		}
	}
}

Cost = 2T_open   +   T_P(N_s + fN)   +   T_D(N + fN)

where

• N_s is number of pages in signature file
• f is filtering factor   (0.0005 under ideal conditions)

Why VA-Files Don't Work (for QBIC)

In experiments with QBIC colour histograms, which have extremely skew distributions, we were unable to achieve better than 0.10 filtering on average.

And this was after "tuning" partition boundaries to place approximately equal numbers of points in each partition.

Before tuning, filtering factor was 0.70.

Conclusion VA-file performance is very sensitive to data distribution.

VA-files will also perform poorly if T_D is large   (we compute D for every signature)

Projection-based Methods   (C-curves)

• projecting data space onto reduced dimensions
• utilising existing access methods (e.g. B-trees) to find objects in projection

Our method, CurveIx (Curve Index), is an example of this approach.

Proposed Approach: CurveIx

(And possibly earlier? ... the idea of space-filling curves has been around for a while)

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

Example: Search with 5 Curves

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

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

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: 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: 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

Other Optimisations for QBIC Indexing

They involve exploiting properties of data structures and access patterns to reduce amount of I/O.

Derived primarily from profiling studies of QBIC.

Caching

Read/write pages only when absolutely necessary.

Most commercial DBMSs do this invisibly and effectively.

The dbm system:

• performs useful caching while a database file is open
• throws away cache each time file is closed

... Caching

Example: insertion of 1000 colour histograms:

...
<1000> Insert of ... successful
Reads: 37504864/13137   Writes: 9383936/2291
1213.8u 49.2s 26:02 80% 1760+4256k 0+0io 2087pf+0w

...
<1000> Insert of ... successful
Reads: 4096/1   Writes: 618496/151
1207.2u 11.8s 24:33 82% 2895+4440k 0+0io 2116pf+0w

Since Unix performs its own caching, this technique yields little impact on wall-clock times.

Since queries are handled by sequential scan, cache provides little benefit for them.

For a query server, may provide some querying benefit.

Compression

• consist of 256 [0..1000] values as short[256]
• contain many zero values (on average >200/256)

Scope for compression

• 16-bit quantities used for 10-bit values   (fixed-length compressed vectors)
• because of repetition of particular value (zero)   (variable-length compressed vectors)

• reduced storage costs and query I/O by around 2/3
• no increase in processing cost   (slight reduction)

Clustering

This situation becomes worse when vectors are smaller, and so N_O becomes larger

Approach: try to ensure that "similar" objects are placed in the same database page.

Plan to look at how effectively clustering can be performed for very large numbers of dimensions.

Conclusions

The following aspects require further research and implementation before this approach could be considered a real solution for k-NN:

• 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] )