Among the many issues in high dimensional index structures using Minimum Bounding Rectangle(MBR), the reduction of fan-out and increase of overlapping area are the key factors in reduction of search speed. It is known that the usage of only minimum and maximum distance in MBR’s pruning process lowers the accuracy of search. In this paper, we present an index structure using cell based MBR in which fan-out gets increased and overlapping is avoided, and a search algorithm which reflects the distribution status of data in MBR to the search. The proposed index structure produces MBR as Vector Approximation-file(VA-file)’s cell units and produces child-MBR by dividing cells. The search algorithm raises the search accuracy by executing pruning using centroid of values included in MBR other than the minimum and maximum distance of cell based MBR and query vector in the k-nn query concerned. Through experiment, we find that the proposed search algorithm has improved its search speed and its accuracy in comparison with existing algorithm.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
- An Efficient Search Algorithm for High-Dimensional Indexing Using Cell Based MBR
- Springer Berlin Heidelberg