General purpose index-based method for efficient MaxRS query

Xiaoling Zhou*, Wei Wang, Jianliang XU

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

3 Citations (Scopus)

Abstract

The Maximizing Range Sum problem is widely applied in facility locating, spatial data mining, and clustering problems. The current most efficient method solves it in time O(n log n) for a particular given rectangle size. This is inefficient in cases where the queries are frequently called with different parameters. Thus, in this paper, we propose an index-based method that solves the maxRS query in time O(log n) for any given query. Besides, our method can be used to solve the k-enclosing problem in time O(1) for any given k value if indexes are sorted according to the optimizing criteria, or O((n − k)2k + n log n) without using any index, which is comparative to the current most efficient work.

Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications - 27th International Conference, DEXA 2016, Proceedings
EditorsSven Hartmann, Hui Ma
PublisherSpringer Verlag
Pages20-36
Number of pages17
ISBN (Print)9783319444024
DOIs
Publication statusPublished - 2016
Event27th International Conference on Database and Expert Systems Applications, DEXA 2016 - Porto, Portugal
Duration: 5 Sep 20168 Sep 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9827 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Conference on Database and Expert Systems Applications, DEXA 2016
Country/TerritoryPortugal
CityPorto
Period5/09/168/09/16

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Index construction
  • Maximizing range sum
  • Query processing

Fingerprint

Dive into the research topics of 'General purpose index-based method for efficient MaxRS query'. Together they form a unique fingerprint.

Cite this