Efficient Computation of Continuous Range Skyline Queries in Road Networks
Skyline query processing in road networks has been investigated extensively in recent years. Skyline points for road network applications may be large while the query point may only interest the ones within a certain range. In this paper, we address the i
- PDF / 1,059,016 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 79 Downloads / 214 Views
College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China {jiangshunqing,jzh,chenjialiang,echoyu}@nuaa.edu.cn 2 School of Computer Science and Engineering, University of New South Wales, Sydney, Australia
Abstract. Skyline query processing in road networks has been investigated extensively in recent years. Skyline points for road network applications may be large while the query point may only interest the ones within a certain range. In this paper, we address the issue of efficient evaluation of Continuous Range Skyline Queries (CRSQ) in road networks. Due to the computation of network distance between objects in road networks is expensive and suffers the limitation of memory resources, we propose a novel method named Dynamic Split Points Setting (DSPS) dividing a given path in road networks into several segments. For each segment, we use Network Voronoi Diagrams (NVDs) based technique to calculate the candidate skyline interest points at the starting point of the segment. After that, when the query point moves, we dynamically set the spilt points by DSPS strategy to ensure that when the query point moves within a segment, skyline points remain unchanged and only need to be updated while moving across the split points. Extensive experiments show that our DSPS strategy is efficient compared with previous approaches. Keywords: Continuous range skyline queries voronoi diagram Dynamic split points setting
Road networks
Network
1 Introduction Inspired by the advance in mobile information systems and positioning technology, the research of skyline queries in road networks has received considerable attention. A traditional skyline query retrieves a set of data points that are not dominated by any other points only considering static dimensions. However, skyline queries in road networks not only take the inherent static attributes of targets into consideration, but also consider spatial attribute (network distances between query point and targets). Figure 1 shows an example where 5 points (p1-p5) represent hotels with two inherent static attributes: price and ranking and a query point q represents a user’s location in a road network (shown in Table 1). When issuing a skyline query: find cheaper, higher ranking and also closer hotels, the network distance from each hotel to q becomes one of the dimensions. For detailed hotel information as shown in Table 1, the skyline query results are (p3, p5) for they are cheaper, higher ranking, and closer than others (p1, p2, p4). © Springer International Publishing Switzerland 2016 D.-S. Huang et al. (Eds.): ICIC 2016, Part III, LNAI 9773, pp. 520–532, 2016. DOI: 10.1007/978-3-319-42297-8_48
Efficient Computation of Continuous Range Skyline Queries
521
In our hotel-finding example, if the query point q is a tourist in a moving car from n1 to n2 in the segment n1n2. The tourist may only interest in the hotels which network distance to him/her are within a certain range, e.g. 6 km. We can see that hotel p3 will not be a skyl
Data Loading...
