XXIV International Conference of the Chilean Computer Science Society (SCCC'04) Spatial Approximation + Sequential Scan = Efficient Metric Indexing Arica, Chile November 11-November 12 ISBN: 0-7695-2200-9
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/QEST.2004.20
Proximity queries in metric spaces, or metric proximity queries for short, have instances suffering from the socalled "curse of dimensionality" referred to the apparent impossibility of beating the brute force approach (an exhaustive search to satisfy a metric proximity query). In other words, the cursed spaces resists indexing. Current research tends to alleviate this particular situation, since easy spaces can be indexed neatly.A recent hypothesis stablishes that it is just a fraction of the database which is resilient to indexing, and the proper approach would be to index each part separately. This is precisely the approach of this work. We use two different techniques for indexing complementary parts of a metric database.The Dynamic Spatial Approximation Tree (dsa-tree) is a recently proposed data structure for searching in metric spaces. It has been shown that it compares favorably against alternative data structures in spaces of high dimension or queries with low selectivity. On the other hand, pivot-based algorithms are effective tools for proximity searching in any metric spaces, if sufficient storage space is available.In this work we combine the concepts of spatial approximation and pivot-based algorithms. The new data structure maintains the full features of a dsa-tree while using the available memory to improve the query time. We show experimentally that our data structure is competitive choice for searching in cursed metric spaces.
Citation:
Edgar Ch?vez, Norma Herrera, Nora Reyes, "Spatial Approximation + Sequential Scan = Efficient Metric Indexing," sccc, pp.121-128, XXIV International Conference of the Chilean Computer Science Society (SCCC'04), 2004 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||