For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Efficient Execution of Range Top-k Queries in Aggregate R-Trees
Seokjin HONG Bongki MOON Sukho LEE
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/11/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
spatial database, data warehouse, range top-k query, aggregate R-tree,
Full Text: PDF>>
A range top-k query returns the topmost k records in the order set by a measure attribute within a specified region of multi-dimensional data. The range top-k query is a powerful tool for analysis in spatial databases and data warehouse environments. In this paper, we propose an algorithm to answer the query by selectively traversing an aggregate R-tree having MAX as the aggregate values. The algorithm can execute the query by accessing only a small part of the leaf nodes within a query region. Therefore, it shows good query performance regardless of the size of the query region. We suggest an efficient pruning technique for the priority queue, which reduces the cost of handling the priority queue, and also propose an efficient technique for leaf node organization to reduce the number of node accesses to execute the range top-k queries.