The HV-tree: a Memory Hierarchy Aware Version Index

Speaker:	Dr. Rui Zhang
		University of Melbourne

Title:		"The HV-tree: a Memory Hierarchy Aware Version Index"

Date:		Thursday, 21 July 2011

Time:		3:00pm - 4:00pm

Venue:		Room 3412 (via lifts 17/18), HKUST

Abstract:

The huge amount of temporal data generated from many important applications 
call for a highly efficient and scalable version index. The TSB-tree has the 
POTENTIAL of large scalability due to its unique feature of progressive 
migration of data to larger mediums. However, its traditional design 
optimized for two levels of the memory hierarchy (the main memory and the 
hard disk) undermines its potential for high efficiency in face of today's 
advances in hardware, especially CPU/cache speed and memory size. We propose 
a novel version index structure called the HV-tree. Different from all i
previous version index structures, the HV-tree has nodes of different sizes, 
each optimized for a level of the memory hierarchy. As data migrates to 
different levels of the memory hierarchy, the HV-tree will adjust the node 
size automatically to exploit the best performance of all levels of the 
memory hierarchy. Moreover, the HV-tree has a unique chain mechanism to 
maximally keep recent data in higher levels of the memory hierarchy. As a 
result, HV-tree is several times faster than the TSB-tree for point queries 
(query with single key and single time value), and up to 1000 times faster 
than the TSB-tree for key-range and time-range queries.


********************
Biography:

Rui Zhang obtained his Bachelor's degree from Tsinghua University and PhD 
from National University of Singapore. Currently he is a senior lecturer in 
the Department of Computer Science and Software Engineering, the University 
of Melbourne. His research interest is data and information management in 
general, particularly in areas of indexing techniques, spatio-temporal 
databases, web data, data streams and sequence databases.