Polygon Similarity Benchmark Dataset
Mallika Kankanamalage, Buddhi Ashan; Puri, Satish; Prasad, Sushil
- Publisher
- Zenodo
- Language
- en
Abstract
Dataset Description: Polygon Similarity Benchmark Dataset Overview This dataset provides a curated collection of polygonal shapes derived from SpatialHadoop GIS dataset: Parks, Water Bodies, and Sports.It is intended to support research in polygon representation learning, geometric similarity search, and spatial indexing. The dataset includes raw polygonal geometries, pre-computed similarity ground truth, and supplementary documentation. For each dataset category, 80% of the polygons were used to build the similarity index, while the remaining 20% were reserved exclusively for evaluation. Dataset Contents The distributed ZIP package contains the following files: 1. ShapeToVecResults2.pdf A supplementary document containing additional experimental results referenced in the publication. 2. poly_data.zip A collection of polygonal GIS datasets extracted from SpatialHadoop. These represent the input geometries used for similarity computation. 3. Ground Truth Files These archives contain precomputed shape similarity results for each domain: parks.tar water_bodies.tar sports_all-query.tar.gz Each ground-truth archive consists of multiple text files, where each line represents a similarity query result. How to Extract the Archives You can extract any of the above `.tar` or `.tar.gz` archives using the methods below, depending on your operating system. Linux Use the tar command in the Terminal: tar -xvf archive_name.tar tar -xzvf archive_name.tar.gz This extracts the files into the current directory. macOS Extraction commands are the same as Linux. Open the Terminal and run: tar -xvf archive_name.tar tar -xzvf archive_name.tar.gz You may also double-click the archive in Finder to extract it automatically. Windows Open the PowerShell (Windows 10 and later): tar -xvf archive_name.tar tar -xzvf archive_name.tar.gz You may also use your preferred uncompress software on Windows (e.g., 7-Zip, WinRAR, or PeaZip) to extract both .tar and .tar.gz archives. Ground Truth Format Each line in a ground-truth file encodes: <input_polygon_id> <similar_polygon_id_1> <similar_polygon_id_2> ... <similar_polygon_id_k> The first value is the ID of the input polygon. The subsequent values are the IDs of polygons determined to be most similar based on geometric shape similarity. The list of similar polygons is sorted in decreasing order of similarity, with the most similar polygon appearing first. These ground-truth lists were generated using geometric similarity (Jaccard Similarity) metrics for evaluation and benchmarking of vector-based polygon encodings. Intended Use This dataset is primarily designed for: Research on polygon representation learning, embedding models, and shape encoders. Benchmarking approximate nearest-neighbor (ANN) algorithms on spatial shape data. Studying spatial indexing, vector search strategies, and geometric similarity measures. GIS analytics, spatial data mining, and machine learning applications involving polygonal geometries.
Full text
Appendix: ShapeToVec: Encoding Polygonal Shapes with Extreme Area Variability for Effective Approximate Jaccard Similarity Queries 1 Feature Vector Max Recall Rate The recall rate metric estimates the number of true positives expected while searching over the index. Since our approach preprocesses the input polygonal data into feature vectors, errors can arise during the polygon encoding and indexing phases. We designed the following experiment to estimate an upper bound on recall after the encoding phase independent of indexing methods. We used bit-encoded feature vectors in this experiment. The brute force all-to-all comparison approach is the most suitable method for this evaluation. However, we did not use it since it is impractical on large datasets. First, we retrieved the 500 most similar polygons for each test polygon from the ground truth data. Subsequently, we computed the Jaccard similarity between each test polygon and the retrieved polygons using their corresponding feature vectors. Next, we arranged them in descending order based on their Jaccard similarity, which was calculated using corresponding feature vectors, to identify the 50 most similar polygons. Finally, we compared the top 50 similar polygons from the ground truth dataset with the subset of 50 polygons computed based on vectors. These recall rates are recorded in Table 1 and indicate that the feature vectors produced using the quad tree-based approach are much more accurate than those encoded using the uniform grid-based approach. Table 1: Max recall rates independent of the index method. Encoding method Grid size Recall for K=50 Uniform grid-based 6,084 11% 18,225 11% Quad tree-based 6,004 77% 18,220 79% 2 Number of Nonzero elements in a feature vector The number of nonzero (NNZ) elements in a feature vector is significant when comparing two vectors as these elements contain shape information about the polygons. Low NNZ elements in the vectors may lead to insufficient information during the comparison operation, potentially compromising high recall. Figure 1 depicts a plot of NNZ elements in the feature vectors over the Parks dataset. We maintain a grid size of approximately 35k in each polygon encoding technique. The feature vectors encoded using the uniform grid approach tend to have lower NNZ elements, whereas those generated using the quad treebased approach tend to have higher NNZ elements. This illustrates that the quad tree-based method can incorporate more information in the feature vectors to represent a polygon, suggesting its appropriateness for handling real-world datasets. 1
Number of nonzero vector elements Polygons Uniform grid-based encoding Quad tree grid-based encoding 10 20 40 60 80 100 Figure 1: The number of nonzero elements in the feature vectors over 100 polygons from the Parks dataset. Grid resolution is 35K. 0.01 0.1 1 10 100 1000 0.00 0.20 0.40 0.60 0.80 1.00 18K 36K 72K 144K 1M 16M Queries per Second Hundreds Recall @K=50 Grid resolution Uniform grid-based Quad tree-based QPS (Uniform grid-based) QPS (Quad tree grid-based) 0.01 0.1 1 10 100 1000 0.00 0.20 0.40 0.60 0.80 1.00 18K 36K 72K 144K 1M 16M Queries per Second Hundreds Recall @K=500 Grid resolution Uniform grid-based Quad tree-based QPS (Uniform grid-based) QPS (Quad tree grid-based) (a) (b) Figure 2: Recall rate and query throughput comparison for different grid sizes over uniform grid-based vectors and quad tree-based bit vectors using 64 threads. A subset of 50k records from the Parks dataset was used for indexing (80%) and testing (20%). (a) Recall at K=50. (b) Recall at K=500. 0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.90 21K 27K 39K Recall (K=50) Grid size Uniform grid-based Quad tree-based 0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.90 21K 27K 39K Recall (K=500) Grid size Uniform grid-based Quad tree-based (a) (d) area range = 5 × 10−7, 5 × 10−5 sample size =127,806 0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.90 21K 27K 39K Recall (K=50) Grid size Uniform grid-based Quad tree-based 0.65 0.70 0.75 0.80 0.85 0.90 0.95 21K 27K 39K Recall (K=500) Grid size Uniform grid-based Quad tree-based (e) (b) area range = 5 × 10−6, 5 × 10−5 sample size = 31,143 0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.90 21K 27K 39K Recall (K=50) Grid size Uniform grid-based Quad tree-based 0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.90 1.00 21K 27K 39K Recall (K=500) Grid size Uniform grid-based Quad tree-based (f) (c) area range = 5 × 10−7, 5 × 10−6 sample size = 96,663 Figure 3: Recall rate comparison over different area ranges. 2
300 320 340 360 380 400 420 440 460 480 0.7 0.75 0.8 0.85 0.9 0.95 1 5 10 20 40 80 160 320 Queries per Second Score Top K Recall Precision F1 score Query throughput (QPS) Figure 4: Performance metrics versus the number of nearest neighbors (K) on the Parks dataset. The plot illustrates the trade-offs between accuracy (Recall, Precision, F1-Score) and query throughput. Table 2: Evaluation of Quad tree-based encoding (K=500). Parks Water bodies Sports 3k 6k 12k 3k 6k 12k 3k 6k 12k Bit encoding Recall 80% 81% 82% 76% 74% 78% 63% 66% 79% Precision 63% 65% 65% 60% 58% 63% 62% 65% 76% F1 score 68% 70% 70% 67% 65% 70% 63% 66% 77% Query throughput (queries/s) 1,642 1,692 1,572 1,876 1,642 1,192 3,937 2,865 1,199 Floating-point encoding Recall 97% 97% 97% 97% 98% 98% 95% 96% 96% Precision 79% 79% 79% 78% 78% 79% 91% 92% 92% F1 score 85% 85% 85% 86% 87% 87% 93% 93% 93% Queries per second 1,115 696 357 246 512 286 974 657 410 3
