Journal of Korea Spatial Information System Society (한국공간정보시스템학회 논문지)

Korea Spatial Information System Society (대한공간정보학회)
권호 표지

DGR-Tree : An Efficient Index Structure for POI Search in Ubiquitous Location Based Services

DGR-Tree : u-LBS에서 POI의 검색을 위한 효율적인 인덱스 구조

  • 이득우 (건국대학교 컴퓨터.정보통신공학과) ;
  • 강홍구 (건국대학교 컴퓨터공학과) ;
  • 이기영 (을지대학교 의료산업학부) ;
  • 한기준 (건국대학교 컴퓨터공학과)
  • Published : 2009.09.30
Download PDF
⟨ Previous Next ⟩

Abstract

Location based Services in the ubiquitous computing environment, namely u-LBS, use very large and skewed spatial objects that are closely related to locational information. It is especially essential to achieve fast search, which is looking for POI(Point of Interest) related to the location of users. This paper examines how to search large and skewed POI efficiently in the u-LBS environment. We propose the Dynamic-level Grid based R-Tree(DGR-Tree), which is an index for point data that can reduce the cost of stationary POI search. DGR-Tree uses both R-Tree as a primary index and Dynamic-level Grid as a secondary index. DGR-Tree is optimized to be suitable for point data and solves the overlapping problem among leaf nodes. Dynamic-level Grid of DGR-Tree is created dynamically according to the density of POI. Each cell in Dynamic-level Grid has a leaf node pointer for direct access with the leaf node of the primary index. Therefore, the index access performance is improved greatly by accessing the leaf node directly through Dynamic-level Grid. We also propose a K-Nearest Neighbor(KNN) algorithm for DGR-Tree, which utilizes Dynamic-level Grid for fast access to candidate cells. The KNN algorithm for DGR-Tree provides the mechanism, which can access directly to cells enclosing given query point and adjacent cells without tree traversal. The KNN algorithm minimizes sorting cost about candidate lists with minimum distance and provides NEB(Non Extensible Boundary), which need not consider the extension of candidate nodes for KNN search.

유비쿼터스 컴퓨팅 환경에서의 LBS, 즉 u-LBS는 실세계의 수많은 객체가 위치정보와 밀접히 연관된 대용량 데이타를 대상으로 한다. 특히, 사용자의 위치 정보와 관련하여 검색하려고 하는 객체인 POI에 대한 빠른 검색이 중요하다. 따라서 u-LBS에서 POI의 효율적인 검색을 위한 인덱스 구조에 대한 연구가 필요하다. 본 논문에서는 u-LBS에서 정적 POI를 대상으로 이를 효율적으로 검색하기 위한 DGR-Tree를 제시한다. DGR-Tree는 변형된 R-Tree를 기본 인덱스로 하고 동적 레벨 그리드를 보조 인덱스로 사용하는 구조이다. DGR-Tree는 점 데이타에 적합하도록 최적화하고 있으며 리프 노드 간 겹침 문제를 해결한다. DGR-Tree에서 동적 레벨 그리드는 점 데이타의 밀집도에 따라 동적으로 구성되며, 각 셀은 DGR-Tree의 리프 노드와 연계를 위한 포인터를 저장하여 리프 노드를 직접 접근하도록 함으로써 인덱스 접근 성능을 향상시킨다. 또한, 본 논문에서는 DGR-Tree를 위한 KNN 검색 알고리즘을 제시한다. 이 알고리즘에서는 KNN 검색 시 후보 셀에 빠르게 접근하기 위하여 동적 레벨 그 리드를 활용하며, 후보를 노드별로 구분하여 저장함으로써 후보 리스트 내에서의 정렬 비용을 감소시킨다. 마지막으로 실험을 통해 DGR-Tree의 우수성을 입증하였다.

Keywords

References

  1. Beckmann, N., Kriegel, H., Schneider, R., and Seeger, B., "The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles", Proc. of the ACM SIGMOD Intl. Conf. on Management of Data, 1990, pp.323-331.
  2. Bentley, J. L., "Multidimensional Binary Search Trees Used for Associative Searching", Communications of the ACM, Vol.18, No.9, 1975, pp.509-517. https://doi.org/10.1145/361002.361007
  3. Bo, H., and Qiang, W., "A Spatial Indexing Approach for High Performance Location Based Services", The Journal of Navigation, Vol.60, No.1, 2007, pp.83-93. https://doi.org/10.1017/S0373463307004043
  4. Chern, H. H., and Hwang, H. K., "Partial Match Queries in Random Quadtrees", SIAM Journal on Computing, Vol.35, No.6, 2003, pp.904-915.
  5. Frentzos, E., Gratsias, K., and Theodoridis, Y., "Towards the Next Generation of Location-based Services", Proc. of the Intl. Workshop on Web and Wireless Geographical Information Systems, 2007, pp.202-215.
  6. Hjaltason, G. R., and Samet, H., "Distance Browsing in Spatial Databases", ACM Transactions on Database Systems, Vol.24, No.2, 1999, pp.265-318. https://doi.org/10.1145/320248.320255
  7. Manolopoulos, Y., Nardelli, E., Papadopoulos, A., and Proietti, G., "QR-Tree: A Hybrid Spatial Data Structure", Proc. of the Intl. Conf. on Geographic Information Systems in Urban, Regional and Environmental Planning, 1996, pp.3-7.
  8. Robinson, J. T., "The K-D-B-Tree: A Search Structure for Large Multi-dimensional Dynamic Indexes", Proc. of the ACM SIGMOD Intl. Conf. on Management of Data, 1981, pp.10-18.
  9. Roussopoulos, Nick., Kelley, S., and Vincent, F., "Nearest Neighbor Queries", Proc. of the ACM SIGMOD Intl. Conf. on Management of Data, 1995, pp.71-79.
  10. Sellis, T. K., Roussopoulos, N., and Faloutsos, C., "The R+-Tree: A Dynamic Index for Multi-dimensional Objects", Proc. of the Intl. Conf. on VLDB, 1987, pp.507-518.
  11. Wang, W., Yang, J., and Munts, R., "PK-Tree: A Spatial Index Structure for High Dimensional Point Data", Proc. of the Intl. Conf. on Foundations of Data Organization and Algorithms, 1998, pp.27-36.