Identifying the most interactive object in spatial databases

Amagata, Daichi; Hara, Takahiro

doi:https://doi.org/10.1109/ICDE.2019.00117

Identifying the most interactive object in spatial databases

Amagata, Daichi; Hara, Takahiro

Proceedings - International Conference on Data Engineering, 2019, 2019-April, 1286-1297

Number of Access:712（2025-08-15 06:45 Counts）

Identifier to cite or link to this item: https://hdl.handle.net/11094/92850

Link to primary information

File	Format	Terms of use	Size	Views	Date.Available	Description	information
ProcIntConfDataEng_2019-April_1286	pdf	None	1.08 MB	91	2023.10.30

Item Information

Output File Export EndNote Basic Export Mendeley

Title	Identifying the most interactive object in spatial databases
Creator	NRID 1000040770649 1000040770649 researchmap permalink amgt amgt Scopus Author ID 55811167300 55811167300 CreatorName Amagata, Daichi
Creator	NRID 1000020294043 1000020294043 ORCID 0000-0003-4807-3156 0000-0003-4807-3156 researchmap permalink hara-osakau hara-osakau Scopus Author ID 7404213547 7404213547 CreatorName Hara, Takahiro
Subject	Mio query
Subject	Spatial databases
Description	Amagata D., Hara T.. Identifying the most interactive object in spatial databases. Proceedings - International Conference on Data Engineering 2019-April, 1286 (2019); https://doi.org/10.1109/ICDE.2019.00117.
Abstract	This paper investigates a new query, called an MIO query, that retrieves the Most Interactive Object in a given spatial dataset. Consider that an object consists of many spatial points. Given a distance threshold, we say that two objects interact with each other if they have a pair of points whose distance is within the threshold. An MIO query outputs the object that interacts with other objects the most, and it is useful for analytical applications e.g., neuroscience and trajectory databases. The MIO query processing problem is challenging: a nested loop algorithm is computationally inefficient and a theoretical algorithm is computationally efficient but incurs a quadratic space cost. Our solution efficiently processes MIO queries with a novel index, BIGrid (a hybrid index of compressed Bitset, Inverted list, and spatial Grid structures), with a practical memory cost. Furthermore, our solution is designed so that previous query results and multi-core environments can be exploited to accelerate query processing efficiency. Our experiments on synthetic and real datasets demonstrate the efficiency of our solution.
Conference Information	Conference Name International Conference on Data Engineering Conference Sequence 35 Conference Date April 8th to April 11th, 2019 Conference Place Macao Conference Country China
Publisher	IEEE Computer Society
Source Title	Proceedings - International Conference on Data Engineering
Volume (Issue)	2019-April
Page	1286-1297
Date of Issued	2019-04-01
Language	English
Handle URL	https://hdl.handle.net/11094/92850
PISSN	10844627
Relation.isVersionOf	DOI (Publisher Version) https://doi.org/10.1109/ICDE.2019.00117
Relation.isPartOf	ISBN 9781538674741
Relation.isPartOf	ISBN 9781538674758
Access Rights	open access
CopyRight	© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
oaire:version	Accepted Manuscript
Category	会議発表論文 Conference Paper

Resource Type	conference paper
Local Type	Conference Paper
DCMI Type	Text
DCTERMS.bibliographicCitation	Proceedings - International Conference on Data Engineering. 2019, 2019-April, p. 1286-1297
DC.title	Identifying the most interactive object in spatial databases
DC.creator	Amagata, Daichi
DC.creator	Hara, Takahiro
DC.publisher	IEEE Computer Society
DC.language' scheme='DCTERMS.RFC1766	English
DC.type' scheme='DCTERMS.DCMIType	Text
DCTERMS.issued' scheme='DCTERMS.W3CDTF	2019-04-01
DC.identifier	https://doi.org/10.1109/ICDE.2019.00117
DC.subject	Mio query
DC.subject	Spatial databases
DC.description	Amagata D., Hara T.. Identifying the most interactive object in spatial databases. Proceedings - International Conference on Data Engineering 2019-April, 1286 (2019); https://doi.org/10.1109/ICDE.2019.00117.
DCTERMS.abstract	This paper investigates a new query, called an MIO query, that retrieves the Most Interactive Object in a given spatial dataset. Consider that an object consists of many spatial points. Given a distance threshold, we say that two objects interact with each other if they have a pair of points whose distance is within the threshold. An MIO query outputs the object that interacts with other objects the most, and it is useful for analytical applications e.g., neuroscience and trajectory databases. The MIO query processing problem is challenging: a nested loop algorithm is computationally inefficient and a theoretical algorithm is computationally efficient but incurs a quadratic space cost. Our solution efficiently processes MIO queries with a novel index, BIGrid (a hybrid index of compressed Bitset, Inverted list, and spatial Grid structures), with a practical memory cost. Furthermore, our solution is designed so that previous query results and multi-core environments can be exploited to accelerate query processing efficiency. Our experiments on synthetic and real datasets demonstrate the efficiency of our solution.
DC.rights	© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
DC.format	92850
citation_title	Identifying the most interactive object in spatial databases
citation_author	Amagata, Daichi
citation_author	Hara, Takahiro
citation_publisher	IEEE Computer Society
citation_language	English
citation_date	2019-04-01
citation_journal_title	Proceedings - International Conference on Data Engineering
citation_volume	2019-April
citation_firstpage	1286
citation_lastpage	1297
citation_doi	https://doi.org/10.1109/ICDE.2019.00117
citation_public_url	https://hdl.handle.net/11094/92850

Identifying the most interactive object in spatial databases

Link to primary information

Item Information

Show details