Earticle

초록

영어

A TPR-tree is a well-known indexing structure that is developed to answer queries about the current or future time locations of moving objects. For the purpose of space efficiency, the TPR-tree employs the notion of VBR (velocity bounding rectangle) so that a regional rectangle presents varying positions of a group of moving objects. Since the rectangle computed from a VBR always encloses the possible maximum range of an indexed object group, a search process only has to follow VBR-based rectangles overlapped with a given query range, while searching toward candidate leaf nodes. Although the TPR-tree index shows up its space efficiency, it easily suffers from the problem of dead space that results from fast and constant expansions of VBR-based rectangles. Against this, the TPR-tree index is enforced to update leaf nodes for reducing dead spaces within them. Such an update-prone feature of the TPR-tree becomes more problematic when the tree is saved in flash storage. This is because flash storage has very expensive update costs. To solve this problem, we propose a new Bloom filter based caching scheme that is useful for reducing updates in a flash TPR-tree. Since the proposed scheme can efficiently control the frequency of updates on a leaf node, it can offer good performance for indexing moving objects in modern flash storage.

목차

Abstract
1. Introduction
2. Preliminaries
2.1. Bloom filter
2.2 TPR-Tree Index
3. Proposed TPR*-tree with BF-caches
3.1 Problem Definition
3.2 BF-Cache for the Proposed TPR*-tree
3.3 Algorithms for the Proposed Flash TPR-tree
4. Performance Evaluation
5. Conclusion
Acknowledgement
References

키워드

저자

• Seong-Chae Lim [ Professor, Dept. of Computer Science, Dongduk Women’s University, South Korea ] Corresponding author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Internet, Broadcasting and Communication

• 간기

  계간

• pISSN

  2288-4920

• eISSN

  2288-4939

• 수록기간

  2009~2025

• 십진분류

  KDC 326 DDC 380