Thumbnail
Access Restriction
Subscribed

Author Junfeng Dong ♦ Xiaohui Yu
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2007
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Indexing ♦ Costs ♦ Quantization ♦ Performance analysis ♦ Information technology ♦ Query processing ♦ Principal component analysis ♦ Geography ♦ Indexes ♦ Databases
Abstract In this paper, we propose a novel index structure, the $CSR^{+}-tree,$ to support efficient high-dimensional similarity search in main memory. We introduce quantized bounding spheres (QBSs) that approximate bounding spheres (BSs) or data points. We analyze the respective pros and cons of both QBSs and the previously proposed quantized bounding rectangles (QBRs), and take the best of both worlds by carefully incorporating both of them into the $CSR^{+}-tree.$ We further propose a novel distance computation scheme that eliminates the need for decompressing QBSs or QBRs, which results in significant cost savings. We present an extensive experimental evaluation and analysis of the $CSR^{+}-tree,$ and compare its performance against that of other representative indexes in the literature. Our results show that the $CSR^{+}-tree$ consistently outperforms other index structures.
Description Author affiliation: Microsoft Corp., Redmond (Junfeng Dong)
ISBN 0769528686
ISSN 15516393
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2007-07-09
Publisher Place Canada
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 239.19 kB
Page Count 1
Starting Page 14
Ending Page 14


Source: IEEE Xplore Digital Library