23 March 2016 in IEEE Transactions on Knowledge and Data Engineering
A representative skyline contains $k$ skyline points that can represent its corresponding full skyline. The existing measuring criteria of $k$ representative skylines are specifically designed for static data, and they cannot effectively handle streaming data. In this paper, we focus on the problem of calculating the $k$ representative skyline over data streams. First, we propose a new criterion to choose $k$ skyline points as the $k$ representative skyline for data stream environments, termed the $k$ largest dominance skyline ( $k$ -LDS), which is representative to the entire data set and is highly stable over the streaming data. Second, we propose an efficient exact algorithm, called Prefix-based Algorithm (PBA), to solve the $k$ -LDS problem in a 2-dimensional space. The time complexity of PBA is only $\mathcal {O}((M-k)\times k)$ where $M$ is the size of the full skyline set. Third, the $k$ -LDS problem for a $d$ -dimensional ( $d\ge 3$ ) space turns out to be very complex. Therefore, a greedy algorithm is designed to answer $k$ -LDS queries. To further accelerate the calculation, we propose a $\epsilon$ -greedy algorithm which can achieve an approximate factor of $\frac{1}{(1+\epsilon)}(1-\frac{1}{\sqrt{e}})$ . Experimental results on both synthetic and real-world data show that our $k$ -LDS significantly outperforms its competitors in data stream environments. Furthermore, we demonstrate that the proposed $\epsilon$ -greedy algorithm can solve $k$ -LDS efficiently and with a competitive accuracy.
30 October 2015 in Frontiers of Computer Science
1 January 2021 in Wireless Communications and Mobile Computing
With the widespread application of location‐based service (LBS) technology in the urban Internet of Things, urban transportation has become a research hotspot. One key issue of urban transportation is the nearest neighbor search of moving objects along a road network. The fast‐updating operations of moving objects along a road network suppress the query response time of urban services. Thus, a tree‐indexed searching method is proposed to quickly find the answers to user‐defined queries on frequently updating road networks. First, a novel index structure, called the double tree‐hash index, is designed to reorganize the corresponding relationships of moving objects and road networks. Second, an index‐enhanced search algorithm is proposed to quickly find the k‐nearest neighbors of moving objects along the road network. Finally, an experiment shows that compared with state‐of‐the‐art algorithms, our algorithm shows a significant improvement in search efficiency on frequently updating road networks.
2 April 2016 in World Wide Web
30 January 2018 in IEEE Access
Skyline queries play an important role in multiple criteria decision making problems. A representative skyline set contains k skyline points that can represent its full skyline set which is more significant. The distance-based representative skyline (k-DRS) is a kind of representative skyline which can describe the tradeoffs among different dimensions offered by the full skyline set. The previous works only focus on the k-DRS queries in total order domains. In this paper, we focus on the k-DRS problem in both total and partial order domains. Since k-DRS is a NP-hard problem in d-dimensional (d ≥ 3) space, it is impossible to calculate the exact k-DRS in d-dimensional space. By in-depth analyzing the properties of the k-DRS, we propose an algorithm DRSTP (k-DRS query algorithm in total and partial order, DRSTP for short) to solve the k-DRS problem from a new perspective. In DRSTP, first, a value in partial order domain is transformed to numerical values in total order domains. Thus the distance of any two partial values can be measured using the transformed values. Then we apply US-ELM to divide the full skyline set into k clusters. Next, in each cluster, we design a method to select a point as the representative point. Experimental results show that our DRSTP significantly outperforms its competitors in terms of both accuracy and efficiency.