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 proceedingpeer-review

4 Citations (Scopus)


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
Number of pages17
ISBN (Print)9783319444024
Publication statusPublished - 2016
Event27th International Conference on Database and Expert Systems Applications, DEXA 2016 - Porto, Portugal
Duration: 5 Sept 20168 Sept 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


Conference27th International Conference on Database and Expert Systems Applications, DEXA 2016

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Index construction
  • Maximizing range sum
  • Query processing


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

Cite this