@conference {16876,
	title = {Efficient position-independent iconic search using an R-theta index},
	booktitle = {Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems},
	series = {GIS {\textquoteright}06},
	year = {2006},
	month = {2006///},
	pages = {27 - 34},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {An iconic image database is a collection of symbolic images where each image is a collection of labeled point features called icons. A method is presented to support fast position-independent similarity search in an iconic database for symbolic images where the similarity condition involves finding icon pairs that satisfy a specific spatial relationship. This is achieved by introducing an index data structure based on r-θ space, which corresponds to the Cartesian product of separation (i.e., inter-icon distance) and (some representation of) relative spatial orientation. In this space, each pairing of two icons is represented by a single point, and all pairs with the same separation and relative orientation (regardless of absolute position) map to the same point. Similarly, all icon pairs with the same separation but different relative orientations map to points on a line parallel to the θ axis, while all pairs with different separations but the same relative orientation map to points on a line parallel to the r axis. Using such an index, database search for icon pairs with a given spatial relationship or range is accomplished by examining the subarea of the index space into which desired pairs would map. This r-θ index space can be organized using well-known spatial database techniques, such as quadtrees or R-trees. Although the size of such an index grows only linearly with respect to the number of images in the collection, it grows quadratically with the average number of icons in an image. A scheme is described to reduce the size of the index by pruning away a subset of the pairs, at the cost of incurring additional work when searching the database. This pruning is governed by a parameter φ, whose variation provides a continuous range of trade-offs between index size and search time.},
	keywords = {iconic database, position-independent, spatial indexing},
	isbn = {1-59593-529-0},
	doi = {10.1145/1183471.1183478},
	url = {http://doi.acm.org/10.1145/1183471.1183478},
	author = {Cranston,Charles B. and Samet, Hanan}
}
@conference {17888,
	title = {Spatial indexing of distributed multidimensional datasets},
	booktitle = {IEEE International Symposium on Cluster Computing and the Grid, 2005. CCGrid 2005},
	volume = {2},
	year = {2005},
	month = {2005/05/09/12},
	pages = {743- 750 Vol. 2 - 743- 750 Vol. 2},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {While declustering methods for distributed multidimensional indexing of large datasets have been researched widely in the past, replication techniques for multidimensional indexes have not been investigated deeply. In general, a centralized index server may become the performance bottleneck in a wide area network rather than the data servers, since the index is likely to be accessed more often than any of the datasets in the servers. In this paper, we present two different multidimensional indexing algorithms for a distributed environment - a centralized global index and a two-level hierarchical index. Our experimental results show that the centralized scheme does not scale well for either insertion or searching the index. In order to improve the scalability of the index server, we have employed a replication protocol for both the centralized and two-level index schemes that allows some inconsistency between replicas without affecting correctness. Our experiments show that the two-level hierarchical index scheme shows better scalability for both building and searching the index than the non-replicated centralized index, but replication can make the centralized index faster than the two-level hierarchical index for searching in some cases.},
	keywords = {centralized global index algorithm, centralized index server, Computer science, database indexing, distributed databases, distributed multidimensional dataset, Educational institutions, File servers, Indexing, Large-scale systems, Multidimensional systems, Network servers, replication protocol, replication techniques, scalability, Sensor systems, spatial data structures, spatial indexing, two-level hierarchical index algorithm, wide area networks},
	isbn = {0-7803-9074-1},
	doi = {10.1109/CCGRID.2005.1558637},
	author = {Nam,B. and Sussman, Alan}
}
@article {16883,
	title = {Decoupling partitioning and grouping: Overcoming shortcomings of spatial indexing with bucketing},
	journal = {ACM Trans. Database Syst.},
	volume = {29},
	year = {2004},
	month = {2004/12//},
	pages = {789 - 830},
	abstract = {The principle of decoupling the partitioning and grouping processes that form the basis of most spatial indexing methods that use tree directories of buckets is explored. The decoupling is designed to overcome the following drawbacks of traditional solutions:(1) multiple postings in disjoint space decomposition methods that lead to balanced trees such as the hB-tree where a node split in the event of node overflow may be such that one of the children of the node that was split becomes a child of both of the nodes resulting from the split;(2) multiple coverage and nondisjointness of methods based on object hierarchies such as the R-tree which lead to nonunique search paths;(3) directory nodes with similarly-shaped hyper-rectangle bounding boxes with minimum occupancy in disjoint space decomposition methods such as those based on quadtrees and k-d trees that make use of regular decomposition.The first two drawbacks are shown to be overcome by the BV-tree where as a result of decoupling the partitioning and grouping processes, the union of the regions associated with the nodes at a given level of the directory does not necessarily contain all of the data points although all searches take the same amount of time. The BV-tree is not plagued by the third drawback. The third drawback is shown to be overcome by the PK-tree where the grouping process is based on ensuring that every node has at least k objects or blocks. The PK-tree is not plagued by the first two drawbacks as they are inapplicable to it. In both cases, the downside of decoupling the partitioning and grouping processes is that the resulting structure is not necessarily balanced, although, since the nodes have a relatively large fanout, the deviation from a balanced structure is relatively small.},
	keywords = {BV-trees, decoupling, object hierarchies, PK-trees, R-trees, space decomposition, spatial indexing},
	isbn = {0362-5915},
	doi = {10.1145/1042046.1042052},
	url = {http://doi.acm.org/10.1145/1042046.1042052},
	author = {Samet, Hanan}
}
@article {16908,
	title = {Speeding up construction of PMR quadtree-based spatial indexes},
	journal = {The VLDB Journal},
	volume = {11},
	year = {2002},
	month = {2002/10//},
	pages = {109 - 137},
	abstract = {Spatial indexes, such as those based on the quadtree, are important in spatial databases for efficient execution of queries involving spatial constraints, especially when the queries involve spatial joins. In this paper we present a number of techniques for speeding up the construction of quadtree-based spatial indexes, specifically the PMR quadtree, which can index arbitrary spatial data. We assume a quadtree implementation using the {\textquotedblleft}linear quadtree{\textquotedblright}, a disk-resident representation that stores objects contained in the leaf nodes of the quadtree in a linear index (e.g., a B-tree) ordered based on a space-filling curve. We present two complementary techniques: an improved insertion algorithm and a bulk-loading method. The bulk-loading method can be extended to handle bulk-insertions into an existing PMR quadtree. We make some analytical observations about the I/O cost and CPU cost of our PMR quadtree bulk-loading algorithm, and conduct an extensive empirical study of the techniques presented in the paper. Our techniques are found to yield significant speedup compared to traditional quadtree building methods, even when the size of a main memory buffer is very small compared to the size of the resulting quadtrees.},
	keywords = {Bulk-loading, I/O, spatial indexing},
	isbn = {1066-8888},
	doi = {10.1007/s00778-002-0067-8},
	url = {http://dx.doi.org/10.1007/s00778-002-0067-8},
	author = {Hjaltason,Gisli R. and Samet, Hanan}
}
