Top-k point of interest retrieval using standard indexes

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

With the proliferation of Internet-connected, location-aware mobile devices, such as smartphones, we are also witnessing a proliferation and increased use of map-based services that serve information about relevant Points of Interest (PoIs) to their users.

We provide an efficient and practical foundation for the processing of queries that take a keyword and a spatial region as arguments and return the k most relevant PoIs that belong to the region, which may be the part of the map covered by the user's screen. The paper proposes a novel technique that encodes the spatio-textual part of a PoI as a compact bit string. This technique extends an existing spatial encoding to also encode the textual aspect of a PoI in compressed form. The resulting bit strings may then be indexed using index structures such as B-trees or hashing that are standard in DBMSs and key-value stores. As a result, it is straightforward to support the proposed functionality using existing data management systems. The paper also proposes a novel top-k query algorithm that merges partial results while providing an exact result.

An empirical study with real-world data indicates that the proposed techniques enable excellent indexing and query execution performance on a standard DBMS
Original languageEnglish
Title of host publicationProceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL '14
EditorsYan Huang, Markus Schneider
Number of pages10
PublisherAssociation for Computing Machinery
Publication year2014
Pages 173-182
ISBN (print) 978-1-4503-3131-9
DOIs
Publication statusPublished - 2014
EventACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - Dallas, United States
Duration: 4 Nov 20147 Nov 2014
Conference number: 22

Conference

ConferenceACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
Nummer22
LandUnited States
ByDallas
Periode04/11/201407/11/2014

See relations at Aarhus University Citationformats

ID: 85048343