Euler++: Improved Selectivity Estimation for Rectangular Spatial Records

A. B. Siddique, Ahmed Eldawy, Vagelis Hristidis

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

Selectivity estimation is one of the common research problems for big spatial data, where the objective is to quickly estimate the number of records in a given query range. Euler histogram has been used to answer the selectivity estimation queries for objects with extents such as rectangles in constant time. However, it is only accurate when the query range is aligned with the histogram grid lines. In this paper, we improve the Euler histogram to accurately answer arbitrary queries, i.e., even if they do not align with the histogram grid lines. The improved histogram, called Euler++, has the same space and time complexity as the regular Euler histogram and provides a better accuracy for objects with extents. We use both real and synthetic datasets for extensive experiments, and show that the proposed technique, Euler++, consistently outperforms the existing ones, while still providing answer in constant time.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE International Conference on Big Data, Big Data 2019
EditorsChaitanya Baru, Jun Huan, Latifur Khan, Xiaohua Tony Hu, Ronay Ak, Yuanyuan Tian, Roger Barga, Carlo Zaniolo, Kisung Lee, Yanfang Fanny Ye
Pages4129-4133
Number of pages5
ISBN (Electronic)9781728108582
DOIs
StatePublished - Dec 2019
Event2019 IEEE International Conference on Big Data, Big Data 2019 - Los Angeles, United States
Duration: Dec 9 2019Dec 12 2019

Publication series

NameProceedings - 2019 IEEE International Conference on Big Data, Big Data 2019

Conference

Conference2019 IEEE International Conference on Big Data, Big Data 2019
Country/TerritoryUnited States
CityLos Angeles
Period12/9/1912/12/19

Bibliographical note

Publisher Copyright:
© 2019 IEEE.

Keywords

  • Euler++
  • Spatial data synopsis
  • big spatial data
  • query optimization
  • selectivity estimation

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Information Systems
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'Euler++: Improved Selectivity Estimation for Rectangular Spatial Records'. Together they form a unique fingerprint.

Cite this