Efficient Execution of Range Top-<I>k</I> Queries in Aggregate R-Trees

Seokjin HONG; Bongki MOON; Sukho LEE

doi:10.1093/ietisy/e88-d.11.2544

Efficient Execution of Range Top-k Queries in Aggregate R-Trees

Seokjin HONG, Bongki MOON, Sukho LEE

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.11 pp.2544-2554

Publication Date: 2005/11/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.11.2544

Type of Manuscript: PAPER

Category: Database

Cite this

Copy

Seokjin HONG, Bongki MOON, Sukho LEE, "Efficient Execution of Range Top-k Queries in Aggregate R-Trees" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 11, pp. 2544-2554, November 2005, doi: 10.1093/ietisy/e88-d.11.2544.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.11.2544/_p

Copy

@ARTICLE{e88-d_11_2544,
author={Seokjin HONG, Bongki MOON, Sukho LEE, },
journal={IEICE TRANSACTIONS on Information},
title={Efficient Execution of Range Top-k Queries in Aggregate R-Trees},
year={2005},
volume={E88-D},
number={11},
pages={2544-2554},
abstract={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.},
keywords={},
doi={10.1093/ietisy/e88-d.11.2544},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - Efficient Execution of Range Top-k Queries in Aggregate R-Trees
T2 - IEICE TRANSACTIONS on Information
SP - 2544
EP - 2554
AU - Seokjin HONG
AU - Bongki MOON
AU - Sukho LEE
PY - 2005
DO - 10.1093/ietisy/e88-d.11.2544
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2005
AB - 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.
ER -