Hypersphere dominance: an optimal approach

Cheng Long, Raymond Chi-Wing Wong, Bin Zhang, Min Xie

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Hyperspheres are commonly used for representing uncertain objects (in uncertain databases) and for indexing spatial objects (in spatial databases). An interesting operator on hyperspheres called dominance is to decide for two given hyperspheres whether one dominates (or is closer than) the other wrt a given query hypersphere. In this paper, we propose an approach called Hyperbola which is optimal in the sense that it gives neither false positives nor false negatives and runs in linear time wrt the dimensionality. To the best of our knowledge, Hyperbola is the first optimal approach for the dominance problem on hyperespheres with any dimensionality. We also study an application of the dominance problem which relies on the dominance operator as the core component. We conducted extensive experiments on both real and synthetic datasets which verified our approaches.
Original languageEnglish
Title of host publicationProceedings of the 2014 ACM SIGMOD International Conference on Management of Data
Place of PublicationSnowbird, USA
PublisherAssociation for Computing Machinery
Pages111-122
Number of pages12
ISBN (Electronic)978-1-4503-2376-5
Publication statusPublished - 2014
Externally publishedYes

Fingerprint

Dive into the research topics of 'Hypersphere dominance: an optimal approach'. Together they form a unique fingerprint.

Cite this