Indexing high-dimensional data for main memory.
Published: 2004
Language: eng
Number of pages: 91
Description: In this thesis, we propose a novel index structure, called cache conscious SR+-tree (CSR+-tree), to support efficient high-dimensional k-nearest neighbor queries in main memory. The CSR+-tree is based on the SR+-tree, an extension of the SR-tree. The basic idea of the CSR+-tree is the introduction of Quantized Bounding Spheres (QBSs) that approximate Minimum Bounding Spheres (MBSs) or data points. Because QBSs can be represented rather compactly, tree nodes can contain a large number of QBS entries. Thus, fan-out becomes large, which leads to fast search. We present an extensive experimental evaluation and analysis of the query performance of main memory indices, including the CSR+ -tree, the SS-tree, the SR-tree, and the A-tree. Our results show that the CSR+-tree is superior in most cases.
Notes: Adviser:  Ken Sevcik.

Thesis (M.Sc.)--University of Toronto, 2004.

Electronic version licensed for access by U. of T. users.

Source: Masters Abstracts International, Volume: 43-03, page: 0874.

MICR copy on microfiche (2 microfiches).