loading...
CSR+-tree: Cache-conscious Indexing for High-dimensional Similarity Search
Banff, Alberta, Canada July 09-July 11
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SSDBM.2007.919th International Conference on Scie ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Junfeng Dong, Microsoft Corporation, USA
Xiaohui Yu, York University, Canada
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.
Citation:
Junfeng Dong, Xiaohui Yu, "CSR+-tree: Cache-conscious Indexing for High-dimensional Similarity Search," ssdbm, pp.14, 19th International Conference on Scientific and Statistical Database Management (SSDBM 2007), 2007
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions