Search Strategies White Papers
Near-Neighbor Query Performance in Search Trees
Overview Near-neighbor search is an increasingly important operation for queries over multimedia, text, and other non-standard datatypes. In large databases, near-neighbor searches must be enhanced by indexed retrieval for efficiency. In this paper, we present a detailed analysis of three proposals for near-neighbor search: one based on the R-tree, and two which motivated the invention of new trees, namely the SS-tree and SR-tree. We find that while the new trees do improve performance, the reason for their improvement comes mostly from a new Penalty metric, and not from a variety of other details in their implementation. Our analysis was done using a Generalized Search Tree, which both allowed us to easily do a fair comparison, and also provided the framework for a clearer analysis of the issues at hand.
| Publisher | University of California, Berkeley | File Format | PDF, requires Acrobat Rdr 5 |
|---|---|---|---|
| Date Published | August 2003 | Downloads | 5 |
| Format | White Papers | ||
| Topics | |||
-
Did you find this white paper useful?
White Paper RSS
Download
Register
