@conference {15621,
	title = {A dynamic data structure for approximate range searching},
	booktitle = {Proceedings of the 2010 annual symposium on Computational geometry},
	series = {SoCG {\textquoteright}10},
	year = {2010},
	month = {2010///},
	pages = {247 - 256},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {In this paper, we introduce a simple, randomized dynamic data structure for storing multidimensional point sets, called a quadtreap. This data structure is a randomized, balanced variant of a quadtree data structure. In particular, it defines a hierarchical decomposition of space into cells, which are based on hyperrectangles of bounded aspect ratio, each of constant combinatorial complexity. It can be viewed as a multidimensional generalization of the treap data structure of Seidel and Aragon. When inserted, points are assigned random priorities, and the tree is restructured through rotations as if the points had been inserted in priority order. In any fixed dimension d, we show it is possible to store a set of n points in a quadtreap of space O(n). The height h of the tree is O(log n) with high probability. It supports point insertion in time O(h). It supports point deletion in worst-case time O(h2) and expected-case time O(h), averaged over the points of the tree. It can answer ε-approximate spherical range counting queries over groups and approximate nearest neighbor queries in time O(h + (1/ε)d-1).},
	keywords = {Approximation algorithms, dynamic data structures, geometric data structures, quadtrees, Range searching},
	isbn = {978-1-4503-0016-2},
	doi = {10.1145/1810959.1811002},
	url = {http://doi.acm.org/10.1145/1810959.1811002},
	author = {Mount, Dave and Park,Eunhui}
}
@article {16846,
	title = {Using a distributed quadtree index in peer-to-peer networks},
	journal = {The VLDB Journal},
	volume = {16},
	year = {2007},
	month = {2007/04//},
	pages = {165 - 178},
	abstract = {Peer-to-peer (P2P) networks have become a powerful means for online data exchange. Currently, users are primarily utilizing these networks to perform exact-match queries and retrieve complete files. However, future more data intensive applications, such as P2P auction networks, P2P job-search networks, P2P multiplayer games, will require the capability to respond to more complex queries such as range queries involving numerous data types including those that have a spatial component. In this paper, a distributed quadtree index that adapts the MX-CIF quadtree is described that enables more powerful accesses to data in P2P networks. This index has been implemented for various prototype P2P applications and results of experiments are presented. Our index is easy to use, scalable, and exhibits good load-balancing properties. Similar indices can be constructed for various multidimensional data types with both spatial and non-spatial components.},
	keywords = {Distributed data structures, peer-to-peer networks, quadtrees, spatial data structures},
	isbn = {1066-8888},
	doi = {10.1007/s00778-005-0001-y},
	url = {http://dx.doi.org/10.1007/s00778-005-0001-y},
	author = {Tanin,Egemen and Harwood,Aaron and Samet, Hanan}
}
@article {16884,
	title = {Object-based and image-based object representations},
	journal = {ACM Comput. Surv.},
	volume = {36},
	year = {2004},
	month = {2004/06//},
	pages = {159 - 217},
	abstract = {An overview is presented of object-based and image-based representations of objects by their interiors. The representations are distinguished by the manner in which they can be used to answer two fundamental queries in database applications: (1) Feature query: given an object, determine its constituent cells (i.e., their locations in space). (2) Location query: given a cell (i.e., a location in space), determine the identity of the object (or objects) of which it is a member as well as the remaining constituent cells of the object (or objects). Regardless of the representation that is used, the generation of responses to the feature and location queries is facilitated by building an index (i.e., the result of a sort) either on the objects or on their locations in space, and implementing it using an access structure that correlates the objects with the locations. Assuming the presence of an access structure, implicit (i.e., image-based) representations are described that are good for finding the objects associated with a particular location or cell (i.e., the location query), while requiring that all cells be examined when determining the locations associated with a particular object (i.e., the feature query). In contrast, explicit (i.e., object-based) representations are good for the feature query, while requiring that all objects be examined when trying to respond to the location query. The goal is to be able to answer both types of queries with one representation and without possibly having to examine every cell. Representations are presented that achieve this goal by imposing containment hierarchies on either space (i.e., the cells in the space in which the objects are found), or objects. In the former case, space is aggregated into successively larger-sized chunks (i.e., blocks), while in the latter, objects are aggregated into successively larger groups (in terms of the number of objects that they contain). The former is applicable to image-based interior-based representations of which the space pyramid is an example. The latter is applicable to object-based interior-based representations of which the R-tree is an example. The actual mechanics of many of these representations are demonstrated in the VASCO JAVA applets found at http://www.cs.umd.edu/\~{}hjs/quadtree/index.html.},
	keywords = {Access methods, feature query, geographic information systems (GIS), image space, location query, object space, octrees, Pyramids, quadtrees, R-trees, space-filling curves, Spatial databases},
	isbn = {0360-0300},
	doi = {10.1145/1031120.1031123},
	url = {http://doi.acm.org/10.1145/1031120.1031123},
	author = {Samet, Hanan}
}
@conference {16906,
	title = {VASCO: visualizing and animating spatial constructs and operations},
	booktitle = {Proceedings of the nineteenth annual symposium on Computational geometry},
	series = {SCG {\textquoteright}03},
	year = {2003},
	month = {2003///},
	pages = {374 - 375},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {A video is used to demonstrate a set of spatial index JAVA applets that enable users on the worldwide web to experiment with a number of variants of the quadtree spatial data structure for different spatial data types, and, most importantly, enable them to see in an animated manner how a number of basic search operations are executed for them. The spatial data types are points, line segments, rectangles, and regions. The search operations are the window query (i.e., a spatial range query) and a nearest neighbor query that enables ranking spatial objects in the order of their distance from a given query object. The representations and algorithms are visualized and animated in a consistent manner using the same primitives and colors so that the differences between the effects of the representations can be easily understood. The video demonstrates the PR quadtree, PM1 quadtree, and R-tree. The applets can be found at: www.cs.umd.edu/~hjs/quadtree/.},
	keywords = {k-d trees, Nearest neighbor algorithms, quadtrees, R-trees, Visualization},
	isbn = {1-58113-663-3},
	doi = {10.1145/777792.777849},
	url = {http://doi.acm.org/10.1145/777792.777849},
	author = {Brabec,Frantivsek and Samet, Hanan and Yilmaz,Cemal}
}
