|
|
 |
| |
|
|
|
A Precomputed Method for Skyline Evaluation |
|
|
|
PP: 1901-1914 |
|
|
|
doi:10.18576/amis/100532
|
|
|
|
Author(s) |
|
|
|
Mei-Tzu Wang,
|
|
|
|
Abstract |
|
|
| In a mobile environment, the query point may take dynamic distance as a factor to determine the skyline. But few research
works involve such a situation. Most efforts are focused on static attributes in static environments. From literature, we also found that
most query points are assumed on an unconstrained space. To have the query that involves dynamic distance in constrained space be
evaluated more efficiently, a pre-computed method is proposed. We express dominance relation with respect to static attributes as a
dominance graph, which is better suited for evaluation. Local pruning is performed within equivalence classes, whereas computing the
skyline is by navigating the graph. Given the number of data points n in the dataset, the analysis indicates that the proposed method has
complexity of the order of O(n). Experimental studies show that the proposed method is much more efficient and more stable than the
existing method BNL. Besides, the dominance graph can be reused indefinitely until some data point changes its static attribute value. |
|
|
|
|
|
|
|
