KOPS - The Institutional Repository of the University of Konstanz

Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks

Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

ABEYWICKRAMA, Tenindra, Muhammad Aamir CHEEMA, Sabine STORANDT, 2020. Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks. Thirtieth International Conference on Automated Planning and Scheduling. Nancy, Oct 26, 2020 - Oct 30, 2020. In: BECK, J. Christopher, ed., Oliver BUFFET, ed., Jörg HOFFMANN, ed. and others. Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling. Menlo Park, Kalifornien:Association for the Advancement of Artificial Intelligence, pp. 2-10

@inproceedings{Abeywickrama2020Hiera-51740, title={Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks}, url={https://www.aaai.org/ojs/index.php/ICAPS/article/view/6639}, year={2020}, number={30}, address={Menlo Park, Kalifornien}, publisher={Association for the Advancement of Artificial Intelligence}, series={Proceedings of the International Conference on Automated Planning and Scheduling}, booktitle={Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling}, pages={2--10}, editor={Beck, J. Christopher and Buffet, Oliver and Hoffmann, Jörg}, author={Abeywickrama, Tenindra and Cheema, Muhammad Aamir and Storandt, Sabine} }

<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/51740"> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-11-11T10:09:14Z</dcterms:available> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:abstract xml:lang="eng">Location-based services rely heavily on efficient methods that search for relevant points-of-interest (POIs) close to a given location. A k nearest neighbors (kNN) query is one such example that finds k closest POIs from an agent's location. While most existing techniques focus on finding nearby POIs for a single agent, many applications require POIs that are close to multiple agents. In this paper, we study a natural extension of the kNN query for multiple agents, namely, the Aggregate k Nearest Neighbors (AkNN) query. An AkNN query retrieves k POIs with the smallest aggregate distances where the aggregate distance of a POI is obtained by aggregating its distances from the multiple agents (e.g., sum of its distances from each agent). Existing search heuristics are designed for a single agent and do not work well for multiple agents. We propose a novel data structure COLT (Compacted Object-Landmark Tree) to address this gap by enabling efficient hierarchical graph traversal. We then utilize COLT for a wide range of aggregate functions to efficiently answer AkNN queries. In our experiments on real-world and synthetic data sets, our techniques significantly improve query performance, typically outperforming existing approaches by more than an order of magnitude in almost all settings.</dcterms:abstract> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:title>Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks</dcterms:title> <dc:rights>terms-of-use</dc:rights> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/51740"/> <dc:creator>Storandt, Sabine</dc:creator> <dc:creator>Cheema, Muhammad Aamir</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-11-11T10:09:14Z</dc:date> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Abeywickrama, Tenindra</dc:contributor> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dc:contributor>Cheema, Muhammad Aamir</dc:contributor> <dc:language>eng</dc:language> <dc:contributor>Storandt, Sabine</dc:contributor> <dcterms:issued>2020</dcterms:issued> <dc:creator>Abeywickrama, Tenindra</dc:creator> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account