NDLI: Scalable Distributed Processing of Spatial Point Data

Content Provider	IEEE Xplore Digital Library
Author	Raack, M. Kao, O.
Copyright Year	2011
Abstract	The increasing availability of cheap location tracking devices is causing a steadily increasing demand for location based services. Such services usually utilize spatial data structures that need to scale with increasing request load. While static data allows for scaling by simple service replication, dynamic data such as moving users requires administration in a single coherent system to provide consistent and up-to-date processing results. In this paper, we propose a distributed system based on a P2P architecture to store and process spatial data, in particular with window- and k-nearest-neighbors queries. Our system is very simple in that it solely manages a range-partitioned linear data space defined by a Hilbert Curve mapping and neither requires explicit hashing, clustering or the maintenance of a dedicated distributed spatial structure at all. Our main focus is on the inherent quad-tree structure of the 2d Hilbert Curve and how it suffices to efficiently evaluate nearest-neighbor queries in a distributed manner. We verify our approach using real-world data from Open Street Map and demonstrate that the throughput of our system scales asymptotically linear with the network size.
Starting Page	597
Ending Page	604
File Size	681835
Page Count	8
File Format	PDF
ISBN	9781457718755
ISSN	15219097
e-ISBN	9780769545769
DOI	10.1109/ICPADS.2011.114
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-12-07
Publisher Place	Taiwan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Distributed databases Spatial databases Peer to peer computing Partitioning algorithms Spatial indexes Maintenance engineering hilbert curve p2p distributed spatial index spatial queries window queries nearest neighbor queries
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture

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