IEEE Transactions on Knowledge and Data Engineering · 2019 · 20 citations · 21 references
ComputingComputer ScienceGeoinformaticsGeographic Information ScienceGeographic Information SystemsInformation RetrievalGeographic Information RetrievalQuery ProcessingSearch SystemsSearching AlgorithmsSpatial DatabasesVoronoi DiagramsApproximate Voronoi DiagramsGeographic Query ProcessingIndex StructuresIndexingIndexing SystemsProximityScalable Spatial IndexingSpatial Indexing
A significant proportion of all search volume consists of local searches. As a result, search engines must be capable of finding relevant results combining both spatial proximity and textual relevance with high query throughput. We observe that existing techniques answering these spatial keyword queries use keyword aggregated indexing, which has several disadvantages on road networks. We propose K-SPIN, a versatile framework that instead uses keyword separated indexing to delay and avoid expensive operations. At first glance, this strategy appears to have impractical pre-processing costs. However, by exploiting several useful observations, we make the indexing cost not only viable but also light-weight. For example, we propose a novel p-Approximate Network Voronoi Diagram (NVD) with one order of magnitude less space cost than exact NVDs. By carefully exploiting features of the K-SPIN framework, our query algorithms are up to two orders of magnitude more efficient than the state-of-the-art as shown in our experimental investigation on various queries, parameter settings, and real road network and keyword datasets.
21
Optimal aggregation algorithms for middleware
Ronald Fagin, Amnon Lotem, Moni Naor · 2001 · 1.1K citations
Computing the shortest path: A search meets graph theory
Andrew V. Goldberg, Chris Harrelson · 2005 · 728 citations
Spatial keyword query processing
Lisi Chen, Gao Cong, Christian S. Jensen et al. · Proceedings of the VLDB Endowment · 2013 · 305 citations