질의 결과를 이용한 거리 브라우징 질의의 처리
Distance Browsing Query Processing using Query Result Set
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
k-최근접 질의와 같은 거리 브라우징 질의는 지리정보시스템(GIS)과 같은 공간 데이터베이스 응용에서 아주 중요한 질의이다. 최근 GIS 응용은 웹과 같은 다중 사용자 환경으로 확장되고 있는 추세이다.이러한 질의를 처리하기 위한 많은 기법들 중에서 Hjaltason과 Samet이 제안한 알고리즘이 가장 우수하지만, 하나의 질의 처리에 대해서만 최적화가 이루어졌다. 따라서 다중 사용자 환경에 적합하도록 이러한 기법들을 보완할 필요성이 있다. 이전에 처리된 질의 결과를 캐쉬에 저장해 두고(즉, 질의 결과 캐슁 기법) 후속 질의를 처리할 때 질의 결과를 이용하는(즉, 질의 결과 매칭 기법) 것은 하나의 좋은 접근 방법이라 할 수 있다. 본 논문은 다중 사용자 GIS 환경에서 거리 브라우징 질의를 효율적으로 처리하기 위해서 캐쉬된 이전 질의 결과를 재사용할 수 있도록 보완된 Hjaltason & Samet의 알고리즘을 제안한다. 실험 결과를 통해 우리의 접근 방법이 효율적임을 보인다.
Abstract
Distance browsing queries, namely k-nearest neighbor queries, are the most important queries in spatial database applications, e.g., Geographic Information Systems(GISs). Recently, GIS applications trends to extend themselves toward wide multi-user environments such as the Web. Since many techniques for such queries, where Hjaltason and Samet's algorithm is the most efficient one, were optimized for only one query, we need to complement them suitable for multi-user environments. It can be a good approach that we store many individual query results in a cache, i.e., query result caching and reuse them in evaluating incoming queries, i.e., query result matching. In this paper, we propose a complementary Hjaltason and Samet's algorithm capable of reusing previous query results in a cache for answering distance browsing queries in multi-user GIS environments. Our experimental results confirm the efficiency of our approach.
참고문헌 (20)
- "GeoWeb Project"
- "The ArcExplorer GIS data viewer"
- T. Barchlay, "A Spatial Data Warehouse." (2000)
- N. Beckmann, "An Efficient And Robust Access Method for Points and Rectangles. In Proceedings of the ACM SIGMOD Conference" (1990)
- B. Braunmuller, "and J. Sander. Efficiently Supporting Multiple Similarity Queries for Mining in Metric Databases." (2000)
- A. J. Broder. Strategies for Efficient Incremental Nearest Neighbor Search. Pattern Recognition,23, "January", pp.1990~
- K. Chakrabarti, "and S. Mehrotra. Efficient Query Refinement in Multimedia Databases." (2000)
- March, "C. M. Chen and R. Roussopoulos. The Implementation and Performance Evaluation of the ADMS Query Optimizer Integrating Query Result Caching and Matching. In 4th International Conference on Extending Database Technology" (1994)
- S. Coetzee, "A New Way to Query GISs on the Web", 6, pp.15(3) (1998), 1998~
- P. M. Deshpande, "and A. Shukla. Caching Multidimensional Queries Using Chunks." (1997)
- June, "S. Finkelstein. Common Expression Analysis in Database Applications. In Proceedings of ACM SIGMOD Conference" (1982)
- A. Guttman. R-trees, "A Dynamic Index Structure for Spatial Searching. In Proceedings of the ACM SIGMOD Conference" (1984)
- V. Harinarayan, "and J. D. Ullman. Implementing data cubes efficiently." (1996)
- December, "A. Henrich. A Distance-scan Algorithm for Spatial Access Structures. In Proceedings of the Second ACM Workshop on Geographic Information Systems" (1994)
- G. R. Hjaltason, "Distance Browsing in Spatial Databases", 24(2), pp.1999~ (1999)
- Y. Kotidis, "DynaMat-A Dynamic View Management System for Data Warehouses." (1998)
- August, "L.-A. Larson and H. Z. Yang. Computing Queries From Derived Relations. In Proceedings of VLDB Conference" (1985)
- D.-J. Park, "An Enhanced Technique for k-Nearest Neighbor Queries with Non-spatial Selection Predicates", 19(1), pp.2003~ (2003)
- N. Roussopoulos, "Nearest Neighbor Queries" (1995)
- Michael Stonebraker, "and Jeff Meredith. The Sequoia 2000 Benchmark. In Proceedings of ACM SIGMOD Conference" (1993)