Spatial-temporal query homogeneity for KNN object search on road networks

We in this paper explore a new research paradigm, called query homogeneity, to process KNN queries on road networks for online LBS applications. While previous works in the literature concentrate on the improvement of query processing time, we turn to examine the issue of response time for a user query, which needs to additionally consider the waiting time in the queue. Note that the response time is the more precise value corresponding to the user experience in an online service, and the unacceptable response time is likely to turn away disgruntled users. Surprisingly, we will show in this paper that the response time will be more significantly dominated by the waiting time but it is left unexplored thus far. Since previous works all perform queries in the one-by-one fashion, which will lead to unexpected long waiting time, we thus in this paper propose a novel query framework, called SHI, aiming at diminishing the waiting time by a new group-by-group solution. SHI relies on the natural phenomenon of query homogeneity, which refers to the behavior that queries are usually issued in the sense of spatial and temporal correlation. Motivated by this natural behavior, operations of query processing and queue processing are incorporated in the SHI framework. During the network expansion for a query, a group of homogeneity queries in the waiting queue, which have results identical to the processing query, will be picked up and flushed out together when the query processing is accomplished, achieving the group-by-group query processing and reducing the waiting time significantly.