research-article

Spatial search processing in embedded devices

Authors:

Masanori IrieAuthors Info & Claims

GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Pages 516 - 519

https://doi.org/10.1145/1653771.1653858

Published: 04 November 2009 Publication History

Get Access

Abstract

Focusing on applying a spatial database management system to embedded devices, we present a spatial search processing method. First, we consider disk storage space to be a severe constraint in embedded devices, we propose a spatial index tree based on the PMR quadtree to reduce the required disk storage space. Second, since we consider it necessary to shorten the processing time for a spatial search in embedded devices, we present efficient range search algorithm in our index tree. The simulation results show that our index tree has a smaller disk storage space requirement than conventional index trees, and our range search method does not require as many disk accesses as conventional methods.

References

[1]

Hitachi, Ltd., Entier Embedded Database, URL: http://www.hitachi.us/Apps/hitachicom/content.jsp?page=index.html&path=jsp/hitachi/forbus/entier/.

Google Scholar

[2]

Oracle, Oracle Database Lite 10g, URL: http://www.oracle.com/technology/products/lite/index.html.

Google Scholar

[3]

IBM, DB2 Everyplace, URL: http://www-306.ibm.com/software/data/db2/everyplace/.

Google Scholar

[4]

J. Goldstein, R. Ramakrishnan, and U. Shaft: Compressing relations and indexes, Proc. of ICDE'98, pp. 370--379 (1998).

Digital Library

Google Scholar

[5]

H. Hayashi, D. Ito, M. Tanizaki, K. Kimura, and H. Kajiyama: Dual-heap kNN: k-nearest neighbor search for spatial data retrieval in embedded DBMS, Proc. of ACM GIS'08, pp. 357--366 (2008).

Digital Library

Google Scholar

[6]

E. G. Hoel and H. Samet: Efficient processing of spatial queries in line segment databases, Proc. of Int'l Symp. on Advances in Spatial Databases (SSD'91), pp. 237--256 (1991).

Digital Library

Google Scholar

[7]

G. R. Hjaltason and H. Samet: Speeding up construction of PMR quadtree-based spatial indexes, VLDB journal vol. 11, no. 2, pp. 109--137 (2002).

Digital Library

Google Scholar

[8]

J. Lee and S. Zlatanova: 3D Geo-Information Sciences (Lecture Notes in Geoinformation and Cartography), Springer (2008).

Google Scholar

[9]

G. M. Morton: A computer oriented geodetic data base and a new technique in file sequencing, IBM Technical Report (1966).

Google Scholar

[10]

H. Samet: Foundations of multidimensional and metric data structures, The Morgan Kaufmann Series in Computer Graphics (2006).

Digital Library

Google Scholar

[11]

A. Sato and M. Tanizaki, "OGC OWS-6 Outdoor and Indoor 3D Routing Services Engineering Report," OGC 09-067rl (2009, to appear).

Google Scholar

[12]

H. Tropf and H. Herzog: Multidimensional range search in dynamically balanced trees, Angewandte informatik, pp. 71--77 (1981).

Google Scholar

Cited By

View all

Hayashi HAsahara ASugaya NOgawa YTomita H(2015)Spatio-temporal join technique for disaster estimation in large-scale natural disasterProceedings of the 6th ACM SIGSPATIAL International Workshop on GeoStreaming10.1145/2833165.2833171(49-58)Online publication date: 3-Nov-2015
https://dl.acm.org/doi/10.1145/2833165.2833171

Index Terms

Spatial search processing in embedded devices
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Information systems applications
    1. Spatial-temporal systems

Recommendations

Dual-heap kNN: k-nearest neighbor search for spatial data retrieval in embedded DBMS
GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

In this paper, we present a kNN search method called the dual-heap kNN method, which is used in an embedded database management system (DBMS) for in-vehicle information systems. The dual-heap kNN method is based on two conventional kNN methods: (1) the ...
Development of an embedded spatial MMDBMS for spatial mobile devices
W2GIS'05: Proceedings of the 5th international conference on Web and Wireless Geographical Information Systems

Recently, with the development of wireless communications and mobile computing, interest in mobile computing is rising. Mobile computing can be regarded as an environment where a user carries mobile devices and shares resources with a server via ...
Efficient query processing on large spatial databases

A spatial index, called xBR+-tree, is compared against the R*-tree and the R+-tree.Performance of tree building and processing of common spatial queries is studied.Existing and new algorithms for processing these queries are utilized.Extensive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2009

575 pages

ISBN:9781605586496

DOI:10.1145/1653771

General Chairs:
Ouri Wolfson
University of Illinois at Chicago
,
Divyakant Agrawal
University of California, Santa Barbara
,
Chang-Tien Lu
Virginia Tech

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GIS '09

Sponsor:

SIGSPATIAL

GIS '09: 17th SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 4 - 6, 2009

Washington, Seattle

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
15
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hayashi HAsahara ASugaya NOgawa YTomita H(2015)Spatio-temporal join technique for disaster estimation in large-scale natural disasterProceedings of the 6th ACM SIGSPATIAL International Workshop on GeoStreaming10.1145/2833165.2833171(49-58)Online publication date: 3-Nov-2015
https://dl.acm.org/doi/10.1145/2833165.2833171

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Dual-heap kNN: k-nearest neighbor search for spatial data retrieval in embedded DBMS

Development of an embedded spatial MMDBMS for spatial mobile devices

Efficient query processing on large spatial databases