NDLI: Energy efficient exact kNN search in wireless broadcast environments

Please wait, while we are loading the content...

Using ontologies in personalized mobile applications

Road extraction from motion cues in aerial video

Time-dependent affine triangulation of spatio-temporal data

Grid based methods for estimating spatial join selectivity

Enabling routes as context in mobile services

Supporting spatial aggregation in sensor network databases

A novel improvement to the R*-tree spatial index using gain/loss metrics

A partial join approach for mining co-location patterns

The future of traffic control

Representing spatiality in a conceptual multidimensional model

Spatio-temporal aggregates over raster image data

An abstract model of three-dimensional spatial data types

Query processing in a geographic mediation system

Energy efficient exact kNN search in wireless broadcast environments

Efficient query routing in distributed spatial databases

A multi-level data structure for vector maps

Efficient detection of motion patterns in spatio-temporal data sets

Grid metadata catalog service-based OGC web registry service

Automatically and accurately conflating orthoimagery and street maps

A new approach for a topographic feature-based characterization of digital elevation data

Object-relational management of complex geographical objects

Capturing complex multidimensional data in location-based data warehouses

On efficiently processing nearest neighbor queries in a loosely coupled set of data sources

Algorithms for the placement of diagrams on maps

Wavelet fuzzy classification for detecting and tracking region outliers in meteorological data

An authorization model for geographical maps

A spatial hash join algorithm suited for small buffer size

A serverless 3D world

Exploiting online sources to accurately geocode addresses

Adaptive hierarchical RBF interpolation for creating smooth digital elevation models

Discovering personal gazetteers: an interactive clustering approach

Energy efficient exact kNN search in wireless broadcast environments

Content Provider	ACM Digital Library
Author	Gedik, Bugra Singh, Aameek Liu, Ling
Abstract	The advances in wireless communication and decreasing costs of mobile devices have enabled users to access desired information at any time. Coupled with positioning technologies like GPS, this opens up an exciting domain of location based services, allowing a mobile user to query for objects based on its current position. Main bottlenecks in such infrastructures are the draining of power of the mobile devices and the limited network bandwidth available. To alleviate these problems, broadcasting spatial information about relevant objects has been widely accepted as an efficient mechanism. An important class of queries for such an infrastructure is the k-nearest neighbor (kNN) queries, in which users are interested in k closest objects to their position. In this paper, we describe mechanisms to perform exact kNN search on conventional sequential-access R-trees, and optimize established kNN search algorithms. We also propose a novel use of histograms for guiding the search and derive analytical results on maximum queue size and node access count. In addition, we discuss the effects of different broadcast organizations on search performance and challenge the traditional use of Depth-First (dfs) organization. We also extend our mechanisms to support kNN search with non-spatial constraints. While we demonstrate our ideas using a broadcast index, they are equally applicable to any kind of sequential access medium like tertiary tape storage. We validate our mechanisms through an extensive experimental analysis and present our findings.
Starting Page	137
Ending Page	146
Page Count	10
File Format	PDF
ISBN	1581139799
DOI	10.1145/1032222.1032244
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-11-12
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Wireless data broadcast K-nearest neighbor search Air indexes
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in