Online Approximation Techniques for Spatial Data

April 21, 2005
Abhinandan Das | Cornell University

Spatial Database Management Systems (SDBMS), e.g., Geographical Information Systems, that manage spatial objects such as points, lines, and hyper-rectangles, often have very high query processing costs. Accurate selectivity estimation during query optimization therefore is crucially important for finding good query plans, especially when spatial joins are involved. Selectivity estimation has been studied for relational database systems, but till date has only received little attention in SDBMS.

In this talk, I will present novel sketch-based methods that permit high-quality selectivity estimation for spatial joins and range queries. The sketch-based synopses can be constructed in a single scan over the input, handle inserts and deletes to the database incrementally, and hence can also be used for processing of streaming data. In contrast to previous approaches which provide no guarantees on the quality of approximate results provided, our techniques return approximate results that come with provable probabilistic quality guarantees. The quality guarantees are user tunable and permit a graceful tradeoff between space consumption and the quality of the resulting approximation.

Speaker Details

Abhinandan Das is a Ph.D. candidate in the Computer Science department at Cornell University. He is advised by Prof. Johannes Gehrke, his graduate studies are supported in part by the Sage Graduate Fellowship. Prior to joining Cornell, he recieved the B.Tech. degree in Computer Science from the Indian Institute of Technology (Bombay) in 2000.For his Ph.D., he worked in the area of data stream processing, and more specifically on techniques for approximate query answering over data streams. Besides data streaming, his research interests broadly include design and analysis of algorithms, database systems, data privacy, and distributed algorithms.