Paper Info
Title
Eliminating Duplicates under Interval and Fuzzy Uncertainty: An Asymptotically Optimal Algorithm and Its Geospatial Applications
Abstract
Geospatial databases generally consist of measurements related to points (or pixels in the case of raster data), lines, and polygons. In recent years, the size and complexity of these databases have increased significantly and they often contain duplicate records, i.e., two or more close records representing the same measurement result. In this paper, we address the problem of detecting duplicates in a database consisting of point measurements. As a test case, we use a database of measurements of anomalies in the Earth's gravity field that we have compiled. In this paper, we show that a natural duplicate deletion algorithm requires (in the worst case) quadratic time, and we propose a new asymptotically optimal O(n⋅ log (n)) algorithm. These algorithms have been successfully applied to gravity databases. We believe that they will prove to be useful when dealing with many other types of point data.
Year
DOI
Venue
2004
10.1023/B:REOM.0000032121.21617.38
Reliable Computing
Keywords
Field
DocType
Voronoi Diagram, Computational Geometry, Cleaning Step, Gravity Measurement, Original Database
Data mining,Raster data,Mathematical optimization,Polygon,Computational geometry,Fuzzy logic,Algorithm,Data type,Pixel,Time complexity,Asymptotically optimal algorithm,Mathematics
Journal
Volume
Issue
ISSN
10
5
1573-1340
Citations 
PageRank 
References 
4
0.60
6
Authors
5
Name
Order
Citations
PageRank
Roberto Torres115914.30
G. Randy Keller240.60
Vladik Kreinovich31091281.07
Luc Longpré424530.26
Scott A. Starks56112.76