The range nearest-neighbor (NN) query is an important query type in location-based services, as it can be applied to the case that an NN query has a spatial region, instead of a location point, as the query location. Examples of the applications of range NN queries include uncertain locations and privacy-preserving queries. Given a set of objects, the range NN answer is a set of objects that includes the nearest object(s) to every point in a given spatial region. The answer set size would signi\ufb01cantly increase as the spatial region gets larger. Unfortunately, mobile users in wireless environments su\ufb00er from scarce bandwidth and low-quality communication, transmitting a large answer set from a database server to the user would pose very high response time. To this end, we propose an approximate range NN query processing algorithm to balance a performance tradeo\ufb00 between query response time and the quality of answers. The distinct features of our algorithm are that (1) it allows the user to specify an approximation tolerance level k, so that we guarantee to provide an answer set A such that each object in A is one of the k nearest objects to every point in a given query region; and (2) it minimizes the number of objects returned in an answer set, in order to minimize the transmission time of sending the answer set to the user. Extensive experimental results show that our proposed algorithm is scalable and e\ufb00ectively reduces query response time while providing approximate query answers that satisfy the user speci\ufb01ed approximation tolerance level.<\/p>\n","protected":false},"excerpt":{"rendered":"
The range nearest-neighbor (NN) query is an important query type in location-based services, as it can be applied to the case that an NN query has a spatial region, instead of a location point, as the query location. Examples of the applications of range NN queries include uncertain locations and privacy-preserving queries. Given a set […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[13547],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-157450","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-systems-and-networking","msr-locale-en_us"],"msr_publishername":"","msr_edition":"The 11th International Symposium on Spatial and Temporal Databases (SSTD)","msr_affiliation":"","msr_published_date":"2009-01-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"207858","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","title":"sstd09-2.pdf","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/sstd09-2.pdf","id":207858,"label_id":0}],"msr_related_uploader":"","msr_attachments":[{"id":207858,"url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/sstd09-2.pdf"}],"msr-author-ordering":[{"type":"text","value":"Chi-Yin Chow","user_id":0,"rest_url":false},{"type":"text","value":"Joe Nap","user_id":0,"rest_url":false},{"type":"user_nicename","value":"sumann","user_id":33753,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=sumann"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[170109],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","related_content":{"projects":[{"ID":170109,"post_title":"SenseWeb","post_name":"senseweb","post_type":"msr-project","post_date":"2008-12-10 10:52:54","post_modified":"2017-06-16 11:08:28","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/senseweb\/","post_excerpt":"SenseWeb is a peer produced sensor network that consists of sensors deployed by contributors across the globe. It allows developing sensing applications that use the shared sensing resources and our sensor querying and tasking mechanisms. SensorMap is one such application that mashes up sensor data from SenseWeb on a map interface, and provides interactive tools to selectively query sensors and visualize data, along with authenticated access to manage sensors.","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170109"}]}}]},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/157450","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/157450\/revisions"}],"predecessor-version":[{"id":542796,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/157450\/revisions\/542796"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=157450"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=157450"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=157450"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=157450"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=157450"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=157450"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=157450"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=157450"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=157450"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=157450"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=157450"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=157450"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=157450"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=157450"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=157450"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=157450"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}