Font Size: a A A

Research And Implementation Of Location-based Skyline Queries In Road Networks

Posted on:2018-10-12Degree:MasterType:Thesis
Country:ChinaCandidate:S Q JiangFull Text:PDF
GTID:2348330536987948Subject:Software engineering
Abstract/Summary:PDF Full Text Request
With the rapid development of technologies such as mobile communication,GPS spatial positioning,electronic map,the Location Based Service has been widely concerned in transportation,security defense,life entertainment and other fields.Skyline retrieves a set of data points that are not dominated by any other points in all dimensions from database,as an important data analysis method,skyline query has become one of the hot topics in database and information retrieval field in recent years.The dissertation studies the location-based skyline query processing technology in road networks,and provides personalized recommendation services according to the location information of query points.The main work and innovations are as follows:(1)The continues range skyline queries in road networks are studied.Due to computation of network distance between objects in road networks is expensive and suffers the limitation of memories resources,we propose a novel method named Dynamic Split Points Setting(DSPS)dividing a given path in a road network into several segments.For each segment,we adopt the Progressive Incremental Network Expansion technique based on Network Voronoi Diagrams to calculate the candidate skyline interest points.After that,when the query point moves,we dynamicly 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.(2)Considering the increasing complexity of traffic conditions in urban road network traffic,the nearest destination cannot be necessarily reached in the fastest time,the k-th order skyline queries in bicriteria networks is proposed and studied.In bicriteria networks,each edge is labeled with two cost attributes: Euclidean distance and travel-time.The k-th order skyline queries consider distance,time preferences thus having two kinds of skyline queries,named Distance Optimal k-th Order Skyline Query and Time Optimal k-th Order Skyline Query respectively.Two algorithms are designed for each kind of skyline queries in bicriteria networks,the first one is based on incremental network expansion method,while the second one is the improved algorithm based on a maxinmum distance/time restriction strategy.The experiments show that for the second algorithm the number of I/O and CPU time are reduced and the computational efficiency is improved.(3)Considring that skyline queries have extensively investigated for researchers all over the worls,but they are almost restricted to the theoretical algorithm.While develop the skyline queries algorithms,the dissertation implements the algorithms that introduced in the third and fourth chapter into a prototype system which based on QT development framework.The prototype adopts the real California road network map data,selects the corresponding query function and set parameters,it could answer relevant skyline queries and return the corresponding query results.The prototype has a friendly interface,and it can be helpful for the research of skyline queries.
Keywords/Search Tags:Road Networks, Spatial Location, Continues Skyline Queries, Time Attribution, k-th Order, QT Framework
PDF Full Text Request
Related items