Loading...
Please wait, while we are loading the content...
Similar Documents
Pivot Selection Techniques for Proximity Searching in Metric Spaces
| Content Provider | CiteSeerX |
|---|---|
| Author | Benjamin Bustos A., B. Edgar Chavez, C. Mexico, Mich Gonzalo Navarro, B. |
| Abstract | With few exceptions, proximity search algorithms in metric spaces based on the use of pivots select them at random among the objects of the metric space. However, it is well known that the way in which the pivots are selected can drastically aect the performance of the algorithm. Between two sets of pivots of the same size, better chosen pivots can largely reduce the search time. Alternatively, a better chosen small set of pivots (requiring much less space) can yield the same eciency as a larger, randomly chosen, set. We propose an eciency measure to compare two pivot sets, combined with an optimization technique that allows us to select good sets of pivots. We obtain abundant empirical evidence showing that our technique is eective, and it is the rst that we are aware of in producing consistently good results in a wide variety of cases and in being based on a formal theory. We also show that good pivots are outliers, but that selecting outliers does not ensure that good pivots are selected. Key words: Metric databases, range queries, pivot based indexing, nearest neigh-bour search. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Abundant Empirical Evidence Neigh-bour Search Chosen Small Set Pivot Selection Technique Eciency Measure Metric Database Proximity Searching Proximity Search Algorithm Pivot Set Good Set Good Pivot |
| Content Type | Text |
