Z-SKY: An Efficient Skyline Query Processing Framework Based on Z-Order
Given a set of data points in a multidimensional space, a skyline query retrieves those data points that are not dominated by any other point in the same dataset. Observing that the properties of Z-order space filling curves (or Z-order curves) perfectly match with the dominance relationships among...
Saved in:
Main Authors: | , , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2010
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/1985 https://ink.library.smu.edu.sg/context/sis_research/article/2984/viewcontent/ZhengBH_2010_Z_SKY_EfficientSkylineQueryProcessingFramework_afv.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-2984 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-29842015-12-25T10:14:46Z Z-SKY: An Efficient Skyline Query Processing Framework Based on Z-Order LEE, Ken C. K. LEE, Wang-chien ZHENG, Baihua LI, Huajing TIAN, Yuan Given a set of data points in a multidimensional space, a skyline query retrieves those data points that are not dominated by any other point in the same dataset. Observing that the properties of Z-order space filling curves (or Z-order curves) perfectly match with the dominance relationships among data points in a geometrical data space, we, in this paper, develop and present a novel and efficient processing framework to evaluate skyline queries and their variants, and to support skyline result updates based on Z-order curves. This framework consists of ZBtree, i.e., an index structure to organize a source dataset and skyline candidates, and a suite of algorithms, namely, (1) ZSearch, which processes skyline queries, (2) ZInsert, ZDelete and ZUpdate, which incrementally maintain skyline results in presence of source dataset updates, (3) ZBand, which answers skyband queries, (4) ZRank, which returns top-ranked skyline points, (5) k-ZSearch, which evaluates k-dominant skyline queries, and (6) ZSubspace, which supports skyline queries on a subset of dimensions. While derived upon coherent ideas and concepts, our approaches are shown to outperform the state-of-the-art algorithms that are specialized to address particular skyline problems, especially when a large number of skyline points are resulted, via comprehensive experiments. 2010-06-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/1985 info:doi/10.1007/s00778-009-0166-x https://ink.library.smu.edu.sg/context/sis_research/article/2984/viewcontent/ZhengBH_2010_Z_SKY_EfficientSkylineQueryProcessingFramework_afv.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Skyline query Skyline query result update Index Search algorithm Z-order space filling curve Databases and Information Systems Numerical Analysis and Scientific Computing |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Skyline query Skyline query result update Index Search algorithm Z-order space filling curve Databases and Information Systems Numerical Analysis and Scientific Computing |
spellingShingle |
Skyline query Skyline query result update Index Search algorithm Z-order space filling curve Databases and Information Systems Numerical Analysis and Scientific Computing LEE, Ken C. K. LEE, Wang-chien ZHENG, Baihua LI, Huajing TIAN, Yuan Z-SKY: An Efficient Skyline Query Processing Framework Based on Z-Order |
description |
Given a set of data points in a multidimensional space, a skyline query retrieves those data points that are not dominated by any other point in the same dataset. Observing that the properties of Z-order space filling curves (or Z-order curves) perfectly match with the dominance relationships among data points in a geometrical data space, we, in this paper, develop and present a novel and efficient processing framework to evaluate skyline queries and their variants, and to support skyline result updates based on Z-order curves. This framework consists of ZBtree, i.e., an index structure to organize a source dataset and skyline candidates, and a suite of algorithms, namely, (1) ZSearch, which processes skyline queries, (2) ZInsert, ZDelete and ZUpdate, which incrementally maintain skyline results in presence of source dataset updates, (3) ZBand, which answers skyband queries, (4) ZRank, which returns top-ranked skyline points, (5) k-ZSearch, which evaluates k-dominant skyline queries, and (6) ZSubspace, which supports skyline queries on a subset of dimensions. While derived upon coherent ideas and concepts, our approaches are shown to outperform the state-of-the-art algorithms that are specialized to address particular skyline problems, especially when a large number of skyline points are resulted, via comprehensive experiments. |
format |
text |
author |
LEE, Ken C. K. LEE, Wang-chien ZHENG, Baihua LI, Huajing TIAN, Yuan |
author_facet |
LEE, Ken C. K. LEE, Wang-chien ZHENG, Baihua LI, Huajing TIAN, Yuan |
author_sort |
LEE, Ken C. K. |
title |
Z-SKY: An Efficient Skyline Query Processing Framework Based on Z-Order |
title_short |
Z-SKY: An Efficient Skyline Query Processing Framework Based on Z-Order |
title_full |
Z-SKY: An Efficient Skyline Query Processing Framework Based on Z-Order |
title_fullStr |
Z-SKY: An Efficient Skyline Query Processing Framework Based on Z-Order |
title_full_unstemmed |
Z-SKY: An Efficient Skyline Query Processing Framework Based on Z-Order |
title_sort |
z-sky: an efficient skyline query processing framework based on z-order |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2010 |
url |
https://ink.library.smu.edu.sg/sis_research/1985 https://ink.library.smu.edu.sg/context/sis_research/article/2984/viewcontent/ZhengBH_2010_Z_SKY_EfficientSkylineQueryProcessingFramework_afv.pdf |
_version_ |
1770571764218200064 |