I det maximerande intervallet summan (MaxRS) problem, givet (i) en uppsättning P av 2D-punkter som var och en är associerad med en positiv vikt, och (ii) en rektangel r av specifika omfattninger, måste vi bestämma var att placera r för att maximera den täckta vikten av r -det vill säga, den totala vikten av de datapunkter som omfattas av r. Algoritmer lösa problemet exakt medför dyra CPU eller I / O kostnad. I praktiken är exakta svar ofta inte obligatoriska i en MaxRS-applikation, där lätt imprecision ofta kan tolereras bekvämt, förutsatt att ungefärliga svar kan beräknas betydligt snabbare. Motiverad av detta, den nuvarande papper studerar (1 −  på)-ungefärlig MaxRS-problem, som medger samma ingångar som MaxRS, men syftar istället till att returnera en rektangel vars täckt vikt är minst (1 −  på)m, där m  till är den optimala täckt vikt, och  till kan vara en godtyckligt liten konstant mellan 0 och 1. Vi presenterar snabba algoritmer som löser detta problem med starka teoretiska garantier.
Tao och Al. REF föreslog ett nytt problem som kallas (1- )-ungefärlig MaxRS som returnerar en lösning som kan vara värre än optimal lösning med en faktor som mest; är en godtycklig liten konstant mellan 0 och 1.
Approximate MaxRS in Spatial Databases
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Mathematics', 'Computer Science']}