@conference {15573,
	title = {Tradeoffs in Approximate Range Searching Made Simpler},
	booktitle = {Computer Graphics and Image Processing, 2008. SIBGRAPI {\textquoteright}08. XXI Brazilian Symposium on},
	year = {2008},
	month = {2008/10//},
	pages = {237 - 244},
	abstract = {Range searching is a fundamental problem in computational geometry. The problem involves preprocessing a set of n points in R^d into a data structure, so that it is possible to determine the subset of points lying within a given query range. In approximate range searching, a parameter eps epsiv gt; 0 is given, and for a given query range R the points lying within distance eps diam(R) of the range{\textquoteright}s boundary may be counted or not. In this paper we present three results related to the issue of tradeoffs in approximate range searching. First, we introduce the range sketching problem. Next, we present a space-time tradeoff for smooth convex ranges, which generalize spherical ranges. Finally, we show how to modify the previous data structure to obtain a space-time tradeoff for simplex ranges. In contrast to existing results, which are based on relatively complex data structures, all three of our results are based on simple, practical data structures.},
	keywords = {approximate range searching, computational geometry, data structure, Data structures, query range},
	doi = {10.1109/SIBGRAPI.2008.24},
	author = {Arya,S. and Fonseca,G. and Mount, Dave}
}
@conference {13343,
	title = {Using state modules for adaptive query processing},
	booktitle = {19th International Conference on Data Engineering, 2003. Proceedings},
	year = {2003},
	month = {2003/03/05/8},
	pages = {353 - 364},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We present a query architecture in which join operators are decomposed into their constituent data structures (State Modules, or SteMs), and dataflow among these SteMs is managed adaptively by an eddy routing operator [R. Avnur et al., (2000)]. Breaking the encapsulation of joins serves two purposes. First, it allows the eddy to observe multiple physical operations embedded in a join algorithm, allowing for better calibration and control of these operations. Second, the SteM on a relation serves as a shared materialization point, enabling multiple competing access methods to share results, which can be leveraged by multiple competing join algorithms. Our architecture extends prior work significantly, allowing continuously adaptive decisions for most major aspects of traditional query optimization: choice of access methods and join algorithms, ordering of operators, and choice of a query spanning tree. SteMs introduce significant routing flexibility to the eddy, enabling more opportunities for adaptation, but also introducing the possibility of incorrect query results. We present constraints on eddy routing through SteMs that ensure correctness while preserving a great deal of flexibility. We also demonstrate the benefits of our architecture via experiments in the Telegraph dataflow system. We show that even a simple routing policy allows significant flexibility in adaptation, including novel effects like automatic "hybridization " of multiple algorithms for a single join.},
	keywords = {adaptive query processing, Bandwidth, Calibration, data encapsulation, data structure, Data structures, Databases, Dictionaries, eddy routing, eddy routing operator, Encapsulation, join operator, multiple algorithm automatic hybridization, multiple competing join algorithm, query architecture, Query processing, query spanning tree, Routing, routing policy, Runtime, shared materialization point, State Module, SteMs, Telegraph dataflow system, Telegraphy, Tree data structures},
	isbn = {0-7803-7665-X},
	doi = {10.1109/ICDE.2003.1260805},
	author = {Vijayshankar Raman and Deshpande, Amol and Hellerstein,J. M}
}
@conference {15589,
	title = {Nearly optimal expected-case planar point location},
	booktitle = {Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on},
	year = {2000},
	month = {2000///},
	pages = {208 - 218},
	abstract = {We consider the planar point location problem from the perspective of expected search time. We are given a planar polygonal subdivision S and for each polygon of the subdivision the probability that a query point lies within this polygon. The goal is to compute a search structure to determine which cell of the subdivision contains a given query point, so as to minimize the expected search time. This is a generalization of the classical problem of computing an optimal binary search tree for one-dimensional keys. In the one-dimensional case it has long been known that the entropy H of the distribution is the dominant term in the lower bound on the expected-case search time, and further there exist search trees achieving expected search times of at most H+2. Prior to this work, there has been no known structure for planar point location with an expected search time better than 2H, and this result required strong assumptions on the nature of the query point distribution. Here we present a data structure whose expected search time is nearly equal to the entropy lower bound, namely H+o(H). The result holds for any polygonal subdivision in which the number of sides of each of the polygonal cells is bounded, and there are no assumptions on the query distribution within each cell. We extend these results to subdivisions with convex cells, assuming a uniform query distribution within each cell},
	keywords = {computational geometry, convex cells, data structure, expected search time, nearly optimal expected-case planar point location, optimal binary search tree, planar point location, planar polygonal subdivision, polygonal cells, polygonal subdivision, probability, search problems, search structure, subdivision, trees (mathematics)},
	doi = {10.1109/SFCS.2000.892108},
	author = {Arya,S. and Malamatos,T. and Mount, Dave}
}
@article {17231,
	title = {Incremental data structures and algorithms for dynamic query interfaces},
	journal = {ACM SIGMOD Record},
	volume = {25},
	year = {1996},
	month = {1996/12//},
	pages = {21 - 24},
	abstract = {Dynamic query interfaces (DQIs) form a recently developed method of database access that provides continuous realtime feedback to the user during the query formulation process. Previous work shows that DQIs are elegant and powerful interfaces to small databases. Unfortunately, when applied to large databases, previous DQI algorithms slow to a crawl. We present a new approach to DQI algorithms that works well with large databases.},
	keywords = {algorithm, data structure, database, direct manipulation, dynamic query, Information Visualization, user interface},
	isbn = {0163-5808},
	doi = {10.1145/245882.245891},
	url = {http://doi.acm.org/10.1145/245882.245891},
	author = {Tanin,Egemen and Beigel,Richard and Shneiderman, Ben}
}
