UTCS Colloquia - Dr. Rui Mao/National High Performance Computing Center at Shenzhen Shenzhen University China, "On Hyper-plane Partitioning in Metric Space Indexing", ACES 6.442

Contact Name: 
Jenna Whitney
Date: 
Feb 23, 2011 11:00am - 12:00pm

Type of Talk: Colloquia

Speaker/Affiliation: Dr. Rui Mao/N

ational High Performance Computing Center at Shenzhen Shenzhen University C

hina

Talk Audience: UTCS Faculty and Grad Students

Date/Time: Wed

nesday, February 23, 2011, 11:00 a.m.

Location: ACES 6.442

Hos

t: Dr. Daniel Miranker

Talk Title: On Hyper-plane Partitioning in Metr

ic Space Indexing

Talk Abstract:
Tree-based index structures for ind

exing metric-spaces support a black-box indexing model. That is, a single
implementation can support similarity searches on any data set where simil

arity is defined using a metric-distance function. A primary distinction a

mong classes of tree-based metric-space index algorithms are constraints on
the direction of the hyper-plane used to define the partitioning surface i

n the pivot space. We relax the hyper-plane constraints for the General Hy

per-plane Tree algorithm (GHT) to form the Complete General Hyper-plane Tre

e algorithm (CGHT). Empirical results over a benchmark suite show that CGH

T outperforms GHT. Further, we show that the CGHT partition is actually a

rotation of the Multiple Vantage Point Tree (MVPT) partition. For a range

query (q,r), let the r-neighborhood of a partition boundary be the region
falls into which (q, r) could possibly have results in both sides of the

boundary. We show that the width of the r-neighborhood is minimized for MV

PT partition, indicating possibly the best query performance. Moreover, w

e show analytically and empirically that MVPT has less number of points in

r-neighborhoods than CGHT. Empirical results confirm that MVPT outperforms

CGHT.