[ACM Press the twelfth ACM SIGACT-SIGMOD-SIGART symposium - Washington, D.C., United States (1993.05.25-1993.05.28)] Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '93 - Towards an analysis of range query performance in spatial data structures

✍ Scribed by Pagel, Bernd-Uwe; Six, Hans-Werner; Toben, Heinrich; Widmayer, Peter

• Book ID: 120657492
• Publisher: ACM Press
• Year: 1993
• Tongue: English
• Weight: 737 KB
• Category: Article
• ISBN-13: 9780897915939
• DOI: 10.1145/153850.153878

✦ Synopsis

In this paper, we motivate four different user defined window query classes and derive a probabilistic model for each of them. For each model, we characterize the efficiency of spatial data structures in terms of the expected number of data bucket accesses needed to perform a window query. Our analytical approach exhibits the performance phenomena independent of data structure and implementation details and whether the objects are points or non-point objects.