Optimized Cost Model for k-NN Queries in R*-Trees over Random Distribution

Abstract:

Efficient storage and retrieval of multidimensional data in large volumes has become one of the key issues in the design and implementation of commercial and application software. The kind of queries posted on such data is also multifarious. Nearest neighbor queries are one such category and have more significance in GIS type of application. R-tree and its sequel are data partitioned hierarchical multidimensional indexing structures that help in this purpose. Today’s research has turned towards the development of powerful analytical method to predict the performance of such indexing structures such as for varies categories of queries such as range, nearest neighbor, join, etc .This paper focuses on performance of R*-tree for k nearest neighbor (kNN) queries. While general approaches are available in literature that works better for larger k over uniform data, few have explored the impact of small values of k. This paper proposes improved performance analysis model for kNN query for small k over random data. The results are tabulated and compared with existing models, the proposed model out performs the existing models in a significant way for small k

• Periodical: Advanced Materials Research (Volumes 403-408)
• Pages: 3315-3321
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.403-408.3315
• Online since: November 2011
• Authors: Sirisala Nageswara Rao
• Keywords: Multidimensional, Nearest Neighbor, Performance Analysis

References

[1] Guttman, A, R-trees,: A Dynamic Index Structure for Spatial Searching, Proc. ACM SIGMOD, pp.47-57, June (1984).

DOI: 10.1145/971697.602266

[2] Yufei Tao, Jun Zhang, Dimitris Papadias, and Nikos Mamoulis An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium dimensional Spaces, IEEE Transactions on knowledge and data engineering, Vol. 12, No. 1, Oct (2004).

DOI: 10.1109/tkde.2004.48

[3] Yannis Theodoridis, Emmanuel Stefanakis, and Timos Sellis, Efficient Cost Models for Spatia Queries Using R-Trees, IEEE Transactions on Knowledge And Data Engineering, Vol 12, NO January (2000).

DOI: 10.1109/69.842247

[4] Yannis Theodoridis, Emmanuel Stefanakis, and Timos Sellis Efficient Cost Model for Spatial Queries Using R-Trees,. IEEE Transactions on knowledge and data engineering, Vol. 12, No. 1, Feb (2004).

DOI: 10.1109/69.842247

[5] Y. -W. Huang, N. Jing and E. Rundensteiner. Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations, Proceedings 23rd VLDB Conference, pp.396-405, Athens, Greece, (1997).

[6] Arya S., Mount D. M., Narayan 0.: Accounting for Boundary Effects in Nearest Neighbor Searching, Proc. 11th Annual Symposium on Computational Geometry, Vancouver, Canada, 1995, pp.336-344.

DOI: 10.1145/220279.220315

[7] C. Boehm, A Cost Model for Query Processing in HighDimensional Data Spaces, ACM Trans. Database Systems, vol. 25, no. 2, pp.129-178, (2000).

DOI: 10.1145/357775.357776

[8] S. Berchtold, C. Boehm, D. Keim, F. Krebs, and H. Kriegel, On Optimizing Nearest Neighbor Queries in High-Dimensional Data Spaces, " Proc. Int, l Conf. Database Theory, (2001).

DOI: 10.1007/3-540-44503-x_28