Paper Info
Title
Q+Tree: An Efficient Quad Tree based Data Indexing for Parallelizing Dynamic and Reverse Skylines
Abstract
Skyline queries play an important role in multi-criteria decision making applications of many areas. Given a dataset of objects, a skyline query retrieves data objects that are not dominated by any other data object in the dataset. Unlike standard skyline queries where the different aspects of data objects are compared directly, dynamic and reverse skyline queries adhere to the around-by semantics, which is realized by comparing the relative distances of the data objects w.r.t. a given query. Though, there are a number of works on parallelizing the standard skyline queries, only a few works are devoted to the parallel computation of dynamic and reverse skyline queries. This paper presents an efficient quad-tree based data indexing scheme, called Q+Tree, for parallelizing the computations of the dynamic and reverse skyline queries. We compare the performance of Q+Tree with an existing quad-tree based indexing scheme. We also present several optimization heuristics to improve the performance of both of the indexing schemes further. Experimentation with both real and synthetic datasets verify the efficiency of the proposed indexing scheme and optimization heuristics.
Year
DOI
Venue
2016
10.1145/2983323.2983764
ACM International Conference on Information and Knowledge Management
Keywords
Field
DocType
Quad Tree,Aggressive Partitioning,Dynamic Skyline,Reverse Skyline,Load Balancing,Parallel Computation
Skyline,Data mining,Data structure,Load balancing (computing),Computer science,Search engine indexing,Theoretical computer science,Heuristics,Semantics,Computation,Quadtree
Conference
Citations 
PageRank 
References 
3
0.37
21
Authors
4
Name
Order
Citations
PageRank
Md. Saiful Islam120953.11
Chengfei Liu21402127.17
J. Wenny Rahayu31275106.72
Tarique Anwar4528.65