Loading...
Please wait, while we are loading the content...
Similar Documents
Search Space Reductions for Nearest-Neighbor Queries
| Content Provider | CiteSeerX |
|---|---|
| Author | Heeringa, Brent Adler, Micah |
| Abstract | Abstract. The vast number of applications featuring multimedia and geometric data has made the R-tree a ubiquitous data structure in databases. A popular and fundamental operation on R-trees is nearest neighbor search. While nearest neighbor on R-trees has received considerable experimental attention, it has received somewhat less theoretical consideration. We study pruning heuristics for nearest neighbor queries on R-trees. Our primary result is the construction of non-trivial families of R-trees where k-nearest neighbor queries based on pessimistic (i.e. min-max) distance estimates provide exponential speedup over queries based solely on optimistic (i.e. min) distance estimates. The exponential speedup holds even when k = 1. This result provides strong theoretical evidence that minmax distance heuristics are an essential component to depth-first nearest-neighbor queries. In light of this, we also consider the time-space tradeoffs of depth-first versus best-first nearest neighbor queries and construct a family of R-trees where best-first search performs exponentially better than depth-first search even when depth-first employs min-max distance heuristics. 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Considerable Experimental Attention Nearest-neighbor Query Primary Result Minmax Distance Heuristic Neighbor Query Essential Component Depth-first Nearest-neighbor Query Neighbor Search Depth-first Versus Time-space Tradeoff Theoretical Consideration Best-first Search Performs Vast Number K-nearest Neighbor Query Ubiquitous Data Structure Min-max Distance Heuristic Non-trivial Family Strong Theoretical Evidence Distance Estimate Geometric Data Depth-first Search Fundamental Operation Search Space Reduction Exponential Speedup |
| Content Type | Text |
| Resource Type | Article |
