K-Nearest Neighbor Query processing in Multi-Dimensional Indexing Structures

Byung-Gon Kim; OH Sung-Kyun

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2005, 10(1), pp.85-91
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Byung-Gon Kim ¹, OH Sung-Kyun ²

¹부천대학교
²서일대학

ABSTRACT

Recently, query processing techniques for the multi-dimensional data like images have been widely used to perform content-based retrieval of the data. Range Quesy and Nearest neighbor query are widly used multi dimensional queries. This paper proposes the efficient pruning strategies for k-nearest neighbor query in R-tree variants indexing structures. Pruning strategy is important for the multi-dimensional indexing query processing so that search space can be reduced. We analyzed the pruning strategies and perform experiments to show overhead and the profit of the strategies. Finally, we propose best use of the strategies.
KEYWORDS

k-Nearest neighbor query, Multi-dimnesional indexing, R-tree, Pruning
REFERENCES (10)

[journal] / “r-trees / A Dynamic Index Structure for Spatial Searching” / pages 47-57 : 1984~

[journal] / “ther*-tree / An Efficient and Robust Access Method for Points and Rectangles” : 1990~

[journal] / 1996 / An Index Structure for High-Dimensional Data” : 28~39

[journal] / 1994. / “The TV-tree - An Index Structure for High-Dimensional Data” 3

[journal] / 2003 / An Optimized Spatio-TemporalAccess Method for Predictive Queries” : 790~801

[journal] / 2004 / A Practically Efficient and Worst-Case Optimal R-tree” : 347~358

[journal] / 1995. / Nearest Neighbor Queries / and Frederick Vincent : 71~79

[journal] / 1998. / Optimal Multi-Step k-Nearest Neighbor Search

[journal] / 1997. / “Distance-Based Indexing for High-Dimensional Metric Spaces” Proceedings of the ACM SIGMOD Conference : 357~368

[journal] / 2004.9 / “멀티미디어 데이터베이스 환경에서 시각화된 사용자 정의 스키마 통합” 9(2)
KCI Citation (1)

KJC Korea
Journal Central

Statistics

Tools